9 miliardów imion Boga

74

9 miliardów imion Boga to krótka historia Arthura C. Clarke'a. Chodzi o grupę tybetańskich mnichów, których porządek poświęcony jest spisaniu wszystkich możliwych imion Boga, zapisanych własnym alfabetem. Zasadniczo poświęcają się pisaniu każdej możliwej permutacji swojego alfabetu, ograniczonej kilkoma zasadami. W opowieści klasztor zatrudnia inżynierów, aby napisali program, który wykona za nich całą pracę. Twoim celem jest napisanie tego programu.

Zasady:

  • Alfabet mnicha używa 13 znaków (według moich szacunków). Możesz użyć ABCDEFGHIJKLMlub innego zestawu 13 znaków.

  • Minimalna długość możliwej nazwy to 1 znak. Maksymalna długość wynosi 9 znaków.

  • Żadna postać nie może powtarzać więcej niż 3 razy z rzędu. AAABAjest prawidłową nazwą, ale AAAABnie jest.

  • Twój program powinien wydrukować (do pliku) każdą możliwą nazwę w kolejności od Ado MMMLMMMLM, oddzieloną dowolnym znakiem spoza alfabetu (znaki nowej linii, średniki, cokolwiek).

  • To jest golf golfowy i możesz używać dowolnego języka. Najkrótsze rozwiązanie do 1 czerwca 2014 wygrywa.

Edycja: nazwy powinny zaczynać się Ai kończyć MMMLMMMLM, przechodząc kolejno przez wszystkie miliardy nazw. Ale konkretna sekwencja należy do ciebie. Możesz wydrukować najpierw wszystkie 1-literowe nazwy, a następnie wszystkie 2-literowe nazwy itp. Lub możesz wydrukować wszystkie nazwy zaczynające się od A, a następnie wszystkie zaczynające się od Blub inny wzór. Ale człowiek powinien być w stanie odczytać plik i potwierdzić, że wszystko tam jest i w dowolnej logicznej kolejności, którą wybierzesz, zakładając, że ma czas.

CSturgess
źródło
29
Próbujesz zakończyć wszechświat, proszę pana?
Boluc Papuccuoglu
8
Link do historii dla wszystkich zainteresowanych.
ThatOneGuy
1
Oto jest! math.stackexchange.com/a/34292
edc65
1
To weryfikuje, że liczba nazw w obecnym problemie rzeczywiście wynosi 11 459 252 883 (jak stwierdzono w programie C edc65 ). Wykonawczego roztwór Ross Millikana jest w MathSE generuje następującego wielomianu wzoru na wielu nazw o długości <= 9, dla zmiennej alfabetu wielkości k: f(k) = k^9 + k^8 + k^7 - 5*k^6 + k^5 + k^4 + 4*k^3 - 2*k^2 + k. Wdrożenie Sage: goo.gl/0srwhq
res
3
@ edc65 Więc 105.8GBwszystko powiedziane i zrobione! Cieszę się, że gwiazdy nie zgasły ... a może musisz wydrukować listę, aby tak się stało ...?
recursion.ninja

Odpowiedzi:

34

Ruby, 46

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

Moje oryginalne, podobne rozwiązanie było dłuższe i niepoprawne (generuje liczby bazowe 13, co nie jest całkiem wszystkie z powodu wiodących zer), ale zostawię to tutaj, ponieważ i tak uzyskało głosy.

1.upto(13**9){|i|(s=i.to_s 13)[/(.)\1{3}/]||puts(s)}
histocrat
źródło
14
Cóż, uruchomiłem twój kod przez około godzinę i dostałem do 2 miliardów nazw i 21 GB pliku tekstowego, zanim to zobaczyłem i zamknąłem. Nie doceniłem wielkości pliku.
CSturgess
2
@CSturgess Cóż, Ruby nie jest najszybszym językiem dla tego rodzaju rzeczy na rynku ...
BenjiWiebe
8
@BenjiWiebe Ale wciąż szybciej niż odręcznie napisane przez mnichów!
Turophile
1
Zaakceptowanie tego, ponieważ ma więcej głosów.
CSturgess
4
Nie publikowanie tego jako oddzielnej odpowiedzi, ponieważ wymaga ogromnie dużej ilości pamięci (~ 30 TB, jeśli moje obliczenia są poprawne), ale teoretycznie można to skrócić do 43 znaków za pomocąk=*?A..?M*9;puts k-k.grep(/(.)\1{3}|[N-Z]/)
Ventero
24

