Die 9 Milliarden Namen Gottes

74

Die 9 Milliarden Namen Gottes ist eine Kurzgeschichte von Arthur C. Clarke. Es handelt von einer Gruppe tibetischer Mönche, deren Auftrag darin besteht, alle möglichen Namen Gottes in ihrem eigenen Alphabet aufzuschreiben. Im Wesentlichen widmen sie sich dem Schreiben jeder möglichen Permutation ihres Alphabets, eingeschränkt durch einige Regeln. In der Geschichte beauftragt das Kloster einige Ingenieure, ein Programm zu schreiben, um die ganze Arbeit für sie zu erledigen. Ihr Ziel ist es, dieses Programm zu schreiben.

Regeln:

  • Das Alphabet des Mönchs besteht aus 13 Zeichen (nach meinen Schätzungen). Sie können auch ABCDEFGHIJKLMeinen anderen Satz von 13 Zeichen verwenden.

  • Die Mindestlänge eines möglichen Namens beträgt 1 Zeichen. Die maximale Länge beträgt 9 Zeichen.

  • Kein Zeichen darf mehr als dreimal hintereinander wiederholt werden. AAABAist ein gültiger Name, aber AAAABnicht.

  • Ihr Programm sollte alle möglichen Namen in der Reihenfolge von Abis (in eine Datei) MMMLMMMLMausgeben, getrennt durch Zeichen, die nicht im Alphabet enthalten sind (Zeilenumbrüche, Semikolons usw.).

  • Dies ist Code-Golf, und Sie können jede Sprache verwenden. Die kürzeste Lösung bis zum 1. Juni 2014 gewinnt.

Bearbeiten: Die Namen sollten mit beginnen Aund mit enden und MMMLMMMLMnacheinander durch alle Milliarden von Namen gehen. Aber die jeweilige Reihenfolge liegt bei Ihnen. Sie können zuerst alle 1-Buchstaben-Namen, dann alle 2-Buchstaben-Namen usw. ausdrucken. Oder Sie können alle Namen ausdrucken, die mit A, dann alle mit Boder einem anderen Muster beginnen. Ein Mensch sollte jedoch in der Lage sein, die Datei zu lesen und zu bestätigen, dass sie alle da sind und in der von Ihnen gewählten logischen Reihenfolge, vorausgesetzt, sie haben die Zeit.

CSturgess
quelle
29
Versuchen Sie, das Universum zu beenden, Sir?
Boluc Papuccuoglu
8
Link zur Geschichte für alle Interessierten.
ThatOneGuy
1
Hier ist es! math.stackexchange.com/a/34292
edc65
1
Dies bestätigt, dass die Anzahl der Namen im vorliegenden Problem tatsächlich 11.459.252.883 beträgt (wie im C-Programm von edc65 zu finden ). Implementieren von Ross Millikan-Lösung bei MathSE erzeugt die folgende Polynom Formel für die Anzahl von Namen mit einer Länge von <= 9, für variable Alphabet Größe k: f(k) = k^9 + k^8 + k^7 - 5*k^6 + k^5 + k^4 + 4*k^3 - 2*k^2 + k. Sage Implementierung: goo.gl/0srwhq
res
3
@ edc65 Also 105.8GBalles gesagt und getan! Ich bin froh, dass die Sterne nicht ausgegangen sind ... oder müssen Sie die Liste ausdrucken, damit das passiert ...?
recursion.ninja

Antworten:

34

Rubin, 46

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

Meine ursprüngliche, ähnliche Lösung war länger und falsch (sie gab base13-Zahlen aus, die aufgrund führender Nullen nicht alle sind), aber ich lasse sie hier, weil sie trotzdem Stimmen erhalten hat.

1.upto(13**9){|i|(s=i.to_s 13)[/(.)\1{3}/]||puts(s)}
Histokrat
quelle
14
Nun, ich habe Ihren Code ungefähr eine Stunde lang ausgeführt und bis zu 2 Milliarden Namen und eine 21-GB-Textdatei erhalten, bevor ich sie gesehen und beendet habe. Ich habe unterschätzt, wie groß die Datei sein würde.
CSturgess
2
@CSturgess Nun, Ruby ist nicht die schnellste Sprache für diese Art von Dingen ...
BenjiWiebe
8
@BenjiWiebe Aber immer noch schneller als von Mönchen handgeschrieben zu werden!
Turophile
1
Akzeptiere dieses, weil es mehr Stimmen hat.
CSturgess
4
Dies nicht als separate Antwort zu posten, da es enorm viel Speicher benötigt (~ 30 TB, wenn meine Berechnung korrekt ist), aber theoretisch können Sie dies mitk=*?A..?M*9;puts k-k.grep(/(.)\1{3}|[N-Z]/)
Ventero
24

