Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
20  
Are you trying to end the universe, sir? –  Boluc Papuccuoglu Jun 2 at 11:21
4  
Link to the story, for anyone interested. –  user1895420 Jun 2 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 at 13:00
1  
Here it is! math.stackexchange.com/a/34292 –  edc65 Jun 5 at 18:34
2  
@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...? –  awashburn Jun 27 at 16:53

10 Answers 10

up vote 29 down vote accepted

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)}
share|improve this answer
11  
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 at 19:49
2  
@CSturgess Well, Ruby isn't the fastest language for this sort of thing out there... –  BenjiWiebe May 31 at 13:33
8  
@BenjiWiebe But still faster than being handwritten by monks! –  Turophile Jun 1 at 22:24
1  
Accepting this one because it has more votes. –  CSturgess Jun 2 at 14:21
4  
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 at 19:24

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.

share|improve this answer
1  
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 at 19:35
1  
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 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 at 19:52
    
@PeterTaylor: You are a gentleman and a scholar! –  Claudiu May 30 at 20:07
    
After AAAM it should be AAABA, and not BAAAB, right? –  justhalf Jun 2 at 4:08

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);
            }
        }
    }
}
share|improve this answer
    
no #includes? –  Simon Kuang Jun 1 at 4:33
    
@SimonKuang, some compilers will put basic ones (stdio) in automatically. –  Paul Draper Jun 1 at 6:50
1  
@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 at 7:15
3  
fits into a tweet! –  CincauHangus Jun 2 at 9:47
1  
+1 for almost certainly the fastest answer –  DigitalTrauma Jun 2 at 15:21

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

share|improve this answer

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
share|improve this answer
9  
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 at 5:32
6  
@Mark, I am certain that APL does have that, but no one knows what the character is :) –  Paul Draper Jun 1 at 6:49
1  
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 at 9:51

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.

share|improve this answer
    
The best thing about this solution is the boob to the left of the 1. –  Dan Hanly Jun 28 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 ;)

share|improve this answer
    
+1 for good code, and introducing me to Pyg! –  Lego Stormtroopr May 31 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.

share|improve this answer
    
Respect! Now why didn't I think of that? ;) –  Zaid Jun 6 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 at 16:01
    
@Ventero Ahh yes, grep will do that. I'm not entirely fluent in Ruby. –  primo Jun 6 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
share|improve this answer

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))
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.