Podczas pracy nad niepalindromicznym poliglakiem Boggle uważam, że dość nużące jest pakowanie kodów tak skutecznie, jak to możliwe, na płycie Boggle, nawet przy użyciu tylko dwóch łańcuchów. Ale jesteśmy programistami, prawda? Wiemy, jak zautomatyzować rzeczy.
Biorąc pod uwagę listę ciągów, musisz wygenerować tablicę Boggle, na której można znaleźć każdy z tych ciągów (niezależnie od pozostałych). Wyzwanie polega na tym, aby tablica Boggle była jak najmniejsza. Ponieważ jest to (miejmy nadzieję) dość trudne zadanie, jest to wyzwanie kodowe : nie ma wymogu optymalności - wyzwanie polega na tym, aby zrobić to najlepiej, jak potrafisz.
Zasady
- Tablica Boggle będzie prostokątna i będzie zawierać tylko wielkie litery. Dlatego ciągi wejściowe będą również zawierać tylko wielkie litery.
- Obowiązują zwykłe reguły Boggle: sznurek jest częścią planszy, jeśli zaczynając gdziekolwiek, możesz go znaleźć, wielokrotnie przechodząc do sąsiednich postaci (poziomo, pionowo lub po przekątnej). Aby utworzyć pojedynczy ciąg, nie możesz użyć żadnej komórki planszy więcej niż jeden raz. Jednak znaki mogą być ponownie użyte między różnymi łańcuchami.
- Masz 30 minut na przetworzenie danych testowych, a Twój kod nie może zużywać więcej niż 4 GB pamięci. Dam trochę swobody w zakresie limitu pamięci, ale jeśli twój program konsekwentnie używa więcej niż 4 GB lub skoków znacznie powyżej tego, zdyskwalifikuję go (tymczasowo).
- Przetestuję wszystkie zgłoszenia na własnym komputerze z systemem Windows 8. Mam maszynę Wirtualną Ubuntu, ale jeśli będę musiał to przetestować, nie będziesz w stanie wykorzystać tych 30 minut tak często, jak w innym przypadku. Dołącz link do bezpłatnego tłumacza / kompilatora dla wybranego języka, a także instrukcje dotyczące kompilowania / uruchamiania kodu.
- Twój wynik będzie miał rozmiar tablicy Boggle dla danych testowych poniżej (nie licząc nowych linii). W przypadku remisu (np. Ponieważ wielu osobom udało się stworzyć optymalne rozwiązanie), zwycięzcą zostanie zgłoszenie, które szybciej stworzy to optymalne rozwiązanie.
- Nie wolno optymalizować kodu specjalnie pod kątem danych testowych. Jeśli podejrzewam, że ktoś to robi, zastrzegam sobie prawo do generowania nowych danych testowych.
Przykład
Biorąc pod uwagę struny
FOO
BAR
BOOM
Kiedyś mógł trywialnie umieścić je na tablicy Boggle 4x3:
FOOX
BARX
BOOM
Wykorzystując fakt, że łańcuchy nie muszą być proste, możemy skompresować je do rozmiaru 5x2:
BORFO
OMABO
Ale możemy go jeszcze zmniejszyć, ponownie wykorzystując znaki między różnymi ciągami i dopasować ciągi w 4x2:
FOOM
BARX
Teraz B
jest używany dla obu BOOM
i BAR
, i OO
jest używany dla obu BOOM
i FOO
.
Dane testowe
Twoje zgłoszenie zostanie przetestowane na następujących 50 ciągach. Do celów testowych możesz po prostu użyć mniejszych podzbiorów tych danych, które powinny następnie działać szybciej. Uważam, że absolutną dolną granicą dla tych danych testowych jest tablica zawierająca 120 znaków, chociaż nie jest to koniecznie osiągalne.
T
WP
GVI
CIHM
EGWIV
QUTYFZ
LWJVPNG
XJMJQWSW
JLPNHFDUW
SWMHBBZWUG
XVDBMDQWDEV
TIUGAVZVUECC
IWDICFWBPSPQR
MMNWFBGMEXMSPY
YIHYXGJXKOUOIZA
BZSANEJNJWWNUJLJ
XTRMGOVPHVZYLLKKG
FLXFVVHNTWLMRRQYFQ
VZKJRAFQIYSBSXORTSH
FNQDIGCPALCHVLHDNZAV
GEAZYFSBSWCETXFKMSWLG
KWIZCEHVBDHEBGDGCJHOID
SKMQPHJAPDQKKHGTIPJCLMH
ZSFQDNYHALSUVWESQVVEUIQC
HXHBESUFCCECHNSTQGDUZPQRB
DSLXVHMOMLUXVHCNOJCBBRPVYB
DVTXKAOYYYRBVAVPSUAOYHIPPWN
PJAIYAWHMTNHTQDZDERPZYQEMLBZ
SYNSHJNOIWESMKWTBIANYUAUNRZOS
WADGUKIHUUFVRVUIBFUXQIOLAWIXAU
LGLXUFIXBEPSOFCKIAHXSHVKZPCXVPI
LIUYFHITTUYKDVQOZPNGZLWOZSRJTCTZ
IZDFTFFPNEBIYGVNTZHINICBXBXLBNBAL
BSKQNTPVUAVBXZGHVZCOUCRGCYISGFGYAS
DPGYYCIKDGCETXQOZGEQQLFQWACMVDTRYAT
RQDNIPGUHRYDRVHIPJLOWKBXMIBFAWCJGFMC
PFKOAGEQLXCMISSVEARWAPVYMRDCLSLPJOMQQ
EQPCNHQPTWABPFBVBXHQTFYELPNMNCWVKDDKGR
RAHTJMGIQJOJVWJBIHVRLJYVCSQJCKMEZRGRJMU
SZBJBPQYVYKDHAJHZMHBEWQEAQQKIEYCFACNLJBC
ANVDUCVXBPIZVRAXEBFEJOHSYKEKBIJELPIWEYXKH
DJUNPRLTISBFMGBEQNXSNUSOGDJNKESVKGAAMTIVXK
TZPUHDSHZFEURBNZTFBKXCDPYRELIAFMUWDIQTYWXGU
FJIKJROQSFSZUCGOOFJIEHBZREEUUSZWOLYFPCYHUSMR
TPMHJEAWVAJOCSDOPMQMHKRESBQSTRBXESYGCDVKLFOVS
ABJCCDJYMYDCYPZSGPGIAIKZQBYTZFDWYUZQBOESDSDGOY
IIHKTVPJNJDBCBOHCIYOPBKOVVKGNAKBDKEEKYIPRPHZOMF
IABGEPCSPNSMLVJBSGLRYNFSSYIALHWWAINTAVZAGJRVMDPW
GFMFVEFYJQJASVRIBLULUEHPMZPEXJMHIEMGJRMBLQLBDGTWT
YPWHLCVHQAVKVGHMLSOMPRERNHVYBECGCUUWTXNQBBTCMVTOVA
Weryfikator
Możesz użyć następującego fragmentu stosu, aby sprawdzić, czy tablica Boggle zawiera wszystkie łańcuchy na danej liście. Przeniesiłem kod wyszukiwania Boggle z odpowiedzi edc65 tutaj . Daj mi znać, jeśli coś wydaje się wadliwe.
źródło