Johnny está tentando criar palavras cruzadas, mas está tendo dificuldades para fazer as palavras se encaixarem.
Ele criou vários retângulos simples de palavras: ou seja, grupos de palavras que formam um retângulo onde todos os caminhos horizontais e verticais formam uma palavra.
//2x2
PA
AM
//2x3
GOB
ORE
//3x3
BAG
AGO
RED
//3x4
MACE
AGES
WEES
No entanto, para fazer um bom quebra-cabeça, ele precisa de alguns retângulos de palavras um pouco maiores que 3x4. Em vez de agonizar as cartas de arranjo por horas, Johnny preferiria ter um programa que faça isso por ele - e no menor número possível de caracteres, porque longos blocos de código são extremamente intimidadores para programadores casuais como Johnny.
Dado
- um dicionário de arquivo de texto em que as palavras são separadas por novas linhas em ordem alfabética,
- entrada especificando o número de linhas e colunas no retângulo de palavras (que pode ser fornecido, porém, é mais conveniente na sua linguagem de programação preferida)
gere pelo menos um retângulo de palavras. Se não for possível gerar um retângulo de palavras com o léxico e as dimensões fornecidos, o programa não precisará ter um comportamento definido. Não é necessário que o programa possa gerar retângulos que contenham mais de 64 letras ou que tenham dimensões que excedam 8 em qualquer direção. O programa deve ser concluído em um período de tempo razoável, digamos, em trinta minutos ou menos.
EDIT: Se você estiver executando um retângulo NxN, poderá usar um arquivo de dicionário menor que contenha apenas palavras com um comprimento de N letras.
Respostas:
Haskell, 586 caracteres
Invocado fornecendo 3 argumentos: número de linhas, número de colunas, número de soluções; e a lista de palavras é aceita em
stdin
:Como você pode ver, o 7 × 7 roda relativamente rápido. Ainda cronometrando 8 × 8 e 7 × 6 ....
Seriam 9 caracteres mais curtos para remover o argumento do número de soluções e apenas produzir todas as soluções, mas torna-se impossível cronometrar.
Map String a
seja mais lento que uma árvore deMap Char a
...Vector
é muito mais rápida do que usar uma simplesMap
. Por que fazer isso? Porque acho que uma solução mais próxima da meta de 8x8 em menos de meia hora é preferível a uma solução mais curta.fonte
--make
depois do ghc) com a lista de palavras postada na pergunta, estou recebendo palavras que não estão na lista, como "zymesz" e "youthy".Python, 232 caracteres
No entanto, ele pode suportar até 6x6 no limite de meia hora.
fonte
3,3
mas suas palavras de retorno3x4
+2
s para+1
s.\r
a partirw
, e no Linux eu tenho arquivo convertido para o formato Unix, então ambos não funcionou.Java (1065 bytes)
Muito longe de ser o mais curto, mas acho que é o mais próximo de atender às restrições de tempo. Eu salvei 14 bytes assumindo que o arquivo de entrada foi filtrado para palavras do tamanho certo; no meu netbook, se você alimentar o todo
words.txt
, ele passará o primeiro minuto pré-processando-o, descartando a maior parte do que ele produz e, em seguida, leva apenas 20 segundos para resolver 7x7. Na minha área de trabalho, ele faz tudo em menos de 15 segundos, fornecendo:Deixei que funcionasse por mais de 50 horas sem encontrar uma solução para 8x7 ou 8x8. As palavras de 8 letras parecem ser um limite crítico para esse problema - apenas paira pela metade sem fazer muito progresso.
A abordagem utilizada é a articulação completa e uma heurística com base no número de conclusões horizontais possíveis vezes o número de conclusões verticais possíveis. Por exemplo, se tivermos grade intermediária
então, atribuímos um valor heurístico ao canto superior esquerdo
count(aean*)count(aa***) + count(bean*)count(ba***) + ... + count(zean*)count(za***)
. De todas as células, escolhemos aquela com o menor valor heurístico (ou seja, mais difícil de satisfazer) e, em seguida, trabalhamos com as letras em ordem decrescente da quantidade em que elas contribuíram para o valor heurístico dessa célula (ou seja, começando pelo mais provável) )fonte
F #
Solução de retrocesso, mas vou otimizar o espaço de pesquisa mais tarde.
fonte
awk, 283
(pode ser necessário adicionar 14 para sinalizadores de entrada de parâmetro)
Ligue com, por exemplo
awk -v x=2 -v y=2
...Encontre a primeira correspondência e imprima-a (283 caracteres):
Encontre o número de correspondências (245 caracteres, muito mais lento):
Para ambos os programas (é claro, mais para a contagem de soluções), o tempo de execução excede em muito 30 minutos alguns valores de x e y.
Por uma questão de interesse, eis a contagem de palavras para cada tamanho de palavra:
fonte