Los 9 mil millones de nombres de Dios es una historia corta de Arthur C. Clarke. Se trata de un grupo de monjes tibetanos cuya orden se dedica a escribir todos los posibles nombres de Dios, escritos en su propio alfabeto. Esencialmente, se dedican a escribir todas las permutaciones posibles de su alfabeto, restringidas por algunas reglas. En la historia, el monasterio contrata a algunos ingenieros para que escriban un programa que haga todo el trabajo por ellos. Tu objetivo es escribir ese programa.
Reglas:
El alfabeto del monje usa 13 caracteres (según mis estimaciones). Puede usar
ABCDEFGHIJKLM
o algún otro conjunto de 13 caracteres.La longitud mínima de un posible nombre es de 1 carácter. La longitud máxima es de 9 caracteres.
Ningún personaje puede repetir más de 3 veces seguidas.
AAABA
es un nombre válido, peroAAAAB
no lo es.Su programa debe imprimir (en un archivo) todos los nombres posibles en secuencia de
A
aMMMLMMMLM
, separados por cualquier carácter que no esté en el alfabeto (líneas nuevas, punto y coma, lo que sea).Este es el código de golf, y puede usar cualquier idioma. La solución más corta para el 1 de junio de 2014 gana.
Editar: los nombres deben comenzar A
y terminar con MMMLMMMLM
, progresando a través de todos los miles de millones de nombres secuencialmente. Pero la secuencia particular depende de usted. Puede imprimir primero todos los nombres de 1 letra, luego todos los nombres de 2 letras, etc. O puede imprimir todos los nombres que comienzan con A
, luego todos los que comienzan con B
, o algún otro patrón. Pero un humano debería poder leer el archivo y confirmar que están todos allí y en el orden lógico que elija, suponiendo que tengan el tiempo.
fuente
f(k) = k^9 + k^8 + k^7 - 5*k^6 + k^5 + k^4 + 4*k^3 - 2*k^2 + k
. Implementación de Sage: goo.gl/0srwhq105.8GB
Todo dicho y hecho! Me alegro de que las estrellas no se apagaran ... ¿o quizás tengas que imprimir la lista para que eso suceda ...?Respuestas:
Ruby, 46
Mi solución original y similar fue más larga e incorrecta (generó números base13, que no son todos debido a ceros iniciales), pero lo dejaré aquí porque obtuvo votos de todos modos.
fuente
k=*?A..?M*9;puts k-k.grep(/(.)\1{3}|[N-Z]/)
C 140
177 235Buen estilo de procedimiento antiguo, sin fantasía.
Cuenta (sin escritura) 11,459,252,883 nombres en 8 minutos.
Luego edite con el tiempo de ejecución y el tamaño del archivo de nombres. Mire el cielo ...
Tiempo de ejecución 57 minutos, tamaño de archivo 126,051,781,713 (9 caracteres + crlf por fila). Por favor, dígame la dirección de correo electrónico de los monjes, para que pueda enviarles el archivo comprimido, para verificación manual ...
Editar Golfed un poco más, volvió a trabajar el cheque para las letras repetidas.
Todavía no es el más corto, pero al menos este termina y genera la salida requerida.
Tiempo de ejecución 51 min, tamaño de archivo 113,637,155,697 (esta vez no hay espacios en blanco)
Una nota al margen: obviamente, el archivo de salida es muy compresible, aún así tuve que matar a 7zip, después de trabajar 36 horas estaba al 70%. Extraño.
Sin golf
fuente
#include
s?Golfscript,
5847 caracteres¡Gracias a Peter Taylor, me he librado del seppuku de no superar la solución Ruby! Ejecute el código hasta 10 usted mismo , y aquí está la prueba de que omite los números de cuatro en una fila .
fuente
n+
lugar de''+n
. Creo que es dentro de las reglas para utilizar un alfabeto con caracteres de control, por lo que también podría reemplazar65+
con13+
y guardar otro personaje nombrando13:^
. Y creo que13,{ stuff [...]
podría ser13,1/{ stuff 4*
.13,
de ahora se puede reemplazar{65+}%n+}%{ backtick {\4*/,}+78,1/%1-!},
por un ahorro total de 8, salvando su vida.AAAM
debería serAAABA
, y noBAAAB
, ¿verdad?Bash + Linux utilidades de línea de comando, 43 bytes
Esto usa una técnica similar a mi respuesta a continuación, pero solo cuenta en la base 16 y elimina todos los "nombres" que contienen
0
,e
of
también aquellos con más de 3 dígitos consecutivos.Convierte al alfabeto del monje de la siguiente manera:
Bash + coreutils (dc y egrep), 46 bytes
Editar - versión corregida
Tardará un tiempo en ejecutarse, pero creo que es correcto.
dc
cuenta hacia abajo de 14 ^ 9 a 1 y sale en la base 14. egrep filtra los números con más de 3 dígitos iguales consecutivos. También filtramos los nombres con dígitos "0", por lo que obtenemos el conjunto correcto de letras en los nombres.La pregunta especifica que se puede usar cualquier alfabeto, así que estoy usando [1-9] [AD]. Pero para las pruebas, esto se puede transformar a [AM] usando tr:
Esto produce la secuencia:
Tenga en cuenta que este
dc
comando requiere recursividad de cola para funcionar. Esto funciona en dc versión 1.3.95 (Ubuntu 12.04) pero no en 1.3 (OSX Mavericks).fuente
APL (59)
Escrito en su propio alfabeto :) Es un poco largo. También lleva mucho tiempo ejecutarlo
9
, pruébelo con un número menor para probar si lo desea.Explicación:
{
...}¨⍳9
: para cada número⍵
del 1 al 9:⍳13*⍵
: obtener todos los números del 1 al13^⍵
¯1⌽
: Girar la lista a la izquierda por 1 (por lo que tenemos13^⍵
,1
,2
, ...,13^⍵-1
, que se convierte en0, 1, 2 ...
módulo13^⍵
).(⍵/13)⊤
: codifica cada número en la base 13 usando⍵
dígitos⎕A[1+
...]
: agregue uno (las matrices están indexadas en 1) y busque⎕A
(el alfabeto)↓⍉
: convierte la matriz en un vector de vectores a lo largo de las columnas.Z←⊃,/
: une cada vector interno de vectores, dándonos una lista de posibles nombres (pero aún no cumple con las reglas).{
...}¨
: para cada nombre, pruebe si cumple con la regla de 4 caracteres repetidos:4/¨⎕A[⍳13]
: para cada personaje, genera una cadena de 4 de ese personaje⍷∘⍵¨
: para cada cadena, pruebe si está presente en⍵
∨/,↑
: tome la lógica o de todas estas pruebas,~
: e invertirlo, lo que1
significa que cumple con las reglas y0
significa que no.Z/⍨
: selecciona entreZ
todos los elementos que cumplen con los ruels↑
: muestra cada uno en una línea separadafuente
Perl,
70686650 caracteresUso:
Lo bueno es que las impresiones están almacenadas en búfer, por lo que primero se imprimen todas las soluciones de 1 carácter, seguidas de las palabras de 2 caracteres, etc.
fuente
Perl - 35 bytes
Contando el shebang como un byte.
Esta es una traducción suelta de la respuesta del histocrat .
A..1x9
es un poco extraño; esta es la abreviatura de'A'..'111111111'
. El acumulador nunca alcanzará el valor del terminal (contiene solo letras mayúsculas), pero aún terminará una vez que tenga más de 9 caracteres de longitud. Esto se puede probar, por ejemplo, utilizando en su1x4
lugar.fuente
Array#-
).grep
lo hará. No soy del todo fluido en Ruby.Pyg (Waaay demasiado largo, para un lenguaje hecho para jugar al golf)
susurros : 101 ...
Aunque esto está cerca de cómo lo haría realmente en Python:
Menos la complicación de la línea larga, por supuesto;)
fuente
Pyth , 34 caracteres
Explicación:
fuente
Python 2: 212 bytes
fuente
Japt , 21 bytes
Pruébalo en línea! (el enlace solo calcula hasta
14**4
).Cómo funciona
Asume una implementación estándar de ECMAScript 2017 como la capa JS (y suficiente memoria para almacenar la matriz), donde un
Array
objeto puede tener un máximo de2**53-1
longitud.fuente