Optymalizacja przesuwania po klawiaturze 1D

16

Jest to wyzwanie kodowe z niestandardowym systemem punktacji, w którym wygrywa najniższy wynik.

Wprowadzenie

Wiele smartfonów pozwala wprowadzać tekst, przesuwając palcem po wirtualnej klawiaturze 2D. Ta technologia jest zwykle łączona z algorytmem przewidywania, który wyświetla listę odgadniętych słów, posortowaną od najbardziej prawdopodobnej do najmniej prawdopodobnej.

W tym wyzwaniu:

  • Przeciągniemy po jednowymiarowej klawiaturze ograniczonej do podzbioru 26 liter.
  • Nie będzie algorytmu przewidywania : chcemy, aby każde słowo było jednoznacznie identyfikowane przez „sekwencję przeciągania”.
  • Chcemy, aby klawiatura była zoptymalizowana w taki sposób, aby całkowita liczba ruchów dla danej listy słów była zminimalizowana.

Przesuwanie w jednym wymiarze

Poniżej znajduje się posortowana leksykograficznie klawiatura 1D ze wszystkimi literami:

ABCDEFGHIJKLMNOPQRSTUVWXYZ

Uwaga: może to być wyświetlane w kilku wierszach, jeśli przeglądasz z telefonu komórkowego. Pomyśl o tym jak o pojedynczym rzędzie.

Aby wprowadzić słowo „ GOLF ” na takiej klawiaturze, będziemy:

  • zacznij o G
  • przesuń w prawo do O
  • przesuń w lewo, aby F

Ponieważ Lznajduje się pomiędzy OiF , po prostu przesuwamy palcem, nie zatrzymując się.

Tak więc sekwencja przeciągania „ GOLF ” na tej klawiaturze jest następującaGOF .

Bardziej ogólnie:

  • Pierwsza i ostatnia litera są zawsze uwzględniane.
  • Inne litery są uwzględniane tylko wtedy, gdy wymagana jest zmiana kierunku tuż po nich.

  • Powtarzane litery należy traktować tak samo jak pojedyncze litery. Na przykład na powyższej klawiaturze:

    • „ LOOP ” byłoby zakodowane jako LP(bez zatrzymania na O)
    • „ GOOFY ” byłoby zakodowane jako GOFY( Ojest uwzględnione, ponieważ istnieje zmiana kierunku - nie dlatego, że jest podwojona)

Optymalizacja klawiatury

Rozważmy następującą listę słów: [„ PROGRAMOWANIE ”, „ PUZZLES ”, „ AND ”, „ CODE ”, „ GOLF ”].

Potrzebujemy 16 różnych liter, aby wpisać te słowa, więc potrzebujemy tylko 16-literowej klawiatury. Poniższy jest - ponownie - posortowany leksykograficznie:

ACDEFGILMNOPRSUZ

Za pomocą tej klawiatury słowa zostaną zakodowane w następujący sposób:

  • PROGRAMOWANIE :PRGRAMING (9 ruchów)
  • PUZZLE : PZES(4 ruchy)
  • AND : AND(3 ruchy)
  • KOD :CODE (4 ruchy)
  • GOLF : GOF(3 ruchy)

To łącznie 23 ruchy dla wszystkich słów.

Ale dzięki tej klawiaturze możemy znacznie lepiej:

CGODSELZNUIFRPAM

Co daje:

  • PROGRAMOWANIE :PGMG (4 ruchy)
  • PUZZLE :PS (2 ruchy)
  • I :AD (2 ruchy)
  • KOD :CE (2 ruchy)
  • GOLF : GF(2 ruchy)

w sumie tylko 12 ruchów .

Punktacja klawiatury

n

∑k=1nmk2)

mkk słowa.

92)+42)+3)2)+42)+3)2)=13142)+2)2)+2)2)+2)2)+2)2)=32

Im niższy, tym lepiej.

Wyzwanie

  • Biorąc pod uwagę listę słów, kod musi wypisać prawidłowy klawiaturę dla tej listy. Klawiatura jest uważana za prawidłową, jeśli każde słowo generuje unikalną sekwencję machnięcia.

  • Otrzymasz 11 niezależnych list słów. Twój wynik będzie równy:

    S.+L.
    S.L. jest długością twojego kodu w bajtach.

    Możesz użyć tego skryptu, aby sprawdzić swój wynik . Thescore()Funkcja oczekuje swoją długość kodu jako pierwszy parametr i tablicę łańcuchów 11 klawiaturze drugiego parametru (w przypadku nie ma znaczenia).

  • Zgłoszenie z najniższą oceną wygrywa. W przypadku remisu zgłoszenie przesłane jako pierwsze wygrywa.

Dodatkowe zasady

  • Twój kod musi być deterministyczny (tzn. Zawsze musi zwracać ten sam wynik dla danego wejścia).
  • Musisz albo A) podać link testowy (np. W TIO), który nie przekroczył limitu czasu, albo B) dołączyć wygenerowane klawiatury w treści odpowiedzi.
  • Możesz wziąć słowa w całości dużymi lub małymi literami. Mieszane przypadki są zabronione.
  • Gwarantujemy, że dane wejściowe mają co najmniej jedno rozwiązanie.
  • Wszystkie słowa składają się z co najmniej 2 różnych liter.
  • Twój kod musi działać dla każdego poprawnego wejścia. Zostanie przetestowany z nieujawnioną listą słów, aby upewnić się, że nie opiera się na wynikach zakodowanych na stałe.
  • Zastrzegam sobie prawo do zwiększenia wielkości pakietu testowego w dowolnym momencie, aby upewnić się, że zgłoszenia nie są zoptymalizowane dla początkowych przypadków testowych.

Listy słów

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
code-challenge optimization Arnauld
źródło
Piaskownica (teraz usunięta).
Arnauld,
Zgadnij, kto jeszcze zna walkę ...
Erik the Outgolfer,
Jeśli zamierzasz uwzględnić tę zasadę: „Twój kod musi być uruchomiony w mniej niż 1 minutę dla każdej listy”, dobrze jest określić, gdzie będzie on działał. Kod działający na jednym komputerze w ciągu jednej minuty może zająć godziny na innym.
mypetlion
@mypetlion To, co naprawdę się liczy, to fakt, że kod faktycznie coś generuje (a nie tylko działa wiecznie), więc rozluźniłem tę zasadę.
Arnauld,
„ Klawiatura jest uważana za prawidłową, jeśli każde słowo generuje unikalną sekwencję machnięcia. ” - co tutaj oznacza unikat? na przykład, czy kolejność alfabetyczna jest nieprawidłowym rozwiązaniem dla słów „abda”, „acda”?
ngn

Odpowiedzi:

5

Python 3 + Google OR-Tools , 1076 + 1971 = 3047

To zawsze znajduje optymalne rozwiązania (ale spędza na tym dużo kodu). Przeprowadza testy 1–9 w ciągu kilku sekund, test 10 w sześć minut, a test 11 w ciągu jednej minuty.

Kod

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

Wynik

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

Sprawdź wynik

Anders Kaseorg
źródło