Os 9 bilhões de nomes de Deus é um conto de Arthur C. Clarke. É sobre um grupo de monges tibetanos cuja ordem é dedicada a escrever todos os nomes possíveis de Deus, escritos em seu próprio alfabeto. Essencialmente, eles são dedicados a escrever todas as permutações possíveis de seu alfabeto, restritas por algumas regras. Na história, o mosteiro contrata alguns engenheiros para escrever um programa para fazer todo o trabalho para eles. Seu objetivo é escrever esse programa.
Regras:
O alfabeto do monge usa 13 caracteres (de acordo com minhas estimativas). Você pode usar
ABCDEFGHIJKLM
ou outro conjunto de 13 caracteres.O comprimento mínimo de um nome possível é de 1 caractere. O comprimento máximo é de 9 caracteres.
Nenhum personagem pode repetir mais de 3 vezes seguidas.
AAABA
é um nome válido, masAAAAB
não é.Seu programa deve imprimir (em um arquivo) todos os nomes possíveis em sequência de
A
paraMMMLMMMLM
, separados por qualquer caractere que não esteja no alfabeto (novas linhas, ponto e vírgula, qualquer que seja).Isso é código-golfe e você pode usar qualquer idioma. A solução mais curta até 1º de junho de 2014 vence.
Editar: Os nomes devem começar A
e terminar com MMMLMMMLM
, progredindo por todos os bilhões de nomes sequencialmente. Mas a sequência específica é com você. Você pode imprimir todos os 1-letra nomes em primeiro lugar, em seguida, todos os nomes de 2 letras, etc. Ou você pode imprimir todos os nomes que começam com A
, em seguida, todos aqueles que começam com B
, ou algum outro padrão. Mas um humano deve ser capaz de ler o arquivo e confirmar se está tudo lá e na ordem lógica que você escolher, supondo que ele tenha tempo.
fonte
f(k) = k^9 + k^8 + k^7 - 5*k^6 + k^5 + k^4 + 4*k^3 - 2*k^2 + k
. Implementação Sage: goo.gl/0srwhq105.8GB
tudo dito e feito! Fico feliz que as estrelas não tenham saído ... ou talvez você precise imprimir a lista para que isso aconteça ...?Respostas:
Ruby, 46
Minha solução original e semelhante foi mais longa e errada (produziu números de base13, que não são todos eles devido a zeros à esquerda), mas deixarei aqui porque ele obteve votos de qualquer maneira.
fonte
k=*?A..?M*9;puts k-k.grep(/(.)\1{3}|[N-Z]/)
C 140
177 235Bom e velho estilo processual, sem fantasia.
Conta (sem gravação) 11.459.252.883 nomes em 8 minutos.
A seguir edite com o tempo de execução e o tamanho do arquivo de nomes. Assista ao céu ...
Tempo de execução 57 minutos, tamanho do arquivo 126.051.781.713 (9 caracteres + crlf por linha). Diga-me o endereço de e-mail dos monges, para que eu possa enviar o arquivo compactado, para verificação manual ...
Editar Golfed um pouco mais, reformulou o cheque para repetir letras.
Ainda não é o mais curto, mas pelo menos este termina e gera a saída necessária.
Tempo de execução 51 min, tamanho do arquivo 113.637.155.697 (sem espaços em branco desta vez)
Uma observação: obviamente, o arquivo de saída é muito compressível, ainda assim eu tive que matar o 7zip, depois de trabalhar 36 horas, estava em 70%. Esquisito.
Ungolfed
fonte
#include
é?Golfscript,
5847 caracteresGraças a Peter Taylor, sou poupado do seppuku por não vencer a solução Ruby! Execute o código até 10 você mesmo , e aqui está a prova de que ele ignora os números quatro em linha .
fonte
n+
vez de''+n
. Eu acho que é dentro das regras para usar um alfabeto com caracteres de controle, então você também poderia substituir65+
com13+
e salvar outro personagem nomeando13:^
. E eu acho que13,{ stuff [...]
poderia ser13,1/{ stuff 4*
.13,
on pode ser substituída por{65+}%n+}%{ backtick {\4*/,}+78,1/%1-!},
uma economia total de 8, salvando sua vida.AAAM
deveria serAAABA
, e nãoBAAAB
, certo?Utilitários de linha de comando Bash + Linux, 43 bytes
Este usa uma técnica semelhante à minha resposta abaixo, mas apenas conta na base 16, e retira todos os "nomes" que contêm
0
,e
ouf
bem aqueles com mais de 3 mesmos dígitos consecutivos.Converta no alfabeto do monge da seguinte maneira:
Bash + coreutils (dc e egrep), 46 bytes
Editar - versão corrigida
Vai demorar um pouco para funcionar, mas acho que está correto.
dc
conta para baixo de 14 ^ 9 para 1 e sai na base 14. egrep filtra os números com mais de 3 mesmos dígitos consecutivos. Também filtramos quaisquer nomes com dígitos "0", para obter o conjunto correto de letras nos nomes.A pergunta especifica que qualquer alfabeto pode ser usado, por isso estou usando [1-9] [AD]. Mas para o teste, isso pode ser transformado para [AM] usando tr:
Isso produz a sequência:
Observe que este
dc
comando requer recursão de cauda para funcionar. Isso funciona na versão dc 1.3.95 (Ubuntu 12.04), mas não na 1.3 (OSX Mavericks).fonte
APL (59)
Escrito em seu próprio alfabeto :) É um pouco longo. Também leva muito tempo para executar
9
, tente com um número menor para testar se você deseja.Explicação:
{
...}¨⍳9
: para cada número⍵
de 1 a 9:⍳13*⍵
: obtenha todos os números de 1 a13^⍵
¯1⌽
: Rodar a lista para a esquerda por 1 (por isso temos13^⍵
,1
,2
, ...,13^⍵-1
, que se transforma em0, 1, 2 ...
modulo13^⍵
).(⍵/13)⊤
: codifique cada número na base 13 usando⍵
dígitos⎕A[1+
...]
: adicione uma (as matrizes são indexadas a 1) e procure⎕A
(o alfabeto)↓⍉
: transforme a matriz em um vetor de vetores ao longo das colunas.Z←⊃,/
: junte cada vetor interno de vetores, fornecendo uma lista de nomes possíveis (mas ainda não atende às regras).{
...}¨
: para cada nome, teste se ele atende à regra de 4 caracteres repetidos:4/¨⎕A[⍳13]
: para cada caractere, gere uma sequência de 4 desse caractere⍷∘⍵¨
: para cada sequência, teste se está presente em⍵
∨/,↑
: faça o lógico ou de todos esses testes,~
: e inverta-o, o que1
significa que ele atende às regras e0
significa que não.Z/⍨
: selecione entreZ
todos os elementos que atendem às ruínas↑
: exibir cada um em uma linha separadafonte
Perl,
70686650 caracteresUso:
O bom é que as impressões são armazenadas em buffer, para que você obtenha todas as soluções de 1 caractere primeiro, seguidas de palavras de 2 caracteres e assim por diante.
fonte
Perl - 35 bytes
Contando o shebang como um byte.
Esta é uma tradução solta da resposta do histocrata .
A..1x9
é um pouco estranho; isso é uma abreviação para'A'..'111111111'
. O acumulador nunca alcançará o valor do terminal (ele contém apenas letras maiúsculas), mas ainda será encerrado quando tiver mais de 9 caracteres. Isso pode ser testado, por exemplo, usando-o1x4
.fonte
Array#-
).grep
fará isso. Eu não sou totalmente fluente em Ruby.Pyg (Waaay muito longo, para um idioma feito para jogar golfe)
sussurros : 101 ...
Mesmo que isso esteja próximo de como eu realmente faria isso em Python:
Menos a complicação de linha longa, é claro;)
fonte
Pitão , 34 caracteres
Explicação:
fonte
Python 2 - 212 bytes
fonte
Japonês , 21 bytes
Experimente online! (o link calcula apenas até
14**4
.)Como funciona
Assume uma implementação padrão do ECMAScript 2017 como a camada JS (e memória suficiente para armazenar a matriz), em que um
Array
objeto pode ter o2**53-1
comprimento máximo .fonte