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? – Boluc Papuccuoglu Jun 2 '14 at 11:21
Link to the story, for anyone interested. – ThatOneGuy Jun 2 '14 at 19:40
"The 11,459,252,883 Names of God"? It would be cool if the number of names were independently verified. It's 11,459,252,883 according to @edc65 's C answer, but the other answers appear too slow for this. (Except by actually enumerating the names, I don't know how to obtain the number.) – r.e.s. Jun 3 '14 at 13:00
Here it is! math.stackexchange.com/a/34292 – edc65 Jun 5 '14 at 18:34
@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...? – recursion.ninja Jun 27 '14 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. – CSturgess May 30 '14 at 19:49
@CSturgess Well, Ruby isn't the fastest language for this sort of thing out there... – BenjiWiebe May 31 '14 at 13:33
@BenjiWiebe But still faster than being handwritten by monks! – Turophile Jun 1 '14 at 22:24
Accepting this one because it has more votes. – CSturgess Jun 2 '14 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]/)` – Ventero Jun 2 '14 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 `#include`s? – Simon Kuang Jun 1 '14 at 4:33
@SimonKuang, some compilers will put basic ones (stdio) in automatically. – Paul Draper Jun 1 '14 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. – edc65 Jun 1 '14 at 7:15
fits into a tweet! – CincauHangus Jun 2 '14 at 9:47
+1 for almost certainly the fastest answer – Digital Trauma Jun 2 '14 at 15:21

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*`. – Peter Taylor May 30 '14 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. – Peter Taylor May 30 '14 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. – CSturgess May 30 '14 at 19:52
@PeterTaylor: You are a gentleman and a scholar! – Claudiu May 30 '14 at 20:07
After `AAAM` it should be `AAABA`, and not `BAAAB`, right? – justhalf Jun 2 '14 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 '14 at 5:32
@Mark, I am certain that APL does have that, but no one knows what the character is :) – Paul Draper Jun 1 '14 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. – CincauHangus Jun 2 '14 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. – Dan Hanly Jun 28 '14 at 13:02

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

-
+1 for good code, and introducing me to Pyg! – Lego Stormtroopr May 31 '14 at 13:21

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 '14 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#-`). – Ventero Jun 6 '14 at 16:01
@Ventero Ahh yes, `grep` will do that. I'm not entirely fluent in Ruby. – primo Jun 6 '14 at 16:40

This is not an answer, but 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:

``````def namecount(n):
#return a formula for the number of names with length <= n
#in terms of variable alphabet size k
var('k')
A,B,C = k,0,0
tot = A + B + C
for i in [2..n]:
a,b,c = (k-1)*(A + B + C), A, B
A,B,C = a,b,c
tot += A + B + C
return expand(tot)

print 'f(k) = ', namecount(9)
print 'f(13) = ', namecount(9).subs(k=13)
``````

Output:

``````f(k) =  k^9 + k^8 + k^7 - 5*k^6 + k^5 + k^4 + 4*k^3 - 2*k^2 + k
f(13) =  11459252883
``````
-

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