¿Alguna vez se preguntó qué países rodean a otros? Yo también, a veces, y, bueno, aquí está el desafío.
He proporcionado una lista de países y los países que tocan que debe reconocer al final de esta publicación en un bloque de código. Debe crear un programa completo que genere (de la manera más conveniente posible en su idioma) la lista de capas de países de países adyacentes a un país de entrada. Así por ejemplo:
>>> "United Kingdom" 1
Republic of IrelandPorque "United Kingdom"es el nombre del país y 1la cantidad de capas que desea crear. De hecho, cualquier número de capas (excepto 0) volverá Republic of Ireland, porque hay un mar en el camino para llegar a otros países.
Mapa de referencia:
Ejemplos (cualquier cosa entre paréntesis son comentarios) (obviamente, el orden de salida no importa):
>>> 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)Como el mundo es grande, debes compensarlo haciendo pequeño tu código. Este es el código de golf , después de todo.
Touching List (sin ningún orden en particular, ojalá en un formato analizable) (si hay errores aquí, por favor avíseme . Lo he pasado muchas veces, pero estoy obligado a haber cometido algunos errores):
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
fuente
fuente
%r=map%$_,%r.Respuestas:
Perl,
150914961392138913861251124812461241 bytesIncluye +2 para
-naEjecutar con el país y contar con STDIN, p. Ej.
perl -na countries0.pl <<< "The Gambia 4"Archivo
countries.pl:Esto funciona como está, pero para obtener la longitud dada, todos los bytes escapados deben ser reemplazados por los literales correspondientes. Puede hacerlo, por ejemplo, usando:
Explicación
Primero visualicemos el programa con algunas transformaciones eliminadas:
La idea básica es tener tres estructuras de datos principales:
@countriescontiene todos los países.%touchesde dos niveles de índices en la@countriesmatriz tal que$touches{$i}{$j}existe si y solo si$countries[$i]toca$countries[$j]%reachableque tiene una clave para el índice de cada país al que se puede acceder en la capa que se está considerando actualmente.Entonces el algoritmo es:
@countriesy úselo para inicializar%reachable$ren%reachablebuscar$touches{$r}y recoger todas las llaves que encuentre allí%reachable. Como se trata de un hash, se eliminarán los duplicados.%reachablepara imprimir el país correspondiente@countries, pero no imprima el país de destino originalAquí es donde termina la simplicidad y comienza el golf.
@countriesmatriz nunca existirá con un nombre, aunque se crea brevemente en la memoria%reachablehash será nombrado%r%toucheshash no existirá explícitamente. En cambio, uso el espacio de nombres global perl. Por ejemplo, ese país 6 toca el país 3 y el país 12 estará representado en el hash%6que contendrá(3 => undef, 12 => undef)@countries[keys %reachable]pero no quiero escribir elkeysy en su lugar lo hago@countries[%reachable]. Pero como%reachablecontendráundefvalores que se convertirán en el índice 0, comenzaré la lista de países real en el índice 1 y colocaré la cadena vacía en el índice 0. Imprimir esa cadena vacía será invisible. También me aseguraré de que el país objetivo sea reemplazado por una cadena vacía. Y finalmente cada país tendrá una nueva línea al final. Sabiendo todo eso, el resultado final se vuelve simplementeprint @countries[%reachable]. Excepto que los países en este punto estarán dentro$_, por lo que el código real esprint+(/$|.+\n/mg)[%r]. Observe cómo la expresión regular se asegura de que las líneas vacías no obtengan una nueva línea, pero los nombres completos de los países sí.%reachableprincipio, los países que se tocan pueden buscarse utilizandomap keys %{$touches{$_}},keys %reachable. Pero, una vez más,keysno es necesario si me encargo de manejar adecuadamente los valores undef que también obtengo sin elkeys. Y como dije antes, uso el globo principal para almacenar los valores, por lo que el fragmento de código real esmap%$_,%r. Quiero agregar cada uno de los valores devueltos como una nueva clave a la%rque se puede hacer como%r=map%$_,%r. Sin embargo, esto necesita que los países se refieran a sí mismos como conmovedores para que la capa de origen permanezca en el conjunto. Este fragmento de código debe repetirse tantas veces como el usuario solicite capas. Tenga en cuenta que este es el núcleo real del programa, todo lo demás es ruido para soportar esto.-aopción recogió el número de capas como el último elemento en@Fque esto puede llevarse a cabo utilizandoeval '%r=map%$_,%r;' x pop @F. En general, esta no es la forma más corta de recorrer Perl, pero tiene la ventaja de que no cambia$_durante el ciclo, un hecho que utilizaré más adelante. Poner el número de capas en su propia línea de STDIN me dejaría reemplazar elx pop@Fdex<>ahorro de 4 bytes, pero quiero seguir siendo lo más cercano a la especificación como sea posible.pop @Feliminar las capas@Fcontiene el nombre del país de inicio. Tenga en cuenta que los países con espacios en su nombre se dividirán en sus partes componentes. Podemos encontrar el objetivo en la cadena de países grandes$_e inmediatamente reemplazar el país de destino por la cadena de emty (para que no se imprima) haciendos/^@F$//m. Observe que los países con espacios en su nombre se reconstruyen por la@Finterpolación. También tenga en cuenta que esto debe anclarse cuidadosamente porque algunos países son subcadenas de otros, por ejemplo,GuineayGuinea-BissauoNigeryNigeria$'=~y/\n//. Si no se encuentra el país de destino$`, contendría un valor de una expresión regular anterior que podría estar muy equivocado. En cambio, queremos 0 (en cuyo índice tenemos una cadena vacía). Esto se puede lograr combinándolo con el partido anterior ens/^@F$//m*$`=~y/\n//.%reachable. El eval entonces se convierteeval '%r=map%$_,%r,%r,s/^@F$//m*$`=~y/\n//;' x pop@F;. Tenga en cuenta que la sustitución destruye el país de destino, por$_lo que solo se agrega la primera vez (no importaría si esto no fuera así, ya que el índice del país de destino ya está de%reachabletodos modos)%r, podemos combinar estoprint+(/$|.+\n/mg)[%r]para llegar al código realprint+(/$|.+\n/mg)[eval'%r=map%$_,%r,s/^@F$//m*$`=~y/\n//;'x pop@F]La siguiente pregunta es cómo codificar la lista de países. Como se explicó anteriormente, lo quiero como una cadena enorme con los países terminados en nueva línea y comenzando con una sola nueva línea. Para esto necesito 26 letras, espacio, nueva línea,
-(paraGuinea-Bissau) y'(paraCote D'Ivoire). El problema es, por supuesto, que a veces las letras están en mayúsculas. Esto se resuelve fácilmente en mayúscula la primera letra después del límite de una palabra. Sin embargo, hay excepciones:Republic of Ireland,Bosnia and HerzegovinayDemocratic Republic of the Congo. Estos tienen una palabra que no comienza con mayúsculas. Puedo manejar eso reemplazando el espacio anterior con un guión bajo_que evita que sea reconocido como un límite de palabra, y luego reemplazarlo_por un espacio. La excepción que queda esUSAque tiene mayúsculas que no está en el límite de una palabra. Para eso, introduzco límites de palabras escribiendo esto comou`s`ay luego elimino las comillas inversas. Juntos eso da:Con este código que puede codificar toda la cadena de países que utilizan solo
a-z,,',-,\n,_y`, lo que es de 32 caracteres diferentes. Por lo tanto, cada carácter puede codificarse con 5 bits. De hecho, si tengo una gran cadena de bits11110100111..., puedo convertirla en los caracteres necesarios usando:Si tengo una cadena de bytes,
$_entonces la enorme cadena de bits que necesito se puede crear usando$_ = unpack"B*". Básicamente, todo esto es un pequeño convertidor de base 256 a base 32 y cada letra de país se codifica utilizando 5 bits en la cadena de países binarios entrantes. Esto es relativamente compacto y no gana nada desarrollar códigos especiales para cadenas repetidas en la lista de países con una excepción:Republicaparece en 5 nombres de países. Como siempre aparece como una palabra completa y ningún nombre de país comienza conX(la única letra de ese tipo), puedo usarlo como código de escape después de que las primeras letras de los nombres de países se hayan colocado en mayúscula.Ahora necesito una forma de codificar la relación de "toques". Lo primero que debe notar es que es simétrico, por lo que si el país
$ntoca al país$t, entonces el país$ttambién toca al país$n. Por lo tanto, solo necesito codificar la mitad de las relaciones si completo el%toucheshash en ambos sentidos. En el código simplificado ves que lo está haciendoExcepto que el código real se usa en
$.lugar de$nporque quiero que el contador comience en 1 en lugar de 0 (el país 0 es la cadena vacía ficticia). La idea es escribir una secuencia de índices de países| A, B, C | D, E | ..que diga que el país 1 toca a los países con índiceA,By elCpaís 2 toca el índiceDyEDe hecho, codifico el desplazamiento del país actual (que luego usaré para hacer que los valores sean pequeños) y solo los desplazamientos positivos (esto asegura que la relación de "toques" solo se codifique en una dirección, y el método que uso puede no maneje números negativos de todos modos). Algunos países tienen una lista vacía de vecinos porque su relación de contacto ya ha sido dada por otros países. Puedo reorganizar la lista de países (cuyo orden es irrelevante) de modo que estos aparezcan al final de la lista. Entonces puedo omitir estos países de la secuencia. Esto no gana nada ya que necesito tantas compensaciones como relaciones "táctiles", pero evita perder bytes al tener que codificar una compensación ficticia. Como se explicó anteriormente, el país 0 es una cadena vacía ficticia, por lo que debo asegurarme de que se omita. Puedo escribir esta secuencia de números como una secuencia de bytes donde el valor del byte corresponde al desplazamiento del índice. Sin embargo, todavía necesito saber dónde comienza el próximo país en una secuencia (las posiciones de la|s en el ejemplo anterior). Hago esto estableciendo un bit alto en 1 para el primer índice en la lista de toques de un país en particular, así que para los índicesAyDen el ejemplo anterior.Sin embargo, hay un problema molesto: hay más de 127 países. Así que no puedo usar el bit de signo de carácter. En cambio, encontré una disposición de los países para que cada país nunca esté más lejos que 15 posiciones lejos de todos los países que toca:
(en el momento en que escribía esta explicación, mi programa de búsqueda realmente encontró un pedido donde la distancia máxima es como máximo 12). Esto significa que puedo usar
0x10como indicador para indicar el inicio de un nuevo país y solo necesito codificar 32 valores diferentes. Esto se puede comprimir para la expansión con el mismo convertidor de base 256 a base 32 que se necesitaba para la lista de países. De hecho, puedo poner la cadena táctil antes de la cadena de país con un0x00intermedio (antes de la codificación) si escribo el decodificador táctil para que se detenga en esto\x00. El decodificador de país se escribe de modo que esto que0x00queda al principio se convierta en la nueva línea inicial que necesito, por lo que el país en el índice 0 es la cadena vacía.Una versión anterior del código utilizaba el hecho de que solo hay 4 componentes conectados en el gráfico del país para reducir los índices de país a menos de 128, pero eso era mucho más complicado y bastante más largo en el código y la cadena codificada.
El código para convertir una secuencia de bytes al
%toucheshash se convierte en:Tenga en cuenta que todos los países singleton simplemente no están codificados en absoluto. Usados como entrada, por lo tanto, nunca coincidirán, por
%reachablelo que solo contendrán referencias al país vacío inicial y no se imprimirá nada.Con eso se explica todo el programa. Todo lo que se necesitaba después de eso era escribir un metaprograma que generara la enorme cadena codificada eligiendo cuidadosamente el orden de los países de manera que
'(lo que invalidaría la cadena final entre comillas)fuente
JavaScript (ES6),
28622324Devuelve un objeto Set que contiene los países adecuados. Tenga en cuenta que esto contiene un montón de no imprimibles.
Fragmento de prueba (se requiere un navegador compatible con ES6)
Mostrar fragmento de código
Cómo funciona
Antes que nada, eliminé todos los países sin vecinos de la lista. Luego reduje la lista a este formato:
Esto condensa la lista a 2130 bytes. Se insertó cuidadosamente una entrada en blanco donde el país representado por una coma sería para evitar la falla de expresiones regulares. Ahora para la parte interesante:
fuente
JavaScript (ES6) 2622
3815Una función que devuelve un conjunto. Escaneo recursivo utilizando un conjunto para evitar repeticiones.
(Se agregaron 2 líneas nuevas para facilitar la lectura; debe ser una sola línea)
Tomar prestada la idea de @ETHproductions de no almacenar países sin vecinos . (Tomando prestada su ortografía también, siempre escribo mal esa palabra)
Explicación
Prueba
fuente
1/xlugar de+x?" Entonces me di cuenta de que es una forma inteligente de sortear el caso0. +1Python 2,
6967696569506906bytesRealmente espero realmente tener todo bien. Ejemplo:
Entrada:
Salida:
Espero que se permita la línea vacía.¡No más líneas vacías! ¡Hurra!Explicación:
La línea larga en la parte superior contiene datos sobre el nombre de cada país y los países vecinos. Cada elemento de la lista es otra lista, cuyo primer elemento es el nombre del país, y el otro elemento es el índice de cada país que lo rodea. Estados Unidos es el primer elemento y contiene los índices
1, 2. El elemento 1 en la lista es Canadá, y el elemento 2 en la lista es México. Esta lista fue generada usando este programa:...... [la gran lista de arriba]
La salida contenía comas que podrían eliminarse con una expresión regular muy simple, que se puede encontrar aquí . El programa completo está disponible aquí. . La salida es de 4.736 bytes, aproximadamente el 88% del programa.
Aquí está el resto del programa con nombres de variables, comentarios y espacios en blanco adecuados (versión anterior):
fuente
{}hace un dictado , desafortunadamente.{x for d in Q[A][1:] if d not in C}y enC|=nlugar delfor A in C:bucle.Mathematica, programa 128B + datos 2856B = 2984 bytes
Donde
FOOhay una cadena de 2856 bytes (no pegada aquí porque contiene caracteres no imprimibles y solo MMA). La cadena es una lista de listas comprimida con BZIP2, donde cada lista interna tiene la forma{Country, Neighbor, Neighbor, ...}. La lista ya está optimizada para eliminar bordes redundantes.Tenerlo en el formato gráfico de Mathematica nos permite hacer cosas fáciles y agradables como esta:
Para obtener cosas como:
fuente
PHP,
5169271626982321 bytesActualizar
Esta es mi segunda versión extremadamente acortada. Publicación original ver abajo.
Esto resultó ser una edición bastante detallada ...
Eliminando países sin vecinos.
Mi definición de matriz original era de 4901 bytes: la eliminación de todos los países sin vecinos (como sugirió @ETHproductions) redujo esto en 725 bytes a 4176 bytes. Por supuesto, esto requiere que se agregue un código lógico adicional para atender el retroceso, pero eso debería ser despreciable en comparación con esta gran ganancia.
Usar caracteres en lugar de números
Mi siguiente paso fue reducir la cantidad de bytes necesarios para decodificar las referencias vecinas. Mi primera idea fue deshacerme del sistema decimal y usar una base más alta para representar los números (por ejemplo, la base 36 que usaría 0-9 más az), pero la lógica adicional necesaria para decodificarlos parecía mucho. Entonces fui por otra cosa: personajes.
Cada carácter ASCII tiene solo un byte de longitud y se asigna a un número bien definido del rango 0..255, que es exactamente lo que se necesitaría. Me salté los primeros 39 caracteres ASCII ya que no se pueden imprimir / incluir
'e"necesitarían escapar. La definición de matriz resultante tenía solo 2878 bytes de longitud, ahorrando 1298 bytes o 31% en comparación con la anterior. Por supuesto, esto también necesita lógica adicional, pero afortunadamentechryordson nombres de funciones en lugar cortos :-)Comprimir nombres de países
Sin embargo, esos nombres de países todavía ocupaban mucho espacio, así que decidí buscar cómo podría comprimirlos. Cinco países tienen el término "República" en ellos, así que pude guardar 16 bytes declarando
$r='Republic'una vez y luego escribiendo"$r of Ireland"etc. Lo mismo ocurre con "Guinea", que aparece 4 veces.También hay bastantes combinaciones de letras que ocurren con relativa frecuencia, pero dado que la escritura
$xsigue siendo dos caracteres, reemplazarlos solo tiene sentido para combinaciones con 3+ letras y si realmente hay MUCHO que se puede reemplazar. Por ejemplo, al reemplazar los 10-nias enTanzaniaetc., se obtuvo solo 1 byte. Lo mismo con-istan(4x, -1), más suerte con-land(7x, -4).PHP "características"
Afortunadamente para el jugador de código, a PHP no le importa demasiado cuando viola sus reglas de sintaxis. Aquí, podemos usar esto para quitar algunas comillas, convirtiendo
'Lesotho'=>'E'(14 bytes) enLesotho=>E(10 bytes). Sorprendentemente (o:? Sorprendentemente) Esto funciona incluso para cualquier cadena que consiste en AZ, 0-9 o la segunda mitad de la tabla ASCII y no se inicia con un número , por lo que algo como esto sea posible:India=>nh¢•Q“.Sin embargo, es una pena que los diseñadores de la tabla ASCII pongan puntuación entre los bloques de letras, lo que significa que no hay un bloque continuo de caracteres sin sentido de PHP para acomodar a los 150 países en la lista. Esto da como resultado que muchas cadenas sigan manteniendo sus comillas. De vez en cuando movía los números hacia atrás para que la cadena no comenzara con un dígito.
Definición de matriz final
Todo esto reduce la definición de la matriz a 2534 bytes, casi la mitad del valor inicial. Por supuesto, ahora se podría ir y optimizar el orden de los países para que tantas entradas como sea posible puedan perder sus cotizaciones, etc., pero no quería poner ESTO esfuerzo en esto. ;-)
Código
Así que aquí está, la segunda versión, con un poco de lógica adicional agregada:
Golfed
Edición de la actualización
Guardado otros 18 bytes por:
$r='Republic'etc. (-10)forconwhileloop (-6)aspalabras clave (-2)Actualicé el código anterior con los cambios.
Otra edición
Afeitó otros 377 bytes mediante la creación de una matriz indexada a partir de una cadena de implosión primero (haciendo que todos
=>y"obsoleta, -417 bytes de sobrecarga) y convertirla en la matriz asociativa querían después (+40 bytes de código). Actualizó el código anterior nuevamente.Publicación inicial
Esta es una primera versión bastante rápida, todavía no hice NINGUNA compresión de la lista además de los números obvios para los nombres; podría trabajar en eso mañana y editar mi publicación en ese momento.
Mi lista es una matriz asociativa simple con una entrada para cada país. La clave de matriz es el nombre del país y el valor de una matriz de sus vecinos, referenciada por su índice en esa matriz. PHP no le permitirá acceder a matrices asociativas por índice, por lo que necesitaba una solución alternativa usando
array_keysyarray_valuesfunciones.El código real comentó:
Como antes y siempre, cualquier comentario es muy apreciado.
fuente
Dyalog APL , programa de 82 bytes + datos de 1924 bytes = 2006 bytes
No hice nada especial para empacar los datos más allá del uso de la (des) serialización (
220⌶) y (un-) zip (219⌶) integrada de Dyalog APL .Donde los puntos suspensivos representan una cadena zlib'ed con estos valores de bytes:
Tenga en cuenta que tanto la cadena codificada como el resto del programa encajan en la página de códigos de 256 caracteres de APL, es decir, un símbolo por byte.
Así es como se ve todo cuando se juntan, (
␀reemplazando a U + 0000):fuente