C 140 177 235

Dobry stary styl proceduralny, bez fantazji.
Liczy (bez zapisu) 11 459 252 883 nazw w 8 minut.
Następnie dokonaj edycji za pomocą środowiska wykonawczego i rozmiaru pliku nazw. Obserwuj niebo ...
Czas działania 57 minut, rozmiar pliku 126 051,781,713 (9 znaków + crlf na wiersz). Podaj mi adres e-mail mnichów, abym mógł wysłać im spakowany plik do sprawdzenia ręcznego ...

Edytuj Gra w golfa jeszcze trochę, przerobiono czek dla powtarzających się liter.
Nadal nie najkrótszy, ale przynajmniej ten kończy się i generuje wymaganą moc wyjściową.
Czas działania 51 min, rozmiar pliku 113 637 155 697 (tym razem bez wiodących odstępów)

Uwaga dodatkowa: oczywiście plik wyjściowy jest bardzo ściśliwy, nadal musiałem zabić 7zip, po 36 godzinach pracy wynosił 70%. Dziwne.

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

Nie golfił

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
źródło
nie ma #include?
Simon Kuang
@ SimonKuang, niektóre kompilatory automatycznie wstawią podstawowe (stdio).
Paul Draper
1
@ Simon to standard C. Domyślnie obiektami globalnymi są int, a funkcje globalne zwracają int. Visual Studio wyświetla C4013 ostrzeżenie o „puts” nie zdefiniowane, ale i tak jest ważne.
edc65
4
zmieści się w tweecie!
CincauHangus
19

Golfscript, 58 47 znaków

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

Dzięki Peterowi Taylorowi oszczędziłem seppuku od nie bicia rozwiązania Ruby! Uruchom sam kod do 10 , a oto dowód na to, że pomija liczby cztery w rzędzie .

Claudiu
źródło
1
Łatwe zapisywanie: użyj n+zamiast ''+n. Myślę, że to w ramach zasad korzystania ze znaków alfabetu kontrolnych, więc można również wymienić 65+ze 13+i zapisać inną postać nazywając 13:^. I myślę, że tak 13,{ stuff [...]może być 13,1/{ stuff 4*.
Peter Taylor
1
Początkowo myślałem, że oszczędzanie nastąpi poprzez filtr i przy odrobinie pracy można to zrobić. Od tego czasu 13,można zastąpić {65+}%n+}%{ backtick {\4*/,}+78,1/%1-!},całkowitą oszczędnością 8, ratując życie.
Peter Taylor
Dopóki postać jest czymś, co można fizycznie zobaczyć, będzie działać. Naprawdę możesz nawet uwzględnić nowe znaki jako postać. Tak długo, jak postacie mają sekwencję.
CSturgess
@PeterTaylor: Jesteś dżentelmenem i uczonym!
Claudiu
Po AAAMtym powinno być AAABA, a nie BAAAB, prawda?
justhalf
18

Narzędzia linii poleceń Bash + Linux, 43 bajty

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

Używa techniki podobnej do mojej poniższej odpowiedzi, ale po prostu liczy się w bazie 16 i usuwa wszystkie „nazwy” zawierające 0, elub fteż te, które zawierają więcej niż 3 takie same kolejne cyfry.

Konwertuj na alfabet mnicha w następujący sposób:

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

Bash + coreutils (dc i egrep), 46 bajtów

Edycja - poprawiona wersja

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

Uruchomienie zajmie trochę czasu, ale myślę, że jest poprawne.

dcodlicza w dół od 14 ^ 9 do 1 i wyświetla w bazie 14. egrep odfiltrowuje liczby z więcej niż 3 kolejnymi cyframi. Odfiltrowujemy również nazwy zawierające cyfry „0”, więc otrzymujemy prawidłowy zestaw liter w nazwach.

Pytanie określa, że ​​można użyć dowolnego alfabetu, więc używam [1-9] [AD]. Ale w celu przetestowania można to przekształcić do [AM] za pomocą tr:

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

Daje to sekwencję:

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

Uwaga: to dcpolecenie wymaga rekurencji ogona do działania. Działa to na wersji DC 1.3.95 (Ubuntu 12.04), ale nie 1.3 (OSX Mavericks).

Cyfrowa trauma
źródło
10

APL (59)

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

Napisane własnym alfabetem :) Jest trochę długie. Uruchomienie zajmuje również dużo czasu 9, wypróbuj go z niższą liczbą, aby przetestować, jeśli chcesz.

