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.

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

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

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 .

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

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

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.

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.

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

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

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

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ść.