9 Miliar Nama Tuhan

74

The 9 Billion Names of God adalah cerita pendek oleh Arthur C. Clarke. Ini tentang sekelompok bhikkhu Tibet yang perintahnya ditujukan untuk menuliskan semua kemungkinan nama Tuhan, ditulis dalam alfabet mereka sendiri. Pada dasarnya, mereka dikhususkan untuk menulis setiap permutasi yang mungkin dari alfabet mereka, dibatasi oleh beberapa aturan. Dalam cerita itu, biara mempekerjakan beberapa insinyur untuk menulis sebuah program untuk melakukan semua pekerjaan untuk mereka. Tujuan Anda adalah menulis program itu.

Aturan:

  • Alfabet biarawan menggunakan 13 karakter (menurut perkiraan saya). Anda dapat menggunakan ABCDEFGHIJKLMatau set 13 karakter lainnya.

  • Panjang minimum nama yang mungkin adalah 1 karakter. Panjang maksimal adalah 9 karakter.

  • Tidak ada karakter yang dapat diulang lebih dari 3 kali berturut-turut. AAABAadalah nama yang valid, tetapi AAAABtidak.

  • Program Anda harus mencetak (untuk file) setiap nama yang mungkin secara berurutan dari Ake MMMLMMMLM, dipisahkan oleh karakter apapun tidak dalam abjad (baris baru, semi-titik dua, apa pun).

  • Ini adalah kode-golf, dan Anda dapat menggunakan bahasa apa pun. Solusi terpendek pada 1 Juni 2014 menang.

Sunting: Nama-nama harus dimulai dengan Adan diakhiri dengan MMMLMMMLM, berlanjut melalui semua miliaran nama secara berurutan. Tetapi urutan tertentu terserah Anda. Anda dapat mencetak semua nama 1-huruf terlebih dahulu, lalu semua nama 2-huruf, dll. Atau Anda dapat mencetak semua nama yang dimulai dengan A, kemudian semua yang dimulai dengan B, atau beberapa pola lainnya. Tetapi manusia harus dapat membaca file dan mengkonfirmasi mereka semua ada di sana dan dalam urutan logis apa pun yang Anda pilih, dengan asumsi mereka punya waktu.

CSturgess
sumber
29
Apakah Anda mencoba mengakhiri alam semesta, tuan?
Boluc Papuccuoglu
8
Tautan ke cerita , untuk siapa saja yang tertarik.
ThatOneGuy
1
Ini memverifikasi bahwa jumlah nama dalam masalah ini memang 11.459.252.883 (seperti yang ditemukan dalam program C edc65 ). Pelaksana solusi Ross Millikan di MathSE menghasilkan rumus polinomial berikut untuk jumlah nama-nama dengan panjang <= 9, untuk variabel alfabet ukuran k: f(k) = k^9 + k^8 + k^7 - 5*k^6 + k^5 + k^4 + 4*k^3 - 2*k^2 + k. Implementasi bijak: goo.gl/0srwhq
res
3
@ edc65 Jadi 105.8GBsemuanya dikatakan dan dilakukan! Saya senang bintang-bintang tidak keluar ... atau mungkin Anda harus mencetak daftar untuk itu terjadi ...?
recursion.ninja

Jawaban:

34

Ruby, 46

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

Solusi orisinal saya, yang serupa lebih panjang dan salah (menghasilkan angka base13, yang tidak semuanya karena angka nol), tapi saya akan meninggalkannya di sini karena tetap mendapat suara.

1.upto(13**9){|i|(s=i.to_s 13)[/(.)\1{3}/]||puts(s)}
histokrat
sumber
14
Yah saya menjalankan kode Anda selama sekitar satu jam dan mendapatkan hingga 2 miliar nama dan file teks 21 GB sebelum melihat ini dan berhenti. Saya meremehkan seberapa besar file tersebut.
CSturgess
2
@CSturgess Nah, Ruby bukan bahasa tercepat untuk hal semacam ini di luar sana ...
BenjiWiebe
8
@BenjiWiebe Tapi masih lebih cepat daripada tulisan tangan oleh para biarawan!
Turophile
1
Menerima yang ini karena memiliki lebih banyak suara.
CSturgess
4
Tidak memposting ini sebagai jawaban terpisah, karena membutuhkan memori yang sangat besar (~ 30 TB, jika perhitungan saya benar), tetapi secara teori Anda dapat mempersingkat ini menjadi 43 karakter dengank=*?A..?M*9;puts k-k.grep(/(.)\1{3}|[N-Z]/)
Ventero
24

