Na nowoczesnych konsolach do gier i innych urządzeniach bez tradycyjnych klawiatur próba wprowadzania tekstu jest koszmarem. Konieczność pisania za pomocą kilku przycisków i joysticka na wirtualnej klawiaturze jest denerwująca i lubię wykonywać jak najmniej ruchów / naciskania przycisków.
Klawiatura, której będziesz używać, wygląda następująco:
+---+---+---+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 |
+---+---+---+---+---+---+---+---+---+---+
| q | w | e | r | t | y | u | i | o | p |
+---+---+---+---+---+---+---+---+---+---+
| a | s | d | f | g | h | j | k | l | - |
+---+---+---+---+---+---+---+---+---+---+
| z | x | c | v | b | n | m | _ | @ | . |
+---+---+---+---+---+---+---+---+---+---+
Można użyć następujących operacji:
L
: przesuń o jeden kwadrat w lewo na klawiaturze (zawija się)R
: przesuń o jeden kwadrat w prawo na klawiaturze (zawija się)U
: przesuń o jeden kwadrat w górę na klawiaturze (zawija się)D
: przesuń o jeden kwadrat w dół na klawiaturze (zawija się)Y
: wstaw spacjęB
: przesuń wskaźnik wstawiania o jedną spację w lewo (nic nie robi, jeśli wskaźnik znajduje się na początku)F
: przesuń wskaźnik wstawiania o jedną spację w prawo (nic nie robi, jeśli wskaźnik znajduje się na końcu)C
: przełącz Caps LockA
: wstaw wybrany znak w miejscu wskaźnika wstawiania
Biorąc pod uwagę ciąg wejściowy zawierający tylko znaki ASCII, które można wpisać za pomocą powyższej klawiatury i poleceń (dopasowań [a-zA-Z0-9 [email protected]]*
), wypisz sekwencję poleceń, które spowodują powstanie ciągu wyjściowego. Początkowa pozycja kursora znajduje się na1
klawiszu (lewy górny róg), a Caps Lock jest początkowo wyłączony.
Punktacja
W przypadku każdego ciągu znaków naiwnym podejściem byłoby, aby dla każdego znaku w ciągu przejść do znaku na klawiaturze najkrótszą ścieżką, w razie potrzeby przełączać Caps Lock i wybrać znak. Takie naiwne podejście generowałoby nakaz długości (length of input string) + (sum of Manhattan distances on keyboard between consecutive non-space characters) + (number of times the string alternates between lowercase and uppercase characters) + (1 if string starts with an uppercase letter else 0)
. Na przykład podejście naiwne dla 101
skutkowałoby ALARA
wydaniem polecenia o długości 5 i Noob 5
skutkowałoby DDDRRRRRCAUURRRCAADDLLLLAYUUUA
wydaniem polecenia o długości 30.
Wasze poddanie się ma jednak na celu lepsze wyniki niż naiwne podejście. Za każdy ciąg wejściowy twoje zgłoszenie otrzyma punkty równe liczbie poleceń, których używa naiwne podejście, minus liczba poleceń, które wyprowadza twoje podanie. Twój ogólny wynik będzie sumą poszczególnych wyników.
Zasady
- Zgłoszenia będą realizowane w wirtualnym obszarze roboczym Cloud9 . Obszar roboczy ma 512 MB pamięci RAM, 2 GB miejsca na dysku, 8 procesorów Intel (R) Xeon (R) @ 2,50 GHz (pełne informacje o procesorze, które
cat /proc/cpuinfo
można znaleźć po uruchomieniu , można znaleźć tutaj ) i działa 64-bitowy Ubuntu 14.04 Wierny. Możesz poprosić o dostęp do testowego obszaru roboczego w celu uruchomienia i oceny twojego zgłoszenia lub też mogę go dla ciebie ocenić. - Zgłoszenia będą uruchamiane raz na przypadek testowy. Przechowywanie stanu między przebiegami jest zabronione. Zgłoszenia nie mogą zapisywać ani odczytywać plików innych niż plik źródłowy (których nie można modyfikować między uruchomieniami), z możliwym wyjątkiem odczytywania pliku wejściowego, jeśli jest to wymagane.
- Zgłoszenia są ograniczone do 1 minuty czasu wykonywania dla każdego przypadku testowego. Zgłoszenia mogą generować wiele rozwiązań, ale do oceny zostanie użyte tylko ostatnie prawidłowe rozwiązanie w wyznaczonym czasie. Brak wydrukowania jakichkolwiek poprawnych rozwiązań w wyznaczonym czasie spowoduje wynik 0 dla tego przypadku testowego.
- Podaj wskazówki, jak wywołać zgłoszenie, a także wszelkie narzędzia / biblioteki, które należy zainstalować, które nie są zawarte w standardowej instalacji Ubuntu 14.04.
- Zwycięzcą zostanie zgłoszenie z największą liczbą punktów. W przypadku remisu wygrywa zgłoszenie o lepszej złożoności algorytmicznej. Jeśli remis nadal nie zostanie rozstrzygnięty, wygrana zostanie pierwsza próba osiągnięcia wyniku i złożoności algorytmu.
- Zgłoszenia mogą nie zostać zoptymalizowane pod kątem przypadków testowych. Zastrzegam sobie prawo do zmiany przypadków testowych, jeśli uważam, że jest taka potrzeba.
Przypadki testowe
Format: input string => naive score
(jeśli zauważysz w nich jakieś błędy, zostaw komentarz z poprawką)
101 => 5
quip => 12
PPCG => 15
Mego => 25
Noob 5 => 26
penguin => 27
867-5309 => 32
2_sPoOkY_4_mE => 60
The Nineteenth Byte => 76
[email protected] => 95
8xM3R__5ltZgrkJ.-W b => 98
correcthorsebatterystaple => 104
verylongRUNSOFCAPSandnocaps => 118
This is an English sentence. => 122
WNtza.akjzSP2GI0V9X .0epmUQ-mo => 131
Programming Puzzles and Code Golf => 140
Odpowiedzi:
do
Wynik to 193.
Skompiluj jako „gcc virtualKeyboard.c”. Uruchom go bez argumentów „./a.out”. Odczytuje dane wejściowe ze standardowego wejścia i zapisuje dane wyjściowe na standardowe wyjście.
źródło
C99
Oto moja próba rozwiązania. Uzyskał 62 punkty.
Wydawało się, że działa poprawnie dla mniejszych słów, a ja po prostu założyłem, że te większe również działają poprawnie, ponieważ są one zbyt duże, aby przetestować je ręcznie.
Skompiluj z „gcc -std = gnu99”
Użycie to „virtualKeyboard” string ”„
źródło
Noob 5
toRRRRRUCALCAYRRRRARRRRDBBBAA
, który produkujeN33b @
, a twój drugi wynik toLLDAAYRRRRAUBBARBBBCA
, który produkuje4oo3 e
. W tej chwili twój obecny wynik to 5, ponieważ twój program drukuje tylko prawidłowe sekwencje poleceń dla pierwszych 3 przypadków testowych.