Les 9 milliards de noms de Dieu

74

Les 9 milliards de noms de Dieu est une nouvelle d'Arthur C. Clarke. Il s'agit d'un groupe de moines tibétains dont l'ordre est consacré à l'écriture de tous les noms possibles de Dieu, écrits dans leur propre alphabet. Ils se consacrent essentiellement à l'écriture de toutes les permutations possibles de leur alphabet, limitées par quelques règles. Dans l’histoire, le monastère a engagé des ingénieurs pour écrire un programme lui permettant de faire tout le travail à sa place. Votre but est d'écrire ce programme.

Règles:

  • L'alphabet du moine utilise 13 caractères (selon mes estimations). Vous pouvez utiliser ABCDEFGHIJKLMou un autre ensemble de 13 caractères.

  • La longueur minimale d'un nom possible est de 1 caractère. La longueur maximale est de 9 caractères.

  • Aucun personnage ne peut se reproduire plus de 3 fois de suite. AAABAest un nom valide, mais AAAABn'est pas.

  • Votre programme doit imprimer (dans un fichier) tous les noms possibles dans l'ordre, de, Aà MMMLMMMLM, séparés par tout caractère ne figurant pas dans l'alphabet (sauts de ligne, points-virgules, peu importe).

  • C'est du code-golf, et vous pouvez utiliser n'importe quelle langue. La solution la plus courte au 1er juin 2014 l'emporte.

Edit: Les noms doivent commencer par Aet se terminer par MMMLMMMLM, en passant en revue tous les milliards de noms de façon séquentielle. Mais la séquence particulière est à vous. Vous pouvez d'abord imprimer tous les noms à une lettre, puis tous les noms à 2 lettres, etc. Vous pouvez également imprimer tous les noms commençant par A, puis tous ceux commençant par B, ou un autre motif. Mais un humain devrait pouvoir lire le fichier et confirmer qu'il est présent et dans l'ordre logique de votre choix, en supposant qu'il en ait le temps.

CSturgess
la source
29
Essayez-vous de mettre fin à l'univers, monsieur?
Boluc Papuccuoglu
8
Lien vers l'histoire , pour toute personne intéressée.
ThatOneGuy
1
C'est ici! math.stackexchange.com/a/34292
edc65
1
Ceci vérifie que le nombre de noms dans le problème actuel est bien de 11 459 252 883 (comme indiqué dans le programme C d'edc65 ). Mise en œuvre de la solution de Ross Millikan à MathSE génère la formule polynôme suivant le nombre de noms avec une longueur <= 9, pour la taille alphabet variable k: f(k) = k^9 + k^8 + k^7 - 5*k^6 + k^5 + k^4 + 4*k^3 - 2*k^2 + k. Sage implémentation: goo.gl/0srwhq
res
3
@ edc65 Alors 105.8GBtout est dit et fait! Je suis content que les stars ne soient pas sorties ... ou peut-être devez-vous imprimer la liste pour que cela se produise ...?
recursion.ninja

Réponses:

34

Ruby, 46 ans

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

Ma solution initiale, similaire, était plus longue et erronée (elle produisait des nombres en base13, qui ne sont pas tous dus à des zéros non significatifs), mais je vais les laisser ici car ils ont obtenu des votes de toute façon.

1.upto(13**9){|i|(s=i.to_s 13)[/(.)\1{3}/]||puts(s)}
histocrate
la source
14
Eh bien, j'ai exécuté votre code pendant environ une heure et obtenu 2 milliards de noms et un fichier texte de 21 Go avant de voir ceci et de le quitter. J'ai sous-estimé la taille du fichier.
CSturgess
2
@CSturgess Eh bien, Ruby n'est pas la langue la plus rapide pour ce genre de choses ...
BenjiWiebe
8
@BenjiWiebe Mais toujours plus rapide que d'être écrit à la main par des moines!
Turophile
1
Accepter celui-ci parce qu'il a plus de votes.
CSturgess
4
Ne pas afficher cette réponse séparément, car elle nécessite une énorme quantité de mémoire (environ 30 To, si mon calcul est correct), mais en théorie, vous pouvez le réduire à 43 caractères aveck=*?A..?M*9;puts k-k.grep(/(.)\1{3}|[N-Z]/)
Ventero
24

C 140 177 235

Bon vieux style procédural, pas de fantaisie.
Il compte (aucune écriture) 11 459 252 883 noms en 8 minutes.
Prochaine édition avec le fichier runtime et la taille des noms. Regarde le ciel ...
Durée 57 minutes, taille du fichier 126 051 781 713 (9 caractères + crlf par ligne). Merci de me communiquer l'adresse email des moines pour que je puisse leur envoyer le fichier compressé, pour vérification manuelle ...

Edit Golfed un peu plus, retravaillé le chèque pour les lettres répétées.
Pas encore le plus court, mais au moins celui-ci se termine et génère la sortie requise.
Durée 51 min, taille du fichier 113 637 155 697 (aucun blanc significatif pour le moment)

Une note de côté: évidemment le fichier de sortie est très compressible, je devais quand même tuer 7zip, après avoir travaillé 36 heures, il était à 70%. Bizarre.

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);}