C 140 177 235

Gaya prosedural lama yang bagus, tidak ada kemewahan.
Itu menghitung (tanpa menulis) 11.459.252.883 nama dalam 8 menit.
Sunting selanjutnya dengan runtime dan ukuran file nama. Saksikan langit ...
Runtime 57 menit, ukuran file 126.051.781.713 (9 karakter + crlf per baris). Tolong beritahu saya alamat email para biarawan, sehingga saya dapat mengirim mereka file zip, untuk pemeriksaan manual ...

Sunting Golf sedikit lagi, ulang cek untuk surat berulang.
Masih bukan yang terpendek, tapi setidaknya yang ini mengakhiri dan menghasilkan output yang diperlukan.
Runtime 51 mnt, ukuran file 113.637.155.697 (kali ini tidak ada yang kosong)

Catatan tambahan: jelas file outputnya sangat kompresibel, masih saya harus mematikan 7zip, setelah bekerja 36 jam ternyata sudah di 70%. Aneh.

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

Tidak disatukan

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
sumber
tidak #include?
Simon Kuang
@SimonKuang, beberapa kompiler akan memasukkan yang dasar (stdio) secara otomatis.
Paul Draper
1
@Simon itu standar C. Secara default, objek global adalah int dan fungsi global mengembalikan int. Visual studio menampilkan peringatan C4013 tentang 'menempatkan' tidak didefinisikan, tapi tetap valid.
edc65
4
cocok dengan tweet!
CincauHangus
19

Golfscript, 58 47 karakter

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

Terima kasih kepada Peter Taylor, saya terhindar dari seppuku karena tidak mengalahkan solusi Ruby! Jalankan kode hingga 10 sendiri , dan ini buktinya melompati angka empat-dalam-baris .

Claudiu
sumber
1
Mudah disimpan: gunakan n+sebagai ganti ''+n. Saya pikir itu dalam aturan untuk menggunakan alfabet dengan karakter kontrol, jadi Anda juga bisa mengganti 65+dengan 13+dan menyimpan karakter lain dengan penamaan 13:^. Dan saya pikir itu 13,{ stuff [...]bisa terjadi 13,1/{ stuff 4*.
Peter Taylor
1
Pikiran awal saya adalah bahwa penghematan akan dilakukan melalui filter, dan dengan sedikit kerja dapat dilakukan. Dari 13,pada dapat diganti dengan {65+}%n+}%{ backtick {\4*/,}+78,1/%1-!},untuk penghematan total 8, menyelamatkan hidup Anda.
Peter Taylor
Selama karakter adalah sesuatu yang secara fisik dapat Anda lihat, itu akan berhasil. Benar-benar Anda bahkan dapat memasukkan baris baru sebagai karakter. Asal ada urutan karakter.
CSturgess
@PeterTaylor: Anda adalah pria terhormat dan terpelajar!
Claudiu
Setelah AAAMitu harus AAABA, dan tidak BAAAB, kan?
justhalf
18

Utilitas baris perintah Bash + Linux, 43 byte

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

Ini menggunakan teknik yang mirip dengan jawaban saya di bawah ini, tetapi hanya menghitung di basis 16, dan menghapus semua "nama" yang mengandung 0, eatau fjuga yang memiliki lebih dari 3 digit berturut-turut yang sama.

Konversikan ke alfabet biarawan sebagai berikut:

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

Bash + coreutils (dc dan egrep), 46 byte

Edit - versi yang diperbaiki

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

Ini akan membutuhkan waktu untuk berjalan tetapi saya pikir itu benar.

dcmenghitung mundur dari 14 ^ 9 ke 1 dan output di basis 14. egrep menyaring angka-angka dengan lebih dari 3 digit yang sama berturut-turut. Kami juga memfilter nama apa pun dengan angka "0", jadi kami mendapatkan set huruf yang benar dalam nama tersebut.

Pertanyaan menentukan bahwa alfabet apa pun dapat digunakan, jadi saya menggunakan [1-9] [AD]. Tetapi untuk pengujian, ini dapat diubah menjadi [AM] menggunakan tr:

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

Ini menghasilkan urutan:

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

Perhatikan dcperintah ini membutuhkan rekursi ekor untuk bekerja. Ini berfungsi pada dc versi 1.3.95 (Ubuntu 12.04) tetapi tidak 1.3 (OSX Mavericks).

Trauma Digital
sumber
10

APL (59)

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

Ditulis dalam alfabet sendiri :) Agak panjang. Ini juga membutuhkan waktu lama untuk dijalankan 9, coba dengan angka yang lebih rendah untuk menguji jika Anda mau.

