Los 9 mil millones de nombres de Dios

74

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 ABCDEFGHIJKLMo 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. AAABAes un nombre válido, pero AAAABno lo es.

  • Su programa debe imprimir (en un archivo) todos los nombres posibles en secuencia de Aa MMMLMMMLM, 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 Ay 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.

CSturgess
fuente
29
¿Está tratando de acabar con el universo, señor?
Boluc Papuccuoglu
8
Enlace a la historia , para cualquier persona interesada.
ThatOneGuy
1
¡Aquí está! math.stackexchange.com/a/34292
edc65
1
Esto verifica que el número de nombres en el problema actual es de hecho 11,459,252,883 (como se encuentra en el programa C de edc65 ). Implementación de la solución de Ross Millikan en MathSE genera la siguiente fórmula polinómica para el número de nombres con longitud <= 9, para el tamaño alfabeto variable de k: 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/0srwhq
res
3
@ edc65 ¡ 105.8GBTodo dicho y hecho! Me alegro de que las estrellas no se apagaran ... ¿o quizás tengas que imprimir la lista para que eso suceda ...?
recursion.ninja

Respuestas:

34

Ruby, 46

?A.upto(?M*9){|s|s[/(.)\1{3}|[N-Z]/]||puts(s)}

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.

1.upto(13**9){|i|(s=i.to_s 13)[/(.)\1{3}/]||puts(s)}
histocrat
fuente
14
Bueno, ejecuté su código durante aproximadamente una hora y obtuve hasta 2 mil millones de nombres y un archivo de texto de 21 GB antes de ver esto y dejarlo. Subestimé cuán grande sería el archivo.
CSturgess
2
@CSturgess Bueno, Ruby no es el lenguaje más rápido para este tipo de cosas ...
BenjiWiebe
8
@BenjiWiebe ¡Pero aún más rápido que ser escrito a mano por monjes!
Turophile
1
Aceptando este porque tiene más votos.
CSturgess
44
No publico esto como una respuesta separada, ya que requiere una cantidad inmensamente grande de memoria (~ 30 TB, si mi cálculo es correcto), pero en teoría puede acortar esto a 43 caracteres conk=*?A..?M*9;puts k-k.grep(/(.)\1{3}|[N-Z]/)
Ventero
24

C 140 177 235

Buen 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.

char n[]="@@@@@@@@@@";p=9,q,r;main(){while(p)if(++n[p]>77)n[p--]=65;else for(r=q=p=9;r&7;)(r+=r+(n[q]!=n[q-1])),n[--q]<65&&puts(n+q+1,r=0);}

Sin golf

char n[]="@@@@@@@@@@";
p=9,q,r;
main()
{
    while (p)
    {
        if (++n[p] > 77)
        {
            n[p--] = 65; // when max reached, set to min and move pointer to left
        }
        else 
        {
            for (r=q=p=9; r & 7 ;) // r must start as any odd number
            {
                r += r+(n[q]!=n[q-1])); // a bitmap: 1 means a difference, 000 means 4 letters equal
                n[--q] < 65 && puts(n+q+1,r=0);
            }
        }
    }
}
edc65
fuente
no #includes?
Simon Kuang
@SimonKuang, algunos compiladores pondrán los básicos (stdio) automáticamente.
Paul Draper
1
@ Simon es el estándar C. Por defecto, los objetos globales son int y las funciones globales devuelven int. Visual studio emite una advertencia de C4013 acerca de 'put' no definido, pero de todos modos es válido.
edc65
44
cabe en un tweet!
CincauHangus
19

Golfscript, 58 47 caracteres

