Ini adalah tantangan kode dengan sistem skor kustom, di mana skor terendah menang.

pengantar

Banyak ponsel pintar yang memungkinkan untuk memasukkan teks dengan menggesekkan jari Anda di papan ketik virtual 2D. Teknologi ini biasanya dikombinasikan dengan algoritma prediksi yang menampilkan daftar kata-kata yang di tebak, diurutkan dari yang paling mungkin hingga yang paling tidak mungkin.

Dalam tantangan ini:

• Kita akan menggeser keyboard satu dimensi yang terbatas pada subset dari 26 huruf.
• Tidak akan ada algoritma prediksi : kami ingin setiap kata diidentifikasi secara unik oleh 'urutan geseknya'.
• Kami ingin keyboard dioptimalkan sedemikian rupa sehingga jumlah gerakan total untuk daftar kata tertentu diminimalkan.

Menggesekkan dalam satu dimensi

Di bawah ini adalah keyboard 1D lexicographically diurutkan dengan semua huruf:

ABCDEFGHIJKLMNOPQRSTUVWXYZ

^{NB: Ini dapat ditampilkan pada beberapa baris jika Anda browsing dari ponsel. Tolong pikirkan itu sebagai satu baris.}

Untuk memasukkan kata ' GOLF ' pada keyboard seperti itu, kami akan:

• dimulai dari G
• geser ke kanan ke O
• geser ke kiri ke F

Karena Lterletak di antara Odan F, kami hanya terus menggesek tanpa berhenti di sana.

Jadi urutan gesek ' GOLF ' pada keyboard ini adalah GOF.

Lebih umum:

• Huruf pertama dan terakhir selalu disertakan.
• Surat-surat lain termasuk jika dan hanya jika perubahan arah diperlukan setelah mereka.

• Surat yang berulang harus diperlakukan dengan cara yang sama seperti huruf tunggal. Misalnya, pada keyboard di atas:

  • ' LOOP ' akan dikodekan sebagai LP(tanpa berhenti O)
  • ' GOOFY ' akan dikodekan sebagai GOFY( Otermasuk karena ada perubahan arah di sana - bukan karena digandakan)

Optimalisasi keyboard

Mari kita perhatikan daftar kata-kata berikut: [' PROGRAMMING ', ' PUZZLES ', ' AND ', ' CODE ', ' GOLF '].

Kami membutuhkan 16 huruf berbeda untuk mengetik kata-kata ini, jadi kami hanya perlu keyboard 16 huruf. Yang berikut ini - lagi - diurutkan secara leksikografis:

ACDEFGILMNOPRSUZ

Dengan keyboard ini, kata-kata akan dikodekan dengan cara ini:

• PEMROGRAMAN : PRGRAMING(9 gerakan)
• PUZZLES : PZES(4 gerakan)
• DAN : AND(3 gerakan)
• KODE : CODE(4 gerakan)
• GOLF : GOF(3 gerakan)

Itu total 23 gerakan untuk semua kata.

Tetapi kita dapat melakukan jauh lebih baik dengan keyboard ini:

CGODSELZNUIFRPAM

Pemberian yang mana:

• PEMROGRAMAN : PGMG(4 gerakan)
• Teka-teki : PS(2 gerakan)
• DAN : AD(2 gerakan)
• KODE : CE(2 gerakan)
• GOLF : GF(2 gerakan)

dengan total hanya 12 gerakan .

Penilaian keyboard

$n$

$m_k$$k$ -th.

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

Semakin rendah, semakin baik.

Tantangan

• Diberikan daftar kata-kata, kode Anda harus menampilkan keyboard yang valid untuk daftar ini. Papan ketik dianggap sah jika setiap kata menghasilkan urutan gesekan unik.

• Anda akan diberikan 11 daftar kata independen. Skor Anda akan sama dengan:

  $$S + L$$ $S$$L$ adalah panjang dari kode Anda dalam bytes.

  Anda dapat menggunakan skrip ini untuk memeriksa skor Anda . The score()Fungsi mengharapkan panjang kode Anda sebagai parameter pertama dan array string 11 Keyboard sebagai parameter kedua (kasus tidak masalah).

• Pengajuan dengan skor terendah akan menang. Dalam hal seri, pengajuan yang diajukan pertama kali menang.

Aturan tambahan

• Kode Anda harus deterministik (yaitu harus selalu mengembalikan output yang sama untuk input yang diberikan).
• Anda harus A) memberikan tautan uji (mis. Pada TIO) yang tidak habis waktu, atau B) termasuk papan ketik yang dihasilkan di dalam badan jawaban Anda.
• Anda dapat menggunakan kata-kata dalam huruf besar atau kecil. Kasus campuran dilarang.
• Input dijamin memiliki setidaknya satu solusi.
• Semua kata terdiri dari setidaknya 2 huruf berbeda.
• Kode Anda harus berfungsi untuk input yang valid. Itu akan diuji dengan daftar kata-kata yang dirahasiakan untuk memastikan bahwa itu tidak bergantung pada hasil kode keras.
• Saya berhak untuk meningkatkan ukuran suite uji setiap saat untuk memastikan bahwa pengiriman tidak dioptimalkan untuk kasus uji awal.

Daftar kata

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

Ini selalu menemukan solusi optimal (tetapi menghabiskan banyak kode untuk melakukannya). Ini menjalankan tes 1-9 dalam beberapa detik, tes 10 dalam enam menit, dan tes 11 dalam satu menit.

Kode

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

Hasil

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

Periksa skor