Ungolfed

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
la source
non #includes?
Simon Kuang
@ SimonKuang, certains compilateurs insèrent automatiquement des bases (stdio).
Paul Draper
1
@ Simon c'est C standard. Par défaut, les objets globaux sont int et les fonctions globales renvoient int. Visual studio affiche le C4013 comme avertissement concernant les «options» non définies, mais il est néanmoins valide.
Edc65
4
s'inscrit dans un tweet!
CincauHangus
19

Golfscript, 58 47 caractères

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

Grâce à Peter Taylor, le seppuku ne me laisse pas battre la solution Ruby! Exécutez le code jusqu'à 10 vous - même , et voici la preuve qu'il omet les quatre numéros dans une ligne .

Claudiu
la source
1
Économie facile: utilisez n+au lieu de ''+n. Je pense qu'il est dans les règles à utiliser un alphabet avec des caractères de contrôle, de sorte que vous pouvez également remplacer 65+avec 13+et enregistrer un autre personnage en nommant 13:^. Et je pense que cela 13,{ stuff [...]pourrait être 13,1/{ stuff 4*.
Peter Taylor
1
Ma pensée initiale était que les économies seraient réalisées via un filtre et qu’un peu de travail pourrait être fait. À partir 13,de peut être remplacé par {65+}%n+}%{ backtick {\4*/,}+78,1/%1-!},pour une économie totale de 8, sauvant la vie.
Peter Taylor
Tant que le personnage est physiquement visible, cela fonctionnera. Vraiment, vous pouvez même inclure des nouvelles lignes en tant que personnage. Tant qu'il y a une séquence de caractères.
CSturgess
@PeterTaylor: Vous êtes un gentleman et un érudit!
Claudiu
Après AAAMça devrait être AAABA, et pas BAAAB, non?
Mi-
18

Utilitaires de ligne de commande Bash + Linux, 43 octets

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

Ceci utilise une technique similaire à celle décrite ci-dessous, mais compte uniquement en base 16 et supprime tous les "noms" contenant 0, eou fégalement ceux comportant plus de 3 mêmes chiffres consécutifs.

Convertissez l'alphabet du moine comme suit:

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

Bash + coreutils (dc et egrep), 46 octets

Edit - version corrigée

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

Ça va prendre du temps à courir mais je pense que c'est correct.

dccompte décroissant de 14 ^ 9 à 1 et sorties en base 14. egrep filtre les nombres avec plus de 3 mêmes chiffres consécutifs. Nous filtrons également tous les noms avec des chiffres "0", nous obtenons donc le jeu de lettres correct dans les noms.

La question spécifie que n'importe quel alphabet peut être utilisé, donc j'utilise [1-9] [AD]. Mais pour tester, cela peut être transformé en [AM] en utilisant tr:

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

Cela donne la séquence:

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

Notez que cette dccommande nécessite la récursion de la queue pour fonctionner. Cela fonctionne sur la version DC 1.3.95 (Ubuntu 12.04) mais pas 1.3 (OSX Mavericks).

Trauma numérique
la source
10

APL (59)

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

Écrit dans son propre alphabet :) C'est un peu long. Cela prend également beaucoup de temps à courir avec 9, essayez-le avec un chiffre inférieur à tester si vous le souhaitez.

