Este é um quebra-cabeça de palavras.
Seu programa deve aceitar duas palavras na entrada padrão.
A primeira palavra é a palavra inicial. A palavra dois é a palavra final.
Desde a palavra inicial, você deve chegar à palavra final alterando / adicionando / removendo uma letra de cada vez. Após cada modificação, ele deve formar uma nova palavra válida. As letras adicionadas são adicionadas ao começo ou ao fim. Você pode remover letras de qualquer local (mas a palavra não deve ficar abaixo de três letras). Nota: Você não pode reorganizar as letras para formar uma palavra.
A saída do programa é a sequência de palavras que vão da palavra inicial à palavra final.
Exemplo:
Input:
Post Shot
Output:
Post
cost
coat
goat
got
hot
shot
Vencedora:
- O programa deve ser executado em um tempo razoável (menos de 10 segundos).
- O programa que pode gerar a menor sequência de saída para as palavras do prêmio.
- Zink -> Silício
- Se mais de um programa obtiver a menor sequência, o menor programa em caracteres (ignorando o espaço em branco).
- Se ainda tivermos mais de uma data / hora de envio do programa, será usada.
Notas:
- A capitalização não é relevante.
- O código para criar um dicionário não conta para o custo do código.
- Palavras e sequência de prêmios serão geradas em:
http://dl.packetstormsecurity.net/Crackers/wordlists/dictionaries/websters-dictionary.gz
- Palavras e sequência de prêmios serão geradas em:
code-golf
word-puzzle
Martin York
fonte
fonte
Respostas:
Python, 288 caracteres
(sem contar a linha de leitura do dicionário)
para o desafio
zink
desilicon
:Existem algumas palavras estranhas nesse dicionário ...
fonte
guester overturn
(leva algum tempo) ouregatta gyrally
(não retorna) ;-)traceroute - 10 caracteres
detalhe
Os roteadores são pré-configurados com o OSPF ativado e organizados dessa maneira.
E sim, preciso de 233614 roteadores para dar suporte total a todas as palavras. :-)
fonte
zink->pink->pank->pani->panic->pinic->sinic->sinico->silico->silicon
eu estou realmente tentando com o algoritmo Dijkstra (que é usado no OSPF) e ele pode encontrar esse caminho em torno de 1s, postá-lo em post separado mais tarde, uma vez que eu jogava golfe.PHP -
886689644612Carregamento do dicionário:
Código real (concat apenas ambos):
uso:
Resultado:
Isso deve ser executado em menos de 0,5 segundo para o 'Zink Silicon' e menos de 1 segundo na maioria dos casos (às vezes mais quando não existe solução, mas a soleira volta).
Isso usa o algoritmo A * com distância de levenshtein para estimar os limites mais baixos das distâncias.
Alguns testes interessantes:
vas arm
->vas bas bar barm arm
(com uma palavra maior que o início e o fim)oxy pom
->oxy poxy poy pom
regatta gyrally
-> (nenhum, mas o script termina corretamente)aal presolution
-> +8 caractereslenticulated aal
-> -9 caracteresacarology lowness
-> 46 saltoscaniniform lowness
-> 51 saltoscauliform lowness
-> 52 saltosoverfoul lowness
-> 54 saltosdance facia
-> algumas palavras no caminho têm mais 4 caracteres do que o início / fimfonte
PHP Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 71 bytes)
php -dmemory_limit=256M
.had->hand
não é uma jogada válida, você só pode adicionar uma letra ao começo ou ao fim. Mesmo paravest->verst
:-)Pitão
Como eu não conseguia usar códigos dijkstra de golfe para compactar até algumas centenas de bytes, aqui está a minha versão não destruída.
Testes
Adicionados testes do user300
Um pouco mais
fonte
3 <= len(x) <= max(map(len, [nodea, nodeb]))
é garantido que o caminho nunca passará por uma palavra mais do que as palavras inicial e final?oxy pom
; caminho mais curto éoxy->poxy->poy->pom
. Também é Parece que você permitir permutações e inserções em qualquer lugar, que não são permitidos :-)