C 140 177 235

Guter alter prozeduraler Stil, keine Fantasie.
Es zählt (kein Schreiben) 11.459.252.883 Namen in 8 Minuten.
Nächste Bearbeitung mit Laufzeit und Größe der Namensdatei. Beobachten Sie den Himmel ...
Laufzeit 57 Minuten, Dateigröße 126.051.781.713 (9 Zeichen + CRLF pro Zeile). Bitte teilen Sie mir die E-Mail-Adresse der Mönche mit, damit ich ihnen die gezippte Datei zur manuellen Überprüfung zusenden kann ...

Bearbeiten Golf ein wenig mehr, überarbeitet den Scheck für wiederholte Briefe.
Immer noch nicht die kürzeste, aber immerhin bricht diese ab und erzeugt die gewünschte Ausgabe.
Laufzeit 51 min, Dateigröße 113.637.155.697 (diesmal keine führenden Leerzeichen)

Eine Randnotiz: Offensichtlich ist die Ausgabedatei sehr komprimierbar, dennoch musste ich 7zip beenden, nachdem ich 36 Stunden gearbeitet hatte, waren es 70%. Seltsam.

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
quelle
nein #includes?
Simon Kuang
@SimonKuang, einige Compiler werden die grundlegenden (stdio) automatisch einfügen.
Paul Draper
1
@ Simon es ist C-Standard. Standardmäßig sind globale Objekte int und globale Funktionen geben int zurück. Visual Studio gibt eine C4013-Warnung über nicht definierte Puts aus, die aber trotzdem gültig ist.
edc65
4
passt in einen Tweet!
CincauHangus
19

Golfscript, 58 47 Zeichen

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

Dank Peter Taylor bleibt mir der Seppuku erspart, die Ruby-Lösung nicht zu schlagen! Führen Sie den Code selbst auf 10 ein , und hier ist der Beweis, dass die Vier-in-einer-Reihe-Zahlen übersprungen werden .

Claudiu
quelle
1
Einfaches Speichern: Verwenden Sie n+anstelle von ''+n. Ich denke , es innerhalb der Regeln ist ein Alphabet mit Steuerzeichen zu verwenden, so dass Sie könnte auch ersetzen 65+mit 13+und ein anderes Zeichen speichern , indem Namensgebung 13:^. Und ich denke das 13,{ stuff [...]könnte sein 13,1/{ stuff 4*.
Peter Taylor
1
Mein erster Gedanke war, dass das Speichern über einen Filter erfolgen würde und mit ein wenig Arbeit erledigt werden kann. Ab 13,sofort kann durch {65+}%n+}%{ backtick {\4*/,}+78,1/%1-!},eine Gesamtsparung von 8 ersetzt werden, um Ihr Leben zu retten.
Peter Taylor
Solange der Charakter etwas ist, das Sie physisch sehen können, funktioniert es. Wirklich, Sie könnten sogar Zeilenumbrüche als Zeichen einfügen. Nur solange es eine Sequenz zu den Charakteren gibt.
CSturgess
@ PeterTaylor: Sie sind ein Gentleman und ein Gelehrter!
Claudiu
Nachdem AAAMes sein sollte AAABAund nicht BAAAB, richtig?
Nur die Hälfte des
18

Bash + Linux Kommandozeilen-Utils, 43 Bytes

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

Dieser verwendet eine ähnliche Technik , um meine Antwort unten, sondern zählt nur in der Basis 16 und abstreift alle „Namen“ enthalten 0, eoder fauch solche mit mehr als drei gleichen aufeinanderfolgende Ziffern.

So konvertieren Sie in das Mönchsalphabet:

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

Bash + Coreutils (dc und egrep), 46 Bytes

Edit - korrigierte Version

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

Das wird eine Weile dauern, aber ich denke, es ist richtig.

dczählt von 14 ^ 9 auf 1 abwärts und gibt in Basis 14 aus. egrep filtert die Zahlen mit mehr als 3 aufeinanderfolgenden gleichen Ziffern heraus. Wir filtern auch alle Namen mit "0" -Ziffern heraus, damit wir den richtigen Satz von Buchstaben in den Namen erhalten.

Die Frage gibt an, dass jedes Alphabet verwendet werden kann, also verwende ich [1-9] [AD]. Zum Testen kann dies jedoch mit tr in [AM] umgewandelt werden:

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

Dies ergibt die Folge:

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

Beachten Sie, dass für diesen dcBefehl eine Schwanzrekursion erforderlich ist. Dies funktioniert mit der DC-Version 1.3.95 (Ubuntu 12.04), jedoch nicht mit der Version 1.3 (OSX Mavericks).

Digitales Trauma
quelle
10

APL (59)

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

Geschrieben in seinem eigenen Alphabet :) Es ist ein bisschen lang. Das Ausführen dauert auch sehr lange. 9Probieren Sie es mit einer niedrigeren Nummer aus, um zu testen, ob Sie dies möchten.

