Il s'agit d'un défi de code avec un système de notation personnalisé, où le score le plus bas l'emporte.

introduction

De nombreux smartphones permettent de saisir du texte en faisant glisser votre doigt sur le clavier virtuel 2D. Cette technologie est généralement associée à un algorithme de prédiction qui génère une liste de mots devinés, triés du plus probable au moins probable.

Dans ce défi:

• Nous allons balayer un clavier unidimensionnel limité à un sous-ensemble de 26 lettres.
• Il n'y aura pas d'algorithme de prédiction : nous voulons que chaque mot soit identifié de manière unique par sa «séquence de balayage».
• Nous voulons que le clavier soit optimisé de manière à minimiser le nombre total de mouvements pour une liste de mots donnée.

Glisser dans une seule dimension

Vous trouverez ci-dessous un clavier 1D trié lexicographiquement avec toutes les lettres:

ABCDEFGHIJKLMNOPQRSTUVWXYZ

^{NB: Cela peut s'afficher sur plusieurs lignes si vous naviguez depuis un mobile. Veuillez le considérer comme une seule ligne.}

Pour saisir le mot « GOLF » sur un tel clavier, nous allons:

• commencer à G
• balayez vers la droite pour O
• balayez vers la gauche pour F

Parce que Lse situe entre Oet F, on continue de glisser sans s'arrêter là.

Ainsi, la séquence de balayage de « GOLF » sur ce clavier est GOF.

Plus généralement:

• La première et la dernière lettre sont toujours incluses.
• D'autres lettres sont incluses si et seulement si un changement de direction est nécessaire juste après elles.

• Les lettres répétées doivent être traitées de la même manière que les lettres simples. Par exemple, sur le clavier ci-dessus:

  • ' LOOP ' serait codé comme LP(sans arrêt activé O)
  • ' GOOFY ' serait codé comme GOFY(le Oest inclus parce qu'il y a un changement de direction - pas parce qu'il est doublé)

Optimisation du clavier

Considérons la liste de mots suivante: [' PROGRAMMATION ', ' PUZZLES ', ' AND ', ' CODE ', ' GOLF '].

Nous avons besoin de 16 lettres distinctes pour taper ces mots, nous avons donc juste besoin d'un clavier à 16 lettres. Le suivant est - encore une fois - trié lexicographiquement:

ACDEFGILMNOPRSUZ

Avec ce clavier, les mots seront encodés de cette façon:

• PROGRAMMATION : PRGRAMING(9 mouvements)
• PUZZLES : PZES(4 coups)
• ET : AND(3 coups)
• CODE : CODE(4 coups)
• GOLF : GOF(3 coups)

C'est un total de 23 coups pour tous les mots.

Mais on peut faire beaucoup mieux avec ce clavier:

CGODSELZNUIFRPAM

Qui donne:

• PROGRAMMATION : PGMG(4 mouvements)
• PUZZLES : PS(2 coups)
• ET : AD(2 coups)
• CODE : CE(2 coups)
• GOLF : GF(2 coups)

pour un total de seulement 12 coups .

Notation au clavier

$n$

$m_k$$k$-ème mot.

Par exemple, les deux claviers décrits dans le paragraphe précédent seraient notés $9^2+4^2+3^2+4^2+3^2=131$ et $4^2+2^2+2^2+2^2+2^2=32$ respectivement.

Plus c'est bas, mieux c'est.

Le défi

• Étant donné une liste de mots, votre code doit générer un clavier valide pour cette liste. Un clavier est considéré comme valide si chaque mot génère une séquence de balayage unique.

• Vous recevrez 11 listes de mots indépendantes. Votre score sera égal à:

  $$S + L$$ où $S$ est la somme des scores de vos claviers pour toutes les listes et $L$ est la longueur de votre code en octets.

  Vous pouvez utiliser ce script pour vérifier votre score . La score()fonction attend votre longueur de code comme premier paramètre et un tableau de 11 chaînes de clavier comme second paramètre (le cas n'a pas d'importance).

• La soumission avec le score le plus bas gagne. En cas d'égalité, la soumission soumise en premier l'emporte.

Règles supplémentaires

• Votre code doit être déterministe (c'est-à-dire qu'il doit toujours renvoyer la même sortie pour une entrée donnée).
• Vous devez soit A) fournir un lien de test (par exemple sur TIO) qui n'expire pas, soit B) inclure les claviers générés dans le corps de votre réponse.
• Vous pouvez prendre les mots en majuscules ou en minuscules. Les cas mixtes sont interdits.
• L'entrée est garantie d'avoir au moins une solution.
• Tous les mots sont constitués d'au moins 2 lettres distinctes.
• Votre code doit fonctionner pour toute entrée valide. Il sera testé avec une liste de mots non divulgués pour s'assurer qu'il ne repose pas sur des résultats codés en dur.
• Je me réserve le droit d'augmenter la taille de la suite de tests à tout moment pour m'assurer que les soumissions ne sont pas optimisées pour les cas de test initiaux.

Listes de mots

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 + Google OR-Tools , 1076 + 1971 = 3047

Cela trouve toujours des solutions optimales (mais dépense beaucoup de code pour le faire). Il exécute les tests 1 à 9 en quelques secondes, teste 10 en six minutes et teste 11 en une minute.

Code

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="")

Résultat

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

Vérifier le score