Explication:

  • {... }¨⍳9: pour chaque numéro de 1 à 9:
    • ⍳13*⍵: obtenir tous les nombres de 1 à 13^⍵
    • ¯1⌽: Tourner la liste à gauche par 1 (donc nous avons 13^⍵, 1, 2, ..., 13^⍵-1qui se transforme en 0, 1, 2 ...modulo 13^⍵).
    • (⍵/13)⊤: encoder chaque nombre en base 13 en utilisant des chiffres
    • ⎕A[1+... ]: en ajouter un (les tableaux sont indexés 1) et regarder dans ⎕A(l'alphabet)
    • ↓⍉: transforme la matrice en un vecteur de vecteurs le long des colonnes.
  • Z←⊃,/: joignez chaque vecteur intérieur de vecteurs, en nous donnant une liste de noms possibles (mais il ne respecte pas encore les règles).
  • {... : pour chaque nom, teste s'il respecte la règle des 4 caractères répétés:
    • 4/¨⎕A[⍳13]: pour chaque caractère, générer une chaîne de 4 de ce caractère
    • ⍷∘⍵¨: pour chaque chaîne, teste si elle est présente dans
    • ∨/,↑: prenez la logique ou de tous ces tests,
    • ~: et inversez-le, ce qui 1signifie qu'il respecte les règles et 0ne le fait pas.
  • Z/⍨: sélectionnez parmi Ztous les éléments qui répondent aux carburants
  • : afficher chacun sur une ligne séparée
marinus
la source
9
Je suis déçu. Compte tenu de sa réputation, on pourrait penser qu'APL disposerait d'une solution à un caractère, qu'aucun clavier ne pourrait taper.
Mark
7
@Mark, je suis certain qu'APL a cela, mais personne ne sait ce que le personnage est :)
Paul Draper
1
on devrait écrire ceci sur une pierre, et quand les futurs humains le découvriront, ils pourraient simplement penser que c'est juste un langage écrit primitif.
CincauHangus
9

Perl, 70 68 66 50 caractères

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

Usage:

$ perl -E 'code' > output_file

La bonne chose est que les impressions sont mises en mémoire tampon, de sorte que toutes les solutions à 1 caractère sont imprimées en premier, suivies des mots à 2 caractères, etc.

Zaid
la source
La meilleure chose à propos de cette solution est le bustier à gauche du 1.
Dan Hanly
8

Perl - 35 octets

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

Compter le shebang comme un octet.

Ceci est une traduction lâche de la réponse de l' histocrate .

A..1x9est un peu une bizarrerie; c'est un raccourci pour 'A'..'111111111'. L'accumulateur n'atteindra jamais la valeur finale (il ne contient que des lettres majuscules), mais il se terminera quand il dépassera 9 caractères. Cela peut être testé, par exemple, en utilisant à la 1x4place.

primo
la source
Le respect! Maintenant, pourquoi n'y ai-je pas pensé? ;)
Zaid
Notez que Ruby ne doit pas non plus créer la totalité de la plage pour pouvoir l'itérer. La seule raison pour laquelle le code dans mon commentaire nécessite une telle quantité de mémoire est qu'il transforme la plage en tableau (pour qu'il puisse l'utiliser Array#-).
Ventero
@ Ventero Ahh oui, grepje vais le faire. Je ne parle pas tout à fait Ruby.
dimanche
6

Pyg (Waaay trop long, pour une langue faite pour jouer au golf)

chuchotements : 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))))

Même si c'est proche de la façon dont je le ferais 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

Moins la complication de la longue ligne bien sûr;)

ıʇǝɥʇuʎs
la source
3

Pyth , 34 caractères

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

Explication:

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
la source
2

Python 2 - 212 octets

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
Zac Crites
la source
0

Japt , 21 octets

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

Essayez-le en ligne! (le lien ne calcule que jusqu'à 14**4.)

Comment ça fonctionne

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.

Suppose une implémentation ECMAScript 2017 standard en tant que couche JS (et suffisamment de mémoire pour stocker le tableau), où un Arrayobjet peut avoir une 2**53-1longueur maximale .

Barboteur
la source