Vous êtes-vous déjà demandé quels pays en entourent un autre? Moi aussi, parfois, et, bien, voici le défi à relever.
J'ai fourni une liste de pays et des pays qu'ils touchent que vous devez reconnaître au bas de cet article dans un bloc de code. Vous devez créer un programme complet qui génère (de la manière la plus pratique possible dans votre langue) la liste des couches de pays des pays adjacents vers un pays d'entrée. Ainsi, par exemple:
>>> "United Kingdom" 1
Republic of IrelandParce que "United Kingdom"c'est le nom du pays et 1le nombre de couches que vous souhaitez créer. En fait, n'importe quel nombre de couches (sauf 0) reviendra Republic of Ireland, car il y a une mer sur le chemin pour se rendre dans d'autres pays.
Carte de référence:
Exemples (tout ce qui est entre parenthèses sont des commentaires) (évidemment, l'ordre de sortie n'a pas d'importance):
>>> 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)Parce que le monde est grand, vous devez compenser en rendant votre code petit. C'est du code-golf , après tout.
Toucher la liste (sans ordre particulier, dans un format, espérons-le, analysable) (s'il y a des erreurs ici, faites-le moi savoir . Je l'ai parcouru plusieurs fois, mais je suis obligé d'avoir fait quelques erreurs):
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
la source
la source
%r=map%$_,%r.Réponses:
Perl,
150914961392138913861251124812461241 octetsComprend +2 pour
-naCourez avec le pays et comptez sur STDIN, par exemple
perl -na countries0.pl <<< "The Gambia 4"Fichier
countries.pl:Cela fonctionne tel quel, mais pour obtenir la longueur donnée, tous les octets d'échappement doivent être remplacés par les littéraux correspondants. Vous pouvez par exemple le faire en utilisant:
Explication
Voyons d'abord le programme avec certaines transformations supprimées:
L'idée de base est d'avoir trois infrastructures de données principales:
@countriescontenant tous les pays%touchesd'index dans le@countriestableau tel qu'il$touches{$i}{$j}existe si et seulement si$countries[$i]touche$countries[$j]%reachablequi a une clé pour l'index de chaque pays qui est accessible à la couche actuellement considérée.Alors l'algorithme est:
@countrieset utilisez-le pour initialiser%reachable$rdans%reachableLook Up$touches{$r}et de recueillir toutes les clés que vous y trouverez%reachable. Comme il s'agit d'un hachage, tous les doublons seront supprimés%reachablepour imprimer le pays correspondant dans@countries, mais n'imprimez pas le pays cible d'origineC'est là que la simplicité se termine et que le golf commence.
@countriestableau n'existera jamais avec un nom, bien qu'il soit créé brièvement en mémoire%reachablehachage sera nommé%r%toucheshachage n'existera pas explicitement. Au lieu de cela, j'utilise l'espace de noms global perl. Par exemple, le pays 6 touche le pays 3 et le pays 12 sera représenté dans le hachage%6qui contiendra(3 => undef, 12 => undef)@countries[keys %reachable]mais je ne veux pas écrire lekeyset plutôt le faire@countries[%reachable]. Mais puisque%reachablecontiendra desundefvaleurs qui deviendront l'index 0, je commencerai la liste de pays réelle à l'index 1 et mettrai la chaîne vide à l'index 0. L'impression de cette chaîne vide sera invisible. Je vais également m'assurer que le pays cible est remplacé par une chaîne vide. Et enfin, chaque pays aura toujours une nouvelle ligne à la fin. Savoir tout ce que la sortie finale devient simplementprint @countries[%reachable]. Sauf que les pays à ce stade seront inclus$_, le code réel l'est doncprint+(/$|.+\n/mg)[%r]. Remarquez comment l'expression régulière s'assure que les lignes vides n'obtiennent pas de nouvelle ligne, contrairement aux noms de pays complets.%reachablepeuvent en principe être récupérés en utilisantmap keys %{$touches{$_}},keys %reachable. Mais là encore, cekeysn'est pas nécessaire si je prends soin de gérer correctement les valeurs undef que j'obtiens également sanskeys. Et comme dit précédemment, j'utilise le glob principal pour stocker les valeurs, de sorte que le fragment de code réel estmap%$_,%r. Je veux ajouter chacune des valeurs retournées en tant que nouvelle clé à%rlaquelle peut être fait en tant que%r=map%$_,%r. Cela nécessite cependant que les pays se considèrent comme touchant pour que la couche d'origine reste dans l'ensemble. Ce fragment de code doit être répété autant de fois que l'utilisateur a demandé de couches. Notez que c'est le cœur même du programme, tout le reste est du bruit pour le supporter.-aoption a collecté le nombre de couches en tant que dernier élément,@Fcela peut être accompli en utilisanteval '%r=map%$_,%r;' x pop @F. Ce n'est généralement pas le moyen le plus court de boucler en perl mais cela a l'avantage de ne pas changer$_pendant la boucle, un fait que j'utiliserai plus tard. Mettre le nombre de couches sur sa propre ligne dans STDIN me permettrait de remplacer lex pop@Fenx<>économisant 4 octets, mais je veux rester aussi proche de la spécification que possible.pop @Fsuppression, les couches@Fcontiennent le nom du pays de départ. Notez que les pays avec des espaces à leur nom seront divisés en leurs composants. Nous pouvons trouver la cible dans la chaîne des grands pays$_et remplacer immédiatement le pays cible par la chaîne emty (afin qu'elle ne soit pas imprimée)s/^@F$//m. Notez que les pays avec des espaces dans leur nom sont reconstruits par l'@Finterpolation. Notez également que cela doit être soigneusement ancré car certains pays sont des sous-chaînes d'autres, par exempleGuineaetGuinea-BissauouNigeretNigeria$'=~y/\n//. Si le pays cible n'est pas trouvé,$`il contiendrait une valeur d'une expression régulière précédente qui pourrait être très erronée. Au lieu de cela, nous voulons 0 (à quel index nous avons une chaîne vide). Cela peut être accompli en le combinant avec le match précédent danss/^@F$//m*$`=~y/\n//.%reachable. L'eval devient alorseval '%r=map%$_,%r,%r,s/^@F$//m*$`=~y/\n//;' x pop@F;. Notez que la substitution détruit le pays cible,$_donc seulement elle n'est ajoutée que la première fois (elle ne résoudrait pas si ce n'était pas le cas, car l'indice du pays cible est déjà de%reachabletoute façon)%rnous pouvons combiner cela avecprint+(/$|.+\n/mg)[%r]pour arriver au code réelprint+(/$|.+\n/mg)[eval'%r=map%$_,%r,s/^@F$//m*$`=~y/\n//;'x pop@F]La question suivante est de savoir comment coder le paysan. Comme expliqué ci-dessus, je le veux comme une énorme chaîne avec les pays terminés par la nouvelle ligne et commençant par une seule nouvelle ligne. Pour cela, j'ai besoin de 26 lettres, d'espace, de nouvelle ligne,
-(pourGuinea-Bissau) et'(pourCote D'Ivoire). Le problème est bien sûr que parfois les lettres sont en majuscules. Ceci est facilement résolu en mettant en majuscule la première lettre après une limite de mot. Cependant , il y a des exceptions:Republic of Ireland,Bosnia and HerzegovinaetDemocratic Republic of the Congo. Ceux-ci ont un mot qui ne commence pas par une majuscule. Je peux gérer cela en remplaçant l'espace avant cela par un trait de soulignement_qui l'empêche d'être reconnu comme une limite de mot, puis plus tard, remplacez le_par un espace. L'exception qui reste estUSAqui a des majuscules qui ne sont pas sur une limite de mot. Pour cela, j'introduis des limites de mots en écrivant ceci au furu`s`aet à mesure que je supprime ensuite les citations. Ensemble, cela donne:Avec ce code , je peux encoder toute la chaîne de pays en utilisant seulement
a-z,,',-,\n,_et`, ce qui est de 32 caractères différents. Ainsi, chaque caractère peut être codé avec 5 bits. En fait, si j'ai une énorme chaîne de bits11110100111..., je peux la convertir en caractères nécessaires en utilisant:Si j'ai une chaîne d'octets,
$_l'énorme chaîne de bits dont j'ai besoin peut être créée à l'aide$_ = unpack"B*". Donc, fondamentalement, tout cela est un petit convertisseur de base 256 en base 32 et chaque lettre de pays est codée en utilisant 5 bits dans la chaîne de pays binaire entrante. C'est relativement compact et cela ne sert à rien de développer des codes spéciaux pour les chaînes répétées dans la liste des pays à une exception près:Republicapparaît dans 5 noms de pays. Puisqu'il apparaît toujours comme un mot complet et qu'aucun nom de pays ne commence parX(la seule lettre de ce type), je peux l'utiliser comme code d'échappement après que les premières lettres des noms de pays ont été mises en majuscule.Maintenant, j'ai besoin d'un moyen de coder la relation "touches". La première chose à noter est qu'elle est symétrique, donc si le pays
$ntouche le pays$t, alors le pays$ttouche également le pays$n. Je n'ai donc besoin de coder la moitié des relations que si je remplis le%toucheshachage dans les deux sens. Dans le code simplifié, vous voyez que cela se fait parSauf que le code réel utilise à la
$.place de$nparce que je veux que le compteur démarre à 1 au lieu de 0 (le pays 0 est la chaîne vide factice). L'idée est d'écrire une séquence d'indices de pays| A, B, C | D, E | ..qui dit que le pays 1 touche les pays avec l'indiceA,BetC, le pays 2 touche l'indiceDetEetc. En fait, j'encode l'offset du pays actuel (que j'utiliserai plus tard pour rendre les valeurs petites) et seulement des décalages positifs (cela garantit que la relation "touches" n'est encodée que dans une seule direction, et la méthode que j'utilise peut ne gère pas les nombres négatifs de toute façon). Certains pays ont une liste de voisins vide car leur relation de contact a déjà été donnée par d'autres pays. Je peux réorganiser la liste des pays (dont l'ordre n'est pas pertinent) de telle sorte que ceux-ci viennent à la fin de la liste. Je peux alors omettre ces pays de la séquence. Cela ne sert à rien puisque j'ai besoin d'autant de décalages qu'il y a de relations "tactiles" mais cela évite de perdre des octets en ayant à encoder un décalage factice. Comme expliqué ci-dessus, le pays 0 est une chaîne vide factice, je dois donc m'assurer qu'il est ignoré. Je peux écrire cette séquence de nombres comme une séquence d'octets où la valeur d'octet correspond au décalage d'index. Cependant, je dois encore savoir où commence le prochain pays dans une séquence (les positions du|s dans l'exemple ci-dessus). Je le fais en définissant un bit élevé à 1 pour le premier index dans la liste des touches d'un pays particulier, donc pour les indicesAetDdans l'exemple ci-dessus.Il y a cependant un problème ennuyeux: il y a plus de 127 pays. Je ne peux donc pas simplement utiliser le bit de signe de caractère. Au lieu de cela, j'ai trouvé un arrangement des pays tel que chaque pays n'est jamais plus éloigné que 15 positions de tous les pays qu'il touche:
(au moment où j'écrivais cette explication, mon programme de recherche a en fait trouvé un ordre où la distance maximale est au maximum de 12). Cela signifie que je peux utiliser
0x10comme indicateur pour indiquer le début d'un nouveau pays et je n'ai besoin que de coder 32 valeurs différentes. Cela peut être compressé pour une expansion avec le même convertisseur de base 256 en base 32 que cela était nécessaire pour la liste des pays. Je peux en fait mettre la chaîne tactile avant la chaîne pays avec un0x00entre-deux (avant l'encodage) si j'écris le décodeur tactile pour qu'il s'arrête là\x00. Le décodeur de pays est écrit de telle sorte que ce qui0x00reste au début devienne la nouvelle ligne initiale dont j'ai besoin pour que le pays à l'index 0 soit la chaîne vide.Une ancienne version du code utilisait le fait qu'il n'y avait que 4 composants connectés dans le graphique du pays pour réduire les indices de pays à moins de 128, mais c'était beaucoup plus compliqué et un peu plus long dans le code et la chaîne codée.
Le code pour convertir une séquence d'octets en
%toucheshachage devient alors:Notez que tous les pays singleton ne sont tout simplement pas codés du tout. Utilisés en entrée, ils ne correspondront donc jamais, ils
%reachablene contiendront donc que des références au pays vide initial et rien ne sera imprimé.Avec cela tout le programme est expliqué. Tout ce qui était nécessaire après cela était d'écrire un méta-programme qui génère l'énorme chaîne encodée en choisissant soigneusement l'ordre des pays de telle sorte que
'(ce qui invaliderait la dernière chaîne entre guillemets)la source
JavaScript (ES6),
28622324Renvoie un objet Set contenant les pays appropriés. Notez que cela contient une tonne d'imprimables.
Extrait de test (navigateur compatible ES6 requis)
Afficher l'extrait de code
Comment ça marche
Avant toute chose, j'ai supprimé tous les pays sans voisin de la liste. J'ai ensuite réduit la liste à ce format:
Cela condense la liste à 2130 octets. Une entrée vierge a été soigneusement insérée là où le pays représenté par une virgule serait pour éviter l'échec de l'expression régulière. Maintenant pour la partie intéressante:
la source
JavaScript (ES6) 2622
3815Une fonction renvoyant un ensemble. Balayage récursif utilisant un ensemble pour éviter les répétitions.
(2 nouvelles lignes ajoutées pour plus de lisibilité - il devrait s'agir d'une seule ligne)
Emprunter l'idée de @ETHproductions de ne pas stocker de pays sans voisins . (empruntant aussi son orthographe, j'épelle toujours mal ce mot)
Explication
Tester
la source
1/xau lieu de+x?" Ensuite, j'ai réalisé que c'était une façon intelligente de contourner l'affaire0. +1Python 2,
6967696569506906 octetsJ'espère vraiment, vraiment que j'ai tout bien fait. Exemple:
Contribution:
Sortie:
J'espère que la ligne vide est autorisée.Plus de ligne vide! Yay!Explication:
La longue ligne en haut représente les données sur le nom de chaque pays et les pays environnants. Chaque élément de la liste est une autre liste, dont le premier élément est le nom du pays et l'autre élément est l'index de chaque pays qui l'entoure. USA est le premier élément et contient les index
1, 2. L'élément 1 de la liste est le Canada et l'élément 2 de la liste est le Mexique. Cette liste a été générée à l'aide de ce programme:...... [la grande liste ci-dessus]
La sortie contenait des virgules qui pouvaient être supprimées par une Regex très simple, que vous pouvez trouver ici . Le programme complet est disponible ici . La sortie est de 4 736 octets, soit environ 88% du programme.
Voici le reste du programme avec les noms de variables, les commentaires et les espaces appropriés (version précédente):
la source
{}fait malheureusement un dicton .{x for d in Q[A][1:] if d not in C}etC|=nau lieu de lafor A in C:boucle.Mathematica, programme 128B + données 2856B = 2984 octets
Où
FOOest une chaîne de 2856 octets (non collée ici car elle contient des caractères non imprimables et MMA uniquement). La chaîne est une liste de listes compressée par BZIP2, où chaque liste interne a la forme{Country, Neighbor, Neighbor, ...}. La liste est déjà optimisée pour supprimer les bords redondants.Le faire au format graphique de Mathematica nous permet de faire de belles choses faciles comme ceci:
Pour obtenir des choses comme:
la source
PHP,
5169271626982321 octetsMise à jour
Ceci est ma deuxième version extrêmement raccourcie. Message d'origine voir ci-dessous.
Cela s'est avéré devenir un montage assez détaillé ...
Suppression de pays sans voisins.
Ma définition d'origine du tableau était longue de 4901 octets - la suppression de tous les pays sans voisins (comme l'a suggéré @ETHproductions) a réduit cela de 725 octets à 4176 octets. Bien sûr, cela nécessite un code logique supplémentaire pour répondre à la solution de repli, mais cela devrait être négligeable par rapport à cet énorme gain.
Utilisation de caractères au lieu de nombres
Ma prochaine étape consistait à réduire la quantité d'octets nécessaires pour décoder les références voisines. Ma première idée a été d'abandonner le système décimal et d'utiliser une base plus élevée pour représenter les nombres (par exemple la base 36 qui utiliserait 0-9 plus az), mais la logique supplémentaire nécessaire pour les décoder semblait beaucoup. J'ai donc opté pour autre chose: des personnages.
Chaque caractère ASCII ne fait qu'un octet de long et correspond à un nombre bien défini de la plage 0..255, ce qui est exactement ce qui serait nécessaire. J'ai sauté les 39 premiers caractères ASCII car ils ne sont pas imprimables / incluent
'et"qui auraient besoin d'être échappés. La définition de tableau résultante ne faisait que 2878 octets de long, économisant 1298 octets ou 31% par rapport à la précédente. Bien sûr, cela nécessite également une logique supplémentaire, mais heureusementchretordsont des noms de fonction plutôt courts :-)Compression des noms de pays
Cependant, ces noms de pays occupaient encore beaucoup d'espace, alors j'ai décidé de voir comment je pouvais les compresser. Cinq pays ont le terme "République" en eux, donc j'ai pu économiser 16 octets en déclarant
$r='Republic'une fois puis en écrivant"$r of Ireland"etc. Il en va de même pour "Guinée", qui apparaît 4 fois.Il existe également un certain nombre de combinaisons de lettres qui se produisent relativement souvent, mais comme la saisie
$xest toujours de deux caractères, leur remplacement n'a de sens que pour les combinaisons de 3+ lettres et s'il y a vraiment un LOT qui peut être remplacé. Par exemple, le remplacement des 10-nias dansTanzaniaetc. n'a gagné qu'un octet. Idem avec-istan(4x, -1), plus de chance avec-land(7x, -4)."Fonctionnalités" PHP
Heureusement pour le golfeur de code, PHP ne dérange pas trop lorsque vous violez ses règles de syntaxe. Ici, nous pouvons utiliser cela pour supprimer certains guillemets, transformant
'Lesotho'=>'E'(14 octets) enLesotho=>E(10 octets). Étonnamment (ou: choquant?), Cela fonctionne même pour toute chaîne composée de AZ, 0-9 ou de la seconde moitié de la table ASCII et ne commence pas par un nombre , ce qui rend quelque chose comme CELA possible:India=>nh¢•Q“.Cependant, il est dommage que les concepteurs de la table ASCII aient mis la ponctuation entre les blocs de lettres, ce qui signifie qu'il n'y a pas de bloc continu de caractères sans signification PHP pour accueillir les 150 pays de la liste. Il en résulte que de nombreuses chaînes conservent toujours leurs guillemets. Parfois, je déplaçais des nombres vers l'arrière pour que la chaîne ne commence pas par un chiffre.
Définition finale du tableau
Tout cela ramène la définition du tableau à 2534 octets, soit près de la moitié de la valeur initiale. Bien sûr, on pourrait maintenant aller et optimiser l'ordre des pays afin que le plus grand nombre possible d'entrées puissent perdre leurs devis, etc., mais je ne voulais pas y mettre beaucoup d'efforts. ;-)
Code
La voici donc, la deuxième version, avec un peu de logique supplémentaire ajoutée:
Golfé
Edition de la mise à jour
Enregistré encore 18 octets par:
$r='Republic'etc. (-10)forparwhileboucle (-6)asmots clés (-2)J'ai mis à jour le code ci-dessus avec les modifications.
Un autre montage
Réduit encore 377 octets en créant d'abord un tableau indexé à partir d'une chaîne implosée (rendant tout
=>et"obsolète, -417 octets de surcharge) et en le transformant ensuite en tableau associatif souhaité (+40 octets de code). Mis à jour le code ci-dessus à nouveau.Poste initial
Ceci est une première version assez rapide, je n'ai encore effectué AUCUNE compression de liste en dehors des nombres évidents pour les noms - je pourrais y travailler demain et éditer mon message.
Ma liste est un simple tableau associatif avec une entrée pour chaque pays. La clé du tableau est le nom du pays et la valeur d'un tableau de ses voisins, référencé par leur index dans ce tableau. PHP ne vous permettra pas d'accéder aux tableaux associatifs par index, j'ai donc eu besoin d'une solution de contournement à l'aide des fonctions
array_keysetarray_values.Le code réel a commenté:
Comme avant et toujours, toute remarque est très appréciée.
la source
Dyalog APL , programme de 82 octets + données de 1924 octets = 2006 octets
Je n'ai rien fait de spécial pour emballer les données au-delà de l'utilisation de (dé-) serialize (
220⌶) et (un-) zip (219⌶) de Dyalog APL .Où les ellipses représentent une chaîne zlib'ed avec ces valeurs d'octet:
Notez que la chaîne codée et le reste du programme tiennent dans la page de code de 256 caractères d'APL, c'est-à-dire un symbole par octet.
Voici à quoi tout cela ressemble une fois assemblés (en
␀remplacement de U + 0000):la source