# The 9 Billion Names of God

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.

• Are you trying to end the universe, sir? Jun 2, 2014 at 11:21
• Link to the story, for anyone interested. Jun 2, 2014 at 19:40
• Here it is! math.stackexchange.com/a/34292 Jun 5, 2014 at 18:34
• This verifies that the number of names in the present problem is indeed 11,459,252,883 (as found in edc65's C program). Implementing Ross Millikan's solution at MathSE generates the following polynomial formula for the number of names with length <= 9, for variable alphabet size k: f(k) = k^9 + k^8 + k^7 - 5*k^6 + k^5 + k^4 + 4*k^3 - 2*k^2 + k. Sage implementation: goo.gl/0srwhq Jun 6, 2014 at 4:01
• @edc65 So 105.8GB all said and done! I'm glad the stars didn't go out... or maybe you have to print the list for that to happen...? Jun 27, 2014 at 16:53

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

• Well I ran your code for about an hour and got up to 2 billion names and a 21 GB text file before seeing this and quitting it. I underestimated just how large the file would be. May 30, 2014 at 19:49
• @CSturgess Well, Ruby isn't the fastest language for this sort of thing out there... May 31, 2014 at 13:33
• @BenjiWiebe But still faster than being handwritten by monks! Jun 1, 2014 at 22:24
• Accepting this one because it has more votes. Jun 2, 2014 at 14:21
• Not posting this as a separate answer, as it requires an immensely huge amount of memory (~30 TB, if my calculation is correct), but in theory you can shorten this to 43 characters with k=*?A..?M*9;puts k-k.grep(/(.)\1{3}|[N-Z]/) Jun 2, 2014 at 19:24

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

• no #includes? Jun 1, 2014 at 4:33
• @SimonKuang, some compilers will put basic ones (stdio) in automatically. Jun 1, 2014 at 6:50
• @Simon it's C standard. By default, global objects are int and global functions return int. Visual studio outputs C4013 warning about 'puts' not defined, but it's valid anyway. Jun 1, 2014 at 7:15
• fits into a tweet! Jun 2, 2014 at 9:47

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

• Easy saving: use n+ instead of ''+n. I think it's within the rules to use an alphabet with control characters, so you could also replace 65+ with 13+ and save another character by naming 13:^. And I think that 13,{ stuff [...] could be 13,1/{ stuff 4*. May 30, 2014 at 19:35
• My initial thought was that the saving would be via a filter, and with a bit of work it can be done. From 13, on can be replaced with {65+}%n+}%{ backtick {\4*/,}+78,1/%1-!}, for a total saving of 8, saving your life. May 30, 2014 at 19:46
• As long as the character is something that you can physically see, it will work. Really you could even include newlines as a character. Just so long as there's a sequence to the characters. May 30, 2014 at 19:52
• @PeterTaylor: You are a gentleman and a scholar! May 30, 2014 at 20:07
• After AAAM it should be AAABA, and not BAAAB, right? Jun 2, 2014 at 4:08

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

## 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
• I'm disappointed. Given its reputation, you'd think APL would have a one-character solution for this, that no keyboard could type.
– Mark
Jun 1, 2014 at 5:32
• @Mark, I am certain that APL does have that, but no one knows what the character is :) Jun 1, 2014 at 6:49
• one should write this onto a stone, and when future humans find this, they might just think it's just primitive written language. Jun 2, 2014 at 9:51

# Perl, 706866 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.

• The best thing about this solution is the boob to the left of the 1. Jun 28, 2014 at 13:02

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

• Respect! Now why didn't I think of that? ;)
– Zaid
Jun 6, 2014 at 10:07
• Note that Ruby doesn't have to create the entire range in order to iterate it, either. The only reason the code in my comment requires such a huge amount of memory is that it turns the range into an Array (so that it can use Array#-). Jun 6, 2014 at 16:01
• @Ventero Ahh yes, grep will do that. I'm not entirely fluent in Ruby. Jun 6, 2014 at 16:40

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

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


# 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


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