Wyjaśnienie:

  • {... }¨⍳9: dla każdej liczby od 1 do 9:
    • ⍳13*⍵: uzyskaj wszystkie liczby od 1 do 13^⍵
    • ¯1⌽: Obracać listę w lewo o 1 (tak mamy 13^⍵, 1, 2, ..., 13^⍵-1, który zamienia się 0, 1, 2 ...modulo 13^⍵).
    • (⍵/13)⊤: zakoduj każdy numer w bazie 13 za pomocą cyfr
    • ⎕A[1+... ]: dodaj jeden (tablice są indeksowane 1) i wyszukaj ⎕A(alfabet)
    • ↓⍉: zamień macierz w wektor wektorów wzdłuż kolumn.
  • Z←⊃,/: połącz ze sobą każdy wewnętrzny wektor wektorów, dając nam listę możliwych nazw (ale nie spełnia jeszcze reguł).
  • {... : dla każdej nazwy sprawdź, czy spełnia zasadę 4 powtórzeń:
    • 4/¨⎕A[⍳13]: dla każdego znaku wygeneruj ciąg 4 tego znaku
    • ⍷∘⍵¨: dla każdego łańcucha sprawdź, czy jest obecny w
    • ∨/,↑: podejmij logiczne lub wszystkie z tych testów,
    • ~: i odwróć to, co 1oznacza, że ​​spełnia zasady i 0oznacza, że ​​nie.
  • Z/⍨: wybierz spośród Zwszystkich elementów, które spełniają ruiny
  • : wyświetl każdy w osobnym wierszu
marinus
źródło
9
Jestem rozczarowany. Biorąc pod uwagę jego reputację, można by pomyśleć, że APL miałoby do tego jednoznakowe rozwiązanie, którego żadna klawiatura nie mogłaby pisać.
Mark
7
@ Mark, jestem pewien, że APL ma to, ale nikt nie wie, co to za postać :)
Paul Draper
1
należy napisać to na kamieniu, a kiedy przyszli ludzie to znajdą, mogą pomyśleć, że to po prostu prymitywny język pisany.
CincauHangus
9

Perl, 70 68 66 50 znaków

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

Stosowanie:

$ perl -E 'code' > output_file

Zaletą jest to, że wydruki są buforowane, więc najpierw drukowane są wszystkie rozwiązania 1-znakowe, a następnie słowa 2-znakowe i tak dalej.

Zaid
źródło
Najlepszą rzeczą w tym rozwiązaniu jest piersi po lewej stronie 1.
Dan Hanly
8

Perl - 35 bajtów

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

Licząc shebang jako jeden bajt.

To luźne tłumaczenie odpowiedzi histokraty .

A..1x9jest trochę dziwny; to jest skrót 'A'..'111111111'. Akumulator nigdy nie osiągnie wartości końcowej (zawiera tylko duże litery), ale nadal będzie się kończył, gdy będzie dłuższy niż 9 znaków. Można to przetestować, na przykład, używając 1x4zamiast tego.

primo
źródło
Szacunek! Dlaczego o tym nie pomyślałem? ;)
Zaid
Zauważ, że Ruby nie musi również tworzyć całego zakresu w celu iteracji. Jedynym powodem, dla którego kod w moim komentarzu wymaga tak ogromnej ilości pamięci, jest to, że zamienia zakres w tablicę (aby mogła go użyć Array#-).
Ventero
@Ventero Ahh tak, grepzrobi to. Nie jestem całkowicie biegły w Ruby.
primo
6

PYG (waaay zbyt długo, na języku, do golfa)

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

Mimo że jest to bliskie tego, jak bym to zrobił w Pythonie:

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

Pomijając oczywiście komplikacje z długiej linii;)

.ıʇǝɥʇuʎs
źródło
3

Pyth , 34 znaki

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

Wyjaśnienie:

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
źródło
2

Python 2 - 212 bajtów

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
źródło
0

Japt , 21 bajtów

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

Wypróbuj online! (link oblicza tylko do 14**4.)

Jak to działa

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.

Zakłada standardową implementację ECMAScript 2017 jako warstwę JS (i wystarczającą ilość pamięci do przechowywania tablicy), w której Arrayobiekt może mieć maksymalną 2**53-1długość.

Bubbler
źródło