Este é um desafio de código com um sistema de pontuação personalizado, onde a pontuação mais baixa vence.

Introdução

Muitos smartphones permitem inserir texto passando o dedo pelo teclado virtual 2D. Essa tecnologia geralmente é combinada com um algoritmo de previsão que gera uma lista de palavras adivinhadas, classificadas da mais provável para a menos provável.

Neste desafio:

• Vamos deslizar através de um teclado unidimensional restrito a um subconjunto das 26 letras.
• Não haverá algoritmo de previsão : queremos que cada palavra seja identificada exclusivamente por sua 'sequência de furto'.
• Queremos que o teclado seja otimizado de forma que o número total de movimentos para uma determinada lista de palavras seja minimizado.

Passando em uma dimensão

Abaixo está um teclado 1D lexicograficamente classificado com todas as letras:

ABCDEFGHIJKLMNOPQRSTUVWXYZ

^{Nota: isso pode ser exibido em várias linhas se você estiver navegando no celular. Por favor, pense nisso como uma única linha.}

Para inserir a palavra ' GOLF ' nesse teclado, iremos:

• Começa ás G
• deslize para a direita para O
• deslize para a esquerda para F

Como Lestá localizado entre Oe F, continuamos passando sem parar por aí.

Portanto, a sequência de furto de ' GOLF ' neste teclado é GOF.

De forma geral:

• A primeira e a última letras estão sempre incluídas.
• Outras letras são incluídas se e somente se uma mudança de direção for necessária logo após elas.

• Letras repetidas devem ser tratadas da mesma maneira que letras únicas. Por exemplo, no teclado acima:

  • ' LOOP ' seria codificado como LP(sem parar O)
  • ' GOOFY ' seria codificado como GOFY( Oestá incluído porque há uma mudança de direção lá - não porque dobrou)

Otimização do teclado

Vamos considerar a seguinte lista de palavras: [' PROGRAMAÇÃO ', ' PUZZLES ', ' AND ', ' CODE ', ' GOLF '].

Precisamos de 16 letras distintas para digitar essas palavras; portanto, precisamos apenas de um teclado de 16 letras. O seguinte é - novamente - ordenado lexicograficamente:

ACDEFGILMNOPRSUZ

Com este teclado, as palavras serão codificadas da seguinte maneira:

• PROGRAMAÇÃO : PRGRAMING(9 movimentos)
• PUZZLES :PZES (4 movimentos)
• E :AND (3 movimentos)
• CÓDIGO :CODE (4 movimentos)
• GOLFE :GOF (3 jogadas)

Isso é um total de 23 movimentos para todas as palavras.

Mas podemos fazer muito melhor com este teclado:

CGODSELZNUIFRPAM

Que dá:

• PROGRAMAÇÃO :PGMG (4 movimentos)
• PUZZLES :PS (2 movimentos)
• E :AD (2 movimentos)
• CÓDIGO :CE (2 movimentos)
• GOLFE :GF (2 movimentos)

para um total de apenas 12 movimentos .

Pontuação do teclado

Para uma determinada lista de $n$ palavras, a pontuação de um teclado é dada por:

$m_k$$k$ ésima palavra.

$9^2+4^2+3^2+4^2+3^2=131$$4^2+2^2+2^2+2^2+2^2=32$ respectivamente.

Quanto mais baixo, melhor.

O desafio

• Dada uma lista de palavras, seu código deve gerar um teclado válido para esta lista. Um teclado é considerado válido se cada palavra gerar uma sequência de furto exclusiva.

• Você receberá 11 listas independentes de palavras. Sua pontuação será igual a:

  $$S + L$$ $S$$L$ é o comprimento do seu código em bytes.

  Você pode usar esse script para verificar sua pontuação . A score()função espera o tamanho do seu código como primeiro parâmetro e uma matriz de 11 seqüências de teclado como segundo parâmetro (o caso não importa).

• A finalização com a menor pontuação vence. Em caso de empate, a finalização enviada vence primeiro.

Regras adicionais

• Seu código deve ser determinístico (ou seja, sempre deve retornar a mesma saída para uma determinada entrada).
• Você deve A) fornecer um link de teste (por exemplo, no TIO) que não exceda o tempo limite ou B) incluir os teclados gerados no corpo da sua resposta.
• Você pode colocar as palavras em maiúsculas ou minúsculas. Casos mistos são proibidos.
• A entrada é garantida para ter pelo menos uma solução.
• Todas as palavras são compostas por pelo menos 2 letras distintas.
• Seu código deve funcionar para qualquer entrada válida. Ele será testado com uma lista não divulgada de palavras para garantir que não depende de resultados codificados.
• Reservo-me o direito de aumentar o tamanho do conjunto de testes a qualquer momento para garantir que os envios não sejam otimizados para os casos de teste iniciais.

Listas de palavras

1) Sanity check #1 (only 4 valid solutions: HES, SEH, ESH or HSE)
SEE, SHE

2) Sanity check #2 (16 valid solutions, of which 4 are optimal: COLD, DOLC, DLOC or CLOD)
COLD, CLOD

3) Sanity check #3
ACCENTS, ACCESS

4) Warm-up
RATIO, NATION, NITRO, RIOT, IOTA, AIR, ART, RAT, TRIO, TRAIN

