Czy zastanawiałeś się kiedyś, jakie kraje otaczają inne? Ja też czasami i cóż, oto wyzwanie.
Na dole tego wpisu umieściłem listę krajów i krajów, których dotykają, które musisz rozpoznać w bloku kodu. Musisz stworzyć pełny program, który wyświetla (w najwygodniejszy możliwy sposób w twoim języku) listę warstw krajów sąsiednich krajów do kraju wejściowego. Na przykład:
>>> "United Kingdom" 1
Republic of IrelandPonieważ "United Kingdom"to nazwa kraju i 1liczba warstw, które chcesz utworzyć. W rzeczywistości powróci dowolna liczba warstw (z wyjątkiem 0) Republic of Ireland, ponieważ istnieje morze na drodze do innych krajów.
Mapa odniesienia:
Przykłady (wszystko w nawiasach to komentarze) (oczywiście kolejność danych wyjściowych nie ma znaczenia):
>>> Bhutan 2
India (layer 1, touching Bhutan)
China (layer 1, touching Bhutan)
Bangladesh (layer 2, touching India)
Myanmar (layer 2, touching China and India)
Laos (layer 2, touching China)
Vietnam (layer 2, touching China)
North Korea (layer 2, touching China)
Russia (layer 2, touching China)
Mongolia (layer 2, touching China)
Kazakstan (layer 2, touching China)
Uzbekistan (layer 2, touching China)
Afganistan (layer 2, touching China)
Pakistan (layer 2, touching China and India)
Kashmir (layer 2, touching China and India)
Nepal (layer 2, touching China and India)>>> Russia 0 (no layers used)
>>> Cyprus 1800 (there's a sea in the way)
>>> "The Gambia" 4 (there's a sea in the way)
Senegal (layer 1)
Mauritania (layer 2)
Mali (layer 2)
Guinea (layer 2)
Guinea-Bissau (layer 2)
Sierra Leone (layer 3)
Liberia (layer 3)
Cote D'Ivoire (layer 3)
Burkina Faso (layer 3)
Niger (layer 3)
Algeria (layer 3)
Western Sahara (layer 3)
Morocco (layer 4)
Tunisia (layer 4)
Libya (layer 4)
Chad (layer 4)
Nigeria (layer 4)
Benin (layer 4)
Togo (layer 4)
Ghana (layer 4)Ponieważ świat jest duży, musisz to zrekompensować, zmniejszając kod. W końcu to jest golf golfowy .
Touching List (w nieokreślonej kolejności, w formacie możliwym do przeanalizowania) (jeśli są tu błędy, proszę dać mi znać . Przeszedłem je wiele razy, ale z pewnością popełniłem kilka błędów):
USA touches: Canada, Mexico
Canada touches: USA
Mexico touches: USA, Belize, Guatemala
Guatemala touches: Mexico, Belize, El Salvador, Honduras
Belize touches: Mexico, Guatemala
El Salvador touches: Guatemala, Honduras
Honduras touches: Guatemala, El Salvador, Nicaragua
Nicaragua touches: Honduras, San Jose
San Jose touches: Nicaragua, Panama
Panama touches: San Jose, Columbia
Columbia touches: Venezuela, Brazil, Peru, Ecuador, Panama
Venezuela touches: Columbia, Brazil, Guyana
Guyana touches: Venezuela, Brazil, Suriname
Suriname touches: Guyana, Brazil, French Guiana
French Guiana touches: Suriname, Brazil
Brazil touches: Columbia, Venezuela, Guyana, Suriname, French Guiana, Peru, Bolivia, Paraguay, Argentina, Uruguay
Ecuador touches: Columbia, Peru
Peru touches: Ecuador, Columbia, Brazil, Bolivia, Chile
Bolivia touches: Peru, Brazil, Paraguay, Argentina, Chile
Chile touches: Peru, Bolivia, Argentina
Paraguay touches: Bolivia, Brazil, Argentina
Argentina touches: Chile, Bolivia, Paraguay, Brazil, Uruguay
Uruguay touches: Argentina, Brazil
The Bahamas touches:
Cuba touches:
Jamaica touches:
Haiti touches: Dominican Republic
Dominican Republic touches: Haiti
Puerto Rico touches:
Saint Kitts and Nevis touches:
Montserrat touches:
Guadeloupe touches:
Dominica touches:
Martinique touches:
Saint Vincent touches:
Barbados touches:
Trinidad and Tobago touches:
Greenland touches:
Azores touches:
Falkland Islands touches:
South Georgia touches:
Cape Verde touches:
Madeira Island touches:
Canary Islands touches:
Faroe Islands touches:
Republic of Ireland touches: United Kingdom
United Kingdom touches: Republic of Ireland
Svalbard touches:
Norway touches: Sweden, Finland, Russia
Sweden touches: Norway, Finland
Finland touches: Sweden, Norway, Russia
Russia touches: Norway, Finland, Estonia, Latvia, Belarus, Ukraine, Turkey, Armenia, Azerbaijan, Kazakhstan, China, Mongolia, North Korea
Denmark touches: Germany
Estonia touches: Russia, Latvia
Latvia touches: Estonia, Russia, Belarus, Lithuania
Lithuania touches: Latvia, Belarus, Poland
Belarus touches: Lithuania, Latvia, Russia, Ukraine, Poland
Germany touches: Luxembourg, Belgium, Netherlands, Denmark, Poland, Czech Republic, Austria, Liechtenstein, Switzerland, France
Netherlands touches: Germany, Belgium
Belgium touches: France, Netherlands, Germany, Luxembourg
Luxembourg touches: France, Belgium, Germany
Poland touches: Germany, Lithuania, Belarus, Ukraine, Slovakia, Czech Republic
Ukraine touches: Slovakia, Poland, Belarus, Russia, Romania, Moldova, Hungary
Czech Republic touches: Germany, Poland, Slovakia, Austria
Slovakia touches: Austria, Czech Republic, Poland, Ukraine, Hungary
Moldova touches: Ukraine, Romania
Romania touches: Hungary, Ukraine, Moldova, Bulgaria, Serbia
Hungary touches: Austria, Slovakia, Ukraine, Romania, Serbia, Croatia, Slovenia
Austria touches: Liechtenstein, Germany, Czech Republic, Slovakia, Hungary, Slovenia, Italy, Switzerland
Liechtenstein touches: Switzerland, Germany, Austria
France touches: Belgium, Luxembourg, Germany, Switzerland, Italy, Spain
Switzerland touches: France, Germany, Liechtenstein, Austria, Italy
Slovenia touches: Italy, Austria, Hungary, Croatia
Croatia touches: Slovenia, Hungary, Serbia, Bosnia and Herzegovina
Bosnia and Herzegovina touches: Croatia, Serbia, Montenegro
Serbia touches: Bosnia and Herzegovina, Croatia, Hungary, Romania, Bulgaria, Macedonia, Albania, Montenegro
Bulgaria touches: Serbia, Romania, Turkey, Greece, Macedonia
Montenegro touches: Bosnia and Herzegovina, Serbia, Albania
Albania touches: Montenegro, Serbia, Macedonia, Greece
Macedonia touches: Albania, Serbia, Bulgaria, Greece
Italy touches: France, Switzerland, Austria, Slovenia
Spain touches: Portugal, France
Portugal touches: Spain
Greece touches: Albania, Macedonia, Bulgaria, Turkey
Turkey touches: Greece, Russia, Armenia, Azerbaijan, Iran, Iraq, Syria, Bulgaria
Malta touches:
Cyprus touches:
Armenia touches: Turkey, Russia, Azerbaijan, Iran
Azerbaijan touches: Turkey, Armenia, Russia, Iran
Kazakhstan touches: Russia, China, Uzbekistan, Turkmenistan
Mongolia touches: China, Russia
North Korea touches: China, Russia, South Korea
South Korea touches: North Korea
China touches: Afghanistan, Uzbekistan, Kazakhstan, Russia, Mongolia, North Korea, Vietnam, Laos, Myanmar, India, Bhutan, Nepal, Kashmir
Uzbekistan touches: Kazakhstan, China, Afghanistan, Turkmenistan
Afghanistan touches: Iran, Turkmenistan, Uzbekistan, China, Kashmir, Pakistan
Turkmenistan touches: Kazakhstan, Uzbekistan, Afghanistan, Iran
Iran touches: Iraq, Turkey, Azerbaijan, Armenia, Turkmenistan, Afghanistan, Pakistan
Iraq touches: Jordan, Syria, Turkey, Iran, Kuwait, Saudi Arabia
Syria touches: Lebanon, Turkey, Iraq, Jordan, Israel
Lebanon touches: Israel, Syria
Israel touches: Egypt, Lebanon, Syria, Jordan
Jordan touches: Israel, Syria, Iraq, Saudi Arabia
Saudi Arabia touches: Jordan, Iraq, Kuwait, Qatar, United Arab Emirates, Oman, Yemen
Kuwait touches: Iraq, Saudi Arabia
Qatar touches: Saudi Arabia
United Arab Emirates touches: Saudi Arabia, Oman
Oman touches: Saudi Arabia, United Arab Emirates, Yemen
Yemen touches: Saudi Arabia, Oman
Pakistan touches: Iran, Afghanistan, Kashmir, India
Kashmir touches: Pakistan, Afghanistan, China, India
India touches: Pakistan, Kashmir, Nepal, Bhutan, Myanmar, Bangladesh, China
Nepal touches: India, China
Bhutan touches: India, China
Bangladesh touches: India, Myanmar
Sri Lanka touches:
Adaman and Nicobar Islands touches:
Myanmar touches: Bangladesh, India, China, Laos, Thailand
Thailand touches: Myanmar, Laos, Cambodia, Malaysia
Laos touches: Myanmar, China, Vietnam, Cambodia, Thailand
Vietnam touches: Laos, China, Cambodia
Cambodia touches: Thailand, Laos, Vietnam
Malaysia touches: Thailand, Brunei, Indonesia
Brunei touches: Malaysia
Phillipines touches:
Indonesia touches: Malaysia, Papua New Guinea
Papua New Guinea touches: Indonesia
Australia touches:
Tasmania touches:
Japan touches:
Guam touches:
Solomon Islands touches:
Vanuatu touches:
Fiji touches:
New Caledonia touches:
New Zealand touches:
Kerguelen Island touches:
Heard Island touches:
Mauritius touches:
Reunion touches:
Mayotte touches:
Comoros touches:
Madagascar touches:
Sao Tome touches:
Bioko touches:
Egypt touches: Libya, Israel, Sudan
Libya touches: Algeria, Tunisia, Egypt, Sudan, Chad, Niger
Tunisia touches: Algeria, Libya
Algeria touches: Western Sahara, Morocco, Tunisia, Libya, Niger, Mali, Mauritania
Morocco touches: Western Sahara, Algeria
Western Sahara touches: Morocco, Algeria, Mauritania
Mauritania touches: Western Sahara, Algeria, Mali, Senegal
Senegal touches: The Gambia, Mauritania, Mali, Guinea, Guinea-Bissau
The Gambia touches: Senegal
Guinea-Bissau touches: Senegal, Guinea
Guinea touches: Guinea-Bissau, Senegal, Mali, Cote D'Ivoire, Liberia, Sierra Leone
Sierra Leone touches: Guinea, Liberia
Liberia touches: Sierra Leone, Guinea, Cote D'Ivoire
Cote D'Ivoire touches: Liberia, Guinea, Mali, Burkina Faso, Ghana
Mali touches: Senegal, Mauritania, Algeria, Niger, Burkina Faso, Cote D'Ivoire, Guinea
Burkina Faso touches: Mali, Niger, Benin, Togo, Ghana, Cote D'Ivoire
Ghana touches: Cote D'Ivoire, Burkina Faso, Togo
Togo touches: Ghana, Burkina Faso, Benin
Benin touches: Togo, Burkina Faso, Niger, Nigeria
Niger touches: Burkina Faso, Mali, Algeria, Libya, Chad, Nigeria, Benin
Nigeria touches: Benin, Niger, Chad, Cameroon
Chad touches: Niger, Libya, Sudan, Central African Republic, Cameroon, Nigeria
Sudan touches: Chad, Libya, Egypt, Eritrea, Ethiopia, Kenya, Uganda, Democratic Republic of the Congo, Central African Republic
Eritrea touches: Sudan, Djibouti, Ethiopia
Djibouti touches: Ethiopia, Eritrea, Somalia
Ethiopia touches: Sudan, Eritrea, Djibouti, Somalia, Kenya
Somalia touches: Kenya, Ethiopia, Djibouti
Kenya touches: Uganda, Sudan, Ethiopia, Somalia, Tanzania
Uganda touches: Democratic Republic of the Congo, Sudan, Kenya, Tanzania, Rwanda
Democratic Republic of the Congo touches: Cabinda, Congo, Central African Republic, Sudan, Uganda, Rwanda, Burundi, Zambia, Angola
Central African Republic touches: Cameroon, Chad, Sudan, Democratic Republic of the Congo, Congo
Cameroon touches: Nigeria, Chad, Central African Republic, Congo, Gabon, Equatorial Guinea
Equatorial Guinea touches: Cameroon, Gabon
Gabon touches: Equatorial Guinea, Cameroon, Congo
Congo touches: Gabon, Cameroon, Central African Republic, Democratic Republic of the Congo, Cabinda
Rwanda touches: Democratic Republic of the Congo, Uganda, Tanzania, Burundi
Burundi touches: Democratic Republic of the Congo, Rwanda, Tanzania
Tanzania touches: Burundi, Rwanda, Uganda, Kenya, Mozambique, Malawi, Zambia
Cabinda touches: Congo, Democratic Republic of the Congo
Angola touches: Democratic Republic of the Congo, Zambia, Namibia
Zambia touches: Angola, Democratic Republic of the Congo, Tanzania, Malawi, Mozambique, Zimbabwe, Botswana, Namibia
Malawi touches: Zambia, Tanzania, Mozambique
Mozambique touches: Zimbabwe, Zambia, Malawi, Tanzania, South Africa, Swaziland
Zimbabwe touches: Namibia, Zambia, Mozambique, South Africa, Botswana
Botswana touches: Namibia, Zambia, Zimbabwe, South Africa
Namibia touches: Angola, Zambia, Zimbabwe, Botswana, South Africa
South Africa touches: Namibia, Botswana, Zimbabwe, Mozambique, Swaziland, Lesotho
Swaziland touches: South Africa, Mozambique
Lesotho touches: South Africa
code-golf
kolmogorov-complexity
Addison Crump
źródło
źródło
%r=map%$_,%r.Odpowiedzi:
Perl,
150914961392138913861251124812461241 bajtówObejmuje +2 za
-naBiegaj z krajem i licz na STDIN, np
perl -na countries0.pl <<< "The Gambia 4"Plik
countries.pl:Działa to tak, jak jest, ale aby uzyskać daną długość, wszystkie znaki zmiany znaczenia muszą zostać zastąpione odpowiednimi literalnymi. Możesz to np. Zrobić za pomocą:
Wyjaśnienie
Najpierw wyświetlmy program z usuniętymi transformacjami:
Podstawową ideą jest posiadanie trzech głównych struktur danych:
@countrieszawierająca wszystkie kraje%toucheswskaźników w@countriestablicy, który$touches{$i}{$j}istnieje wtedy i tylko wtedy, gdy$countries[$i]dotyka$countries[$j]%reachablektóry ma klucz do indeksu każdego kraju, który jest osiągalny na aktualnie rozważanej warstwie.Algorytm to:
@countriesi użyj go do zainicjowania%reachable$rw%reachablewyglądzie się$touches{$r}i zebrać wszystkie klucze można znaleźć tam%reachable. Ponieważ jest to skrót, wszelkie duplikaty zostaną usunięte%reachableaby wydrukować odpowiedni kraj w@countries, ale nie drukuj oryginalnego kraju docelowegoTu kończy się prostota, kończy się gra w golfa.
@countriesArray nigdy nie będzie istnieć z nazwą, choć jest on tworzony w pamięci krótko%reachableHash będzie nazwany%r%touchesHash nie będzie jawnie istnieje. Zamiast tego używam globalnej przestrzeni nazw Perla. Np. Ten kraj 6 dotyka kraju 3, a kraj 12 będzie reprezentowany w haszu,%6który będzie zawierał(3 => undef, 12 => undef)@countries[keys %reachable]ale nie chcę pisaćkeysi zamiast tego@countries[%reachable]. Ale ponieważ%reachablebędą zawieraćundefwartości, które stają się indeksem 0, zacznę aktualną listę krajów od indeksu 1 i ustawię pusty ciąg o indeksie 0. Drukowanie tego pustego ciągu będzie niewidoczne. Upewnię się również, że kraj docelowy zostanie zastąpiony pustym ciągiem znaków. I na koniec każdy kraj będzie miał na końcu nową linię. Wiedząc, że końcowy wynik staje się po prostuprint @countries[%reachable]. Tyle, że kraje w tym momencie będą w$_, więc rzeczywisty kod toprint+(/$|.+\n/mg)[%r]. Zauważ, że regex upewnia się, że puste linie nie otrzymują nowej linii, ale pełne nazwy krajów.%reachablemożna w zasadzie pobrać za pomocąmap keys %{$touches{$_}},keys %reachable. Ale znowukeysnie jest to konieczne, jeśli staram się odpowiednio obsługiwać wartości undef, które również otrzymuję bezkeys. I jak powiedziano wcześniej, używam głównego globu do przechowywania wartości, więc rzeczywisty fragment kodu tomap%$_,%r. Chcę dodać każdą ze zwróconych wartości jako nowy klucz, do%rktórego można to zrobić jako%r=map%$_,%r. Wymaga to jednak od krajów odniesienia się do siebie jako dotykających, aby warstwa początkowa pozostała w zbiorze. Ten fragment kodu należy powtórzyć tyle razy, ile użytkownik poprosił o warstwy. Zauważ, że jest to rzeczywisty rdzeń programu, wszystko inne to hałas, aby to wspierać.-aopcja zebrała liczbę warstw jako ostatni element w@Ftym można osiągnąć za pomocąeval '%r=map%$_,%r;' x pop @F. Zasadniczo nie jest to najkrótszy sposób na zapętlenie w perlu, ale ma tę zaletę, że nie zmienia się$_podczas pętli, co wykorzystam później. Umieszczenie liczby warstw z własnej linii STDIN pozwolił mi zastąpićx pop@Fprzezx<>oszczędność 4 bajty, ale chcę, aby pozostać jak najbliżej specyfikacji, jak to możliwe.pop @Fusunięciu warstwy@Fzawierają początkową nazwę kraju. Zwróć uwagę, że kraje ze spacjami w nazwie zostaną podzielone na części składowe. Możemy znaleźć cel w ciągu dużych krajów$_i natychmiast zastąpić kraj docelowy ciągiem emty (aby nie został wydrukowany)s/^@F$//m. Zauważ, że kraje ze spacjami w ich nazwie są odtwarzane przez@Finterpolację. Zauważ też, że należy to dokładnie zakotwiczyć, ponieważ niektóre kraje są podłańcami innych, np.GuineaIGuinea-BissaulubNigeriNigeria$'=~y/\n//. Jeśli kraj docelowy nie$`zostanie znaleziony , zawiera wartość z poprzedniego wyrażenia regularnego, co może być bardzo błędne. Zamiast tego chcemy 0 (przy którym indeksie mamy pusty ciąg). Można to osiągnąć, łącząc go z poprzednim dopasowaniem ws/^@F$//m*$`=~y/\n//.%reachable. Ewaluacja staje się wtedyeval '%r=map%$_,%r,%r,s/^@F$//m*$`=~y/\n//;' x pop@F;. Zwróć uwagę, że podstawienie niszczy kraj docelowy,$_więc tylko dodaje się go za pierwszym razem (nie byłoby tak, gdyby tak nie było, ponieważ indeks kraju docelowego i tak już istnieje%reachable)%rmożemy go połączyć z,print+(/$|.+\n/mg)[%r]aby uzyskać rzeczywisty kodprint+(/$|.+\n/mg)[eval'%r=map%$_,%r,s/^@F$//m*$`=~y/\n//;'x pop@F]Kolejne pytanie dotyczy sposobu zakodowania listy krajów. Jak wyjaśniono powyżej, chcę, aby był to ogromny ciąg z krajami zakończonymi znakiem nowej linii i rozpoczynającym się od jednej nowej linii. Potrzebuję do tego 26 liter, spacji, nowej linii,
-(dlaGuinea-Bissau) i'(dlaCote D'Ivoire). Problemem jest oczywiście, że czasami litery są pisane wielkimi literami. Można to łatwo rozwiązać, umieszczając pierwszą literę po granicy słowa. Jednak istnieją wyjątki:Republic of Ireland,Bosnia and HerzegovinaiDemocratic Republic of the Congo. Mają słowo, które nie zaczyna się od wielkich liter. Mogę sobie z tym poradzić, zastępując spację wcześniej znakiem podkreślenia,_który uniemożliwia rozpoznanie jej jako granicy słowa, a następnie zastąpić_spacją. Pozostał wyjątekUSAktóry ma wielkie litery, które nie znajdują się na granicy słowa. W tym celu wprowadzam granice słów, pisząc to jako,u`s`aa następnie usuwam cudzysłowy. Razem daje to:Z tym kodem mogę kodować cały ciąg przy użyciu tylko kraje
a-z,,',-,\n,_i`, co jest 32 różnych znaków. Tak więc każdy znak można zakodować za pomocą 5 bitów. W rzeczywistości, jeśli mam ogromny ciąg bitów11110100111..., mogę przekonwertować go na potrzebne znaki, używając:Jeśli mam ciąg bajtów,
$_to mogę utworzyć ogromny ciąg bitów, którego potrzebuję$_ = unpack"B*". Zasadniczo wszystko to jest mały konwerter od bazy 256 do bazy 32, a każda litera kraju jest kodowana przy użyciu 5 bitów w ciągu przychodzących ciągów krajów binarnych. Jest to stosunkowo kompaktowe i nie ma nic do opracowania specjalnych kodów dla powtarzających się ciągów na liście krajów z jednym wyjątkiem:Republicpojawia się w 5 nazwach krajów. Ponieważ zawsze pojawia się jako pełne słowo i żadna nazwa kraju nie zaczyna się odX(jedyna taka litera), mogę użyć go jako kodu ucieczki po pierwszych literach nazw krajów.Teraz potrzebuję sposobu na zakodowanie relacji „dotyka”. Pierwszą rzeczą, na którą należy zwrócić uwagę, jest to, że jest symetryczna, więc jeśli kraj
$ndotyka kraju$t, to kraj$trównież dotyka kraju$n. Muszę więc zakodować tylko połowę relacji, jeśli wypełnię%touchesskrót w obie strony. W uproszczonym kodzie widać, że robi toTyle że rzeczywisty kod używa
$.zamiast,$nponieważ chcę, aby licznik zaczynał się od 1 zamiast 0 (kraj 0 to pusty ciąg znaków). Chodzi o to, aby napisać sekwencję indeksów krajów,| A, B, C | D, E | ..która mówi, że kraj 1 dotyka krajów z indeksemA,BaCkraj 2 dotyka indeksuDiEitd. W rzeczywistości koduję przesunięcie względem bieżącego kraju (którego później użyję, aby wartości były małe) i tylko dodatnie przesunięcia (zapewnia to, że relacja „dotyka” jest kodowana tylko w jednym kierunku, a metoda, której używam, może i tak nie obsługuje liczb ujemnych). Niektóre kraje mają pustą listę sąsiadów, ponieważ ich relacje dotykowe zostały już podane przez inne kraje. Mogę zmienić listę krajów (której kolejność jest nieistotna) tak, aby znalazły się na końcu listy. Mogę następnie pominąć te kraje z sekwencji. To nic nie zyskuje, ponieważ potrzebuję tyle przesunięć, ile jest relacji „dotykowych”, ale unika się utraty bajtów przez konieczność kodowania zastępczego przesunięcia. Jak wyjaśniono powyżej, kraj 0 jest pustym smoczkiem, więc muszę się upewnić, że zostanie pominięty. Mogę zapisać tę sekwencję liczb jako sekwencję bajtów, w której wartość bajtu odpowiada przesunięciu indeksu. Jednak wciąż muszę wiedzieć, gdzie zaczyna się następny kraj w sekwencji (pozycje|sw powyższym przykładzie). Robię to, ustawiając jakiś wysoki bit na 1 dla pierwszego indeksu na liście zmian danego kraju, a więc dla indeksówAiDw powyższym przykładzie.Jest jednak jeden irytujący problem: istnieje ponad 127 krajów. Więc nie mogę po prostu użyć bitu znaku. Zamiast tego znalazłem taki układ krajów, że każdy kraj nigdy nie jest dalej niż 15 pozycji od wszystkich krajów, których dotyka:
(w momencie pisania tego objaśnienia mój program wyszukiwania znalazł zamówienie, w którym maksymalna odległość wynosi co najwyżej 12). Oznacza to, że mogę użyć
0x10jako flagi do wskazania początku nowego kraju i muszę jedynie zakodować 32 różne wartości. Można to skompresować w celu rozszerzenia za pomocą tego samego konwertera od bazy 256 do bazy 32, jaki był potrzebny na liście krajów. Mogę w rzeczywistości umieścić ciąg dotykowy przed ciągiem kraju z0x00pośrednim (przed kodowaniem), jeśli napiszę dekoder dotykowy, aby na tym skończył\x00. Dekoder kraju jest zapisany tak, że0x00pozostawiony na początku staje się początkową nową linią, której potrzebuję, więc kraj o indeksie 0 jest pustym ciągiem.W starszej wersji kodu wykorzystano fakt, że na wykresie kraju są tylko 4 połączone komponenty, aby obniżyć wskaźniki kraju do poniżej 128, ale było to znacznie skomplikowane i nieco dłuższe w kodzie i łańcuchu kodowym.
Kod do konwertowania sekwencji bajtów na
%touchesskrót następnie staje się:Zauważ, że wszystkie kraje singleton po prostu w ogóle nie są kodowane. Wykorzystane jako dane wejściowe nigdy nie będą pasować, więc
%reachablebędą zawierać tylko odniesienia do początkowego pustego kraju i nic nie zostanie wydrukowane.Dzięki temu cały program jest wyjaśniony. Wszystko, co było potem potrzebne, to napisanie metaprogramu, który generuje olbrzymi zakodowany ciąg, starannie wybierając porządek krajów, tak aby
'(co unieważniłoby końcowy ciąg pojedynczego cudzysłowu)źródło
JavaScript (ES6),
28622324Zwraca obiekt Set zawierający odpowiednie kraje. Pamiętaj, że zawiera on mnóstwo materiałów niedrukowalnych.
Fragment testowy (wymagana przeglądarka zgodna z ES6)
Pokaż fragment kodu
Jak to działa
Przede wszystkim usunąłem z listy wszystkie kraje bez sąsiadów. Następnie zredukowałem listę do tego formatu:
Spowoduje to skrócenie listy do 2130 bajtów. Ostrożnie wstawiono pusty wpis, w którym kraj reprezentowany przez przecinek miałby uniknąć niepowodzenia wyrażenia regularnego. Teraz interesująca część:
źródło
JavaScript (ES6) 2622
3815Funkcja zwracająca zestaw. Skanowanie rekurencyjne przy użyciu zestawu, aby uniknąć powtórzeń.
(Dodano 2 nowe wiersze dla czytelności - powinna to być pojedyncza linia)
Zapożyczenie pomysłu na @ETHProdukty krajów, które nie przechowują krajów bez sąsiadów . (zapożyczając również swoją ortografię, zawsze źle wpisuję to słowo)
Wyjaśnienie
Test
źródło
1/xzamiast+x?” Potem zdałem sobie sprawę, że to sprytny sposób na obejście sprawy0. +1Python 2,
6967696569506906 bajtówNaprawdę, naprawdę mam nadzieję, że wszystko mi się udało. Przykład:
Wkład:
Wydajność:
Mam nadzieję, że pusta linia jest dozwolona.Nigdy więcej pustej linii! Tak!Wyjaśnienie:
Długa linia u góry to dane o nazwie każdego kraju i sąsiednich krajach. Każdy element na liście jest inną listą, której pierwszym elementem jest nazwa kraju, a drugim elementem jest indeks każdego otaczającego go kraju. USA jest pierwszym elementem i zawiera indeksy
1, 2. Element 1 na liście to Kanada, a element 2 na liście to Meksyk. Ta lista została wygenerowana przy użyciu tego programu:...... [duża lista powyżej]
Dane wyjściowe zawierały przecinki, które można usunąć za pomocą bardzo prostego wyrażenia regularnego, które można znaleźć tutaj . Cały program jest dostępny tutaj . Dane wyjściowe to 4736 bajtów, co stanowi około 88% programu.
Oto reszta programu z odpowiednimi nazwami zmiennych, komentarzami i białymi znakami (poprzednia wersja):
źródło
{}dokonuje dyktanda .{x for d in Q[A][1:] if d not in C}iC|=nzamiastfor A in C:pętli.Mathematica, program 128B + dane 2856B = 2984 bajtów
Gdzie
FOOjest łańcuch o długości 2856 bajtów (nie wkleja się tutaj, ponieważ zawiera znaki niedrukowalne i tylko znaki MMA). Ciąg jest skompresowaną listą BZIP2 list, przy czym każda lista wewnętrzna ma formę{Country, Neighbor, Neighbor, ...}. Lista jest już zoptymalizowana do usuwania zbędnych krawędzi.Posiadanie go w formacie wykresu Mathematica pozwala nam robić proste, miłe rzeczy, takie jak:
Aby uzyskać takie rzeczy jak:
źródło
PHP,
5169271626982321 bajtówAktualizacja
To moja druga, bardzo skrócona wersja. Oryginalny post patrz poniżej.
Okazało się to dość szczegółową edycją ...
Usuwanie krajów bez sąsiadów.
Moja pierwotna definicja tablicy miała aż 4901 bajtów - usunięcie wszystkich krajów bez sąsiadów (jak sugerowało @ETHproductions) zmniejszyło to o 725 bajtów do 4176 bajtów. Oczywiście wymaga to dodania dodatkowego kodu logicznego, aby uwzględnić awarię, ale powinno to być pomijalne w porównaniu z tym ogromnym zyskiem.
Używanie znaków zamiast liczb
Moim następnym krokiem było zmniejszenie ilości bajtów potrzebnych do odkodowania odniesień sąsiada. Moim pierwszym pomysłem było porzucenie systemu dziesiętnego i użycie wyższej podstawy do przedstawienia liczb (na przykład baza 36, która użyłaby 0-9 plus az), ale dodatkowa logika potrzebna do ich odkodowania wydawała się dużo. Wybrałem więc coś innego: postacie.
Każdy znak ASCII ma tylko jeden bajt długości i odwzorowuje na dobrze określoną liczbę z zakresu 0..255, co jest dokładnie tym, co byłoby potrzebne. Pominąłem pierwsze 39 znaków ASCII, ponieważ nie można ich wydrukować / dołączyć
'i"które wymagają ucieczki. Wynikowa definicja tablicy miała tylko 2878 bajtów, oszczędzając 1298 bajtów lub 31% w porównaniu z poprzednią. Oczywiście to również wymaga dodatkowej logiki, ale na szczęściechriordsą raczej krótkimi nazwami funkcji :-)Kompresowanie nazw krajów
Te nazwy krajów wciąż zajmowały dużo miejsca, więc postanowiłem sprawdzić, jak je skompresować. Pięć krajów ma w sobie termin „Republika”, więc byłem w stanie zaoszczędzić 16 bajtów, deklarując
$r='Republic'raz, a następnie pisząc"$r of Ireland"itp. To samo dotyczy „Gwinei”, która pojawia się 4 razy.Istnieje również całkiem sporo kombinacji liter, które występują stosunkowo często, ale ponieważ pisanie
$xwciąż składa się z dwóch znaków, zastąpienie ich ma sens tylko w przypadku kombinacji 3+ liter i jeśli naprawdę jest DUŻO, które można zastąpić. Na przykład, zastąpienie wszystkich 10-niasekundTanzaniaitd. Zyskało tylko 1 bajt. To samo z-istan(4x, -1), więcej szczęścia z-land(7x, -4).„Funkcje” PHP
Na szczęście dla golfisty kodu PHP nie ma nic przeciwko, jeśli naruszysz jego zasady składniowe. Tutaj możemy użyć tego do usunięcia niektórych znaków cudzysłowu, zamieniając
'Lesotho'=>'E'(14 bajtów) naLesotho=>E(10 bajtów). Zadziwiająco (lub: szokująco) to nawet działa na dowolny ciąg, który składa się z AZ, 0-9 lub drugiej połowie tabeli ASCII i nie startuje z numerem , dzięki czemu coś takiego jest możliwe:India=>nh¢•Q“.Szkoda jednak, że projektanci tabeli ASCII umieścili interpunkcję między blokami liter, co oznacza, że nie ma ciągłego bloku znaków bez znaczenia dla PHP, aby pomieścić wszystkie 150 krajów na liście. Powoduje to, że wiele ciągów wciąż zachowuje swoje cytaty. Czasami przenosiłem cyfry do tyłu, aby ciąg znaków nie zaczynał się od cyfry.
Ostateczna definicja tablicy
Wszystko to sprowadza definicję tablicy do 2534 bajtów, prawie połowy wartości początkowej. Oczywiście można teraz zoptymalizować kolejność krajów, aby jak najwięcej wpisów mogło stracić swoje cytaty itp., Ale nie chciałem wkładać w to tak wiele wysiłku. ;-)
Kod
Oto druga wersja z dodaną odrobiną dodatkowej logiki:
Grał w golfa
Edycja aktualizacji
Zapisano kolejne 18 bajtów przez:
$r='Republic'itp. (-10)forzwhilepętli (-6)assłowach kluczowych (-2)Zaktualizowałem powyższy kod o zmiany.
Kolejna edycja
Ogolono kolejne 377 bajtów, tworząc najpierw indeksowaną tablicę z implodowanego łańcucha (tworząc wszystkie
=>i"przestarzałe, -417 bajtów narzutu), a następnie przekształcając ją w pożądaną tablicę asocjacyjną (+40 bajtów kodu). Zaktualizowałem powyższy kod ponownie.Początkowy post
To jest dość szybka pierwsza wersja, nie zrobiłem ŻADNEJ kompresji listy oprócz oczywistych liczb dla nazwisk - mógłbym nad tym jutro pracować i edytować mój post.
Moja lista to prosta tablica asocjacyjna z wpisem dla każdego kraju. Klucz tablicy to nazwa kraju i wartość tablicy sąsiadów, do której odwołuje się ich indeks w tej tablicy. PHP nie pozwala na dostęp do tablic asocjacyjnych według indeksu, więc potrzebowałem obejścia przy użyciu
array_keysiarray_valuesfunkcji.Rzeczywisty kod skomentował:
Jak zawsze i wcześniej, wszelkie uwagi są bardzo mile widziane.
źródło
Dyalog APL , program 82 bajty + dane 1924 bajty = 2006 bajtów
Nie zrobiłem nic specjalnego, aby spakować dane poza wykorzystaniem wbudowanej (de-) serialize (
220⌶) i (un-) zip (219⌶) aplikacji APL APL .Gdzie elipsy oznaczają łańcuch zlib'ed z tymi wartościami bajtów:
Zauważ, że zarówno zakodowany ciąg, jak i reszta programu mieści się na 256-znakowej stronie kodowej APL, tj. Jeden symbol na bajt.
Oto, jak to wszystko wygląda po złożeniu (
␀w zastępstwie U + 0000):źródło