Haben Sie sich jemals gefragt, welche Länder ein anderes umgeben? Das tue ich manchmal auch und hier ist die Herausforderung dafür.
Ich habe eine Liste der Länder und der Länder, die sie berühren, bereitgestellt, die Sie am Ende dieses Beitrags in einem Codeblock erkennen müssen. Sie müssen ein vollständiges Programm erstellen, das die Liste der Länderebenen benachbarter Länder (auf die in Ihrer Sprache bequemste Weise) an ein Eingabeland ausgibt. Also zum Beispiel:
>>> "United Kingdom" 1
Republic of IrelandDenn "United Kingdom"ist der Ländername und 1die Anzahl der Ebenen, die Sie erstellen möchten. Tatsächlich wird eine beliebige Anzahl von Schichten (außer 0) zurückkehren Republic of Ireland, da ein Meer im Weg ist, um in andere Länder zu gelangen.
Referenzkarte:
Beispiele (alles in Klammern sind Kommentare) (natürlich spielt die Reihenfolge der Ausgabe keine Rolle):
>>> 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)Weil die Welt groß ist, müssen Sie dies kompensieren, indem Sie Ihren Code klein machen. Das ist schließlich Code-Golf .
Berührungsliste (in keiner bestimmten Reihenfolge, in hoffentlich einem analysierbaren Format) (wenn es Fehler hier gibt, lassen Sie es mich bitte wissen . Ich habe es viele Male durchgearbeitet , aber ich muss ein paar Fehler gemacht haben):
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
quelle
quelle
%r=map%$_,%r.Antworten:
Perl,
1509,1496,1392,1389,1386,1251,1248,1246,1241 BytesBeinhaltet +2 für
-naLaufen Sie mit dem Land und der Zählung auf STDIN, zB
perl -na countries0.pl <<< "The Gambia 4"Datei
countries.pl:Dies funktioniert so wie es ist, aber um die angegebene Länge zu erhalten, müssen alle maskierten Bytes durch die entsprechenden Literalen ersetzt werden. Das können Sie zB machen mit:
Erläuterung
Lassen Sie uns zuerst das Programm anzeigen, wobei einige Transformationen entfernt wurden:
Die Grundidee besteht darin, drei Hauptdatenstrukturen zu haben:
@countriesdas alle Länder enthält%touchesvon Indizes im@countriesArray, der$touches{$i}{$j}genau dann vorhanden ist, wenn er$countries[$i]berührt wird$countries[$j]%reachableder einen Schlüssel für den Index jedes Landes enthält, der auf der aktuell betrachteten Ebene erreichbar ist.Dann ist der Algorithmus:
@countriesund verwenden Sie diesen zum Initialisieren%reachable$rin%reachablesuchen$touches{$r}und sammeln Sie alle Schlüssel, die Sie dort finden%reachable. Da dies ein Hash ist, werden alle Duplikate gelöscht%reachable, um das entsprechende Land in zu drucken, drucken Sie@countriesjedoch nicht das ursprüngliche Zielland ausHier hört die Einfachheit auf und das Golfen beginnt.
@countriesArray wird niemals mit einem Namen existieren, obwohl es kurz im Speicher erstellt wird%reachableHash wird benannt%r%touchesHash wird nicht explizit existieren. Stattdessen verwende ich den globalen Namespace von Perl. Beispiel: Land 6 berührt Land 3 und Land 12 wird in dem Hash dargestellt,%6der enthalten sein wird(3 => undef, 12 => undef)@countries[keys %reachable]aber ich möchte nicht schreibenkeysund stattdessen tun@countries[%reachable]. Da%reachablejedochundefWerte enthalten werden, die Index 0 werden, beginne ich die aktuelle Länderliste bei Index 1 und setze die leere Zeichenfolge bei Index 0. Das Drucken dieser leeren Zeichenfolge ist unsichtbar. Ich werde auch sicherstellen, dass das Zielland durch eine leere Zeichenfolge ersetzt wird. Und schließlich wird jedes Land am Ende noch eine neue Zeile haben. Zu wissen, dass die endgültige Ausgabe einfach wirdprint @countries[%reachable]. Abgesehen davon, dass sich die Länder zu diesem Zeitpunkt in befinden$_, lautet der tatsächliche Codeprint+(/$|.+\n/mg)[%r]. Beachten Sie, wie der reguläre Ausdruck sicherstellt, dass leere Zeilen keine neuen Zeilen erhalten, vollständige Ländernamen jedoch.%reachablekönnen grundsätzlich mit abgerufen werdenmap keys %{$touches{$_}},keys %reachable. Aber auch daskeyswird nicht benötigt, wenn ich darauf achte, die undef-Werte, die ich auch ohne das bekomme, richtig zu behandelnkeys. Und wie gesagt, bevor ich den Haupt-Glob zum Speichern der Werte verwende, ist das eigentliche Codefragmentmap%$_,%r. Ich möchte jeden der zurückgegebenen Werte als neuen Schlüssel hinzufügen, zu%rdem getan werden kann als%r=map%$_,%r. Dies erfordert jedoch, dass die Länder sich selbst als berührend bezeichnen, damit die Ursprungsschicht in der Menge bleibt. Dieses Codefragment muss so oft wiederholt werden, wie der Benutzer Ebenen angefordert hat. Beachten Sie, dass dies der eigentliche Kern des Programms ist. Alles andere ist Rauschen, um dies zu unterstützen.-aOption die Anzahl der Ebenen als letztes Element@Ferfasst hat, kann dies mit erreicht werdeneval '%r=map%$_,%r;' x pop @F. Dies ist im Allgemeinen nicht der kürzeste Weg, um eine Perl-Schleife zu erstellen, aber es hat den Vorteil, dass es sich$_während der Schleife nicht ändert , eine Tatsache, die ich später verwenden werde. Wenn ich die Anzahl der Schichten in STDIN in eine eigene Zeile setze, ersetze ich diex pop@Fdurchx<>Einsparung von 4 Bytes, aber ich möchte so nah wie möglich an der Spezifikation bleiben.pop @FEntfernen@Fenthält der Layer den Namen des Startlandes. Beachten Sie, dass Länder mit Leerzeichen im Namen in ihre Bestandteile aufgeteilt werden. Wir können das Ziel in der großen$_Länderzeichenfolge in finden und das Zielland sofort durch die leere Zeichenfolge ersetzen (damit es nicht gedruckt wird), indem wir tuns/^@F$//m. Beachten Sie, dass Länder mit Leerzeichen im Namen durch die@FInterpolation rekonstruiert werden . Beachten Sie auch, dass dies sorgfältig verankert werden muss, da einige Länder Teilzeichenfolgen anderer Länder sind, z. B.GuineaundGuinea-BissauoderNigerundNigeria$'=~y/\n//. Wenn das Zielland nicht gefunden wird,$`würde es einen Wert aus einer früheren regulären Ausdrucksweise enthalten, der sehr falsch sein könnte. Stattdessen wollen wir 0 (bei welchem Index haben wir eine leere Zeichenfolge). Dies kann erreicht werden, indem es mit dem vorherigen Match in kombiniert wirds/^@F$//m*$`=~y/\n//.%reachable. Das eval wird danneval '%r=map%$_,%r,%r,s/^@F$//m*$`=~y/\n//;' x pop@F;. Beachten Sie, dass die Substitution das Zielland zerstört,$_sodass sie nur beim ersten Hinzufügen hinzugefügt wird (dies würde jedoch nicht stören, da der Ziellandindex bereits%reachablevorhanden ist).%rwir dies kombinierenprint+(/$|.+\n/mg)[%r], um den eigentlichen Code zu erhaltenprint+(/$|.+\n/mg)[eval'%r=map%$_,%r,s/^@F$//m*$`=~y/\n//;'x pop@F]Die nächste Frage ist, wie man die Country-Liste verschlüsselt. Wie oben erklärt, möchte ich, dass es sich um eine riesige Zeichenfolge handelt, bei der die Länder durch eine neue Zeile abgeschlossen werden und mit einer einzelnen neuen Zeile beginnen. Dafür benötige ich 26 Buchstaben, Leerzeichen, Zeilenvorschub,
-(fürGuinea-Bissau) und'(fürCote D'Ivoire). Das Problem ist natürlich, dass die Buchstaben manchmal in Großbuchstaben geschrieben sind. Dies lässt sich leicht lösen, indem der erste Buchstabe nach einer Wortgrenze groß geschrieben wird. Allerdings gibt es Ausnahmen:Republic of Ireland,Bosnia and HerzegovinaundDemocratic Republic of the Congo. Diese haben ein Wort, das nicht mit Großbuchstaben beginnt. Ich kann damit umgehen, indem ich das Leerzeichen davor durch einen Unterstrich ersetze, der verhindert, dass_es als Wortgrenze erkannt wird, und später das_durch ein Leerzeichen ersetze . Die Ausnahme, die übrig bleibt, istUSADas hat Großbuchstaben, die sich nicht an einer Wortgrenze befinden. Dazu füge ich Wortgrenzen ein, indem ich dies schreibeu`s`aund später die Anführungszeichen entferne. Zusammen ergibt das:Mit diesem Code kann ich den ganzen Länder Zeichenfolge kodieren nur mit
a-z,,',-,\n,_und`, die 32 verschiedene Zeichen sind. So kann jedes Zeichen mit 5 Bits codiert werden. Tatsächlich kann ich eine riesige Bitfolge11110100111...in die benötigten Zeichen konvertieren, indem ich Folgendes verwende:Wenn ich einen Byte-String habe, kann
$_der riesige Bitstring, den ich benötige, mit erstellt werden$_ = unpack"B*". Im Grunde genommen ist dies alles ein kleiner Konverter von Basis 256 zu Basis 32, und jeder Länderbuchstabe wird unter Verwendung von 5 Bits in der eingehenden binären Länderkette codiert. Dies ist relativ kompakt und es bringt nichts, spezielle Codes für wiederholte Zeichenfolgen in der Länderliste zu entwickeln, mit einer Ausnahme:RepublicErscheint in 5 Ländernamen. Da es sich immer um ein vollständiges Wort handelt und kein Ländername mitX(dem einzigen Buchstaben) beginnt, kann ich dieses Wort als Escape-Code verwenden, nachdem die ersten Buchstaben der Ländernamen in Großbuchstaben geschrieben wurden.Jetzt brauche ich eine Möglichkeit, die Beziehung "Berührungen" zu codieren. Das Erste, was zu bemerken ist, ist, dass es symmetrisch ist. Wenn also Land Land
$nberührt$t,$tberührt Land auch Land$n. Ich muss also nur die Hälfte der Beziehungen verschlüsseln, wenn ich den%touchesHash auf beide Arten ausfülle . Im vereinfachten Code sehen Sie, dass dies von ausgeführt wirdAußer , dass die tatsächlichen Code Verwendungen
$.statt ,$nweil ich die Zähler will bei 1 starten anstelle von 0 (Land 0 ist die Dummy - leere Zeichenkette). Die Idee ist , eine Folge von Länderindizes zu schreiben ,| A, B, C | D, E | ..das Land 1 berühren Länder mit dem Index sagtA,BundC, Land 2 berührt IndexDundEusw. Tatsächlich codiere ich den Versatz aus dem aktuellen Land (den ich später verwenden werde, um die Werte klein zu machen) und nur positive Versätze (dies stellt sicher, dass die "Berührungs" -Beziehung nur in eine Richtung codiert wird, und die von mir verwendete Methode kann negative Zahlen sowieso nicht behandeln). Einige Länder haben eine leere Liste von Nachbarn, da ihre Kontaktbeziehung bereits von anderen Ländern angegeben wurde. Ich kann die Länderliste (deren Reihenfolge irrelevant ist) so ändern, dass sie am Ende der Liste steht. Ich kann diese Länder dann in der Sequenz weglassen. Das bringt nichts, da ich so viele Offsets benötige, wie es "Touch" -Relationen gibt, aber es vermeidet den Verlust von Bytes, indem ein Dummy-Offset codiert werden muss. Wie oben erklärt, ist country 0 eine leere Dummy-Zeichenfolge, daher muss sichergestellt werden, dass sie übersprungen wird. Ich kann diese Folge von Zahlen als Folge von Bytes schreiben, wobei der Bytewert dem Indexoffset entspricht. Ich muss jedoch noch wissen, wo das nächste Land in einer Sequenz beginnt (die Positionen der|s im obigen Beispiel). Dazu setze ich für den ersten Index in der Kontaktliste eines bestimmten Landes ein hohes Bit auf 1, also für IndizesAundDim obigen Beispiel.Es gibt jedoch ein ärgerliches Problem: Es gibt mehr als 127 Länder. Ich kann also nicht einfach das Vorzeichen-Bit verwenden. Stattdessen habe ich eine Anordnung der Länder gefunden, bei der jedes Land nie weiter als 15 Positionen von allen Ländern entfernt ist, die es berührt:
(Zu der Zeit, als ich diese Erklärung schrieb, fand mein Suchprogramm tatsächlich eine Reihenfolge, in der der maximale Abstand höchstens 12 beträgt.) Dies bedeutet, dass ich
0x10als Flagge den Beginn eines neuen Landes angeben kann und nur 32 verschiedene Werte codieren muss. Dies kann zur Erweiterung mit demselben Konverter von Basis 256 zu Basis 32 komprimiert werden, der für die Länderliste benötigt wurde. Tatsächlich kann ich die Touch-Zeichenfolge vor der Country-Zeichenfolge mit einem0x00Zwischenzeichen (vor der Codierung) setzen, wenn ich den Touch-Decoder schreibe, sodass er an dieser Stelle stoppt\x00. Der Country-Decoder ist so geschrieben, dass der0x00am Anfang verbleibende Code die benötigte neue Zeile darstellt, sodass das Land mit dem Index 0 der leere String ist.Eine ältere Version des Codes verwendete die Tatsache, dass es nur 4 verbundene Komponenten im Länderdiagramm gibt, um die Länderindizes auf unter 128 zu reduzieren, aber das war sehr kompliziert und im Code und in der codierten Zeichenfolge viel länger.
Der Code zum Konvertieren einer Bytefolge in den
%touchesHash lautet dann:Beachten Sie, dass nicht alle Singleton-Länder codiert sind. Als Eingabe verwendet, stimmen sie daher nie überein. Sie
%reachableenthalten lediglich Verweise auf das ursprüngliche leere Land, und es wird nichts gedruckt.Damit ist das ganze Programm erklärt. Alles, was danach benötigt wurde, war ein Metaprogramm zu schreiben, das die riesige codierte Zeichenkette erzeugt, indem die Reihenfolge der Länder sorgfältig so gewählt wird, dass
'(was die endgültige Zeichenfolge in einfachen Anführungszeichen ungültig machen würde).quelle
JavaScript (ES6),
28622324Gibt ein Set-Objekt zurück, das die richtigen Länder enthält. Beachten Sie, dass dies eine Menge nicht druckbarer Dateien enthält.
Test-Snippet (ES6-kompatibler Browser erforderlich)
Code-Snippet anzeigen
Wie es funktioniert
Vor allem habe ich alle Länder ohne Nachbarn von der Liste gestrichen. Dann habe ich die Liste auf dieses Format reduziert:
Dies komprimiert die Liste auf 2130 Bytes. Es wurde sorgfältig ein leerer Eintrag eingefügt, in dem das Land, das durch ein Komma dargestellt wird, Regex-Fehler vermeiden soll. Nun zum interessanten Teil:
quelle
JavaScript (ES6) 2622
3815Eine Funktion, die einen Satz zurückgibt. Rekursiver Scan mit einem Satz, um Wiederholungen zu vermeiden.
(2 neue Zeilen zur besseren Lesbarkeit hinzugefügt - es sollte eine einzelne Zeile sein)
Entlehnung der Idee von @ETHproductions, keine Länder ohne Nachbarn zu speichern . (leiht sich auch seine Rechtschreibung aus, ich schreibe das Wort immer falsch)
Erläuterung
Prüfung
quelle
1/xstatt+x?" Dann wurde mir klar, dass dies ein kluger Weg ist, um den Fall zu umgehen0. +1Python 2,
6967696569506906 BytesIch hoffe wirklich, dass ich alles richtig gemacht habe. Beispiel:
Eingang:
Ausgabe:
Ich hoffe die Leerzeile ist erlaubt.Keine Leerzeile mehr! Yay!Erläuterung:
Die lange Linie oben enthält Daten zum Namen jedes Landes und zu den umliegenden Ländern. Jedes Element in der Liste ist eine andere Liste, deren erstes Element der Name des Landes ist, und das andere Element ist der Index jedes Landes, das es umgibt. USA ist das erste Element und enthält die Indizes
1, 2. Element 1 in der Liste ist Kanada und Element 2 in der Liste ist Mexiko. Diese Liste wurde mit diesem Programm erstellt:...... [die große Liste oben]
Die Ausgabe enthielt Kommas, die durch einen sehr einfachen Regex entfernt werden konnten, der hier zu finden ist . Das gesamte Programm finden Sie hier . Die Ausgabe ist 4.736 Bytes, etwa 88% des Programms.
Hier ist der Rest des Programms mit korrekten Variablennamen, Kommentaren und Leerzeichen (vorherige Version):
quelle
{}macht leider ein Diktat .{x for d in Q[A][1:] if d not in C}undC|=nanstelle derfor A in C:Schleife.Mathematica, 128B Programm + 2856B Daten = 2984 Bytes
Wo
FOOist eine 2856-Byte-Zeichenfolge (hier nicht eingefügt, da sie nicht druckbare Zeichen und MMA-Zeichen enthält). Die Zeichenfolge ist eine BZIP2-komprimierte Liste von Listen, wobei jede innere Liste die Form hat{Country, Neighbor, Neighbor, ...}. Die Liste ist bereits optimiert, um redundante Kanten zu entfernen.Wenn wir es im Grafikformat von Mathematica haben, können wir ganz einfach nette Dinge tun:
Um Dinge zu bekommen wie:
quelle
PHP,
5169271626982321 BytesAktualisieren
Dies ist meine zweite, extrem verkürzte Version. Ursprünglicher Beitrag siehe unten.
Es stellte sich heraus, dass dies eine ziemlich detaillierte Bearbeitung wurde ...
Länder ohne Nachbarn entfernen.
Meine ursprüngliche Array-Definition war satte 4901 Byte lang - durch Entfernen aller Länder ohne Nachbarn (wie von @ETHproductions vorgeschlagen) wurde diese um 725 Byte auf 4176 Byte reduziert. Natürlich muss dazu ein zusätzlicher Logikcode hinzugefügt werden, um den Fallback zu berücksichtigen, aber das sollte im Vergleich zu diesem enormen Gewinn vernachlässigbar sein.
Verwenden Sie Zeichen anstelle von Zahlen
Mein nächster Schritt bestand darin, die Anzahl der zum Dekodieren der Nachbarreferenzen benötigten Bytes zu verringern. Meine erste Idee war, das Dezimalsystem aufzuheben und eine höhere Basis für die Darstellung der Zahlen zu verwenden (zum Beispiel Basis 36, die 0-9 plus az verwendet), aber die zusätzliche Logik, die zum Dekodieren dieser Zahlen erforderlich ist, schien sehr viel zu sein. Also habe ich mich für etwas anderes entschieden: Charaktere.
Jedes ASCII-Zeichen ist nur ein Byte lang und wird auf eine genau definierte Zahl im Bereich 0..255 abgebildet. Dies ist genau das, was benötigt würde. Ich übersprang die ersten 39 ASCII - Zeichen , wie sie sind nicht druckbare / umfassen
'und"wäre. Die resultierende Array-Definition war nur 2878 Bytes lang und sparte 1298 Bytes oder 31% im Vergleich zur vorherigen. Natürlich braucht auch dies zusätzliche Logik, aber zum Glückchrundordsind eher kurze Funktionsnamen :-)Komprimieren von Ländernamen
Diese Ländernamen nahmen jedoch immer noch viel Platz ein, sodass ich mich entschied, zu prüfen, wie ich sie komprimieren könnte. Fünf Länder tragen den Begriff "Republik", so dass ich 16 Bytes einsparen konnte, indem ich
$r='Republic'einmal deklarierte und dann schrieb"$r of Ireland"usw. Das gleiche gilt für "Guinea", das viermal vorkommt.Es gibt auch einige Buchstabenkombinationen, die relativ häufig vorkommen, aber da die Eingabe
$ximmer noch aus zwei Zeichen besteht, ist das Ersetzen dieser nur bei Kombinationen mit mehr als 3 Buchstaben sinnvoll und wenn es wirklich eine LOT gibt, die ersetzt werden kann. Zum Beispiel hat das Ersetzen aller 10-nias inTanzaniausw. nur 1 Byte gewonnen. Gleiches gilt für-istan(4x, -1), mehr Glück für-land(7x, -4).PHP "Funktionen"
Zum Glück für den Code-Golfer macht es PHP nichts aus, wenn Sie seine Syntaxregeln verletzen. Hier können wir dies verwenden, um einige Anführungszeichen zu entfernen und
'Lesotho'=>'E'(14 Bytes) inLesotho=>E(10 Bytes) umzuwandeln. Erstaunlicherweise (oder: schockierend?) Funktioniert dies sogar für alle Zeichenfolgen, die aus AZ, 0-9 oder der zweiten Hälfte der ASCII-Tabelle bestehen und nicht mit einer Zahl beginnen. Dies ermöglicht Folgendes:India=>nh¢•Q“.Es ist jedoch schade, dass die Designer der ASCII-Tabelle Interpunktionszeichen zwischen die Buchstabenblöcke setzen, was bedeutet, dass es keinen fortlaufenden Block von PHP-bedeutungslosen Zeichen gibt, der alle 150 Länder in der Liste aufnehmen kann. Dies führt dazu, dass viele Zeichenfolgen ihre Anführungszeichen beibehalten. Gelegentlich habe ich Zahlen nach hinten verschoben, damit die Zeichenfolge nicht mit einer Ziffer beginnt.
Endgültige Array-Definition
All dies reduziert die Array-Definition auf 2534 Bytes, fast die Hälfte des Anfangswerts. Natürlich könnte man jetzt die Reihenfolge der Länder optimieren, so dass so viele Einträge wie möglich ihre Zitate usw. verlieren können, aber ich wollte DIESEN großen Aufwand nicht darauf verwenden. ;-)
Code
Also hier ist es, die zweite Version, mit ein bisschen zusätzlicher Logik:
Golf gespielt
Bearbeiten Sie das Update
Weitere 18 Bytes gespeichert von:
$r='Republic'usw. (-10)fordurchwhileSchleife (-6)asSchlüsselwörtern entfernen (-2)Ich habe den obigen Code mit den Änderungen aktualisiert.
Noch eine Bearbeitung
Abrasiert weitere 377 Bytes , die durch ein indiziertes Array aus einem implodierten String zu schaffen ersten (so dass alle
=>und"überholt, -417 Byte Overhead) und Drehen, die in denen wollten anschließend assoziative Array (+40 Byte - Code). Den obigen Code erneut aktualisiert.Erster Beitrag
Dies ist eine recht schnelle erste Version, ich habe noch KEINE Listenkomprimierung außer den offensichtlichen Nummern für Namen durchgeführt - ich könnte morgen daran arbeiten und meinen Beitrag dann bearbeiten.
Meine Liste ist ein einfaches assoziatives Array mit einem Eintrag für jedes Land. Der Array-Schlüssel ist der Name des Landes und der Wert eines Arrays seiner Nachbarn, auf das durch den Index in diesem Array verwiesen wird. Mit PHP können Sie nicht über den Index auf assoziative Arrays zugreifen. Daher brauchte ich eine Problemumgehung mit
array_keysundarray_values-Funktionen.Der eigentliche Code kommentiert:
Wie immer sind alle Anmerkungen sehr willkommen.
quelle
Dyalog APL , 82 Bytes Programm + 1924 Bytes Daten = 2006 Bytes
Ich habe nichts Besonderes getan, um die Daten zu packen, außer mit Dyalog APLs integriertem (De-) Serialize (
220⌶) und (Un-) Zip ().219⌶) zu verwenden.Wo die Ellipsen für eine zlib-Zeichenfolge mit diesen Bytewerten stehen:
Beachten Sie, dass sowohl die codierte Zeichenfolge als auch der Rest des Programms in die 256-Zeichen-Codepage von APL passen, dh ein Symbol pro Byte.
So sieht alles aus, wenn man es zusammensetzt (
␀steht für U + 0000):quelle