Dada uma lista de cadeias, encontre a menor matriz quadrada que contém cada uma das cadeias iniciais. As strings podem aparecer na horizontal, na vertical ou na diagonal e para a frente ou para trás, como nesta pergunta Word Search Puzzle .
As palavras devem ser colocadas no quadrado, com pelo menos uma palavra em cada direção (horizontal, vertical e diagonal). As palavras devem aparecer apenas uma vez.
Portanto, a entrada é apenas uma lista de palavras. Por exemplo: CAT, TRAIN, CUBE, BICYCLE
. Uma solução possível é:
B N * * * * *
* I * * C A T
* A C * * * *
* R * Y * * C
* T * * C * U
* * * * * L B
* * * * * * E
Substituí o preenchimento de cartas por asteriscos apenas para maior clareza. A saída desejada deve incluir letras de preenchimento aleatórias.
AC
no seu exemplo faria outra,CAT
se forT
.A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
não tem solução.Respostas:
JavaScript (ES6),
595628680Editar Alguma limpeza e mesclagem:
- função P mesclada dentro da função R
- calc x e z no mesmo .map
- quando a solução for encontrada, defina x como 0 para sair do loop externo
- definição e chamada mescladas de W
Edit2 mais golfe, preenchimento aleatório reduzido, loop externo revisado ... veja a história para algo mais legível
Diferentemente da resposta aceita,isso deve funcionar para a maioria das entradas. Apenas evite palavras de letra única. Se uma saída for encontrada, é ideal e use todas as três direções.A restrição de evitar repetir palavras é muito difícil. Eu tive que procurar por palavras repetidas em cada etapa, adicionando palavras à grade e em cada caractere de preenchimento aleatório.
Subfunções principais:
P (w) verdadeiro se palavra palíndromo. Uma palavra palindrom será encontrada duas vezes ao procurar por palavras repetidas.
R (s) verifica palavras repetidas na grade s
Q (s) preenchem a grade s com caracteres aleatórios - são recursivos e retornam em caso de repetição de palavras - e podem falhar.
W () recursivo, tente preencher uma grade de determinado tamanho, se possível.
A função principal usa W () para encontrar uma grade de saída, tentando desde o tamanho da palavra mais longa na entrada até a soma do comprimento de todas as palavras.
Ungolfed e explicou (incompleto, desculpe pessoal, é muito trabalho)
Teste no console Firefox / FireBug
F (['TREM', 'CUBO', 'CAIXA', 'BICICLETA'])
não preenchido
F (['TREM', 'ARTES', 'RAT', 'CUBO', 'CAIXA', 'BICICLETA', 'TEMPESTADE', 'CÉREBRO', 'PROFUNDIDADE', 'BOCA', 'TRABALHO'])
F (['AA', 'AB', 'AC', 'AD', 'AE', 'AF', 'AG'])
F (['AA', 'AB', 'AC', 'AD', 'AE', 'AF'])
saída não preenchida - @nathan: agora você não pode adicionar outro A x sem repetições. Você precisará de uma grade maior.
fonte
C #
Aqui está uma implementação simples, com ainda o trabalho a ser feito. Existem muitas combinações para obter o menor tamanho. Então, só usei o algoritmo mais simples possível.
Teste
fonte
at least one word in each direction (horizontal, vertical and diagonal)
. Executando o programa de teste, nenhuma palavra horizontal (3 vertical, 1 diag)