5) Pangram
THE, QUICK, BROWN, FOX, JUMPS, OVER, LAZY, DOG

6) Common prepositions
TO, OF, IN, FOR, ON, WITH, AT, BY, FROM, UP, ABOUT, INTO, OVER, AFTER

7) Common verbs
BE, HAVE, DO, SAY, GET, MAKE, GO, KNOW, TAKE, SEE, COME, THINK, LOOK, WANT, GIVE, USE, FIND, TELL, ASK, WORK, SEEM, FEEL, TRY, LEAVE, CALL

8) Common adjectives
GOOD, NEW, FIRST, LAST, LONG, GREAT, LITTLE, OWN, OTHER, OLD, RIGHT, BIG, HIGH, DIFFERENT, SMALL, LARGE, NEXT, EARLY, YOUNG, IMPORTANT, FEW, PUBLIC, BAD, SAME, ABLE

9) Common nouns
TIME, PERSON, YEAR, WAY, DAY, THING, MAN, WORLD, LIFE, HAND, PART, CHILD, EYE, WOMAN, PLACE, WORK, WEEK, CASE, POINT, GOVERNMENT, COMPANY, NUMBER, GROUP, PROBLEM, FACT

10) POTUS
ADAMS, ARTHUR, BUCHANAN, BUREN, BUSH, CARTER, CLEVELAND, CLINTON, COOLIDGE, EISENHOWER, FILLMORE, FORD, GARFIELD, GRANT, HARDING, HARRISON, HAYES, HOOVER, JACKSON, JEFFERSON, JOHNSON, KENNEDY, LINCOLN, MADISON, MCKINLEY, MONROE, NIXON, OBAMA, PIERCE, POLK, REAGAN, ROOSEVELT, TAFT, TAYLOR, TRUMAN, TRUMP, TYLER, WASHINGTON, WILSON

11) Transition metals
SCANDIUM, TITANIUM, VANADIUM, CHROMIUM, MANGANESE, IRON, COBALT, NICKEL, COPPER, ZINC, YTTRIUM, ZIRCONIUM, PLATINUM, GOLD, MERCURY, RUTHERFORDIUM, DUBNIUM, SEABORGIUM, BOHRIUM, HASSIUM, MEITNERIUM, UNUNBIUM, NIOBIUM, IRIDIUM, MOLYBDENUM, TECHNETIUM, RUTHENIUM, RHODIUM, PALLADIUM, SILVER, CADMIUM, HAFNIUM, TANTALUM, TUNGSTEN, RHENIUM, OSMIUM

Python 3 + Ferramentas OR do Google , 1076 + 1971 = 3047

Isso sempre encontra soluções ótimas (mas gasta muito código para fazer isso). Ele executa os testes 1 a 9 em alguns segundos, os testes 10 em seis minutos e os testes 11 em um minuto.

Código

from ortools.sat.python.cp_model import*
from itertools import*
C=combinations
R=range
L=len
T=lambda w:[*zip(w,w[1:],w[2:])]
W=[(*(g[0]for g in groupby(w)),)for w in input().split()]
K={*sum(W,())}
m=CpModel()
V=m.NewBoolVar
B={c:V(f"B{c}")for c in C(K,2)}
for a,b in[*B]:B[b,a]=B[a,b].Not()
for a,b,c in permutations(K,3):m.AddBoolOr([B[a,b],B[b,c],B[c,a]])
M={t:V(f"M{t}")for t in{*sum(map(T,W),[])}}
for a,b,c in M:m.AddBoolXOr([B[a,b],B[b,c],M[a,b,c].Not()])
N={(w,n):V(f"N{w,n}")for w in W for n in R(1,L(w))}
for w in W:
 for n in R(1,L(w)-1):s=sum(M[t]for t in T(w));m.Add(s>=n).OnlyEnforceIf(N[w,n]);m.Add(s<n).OnlyEnforceIf(N[w,n].Not())
for a,b in C(W,2):
 if(a[0],a[-1])==(b[0],b[-1]):m.AddForbiddenAssignments([M[t]for t in T(a)+T(b)],[[x in X for x in R(L(a)-2)]+[y in Y for y in R(L(b)-2)]for n in R(L(a))for X in C(R(L(a)-2),n)for Y in C(R(L(b)-2),n)if[a[x+1]for x in X]==[b[y+1]for y in Y]])
m.Minimize(sum((2*n+3)*N[w,n]for w,n in N))
s=CpSolver()
s.Solve(m)
o={k:0for k in K}
for c in C(K,2):o[c[s.Value(B[c])]]+=1
print(*sorted(K,key=lambda k:o[k]),sep="")

Resultado

1. SEH, 13
2. DOLC, 20
3. TNSECA, 13
4. RATION, 80
5. TYKCIDBRFHJUEVOXWNGZALQMPS, 32
6. REWINTHUVOFABMPY, 66
7. FYCWORTMHAGINDKVESULB, 125
8. TSHRDABXLYOWUPMIENGCF, 213
9. PVKEFDLBMUSWOIHACNYTRG, 212
10. XHGTPMCKSUABYORDLJEIWNFV, 596
11. PYLFNAVEKBOCHTRGDSIZUM, 601

Verificar pontuação