Wydaje się, że istnieje ciągłe szaleństwo, gdy ludzie żmudnie uczą się nowych układów klawiatury, takich jak Dvorak lub Neo, ponieważ podobno sprawia to, że są bardziej produktywni. Twierdzę, że zmiana układu klawiatury jest złym pomysłem, ponieważ przyśpieszenie może ci zająć miesiące, a kiedy jesteś ostatecznie o 5% szybszy niż reszta, wkręca cię, jeśli musisz pisać na komputerze, który nie jest twój własny.
Ponadto wszyscy ci ludzie zapominają, gdzie leży prawdziwe wąskie gardło we współczesnej komunikacji - klawiatura telefoniczna.
Oto jak wygląda przeciętna klawiatura telefonu:
Litera „r” jest trzecią literą na przycisku 7; więc jeśli miałbyś wpisać literę „r” na telefonie komórkowym, nacisnąłbyś przycisk 7 trzy razy, dla „s” nacisnąłbyś go 4 razy, a dla „a” nacisnąłbyś przycisk 2 raz.
Biorąc to pod uwagę, umieszczenie „e” po „d” było prawdopodobnie złą decyzją - „e” jest najczęściej używaną literą w alfabecie angielskim, więc jeśli miałbyś oznaczyć przycisk 3 „EDF” zamiast „DEF”, zaoszczędziłoby sporo naciśnięć klawiszy.
Co więcej, prawdopodobnie doświadczyłeś już, że pisanie 2 liter, które korzystają z tego samego przycisku, jest uciążliwe - jeśli chcesz napisać „TU”, nie możesz po prostu nacisnąć 8 trzy razy, ponieważ spowodowałoby to „V”. Tak więc zwykle piszesz „T”, następnie naciskasz spację, następnie naciskasz backspace, a następnie piszesz „U”, co odpowiada 5 naciśnięciom przycisków zamiast 3.
TL; DR
Biorąc pod uwagę te dwie zasady:
- Litera jest wpisywana przez naciśnięcie przycisku n razy, gdzie n oznacza pozycję litery na etykiecie przycisku
- Pisanie dwóch liter, które są wpisywane za pomocą tego samego przycisku, wymaga dodatkowych 2 naciśnięć przycisku
Jaki jest układ klawiatury telefonu, który wymaga najmniejszej liczby naciśnięć przycisków, biorąc pod uwagę określony tekst? Należy używać tylko przycisków 2-9, 1 i 0, które są zarezerwowane dla symboli specjalnych.
Wkład
Tekst, dla którego powinieneś znaleźć optymalny układ, jest dostarczany przez stdin. Nie musisz obsługiwać niczego innego niż małe litery i możesz założyć, że dane wejściowe składają się tylko z tego. Możesz również założyć, że tekst wejściowy jest dość duży i każda litera jest tam co najmniej raz, jeśli to pomoże.
Wydajność
Nie chcę nakładać zbyt wielu ograniczeń na dane wyjściowe, ponieważ czasami daje to jedne języki przewagę nad innymi; więc jednak twój język pokazuje, że tablice są w porządku, alternatywnie możesz oddzielić każdą etykietę nowym wierszem.
Może istnieć wiele możliwych optymalnych układów, możesz wydrukować dowolny z nich. Oto prosty przykład:
>> echo "jackdawslovemybigsphinxofquartz" | foo.sh
ojpt
avhz
cen
skm
dyf
wbq
ixu
lgr
Punkty bonusowe
-35, jeśli twój algorytm nie wymusza brutalnie wszystkich możliwych układów (tutaj patrzę na `` permutacje '' Haskella)
-3, jeśli Twój kod mieści się w wiadomości tekstowej (140 znaków), a Ty wysyłasz zdjęcie, że wysyłasz swój kod znajomemu.
To jest moje pierwsze wyzwanie na StackExchange. Z przyjemnością usłyszę, czy Ci się podoba, czy masz jakieś uwagi na ten temat!
26! / (2! * 6!) = 280,063,514,671,253,913,600,000 > 2^77
unikalne kombinacje, licząc proste przestawienie klawiszy tylko raz.