"A"13
9?,{13base{65+}%n+}%{`{\4*/,}+78,1/%1-!},

¡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 .

Claudiu
fuente
1
Ahorro fácil: usar en 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 reemplazar 65+con 13+y guardar otro personaje nombrando 13:^. Y creo que 13,{ stuff [...]podría ser 13,1/{ stuff 4*.
Peter Taylor
1
Mi pensamiento inicial fue que el ahorro sería a través de un filtro, y con un poco de trabajo se puede hacer. A partir 13,de ahora se puede reemplazar {65+}%n+}%{ backtick {\4*/,}+78,1/%1-!},por un ahorro total de 8, salvando su vida.
Peter Taylor
Mientras el personaje sea algo que puedas ver físicamente, funcionará. Realmente incluso podrías incluir nuevas líneas como personaje. Siempre y cuando haya una secuencia de los personajes.
CSturgess
@PeterTaylor: ¡Eres un caballero y un erudito!
Claudiu
Después AAAMdebería ser AAABA, y no BAAAB, ¿verdad?
justhalf
18

Bash + Linux utilidades de línea de comando, 43 bytes

jot -w%x $[16**9]|egrep -v "[0ef]|(.)\1{3}"

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, eo ftambién aquellos con más de 3 dígitos consecutivos.

Convierte al alfabeto del monje de la siguiente manera:

jot -w%x $[16**9]|egrep -v "[0ef]|(.)\1{3}" | tr 1-9a-d A-M

Bash + coreutils (dc y egrep), 46 bytes

Editar - versión corregida

dc<<<Edo9^[p1-d0\<m]dsmx|egrep -v "0|(.)\1{3}"

Tardará un tiempo en ejecutarse, pero creo que es correcto.

dccuenta 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:

dc<<<Edo9^[p1-d0\<m]dsmx|egrep -v "0|(.)\1{3}" | tr 1-9A-D A-M

Esto produce la secuencia:

MMMLMMMLM MMMLMMMLL MMMLMMMLK ... AC AB AA M L K ... C B A

Tenga en cuenta que este dccomando 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).

Trauma digital
fuente
10

APL (59)

↑Z/⍨{~∨/,↑⍷∘⍵¨4/¨⎕A[⍳13]}¨Z←⊃,/{↓⍉⎕A[1+(⍵/13)⊤¯1⌽⍳13*⍵]}¨⍳9

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 al 13^⍵
    • ¯1⌽: Girar la lista a la izquierda por 1 (por lo que tenemos 13^⍵, 1, 2, ..., 13^⍵-1, que se convierte en 0, 1, 2 ...módulo 13^⍵).
    • (⍵/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 que 1significa que cumple con las reglas y 0significa que no.
  • Z/⍨: selecciona entre Ztodos los elementos que cumplen con los ruels
  • : muestra cada uno en una línea separada
marinus
fuente
9
Estoy decepcionado. Dada su reputación, pensarías que APL tendría una solución de un carácter para esto, que ningún teclado podría escribir.
Marcar el
77
@ Mark, estoy seguro de que APL tiene eso, pero nadie sabe cuál es el personaje :)
Paul Draper
1
uno debería escribir esto en una piedra, y cuando los humanos futuros encuentren esto, podrían pensar que es solo un lenguaje escrito primitivo.
CincauHangus
9

Perl, 70 68 66 50 caracteres

$"=",";map/(.)\1{3}/||say,glob$i.="{@a}"for@a=A..M

Uso:

$ perl -E 'code' > output_file

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.

Zaid
fuente
Lo mejor de esta solución es el pecho a la izquierda de la 1.
Dan Hanly
8

Perl - 35 bytes

#!perl -l
/(.)\1{3}|[N-Z]/||print for A..1x9

Contando el shebang como un byte.

Esta es una traducción suelta de la respuesta del histocrat .

A..1x9es 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 su 1x4lugar.

primo
fuente
¡El respeto! Ahora, ¿por qué no pensé en eso? ;)
Zaid
Tenga en cuenta que Ruby tampoco tiene que crear todo el rango para iterarlo. La única razón por la que el código en mi comentario requiere una cantidad de memoria tan grande es porque convierte el rango en una matriz (para que pueda usar Array#-).
Ventero
@Ventero Ahh sí, greplo hará. No soy del todo fluido en Ruby.
primo
6

Pyg (Waaay demasiado largo, para un lenguaje hecho para jugar al golf)

susurros : 101 ...

Pe(*ItCh(((J(x)for x in ItPr("ABCDEFGHIJKLM",repeat=j)if not An((i*3 in x)for i in x))for j in R(14))))

Aunque esto está cerca de cómo lo haría realmente en Python:

from itertools import *
for i in range(14):
    for j in ("".join(k) for k in product("ABCDEFGHIJKLM",repeat=i) if not any((i*3 in k) for i in k)):
        print j

Menos la complicación de la línea larga, por supuesto;)

ɐɔıʇǝɥʇuʎs
fuente
3

Pyth , 34 caracteres

Kf<T"n"GJKFbJI>lb9Bb~Jm+bdfXVb*Y3K

Explicación:

Kf<T"n"G        K = list of letters in the alphabet before n.
JK              J = copy of K
FbJ             For b in J:
I>lb9B          If length of b > 9: break
b               print(b)
~J              J+=
~Jm+bd          J+=map(lambda d:b+d,
       XVb*Y3   index of Y*3 in reversed(b)
      fXVb*Y3K  filter for non-zero for Y in K on function index of Y*3 in reversed(b)
~Jm+bdfXVb*Y3K  J+=map(lambda d:b+d, filter(lambda Y:index of Y*3 in reversed(b), K))
isaacg
fuente
2

Python 2: 212 bytes

from itertools import chain,product as p
a='ABCDEFGHIJKLM'
q={c*4 for c in a}
c=0
for n in chain(*(p(*([a]*l)) for l in range(1,10))):
 n=''.join(n)
 if not any(u in n for u in q):print n
 c+=1
 if c==10**9:break
Criterios de Zac
fuente
0

Japt , 21 bytes

Ep9 osE kè/0|(.)\1{3}

Pruébalo en línea! (el enlace solo calcula hasta 14**4).

Cómo funciona

Ep9 osE kè/0|(.)\1{3}/

Ep9  14**9
osE  Range from 0 to n (exclusive), mapped through base-14 conversion
kè   Remove elements that match at least once...
/0|(.)\1{3}/  the regex that matches a zero or four times same char.

Asume una implementación estándar de ECMAScript 2017 como la capa JS (y suficiente memoria para almacenar la matriz), donde un Arrayobjeto puede tener un máximo de 2**53-1longitud.

Bubbler
fuente