Penjelasan:

  • {... }¨⍳9: untuk setiap nomor dari 1 hingga 9:
    • ⍳13*⍵: dapatkan semua angka dari 1 hingga 13^⍵
    • ¯1⌽: Memutar daftar ke kiri oleh 1 (jadi kita harus 13^⍵, 1, 2, ..., 13^⍵-1, yang berubah menjadi 0, 1, 2 ...modulo 13^⍵).
    • (⍵/13)⊤: menyandikan setiap angka dalam basis 13 menggunakan digit
    • ⎕A[1+... ]: tambahkan satu (array berindeks 1) dan cari ⎕A(alfabet)
    • ↓⍉: ubah matriks menjadi vektor vektor di sepanjang kolom.
  • Z←⊃,/: gabungkan setiap vektor vektor bagian dalam bersama-sama, berikan kami daftar nama yang mungkin (tetapi belum memenuhi aturan).
  • {... : untuk masing-masing nama, uji apakah itu memenuhi aturan 4-berulang-karakter:
    • 4/¨⎕A[⍳13]: untuk setiap karakter, hasilkan string 4 dari karakter itu
    • ⍷∘⍵¨: untuk setiap string, uji jika ada
    • ∨/,↑: ambil yang logis atau dari semua tes ini,
    • ~: dan balikkan, jadi itu 1berarti memenuhi aturan dan 0berarti tidak.
  • Z/⍨: pilih dari Zsemua elemen yang memenuhi reruntuhan
  • : tampilkan masing-masing pada baris yang terpisah
marinus
sumber
9
Saya kecewa. Mengingat reputasinya, Anda akan berpikir APL akan memiliki solusi satu karakter untuk ini, yang tidak dapat diketik oleh keyboard.
Tandai
7
@ Mark, saya yakin APL memang memilikinya, tetapi tidak ada yang tahu karakternya :)
Paul Draper
1
orang harus menulis ini di atas batu, dan ketika manusia masa depan menemukan ini, mereka mungkin berpikir itu hanya bahasa tulisan primitif.
CincauHangus
9

Perl, 70 68 66 50 karakter

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

Pemakaian:

$ perl -E 'code' > output_file

Yang menyenangkan adalah bahwa cetakannya buffer, sehingga Anda mendapatkan semua solusi 1-karakter dicetak terlebih dahulu, diikuti oleh kata-kata 2-karakter dan seterusnya.

Zaid
sumber
Hal terbaik tentang solusi ini adalah dada di sebelah kiri 1.
Dan Hanly
8

Perl - 35 byte

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

Menghitung shebang sebagai satu byte.

Ini adalah terjemahan longgar dari jawaban histokrat .

A..1x9sedikit aneh; ini adalah singkatan 'A'..'111111111'. Akumulator tidak akan pernah benar-benar mencapai nilai terminal (hanya berisi huruf besar), tetapi masih akan berakhir begitu panjangnya menjadi lebih dari 9 karakter. Ini dapat diuji, misalnya, dengan menggunakan 1x4sebagai gantinya.

primo
sumber
Menghormati! Sekarang mengapa saya tidak memikirkan itu? ;)
Zaid
Perhatikan bahwa Ruby tidak harus membuat seluruh rentang untuk mengulanginya juga. Satu-satunya alasan kode dalam komentar saya memerlukan jumlah memori yang sangat besar adalah karena ia mengubah rentang menjadi Array (sehingga dapat digunakan Array#-).
Ventero
@Ventero Ahh ya, grepakan melakukannya. Saya tidak sepenuhnya fasih di Ruby.
Primo
6

Pyg (Waaay terlalu lama, untuk bahasa yang dibuat untuk golf)

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

Meskipun ini dekat dengan bagaimana saya benar-benar akan melakukannya dengan 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 komplikasi garis panjang tentu saja;)

ɐɔıʇǝɥʇu
sumber
3

Pyth , 34 karakter

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

Penjelasan:

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
sumber
2

Python 2 - 212 byte

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
sumber
0

Japt , 21 byte

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

Cobalah online! (tautan hanya menghitung hingga 14**4.)

Bagaimana itu bekerja

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.

Mengasumsikan implementasi ECMAScript 2017 standar sebagai lapisan JS (dan cukup memori untuk menyimpan array), di mana Arrayobjek dapat memiliki 2**53-1panjang maksimum .

Bubbler
sumber