The 9 Billion Names of God

Question

The 9 Billion Names of God is a short story by Arthur C. Clarke. It's about a group of Tibetan monks whose order is devoted to writing down all the possible names of God, written in their own alphabet. Essentially, they are devoted to writing every possible permutation of their alphabet, restricted by a few rules. In the story, the monastery hires some engineers to write a program to do all the work for them. Your goal is to write that program.

Rules:

• The monk's alphabet uses 13 characters (according to my estimations). You may use ABCDEFGHIJKLM or some other set of 13 characters.

• The minimum length of a possible name is 1 character. The maximum length is 9 characters.

• No character may repeat more than 3 times in succession. AAABA is a valid name, but AAAAB is not.

• Your program should print out (to a file) every possible name in sequence from A to MMMLMMMLM, separated by any character not in the alphabet (newlines, semi-colons, whatever).

• This is code-golf, and you can use any language. The shortest solution by June 1st 2014 wins.

Edit: The names should start with A and end with MMMLMMMLM, progressing through all the billions of names sequentially. But the particular sequence is up to you. You can print out all the 1-letter names first, then all the 2-letter names, etc. Or you can print all the names starting with A, then all the ones starting with B, or some other pattern. But a human should be able to read through the file and confirm they are all there and in whatever logical order you choose, assuming they have the time.

Answer 1

Ruby, 46

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

My original, similar solution was longer and wrong (it output base13 numbers, which isn't quite all of them due to leading zeroes), but I'll leave it here because it got votes anyway.

1.upto(13**9){|i|(s=i.to_s 13)[/(.)\1{3}/]||puts(s)}

Answer 2

C 140 177 235

Good old procedural style, no fancyness.
It counts (no write) 11,459,252,883 names in 8 minutes.
Next edit with the runtime and size of names file. Watch the sky...
Runtime 57 minutes, file size 126,051,781,713 (9 chars+crlf per row). Please tell me the monks' email address, so that I can send them the zipped file, for manual check...

Edit Golfed a little more, reworked the check for repeated letters.
Still not the shortest, but at least this one terminates and generates the required output.
Runtime 51 min, file size 113,637,155,697 (no leading blanks this time)

A side note: obviously the output file is very compressible, still I had to kill 7zip, after working 36 hours it was at 70%. Weird.

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

Answer 3

Golfscript, 58 47 characters

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

Thanks to Peter Taylor, I am spared from the seppuku from not beating the Ruby solution! Run the code up to 10 yourself, and here is proof it skips the four-in-a-row numbers.

Answer 4

Bash+Linux command line utils, 43 bytes

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

This uses a similar technique to my answer below, but just counts in base 16, and strips out all "names" containing 0, e or f as well those with more than 3 same consecutive digits.

Convert to the monk's alphabet as follows:

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

---

Bash+coreutils (dc and egrep), 46 bytes

Edit - corrected version

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

This'll take a while to run but I think its correct.

dc counts downwards from 14^9 to 1 and outputs in base 14. egrep filters out the numbers with more than 3 consecutive same digits. We also filter out any names with "0" digits, so we get the correct set of letters in the names.

The question specifies that any alphabet may be used, so I am using [1-9][A-D]. But for testing, this can be transformed to [A-M] using tr:

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

This yields the sequence:

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

Note this dc command requires tail recursion to work. This works on dc version 1.3.95 (Ubuntu 12.04) but not 1.3 (OSX Mavericks).

Answer 5

APL (59)

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

Written in its own alphabet :) It's a bit long. It also takes a long time to run with 9, try it with a lower number to test if you want.

Explanation:

• {...}¨⍳9: for each number ⍵ from 1 to 9:
  • ⍳13*⍵: get all numbers from 1 to 13^⍵
  • ¯1⌽: rotate the list to the left by 1 (so we have 13^⍵, 1, 2, ..., 13^⍵-1, which turns into 0, 1, 2 ... modulo 13^⍵).
  • (⍵/13)⊤: encode each number in base 13 using ⍵ digits
  • ⎕A[1+...]: add one (arrays are 1-indexed) and look up in ⎕A (the alphabet)
  • ↓⍉: turn the matrix into a vector of vectors along the columns.
• Z←⊃,/: join each inner vector of vectors together, giving us a list of possible names (but it doesn't meet the rules yet).
• {...}¨: for each name, test if it meets the 4-repeated-chars rule:
  • 4/¨⎕A[⍳13]: for each character, generate a string of 4 of that character
  • ⍷∘⍵¨: for each string, test if it is present in ⍵
  • ∨/,↑: take the logical or of all these tests,
  • ~: and invert it, so that 1 means that it meets the rules and 0 means it doesn't.
• Z/⍨: select from Z all the elements that meet the ruels
• ↑: display each one on a separate line

Answer 6

Perl, 70 68 66 50 characters

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

Usage:

$ perl -E 'code' > output_file

The nice thing is that the prints are buffered, so you get all 1-character solutions printed first, followed by 2-character words and so on.

Answer 7

Perl - 35 bytes

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

Counting the shebang as one byte.

This is a loose translation of histocrat's answer.

A..1x9 is a bit of an oddity; this is shorthand for 'A'..'111111111'. The accumulator will never actually reach the terminal value (it contains only upper-case letters), but it will still terminate once it becomes longer than 9 characters long. This can be tested, for example, by using 1x4 instead.

Answer 8

Pyg (Waaay too long, for a language made for golfing)

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

Even though this is close to how I would actually do it in 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

Minus the long line complication of course ;)

Answer 9

Pyth, 34 characters

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

Explanation:

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

Answer 10

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

Answer 11

Japt, 21 bytes

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

Try it online! (the link only computes up to 14**4.)

How it works

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.

Assumes a standard ECMAScript 2017 implementation as the JS layer (and enough memory to store the array), where an Array object can have maximum of 2**53-1 length.