Erläuterung:

  • {... }¨⍳9: für jede Zahl von 1 bis 9:
    • ⍳13*⍵: Erhalte alle Zahlen von 1 bis 13^⍵
    • ¯1⌽: Die Liste nach links um 1 drehen (so haben wir 13^⍵, 1, 2, ..., 13^⍵-1, die sich in die Kurven 0, 1, 2 ...Modulo 13^⍵).
    • (⍵/13)⊤: Kodiere jede Zahl in Basis 13 mit Ziffern
    • ⎕A[1+... ]: Addiere eins (Arrays sind 1-indiziert) und schaue in ⎕A(dem Alphabet) nach
    • ↓⍉: verwandle die Matrix in einen Vektor von Vektoren entlang der Spalten.
  • Z←⊃,/: Füge jeden inneren Vektor von Vektoren zusammen und gib uns eine Liste möglicher Namen (aber er entspricht noch nicht den Regeln).
  • {... : Teste für jeden Namen, ob er der 4-Wiederholungs-Zeichen-Regel entspricht:
    • 4/¨⎕A[⍳13]: Erzeugt für jedes Zeichen eine Zeichenfolge mit 4 Zeichen
    • ⍷∘⍵¨: Testen Sie für jede Zeichenfolge, ob sie in vorhanden ist
    • ∨/,↑: Nehmen Sie die logische oder alle diese Tests,
    • ~: und invertiere es, was 1bedeutet, dass es den Regeln entspricht und 0dass es nicht den Regeln entspricht.
  • Z/⍨: Wähle aus Zallen Elementen, die auf die Ruinen treffen
  • : Zeigen Sie jeden in einer separaten Zeile an
Marinus
quelle
9
Ich bin enttäuscht. Aufgrund seiner Reputation würde man denken, dass APL dafür eine Ein-Zeichen-Lösung haben würde, die keine Tastatur eingeben könnte.
Mark
7
@ Mark, ich bin sicher, dass APL das hat, aber niemand weiß, was der Charakter ist :)
Paul Draper
1
man sollte dies auf einen Stein schreiben, und wenn zukünftige Menschen dies finden, denken sie vielleicht, es sei nur primitive geschriebene Sprache.
CincauHangus
9

Perl, 70 68 66 50 Zeichen

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

Verwendungszweck:

$ perl -E 'code' > output_file

Das Schöne ist, dass die Ausdrucke gepuffert sind, sodass zuerst alle Lösungen mit einem Zeichen gedruckt werden, gefolgt von Wörtern mit zwei Zeichen und so weiter.

Zaid
quelle
Das Beste an dieser Lösung ist der Busen links vom 1.
Dan Hanly
8

Perl - 35 Bytes

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

Den Shebang als ein Byte zählen.

Dies ist eine lose Übersetzung der Antwort des Histokraten .

A..1x9ist ein bisschen seltsam; Dies ist eine Abkürzung für 'A'..'111111111'. Der Akku erreicht nie den Endwert (er enthält nur Großbuchstaben), wird jedoch trotzdem beendet, sobald er länger als 9 Zeichen ist. Dies kann beispielsweise mit getestet werden 1x4.

primo
quelle
Respekt! Warum habe ich nicht daran gedacht? ;)
Zaid
Beachten Sie, dass Ruby nicht den gesamten Bereich erstellen muss, um ihn zu durchlaufen. Der einzige Grund, warum der Code in meinem Kommentar so viel Speicher benötigt, ist, dass er den Bereich in ein Array verwandelt (damit er verwendet werden kann Array#-).
Ventero
@Ventero Ahh ja, grepwerde das machen. Ich spreche nicht ganz fließend Ruby.
Primo
6

Pyg (Waaay zu lang, für eine Sprache zum Golfen gemacht)

Flüstern : 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))))

Auch wenn dies in etwa so ist, wie ich es in Python machen würde:

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

Abzüglich der langen Wartezeit natürlich;)

ɐɔıɐɔuʇǝɥʇs
quelle
3

Pyth , 34 Zeichen

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

Erläuterung:

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
quelle
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
Zac Crites
quelle
0

Japt , 21 Bytes

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

Probieren Sie es online! (Der Link berechnet nur bis zu 14**4.)

Wie es funktioniert

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.

Es wird eine Standardimplementierung von ECMAScript 2017 als JS-Ebene (und genügend Speicher zum Speichern des Arrays) vorausgesetzt, in der ein ArrayObjekt maximal 2**53-1lang sein kann.

Bubbler
quelle