Zaniepokoiła mnie rosnąca nienawiść do przestrzeni, a ta odpowiedź zainspirowała mnie do upewnienia się, że kod Morse'a jest bezpieczny przed tym podstępnym usunięciem białych znaków.
Twoim zadaniem będzie stworzenie programu, który z powodzeniem przetłumaczy kod Morse'a ze wszystkimi spacjami.
Zasady:
Wejście będzie ciągiem złożonym wyłącznie z myślników i kropek (ASCII 2D i 2E). Dane wyjściowe są niezdefiniowane dla danych wejściowych zawierających inne znaki. Możesz użyć dowolnej metody dogodnej dla wybranego języka, aby otrzymać dane wejściowe (standardowe, plik tekstowy, monit użytkownika, cokolwiek). Możesz założyć, że wprowadzony kod Morse'a składa się tylko z liter AZ, a pasujące liczby lub znaki interpunkcyjne nie są wymagane.
Dane wyjściowe powinny zawierać tylko słowa zawarte w tym pliku słownika (ponownie, skorzystaj z dowolnej dogodnej metody dostępu do pliku słownika). Wszystkie prawidłowe dekodowania powinny być wyprowadzane na standardowe wyjście, a wszystkie kropki i myślniki na wejściu muszą być użyte. Każde dopasowane słowo na wyjściu powinno być oddzielone spacją, a każde możliwe dekodowanie powinno być oddzielone znakiem nowej linii. Jako wygodę możesz używać drukowania wielkich, małych lub mieszanych znaków.
Obowiązują wszystkie ograniczenia dotyczące standardowych luk z jednym wyjątkiem, jak wspomniano powyżej, jeśli chcesz, możesz uzyskać dostęp do pliku słownika wymienionego w wymaganiu 2 za pośrednictwem połączenia internetowego. Skracanie adresów URL jest dopuszczalne, uważam, że goo.gl/46I35Z jest prawdopodobnie najkrótszy.
To jest golf golf, wygrywa najkrótszy kod.
Uwaga: opublikowanie pliku słownika na Pastebin zmieniło wszystkie zakończenia linii na sekwencje 0A 0E w stylu Windows. Twój program może przyjmować zakończenia linii tylko z 0A, tylko 0E lub 0A 0E.
Przypadki testowe:
Wkład:
......-...-.. ---. -----.-..-..- ..
Dane wyjściowe muszą zawierać:
Witaj świecie
Wkład:
. - ..-. ----- ..-.. ----- ..-. - .. - ... --- .. - ...-.... ... -.-..-.-. ---- ... -. ---.-....-.
Dane wyjściowe muszą zawierać:
programowanie zagadek i golfa kodu
Wkład:
-..... -.-..-..-.-.-. - ....-. ---. --- ...-. ---- ..-.- --.. ---. - .... --- ...-..-.-......-... --- ..-. --- ..-- ---.
Dane wyjściowe muszą zawierać:
szybki brązowy lis przeskakuje nad leniwym psem
AN (.- -.)
iEG (. --.)
?Odpowiedzi:
Ruby, 210
Jeśli istnieje taka praktyka jak „over-golfing”, podejrzewam, że tym razem brałem udział. To rozwiązanie generuje tablicę tablic powtarzających się permutacji wszystkich słów słownika , od długości 1 do długości danych wejściowych. Biorąc pod uwagę, że „a” jest najkrótszym słowem w pliku słownika, a jego kod ma długość dwóch znaków, wystarczyłoby wygenerować permutacje o długości do połowy wielkości danych wejściowych, ale dodawanie
/2
jest równoznaczne z gadatliwością w tej dziedzinie, więc powstrzymałem się.Po wygenerowaniu tablicy permutacji ( NB : ma ona długość 45404 104 w przypadku przykładowego pangramatycznego przykładu), każda tablica permutacji jest konkatenowana, a jej znaki alfabetyczne są zastępowane odpowiednikami kodu Morse'a za pomocą dość wygodnego
(Regexp, Hash)
wariantu#gsub
metoda; znaleźliśmy prawidłowe dekodowanie, jeśli ten ciąg znaków jest równy wejściowi.Słownik jest odczytywany (kilka razy) z pliku o nazwie „d”, a dane wejściowe nie mogą zawierać nowego wiersza.
Przykładowy przebieg (ze słownikiem, który da programowi szansę na zakończenie walki przed śmiercią wszechświata):
źródło
Haskell, 296 znaków
Objaśnienie elementów:
main
odczytuje słownik, odczytuje stdin, wykonuje&
i formatuje dane wyjściowe&
z odpowiednią białą spacją.(replicate 97"X"++words".- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --..")!!)
(wyrażenie wewnątrz definicji&
) to lista, której indeksy są kodami znaków (97 to kod'a'
), a wartości to sekwencje Morse'a.!
(funkcja nazwana jako operator infix) dopasowuje ciąg znaków do prefiksu; jeśli prefiks jest obecny, zwraca resztę z listy jednoelementowej (sukces w monadzie listy), w przeciwnym razie pusta lista (błąd w monadzie listy)&
używa monady listy do wykonania „niedeterministycznego”; tod
(słowa ze słownika),!
do dopasowania formy Morse'a tego słowa (w>>=((…)!!).fromEnum
równoważnejconcatMap (((…)!!) . fromEnum) w
) do ciągu wejściowegoi
,d&j
), aby dopasować resztę ciągu, orazw:n
w monadzie listy[w:n]
(która jest krótszym, konkretnym odpowiednikiemreturn (w:n)
).Zauważ, że każda linia po linii 6 jest częścią
do
wyrażenia rozpoczętego w linii 6; zajmuje to dokładnie tyle samo znaków, co średników w jednym wierszu, ale jest bardziej czytelny, chociaż można to zrobić tylko raz w programie.Ten program jest bardzo wolny. Można to zrobić szybciej (i nieco dłużej) łatwo, przechowując zmoryfikowane słowa obok oryginałów na liście, a nie przeliczając je przy każdym dopasowaniu wzoru. Następną rzeczą do zrobienia byłoby przechowywanie słów w drzewie binarnym kluczowanym przez symbole Morse'a (2-arytowe trie ), aby uniknąć próbowania niepotrzebnych gałęzi.
Można go nieco skrócić, jeśli plik słownika nie zawiera nieużywanych symboli, takich jak „-”, umożliwiając usunięcie
replicate 97"X"++
na korzyść robienia.(-97+)
przed!!
.źródło
(+(-97))
można to przepisać jako(-97+)
?|0<1=[]
do drugiej definicjiinteract
i wygraj 12 znaków.interact$unlines.map unwords.(words f&)
concatMap
z>>=
Python -
363345Kod:
Wyjaśnienie:
Słownik musi być przechowywany jako zwykły plik tekstowy o nazwie „d”.
D
,P
,U
AN
to tylko niektóre zmienne pomocnicze dla krótszej definicji tabeli Morse wyszukiwania.s(i)
to funkcja rekurencyjna, która drukuje poprzednio przetłumaczoną część komunikatup
i każde prawidłowe tłumaczenie pozostałej części kodui
: Jeślii
jest pusta, osiągnęliśmy koniec kodu ib
zawiera całe tłumaczenie, a więc po prostuprint
to. W przeciwnym razie sprawdzamy każde słowow
w słownikud
, tłumaczymy je na kod Morse'a,C
a jeśli pozostały kodi
zaczyna się odC
, dodajemy słowow
do przetłumaczonego początkub
i wywołujemy funkcjęs
rekurencyjnie na pozostałej części.Uwaga na temat wydajności:
To dość powolna, ale golfowa wersja. Szczególnie ładowanie słownika i konstruowanie tabeli odnośników Morse'a (
dict(zip(...))
) w każdej iteracji (aby uniknąć większej liczby zmiennych) kosztuje dużo. Bardziej efektywne byłoby przetłumaczenie wszystkich słów w pliku słownika z wyprzedzeniem, a nie każdej rekurencji na żądanie. Te pomysły prowadzą do następnej wersji z 40 dodatkowymi postaciami, ale znaczącym przyspieszeniem:źródło
.startswith(C)
je[:len(C)]==C
.d=sorted(open('d').read().split(),key=len,reverse=1)
Lub zrób to zewnętrznie, wstępnie sortując słownik w ten sposób.M=eval(open('d').read())
:)Perl (5.10+), 293 znaków
Plik słownika powinien być zapisany jako „d” (i powinien być w formacie uniksowym, jeśli nie chcesz CRs między słowami), Morse na stdin, bez końcowego znaku nowej linii (użyj
echo -n
).(podziały wierszy tylko w przypadku formatowania).
Nieskluczony kod:
Modus operandi:
Symbole kodu Morse'a są przechowywane przez zmianę „.” i „-” na cyfry binarne 0 i 1, poprzedzając „1” (aby kropki nie były pochłaniane), konwertując liczbę binarną na dziesiętną, a następnie kodując znak o wartości 61 wyższej (co daje mi wszystko znaki do druku i nic, co wymaga ukośnika odwrotnego).
Myślałem o tym jako o problemie z partycjonowaniem i na tej podstawie zbudowałem rozwiązanie. Dla każdego słowa w słowniku konstruuje obiekt wyrażenia regularnego, który będzie pasował (i przechwytywał) bezprzestrzenną reprezentację Morse'a tego słowa na początku łańcucha. Następnie rozpoczyna się wyszukiwanie od początku do końca, tworząc stan, który nie pasuje do żadnych słów i zawiera całe dane wejściowe jako „pozostałe dane wejściowe”. Następnie rozszerza każdy stan, szukając słów pasujących na początku pozostałych danych wejściowych i tworząc nowe stany, które dodają słowo do dopasowanych słów i usuwają Morse'a z pozostałych danych wejściowych. Stany, które nie mają żadnych pozostałych danych wejściowych, są udane i wydrukowano ich listę słów. Stany, które nie mogą dopasować żadnych słów (w tym te zakończone sukcesem), nie generują stanów potomnych.
Zauważ, że w wersji bez golfa stany są skrótami dla czytelności; w wersji golfowej są to tablice (dla krótszego kodu i mniejszego zużycia pamięci); szczelina
[0]
to pozostałe wejście, a szczelina[1]
to dopasowane słowa.Komentarz
To jest bezbożnie wolne. Zastanawiam się, czy istnieje rozwiązanie, które nie jest. Próbowałem zbudować jeden przy użyciu Marpy (parsera Earleya z możliwością dawania wielu parsów dla jednego ciągu wejściowego), ale zabrakło mi pamięci po prostu konstruując gramatykę. Może gdybym użył interfejsu API niższego poziomu zamiast wejścia BNF ...
źródło
chomp()
. Czy powinienem?ord
zamiastord$_
. Ogol 1 bajt mówiącjoin$"
zamiastjoin" "
Haskell - 418
Ten problem dekompresyjny można skutecznie rozwiązać za pomocą programowania dynamicznego. Wiem, że to kodegolf, ale uwielbiam szybki kod.
Załóżmy, że mamy ciąg wejściowy
s
, a następnie budujemy tablicędp
,dp[i]
jest to lista wszystkich prawidłowych wyników dekodowania podłańcuchas[:i]
. Dla każdego słowaw
w słowniku najpierw go kodujemymw
, a następnie możemy obliczyć częśćdp[i]
zdp[i - length(mw)]
ifs[i - length(mw):i] == mw
. Złożoność czasowa budowydp
jestO({count of words} {length of s} {max word length})
. Wreszciedp[length(s)]
ostatni element jest tym, czego potrzebujemy.W rzeczywistości nie musimy przechowywać całego dekodowania jako elementu każdego z nich
dp[i]
. Potrzebujemy ostatniego zdekodowanego słowa. Dzięki temu wdrożenie jest znacznie szybsze. Ukończenie „hello world” na moim laptopie i3 kosztowało mniej niż 2 sekundy. W innych przypadkach zamieszczonych w pytaniu program nie zakończy się w sposób praktyczny, ponieważ jest zbyt wiele danych wyjściowych.Za pomocą techniki programowania dynamicznego możemy obliczyć liczbę prawidłowych dekodowań . Możesz znaleźć kod tutaj . Wyniki:
Bez golfa
Grał w golfa
źródło
PHP,
234226 bajtówfunkcja rekurencyjna, pobiera słownik z pliku o nazwie
d
.Nie powiedzie się za każde słowo w słowniku zawierające nieliterową literę.
Możesz użyć dowolnej nazwy pliku, jeśli
define ("d","<filename>");
przed wywołaniem funkcji.Dodaj 2 lub 3 bajty, aby przyspieszyć wykonanie:
Usuń
$s?:print"$r\n";
, wstaw$s!=$m?
przed0!==
i:print$r.$w
przed;}}
.awaria
źródło
Groovy
377337Notatki
Dict musi być plikiem o nazwie
d
. Ciąg Morse'a jest przekazywany z wiersza poleceń. na przykład:Do „kompresji kodu Morse'a” używam drzewa binarnego
źródło