Como encontrar a lista de possíveis palavras de uma matriz de letras [Boggle Solver]
Ultimamente, tenho jogado um jogo no meu iPhone chamado Scramble. Alguns de vocês podem conhecer este jogo como Boggle. Essencialmente, quando o jogo começa, você obtém uma matriz de letras da seguinte forma:
O objetivo do jogo é encontrar o maior número possível de palavras que possam ser formadas encadeando letras. Você pode começar com qualquer letra e todas as letras que a cercam são justas e, depois de passar para a próxima letra, todas as letras que cercam essa letra são justas, exceto as letras usadas anteriormente . Então na grade acima, por exemplo, eu poderia vir acima com as palavras LOB, TUX, SEA, FAME, etc. As palavras devem ter no mínimo 3 caracteres e um máximo de caracteres NxN, o que seria 16 neste jogo, mas pode variar em algumas implementações . Embora este jogo seja divertido e viciante, aparentemente eu não sou muito bom nisso e queria trapacear um pouco, criando um programa que me desse as melhores palavras possíveis (quanto mais longa a palavra, mais pontos você ganha).
(fonte: boggled.org )
Infelizmente, não sou muito bom com algoritmos ou suas eficiências e assim por diante. Minha primeira tentativa usa um dicionário como este (~ 2,3 MB) e faz uma pesquisa linear tentando combinar combinações com entradas do dicionário. Demora muito tempo para encontrar as palavras possíveis e, como você recebe apenas 2 minutos por rodada, isso simplesmente não é adequado.
Estou interessado em ver se algum Stackoverflowers pode apresentar soluções mais eficientes. Estou procurando principalmente soluções usando os Big 3 Ps: Python, PHP e Perl, embora qualquer coisa com Java ou C ++ seja legal também, pois a velocidade é essencial.
SOLUÇÕES ATUAIS :
Adam Rosenfield, Python, ~ 20 anos
rvarcher, VB.NET (link ao vivo) , ~ 1s
Paolo Bergantino, PHP (link ao vivo) , ~ 5s (~ 2s localmente)
pedido de recurso MOAR PUZZLES
Com relação aos horários: na minha solução, praticamente todo o tempo é gasto na construção do teste. Uma vez construído, o trie pode ser reutilizado várias vezes. Se apenas resolvesse um quebra-cabeça, seria mais eficiente usar uma estrutura de dados mais simples (como um conjunto de todas as palavras e todos os prefixos).
— 23411 Adam Rosenfield
Além disso, o de Adam possui um dicionário maior, evidenciado pelo número de palavras mais longas que sua solução usa. Todos devem ser testados com base em um dicionário comum.
— 22320 Rich Bradshaw
Eu acho que ninguém joga muito Boggle? "Qu" é uma "letra" e não sei ao certo quantas das soluções captaram esse pequeno detalhe. Parece que alguns deles permitiriam que você usasse o "u" independentemente, entre outros problemas.
— Qsario
Recentemente, tive isso como uma pergunta de entrevista e fiquei bem preso nos detalhes. Eu estava tratando isso como um problema gráfico, o que é bom, mas as soluções aqui usam muito menos espaço. Estou codificando minha própria solução agora. Bem feito a todos que contribuíram!
— Peter amigo
Minha resposta funciona como as outras aqui, mas vou publicá-la porque parece um pouco mais rápida do que as outras soluções Python, de configurar o dicionário mais rapidamente. (Verifiquei isso com a solução de John Fouhy.) Após a instalação, o tempo para resolver é baixo no barulho.
Editar: filtrar palavras com menos de 3 letras.
Edit 2: Fiquei curioso por que a solução Perl de Kent Fredric era mais rápida; ela usa correspondência de expressão regular em vez de um conjunto de caracteres. Fazer o mesmo em Python duplica a velocidade.
O programa está me dando apenas 1 palavra. Por quê?
Eu não queria me afogar na saída. Veja o comentário na parte inferior.
Ou obter todas as palavras sem os caminhos: print '' .join (ordenadas (set (palavra (word, path) em resolver ())))
A maior parte do tempo é gasta apenas analisando o dicionário. Eu pré-analisei isso em um arquivo "wordlines.py" que é apenas uma lista com cada palavra sendo um elemento. Por ser um arquivo .py, ele será transformado em um arquivo .pyc. Então, eu faço uma importação disso em vez de read (). Splitlines (). Com isso, na minha caixa, estou resolvendo isso em cerca de um décimo de segundo.
@shellscape, é código Python 2. Python 3 abandonou a capacidade de desconstruir argumentos, como def neighbors((x, y))(inutilmente, tanto quanto eu posso ver). Também requer parênteses ao redor do argumento print.
A solução mais rápida que você obterá provavelmente envolverá o armazenamento do seu dicionário em três tentativas . Em seguida, crie uma fila de trigêmeos ( x , y , s ), em que cada elemento na fila corresponde a um prefixo s de uma palavra que pode ser escrita na grade, terminando no local ( x , y ). Inicialize a fila com N x N elementos (onde N é o tamanho da sua grade), um elemento para cada quadrado na grade. Em seguida, o algoritmo prossegue da seguinte maneira:
Retirar da fila uma tripla (x, y, s)
Para cada quadrado (x ', y') com a letra c adjacente a (x, y):
Se s + c é uma palavra, produza s + c
Se s + c for o prefixo de uma palavra, insira (x ', y', s + c) na fila
Se você armazena seu dicionário em uma tentativa, é possível testar se s + c é uma palavra ou um prefixo de uma palavra em tempo constante (desde que você também mantenha alguns metadados extras em cada dado da fila, como um ponteiro para o nó atual no experimento), então o tempo de execução desse algoritmo é O (número de palavras que podem ser escritas).
[Editar] Aqui está uma implementação em Python que acabei de codificar:
['fa', 'xi', 'ie', 'io', 'el', 'am', 'ax', 'ae', 'aw', 'mi', 'ma', 'eu', ' lo ',' li ',' oe ',' boi ',' em ',' ea ',' ea ',' es ',' wa ',' nós ',' wa ',' bo ',' bu ' , 'as', 'aw', 'ae', 'st', 'se', 'sa', 'tu', 'ut', 'fam', 'fae', 'imi', 'eli', ' elm ',' elb ',' ami ',' ama ',' ame ',' aes ',' awl ',' wake ',' incrédulo ',' wake ',' mix ',' mim ',' mil ' , 'mam', 'max', 'mae', 'maw', 'mew', 'mem', 'mes', 'lob', 'lox', 'lei ',' leo ',' mentira ',' lim ',' óleo ',' olm ',' ovelha ',' eme ',' cera ',' waf ',' wae ',' waw ',' wem ' , 'wea', 'wea', 'was', 'waw', 'wae', 'bob', 'blo', 'bub', 'but', 'ast', 'ase', 'asa', ' awl ',' wake ',' incrédulo ',' wake ',' aes ',' swa ',' swa ',' costurar ',' mar ',' mar ',' serra ',' tux ',' banheira ' , 'tut', 'twa', 'twa', 'tst', 'utu', 'fama', 'fama', 'ixil', 'imam', 'amli', 'amil', 'ambo', ' axil ',' axle ',' mimi ',' mima ',' mime ',' milo ','milha ',' mewl ',' mese ',' mesa ',' lolo ',' lobo ',' lima ',' lime ',' limb ',' lile ',' oime ',' oleo ',' olio ' , 'oboé', 'obol', 'emim', 'emil', 'leste', 'facilidade', 'wame', 'wawa', 'wawa', 'weam', 'west', 'wese', ' wast ',' wase ',' wawa ',' wawa ',' boil ',' bolo ',' bole ',' bobo ',' blob ',' bleo ',' bubo ',' asem ',' stub ' , 'stut', 'swam', 'semi', 'seme', 'costura', 'seax', 'sasa', 'sawt', 'tutu', 'tuts', 'twae', 'twas', ' twae ',' ilima ',' amble ',' axile ', 'awest', 'mamie', 'mambo', 'maxim', 'mease', 'mesem', 'limax', 'limes', 'limbo', 'limbu', 'obole', 'emesa', ' embox ',' awest ',' swami ',' famble ',' mimble ',' maxima ',' embolo ',' embole ',' wamble ',' semese ',' semble ',' sawbwa ',' sawbwa ' ]sawbwa ']sawbwa ']
Notas: Este programa não gera palavras de uma letra ou filtra de acordo com o tamanho da palavra. É fácil adicionar, mas não é realmente relevante para o problema. Também gera algumas palavras várias vezes, se puderem ser escritas de várias maneiras. Se uma determinada palavra puder ser escrita de várias maneiras diferentes (na pior das hipóteses: todas as letras da grade são iguais (por exemplo, 'A') e uma palavra como 'aaaaaaaaaa' está no seu dicionário), o tempo de execução ficará terrivelmente exponencial . A filtragem de duplicatas e a classificação são triviais devido ao término do algoritmo.
Ooo. Fico feliz que alguém se aproximou do prato. Embora isso funcione, ele não "se lembra" da letra que já usou e apresenta palavras que exigiriam o uso da mesma letra duas vezes, o que não é permitido. Como eu sou um idiota, como eu iria consertar isso?
É verdade que não se lembra quais cartas foram visitadas, mas isso não foi especificado em sua especificação =). Para corrigir isso, você teria que adicionar a cada dado da fila uma lista de todos os locais visitados e depois verificar essa lista antes de adicionar o próximo caractere.
— 14119 Adam Rosenfield
Não, dentro do BoggleWords (). Em vez de armazenar um quádruplo (x, y, s, n), você armazena um quíntuplo (x, y, s, n, l), em que l é a lista dos (x, y) visitados até agora. Então você verifica cada (x2, y2) contra l e aceita-o apenas se não estiver em l. Então você o adiciona ao novo l.
Também fiz isso quando fiquei cansado de jogar Scramble. Eu acho que a solução recursiva (DFS em vez de BFS) é mais sexy, pois você pode manter um conjunto de células ativas (para não visitar a mesma célula duas vezes). Muito mais organizado, mantendo um monte de listas.
— Justin Scheiner
Isso não deveria cair em um loop infinito? Quero dizer, digamos (x,y), um possível seguidor é (x+1,y+1). Em seguida, (x+1,y+1)é empurrado para a fila. No entanto (x,y), também será um seguidor (x+1,y+1), então isso não levará a um retorno interminável entre eles?
— SexyBeast #
Para uma aceleração de dicionário, há uma transformação / processo geral que você pode fazer para reduzir bastante as comparações de dicionário com antecedência.
Dado que a grade acima contém apenas 16 caracteres, alguns deles duplicados, você pode reduzir bastante o número total de chaves no seu dicionário, simplesmente filtrando as entradas que possuem caracteres inatingíveis.
Eu pensei que essa era a otimização óbvia, mas vendo que ninguém fez isso, estou mencionando.
Isso me reduziu de um dicionário de 200.000 chaves para apenas 2.000 chaves simplesmente durante o passe de entrada. Isso reduz, no mínimo, a sobrecarga da memória, e é certo que é mapeado para um aumento de velocidade em algum lugar, pois a memória não é infinitamente rápida.
Implementação Perl
Minha implementação é um pouco pesada, porque enfatizei a capacidade de saber o caminho exato de cada string extraída, não apenas a validade nela.
Também tenho algumas adaptações que teoricamente permitiriam que uma grade com furos funcionasse e grades com linhas de tamanhos diferentes (supondo que você tenha a entrada correta e ela se alinha de alguma forma).
O filtro inicial é de longe o gargalo mais significativo no meu aplicativo, como suspeito anteriormente, comentando que a linha incha de 1,5s para 7,5s.
Após a execução, parece que todos os dígitos estão com suas próprias palavras válidas, mas tenho certeza de que é devido ao modo como o arquivo do dicionário funciona.
Está um pouco inchado, mas pelo menos eu reutilizo o Tree :: Trie do cpan
Parte disso foi inspirada parcialmente pelas implementações existentes, algumas das quais eu já tinha em mente.
Críticas construtivas e formas de melhorar as boas-vindas (/ me observa que ele nunca procurou no CPAN um solucionador de problemas , mas isso era mais divertido de resolver)
atualizado para novos critérios
Informações de arco / execução para comparação:
Mais resmungos nessa otimização Regex
A otimização de regex que uso é inútil para dicionários com várias resoluções, e para várias resoluções, você desejará um dicionário completo, não um pré-aparado.
No entanto, dito isso, para soluções pontuais, é realmente rápido. (Regex Perl estão em C! :))
Aqui estão algumas adições de código variadas:
s / iter não filtrado
não filtrado 8,16 - -94%
filtrada 0,464 1658% -
ps: 8,16 * 200 = 27 minutos.
Sei que estou falhando no clube de otimização, mas tive problemas de velocidade antes de chegar ao trabalho real do código, e reduzir o tempo de entrada de 2s para 1,2s significa muito para mim.
— 21710 Kent Kentric
Eu percebi que era estranho agora levar menos tempo para regexar e pular entradas do que para adicionar chaves a um hash.
Bom, uma implementação Perl! Eu vou correr agora.
— 21411 Paolo Bergantino
Blerg, tendo dificuldade em instalar o Tree :: Trie no meu servidor da web. :(
Como você gerou esse último relatório (informações de arco / execução)? Parece útil.
Você pode dividir o problema em duas partes:
Algum tipo de algoritmo de pesquisa que enumerará possíveis sequências na grade.
Uma maneira de testar se uma string é uma palavra válida.
Idealmente, (2) também deve incluir uma maneira de testar se uma sequência de caracteres é o prefixo de uma palavra válida - isso permitirá que você faça uma busca na sua pesquisa e economize bastante tempo.
Trie de Adam Rosenfield é uma solução para (2). É elegante e provavelmente o que seu especialista em algoritmos preferiria, mas com linguagens modernas e computadores modernos, podemos ser um pouco mais preguiçosos. Além disso, como Kent sugere, podemos reduzir o tamanho do dicionário descartando palavras com letras que não estão presentes na grade. Aqui está um python:
Uau; teste de prefixo em tempo constante. Demora alguns segundos para carregar o dicionário que você vinculou, mas apenas alguns :-) (observe isso words <= prefixes)
Agora, para a parte (1), estou inclinado a pensar em termos de gráficos. Então, eu vou construir um dicionário que se parece com isso:
ou seja, graph[(x, y)]é o conjunto de coordenadas que você pode alcançar da posição (x, y). Também adicionarei um nó fictício Noneque se conectará a tudo.
Construir é um pouco desajeitado, porque há 8 posições possíveis e você precisa fazer uma verificação de limites. Aqui está um código python correspondentemente desajeitado:
Esse código também cria um mapeamento de dicionário (x,y)para o caractere correspondente. Isso me permite transformar uma lista de posições em uma palavra:
Por fim, fazemos uma pesquisa profunda. O procedimento básico é:
A pesquisa chega em um nó específico.
Verifique se o caminho até agora pode fazer parte de uma palavra. Caso contrário, não explore mais esse ramo.
Verifique se o caminho até agora é uma palavra. Nesse caso, adicione à lista de resultados.
Explore todas as crianças que não fazem parte do caminho até agora.
Execute o código como:
e inspecione respara ver as respostas. Aqui está uma lista de palavras encontradas para o seu exemplo, classificadas por tamanho:
O código leva (literalmente) alguns segundos para carregar o dicionário, mas o resto é instantâneo na minha máquina.
Muito agradável! Muito rápido também. Vou esperar para ver se mais alguém se aproxima, mas sua resposta está boa até agora.
Estou confuso por que "embole" é a sua única palavra de 6 letras, tenho 10 palavras diferentes para isso. Parece que você proíbe visitar o mesmo nó duas vezes e, como afirmou o OP, é um jogo justo.
ok, ele ainda pode ter um bug ao descartar "FAMBLE" "WAMBLE" e "SEMBLE", que não compartilham caracteres.
Bem manchado! O bug estava na criação do conjunto de prefixos: eu precisava usar em range(len(w)+1)vez de range(len(w)). Eu afirmei isso, words <= prefixesmas aparentemente não testei isso: - /
— John Fouhy 14/04/2009
Isso me ajudou a aprender como um DFS funciona e como implementá-lo. Não tinha certeza de nenhuma maneira de demonstrar apreço por isso, exceto por um comentário. Obrigado!
Minha tentativa em Java. Demora cerca de 2 s para ler o arquivo e criar trie, e cerca de 50 ms para resolver o quebra-cabeça. Eu usei o dicionário vinculado na pergunta (há algumas palavras que eu não sabia existir em inglês, como fae, ima)
O código fonte consiste em 6 classes. Vou publicá-las abaixo (se essa não é a prática correta no StackOverflow, por favor me diga).
— gineer
Eu estava comparando minha saída com as saídas de outros StackOverflowers, e parece que as saídas de Adam, John e rvarcher estavam faltando algumas palavras. Por exemplo, "Mwa" está no dicionário (sim!), Mas não é retornado nas saídas de Adam, John e rvarcher. É retornado duas vezes no link PHP de Paolo.
Eu tentei este copiando e colando. Diz "Lendo ..." e "Terminar a leitura ...", mas nada aparece depois disso. Nenhuma correspondência é exibida.
Acho que você provavelmente passará a maior parte do tempo tentando combinar palavras que não podem ser construídas pela grade de letras. Então, a primeira coisa que eu faria é tentar acelerar essa etapa e isso deve levá-lo até lá.
Para isso, eu expressaria novamente a grade como uma tabela de possíveis "movimentos" que você indexa pela transição de letras que está observando.
Comece atribuindo a cada letra um número do alfabeto inteiro (A = 0, B = 1, C = 2, ... e assim por diante).
E, por enquanto, vamos usar o alfabeto das letras que temos (normalmente você provavelmente desejaria usar o mesmo alfabeto todo o tempo):
Em seguida, você cria uma matriz booleana 2D que informa se você tem uma certa transição de letra disponível:
Agora passe pela sua lista de palavras e converta as palavras em transições:
Em seguida, verifique se essas transições são permitidas procurando-as na sua tabela:
Se todos forem permitidos, é possível que essa palavra seja encontrada.
Por exemplo, a palavra "capacete" pode ser descartada na quarta transição (m para e: helMEt), pois essa entrada na sua tabela é falsa.
E a palavra hamster pode ser descartada, uma vez que a primeira transição (h para a) não é permitida (nem existe na sua tabela).
Agora, para as provavelmente poucas palavras restantes que você não eliminou, tente encontrá-las na grade da maneira que você está fazendo agora ou como sugerido em algumas das outras respostas aqui. Isso evita falsos positivos resultantes de saltos entre letras idênticas em sua grade. Por exemplo, a palavra "ajuda" é permitida pela tabela, mas não pela grade.
Mais algumas dicas de melhoria de desempenho sobre essa ideia:
Em vez de usar uma matriz 2D, use uma matriz 1D e simplesmente calcule o índice da segunda letra. Portanto, em vez de uma matriz de 12x12 como acima, faça uma matriz 1D de comprimento 144. Se você sempre usar o mesmo alfabeto (ou seja, uma matriz 26x26 = 676x1 para o alfabeto inglês padrão), mesmo que nem todas as letras apareçam na sua grade , você pode pré-calcular os índices nessa matriz 1D que precisa testar para corresponder às palavras do seu dicionário. Por exemplo, os índices para 'olá' no exemplo acima seriam
Estenda a ideia a uma tabela 3D (expressa como uma matriz 1D), ou seja, todas as combinações de 3 letras permitidas. Dessa forma, você pode eliminar ainda mais palavras imediatamente e reduzir o número de pesquisas de matriz para cada palavra em 1: Para 'hello', você precisa apenas de 3 pesquisas de matriz: hel, ell, llo. A propósito, será muito rápido criar esta tabela, pois existem apenas 400 movimentos possíveis de três letras em sua grade.
Pré-calcule os índices dos movimentos na sua grade que você precisa incluir na sua tabela. Para o exemplo acima, você precisa definir as seguintes entradas como 'True':
Também represente sua grade de jogo em uma matriz 1-D com 16 entradas e faça com que a tabela pré-calculada em 3. contenha os índices nessa matriz.
Tenho certeza de que, se você usar essa abordagem, poderá fazer com que seu código funcione incrivelmente rápido, se você tiver o dicionário pré-calculado e já carregado na memória.
BTW: Outra coisa legal a se fazer, se você estiver criando um jogo, é executar esse tipo de coisa imediatamente em segundo plano. Comece a gerar e resolver o primeiro jogo enquanto o usuário ainda estiver olhando para a tela de título do seu aplicativo e colocando o dedo na posição para pressionar "Play". Em seguida, gere e resolva o próximo jogo conforme o usuário joga o anterior. Isso deve lhe dar muito tempo para executar seu código.
(Eu gosto desse problema, provavelmente terei a tentação de implementar minha proposta em Java nos próximos dias para ver como ela realmente funcionaria ... Eu publicarei o código aqui assim que o fizer.)
Ok, eu tive algum tempo hoje e implementei essa idéia em Java:
Para a grade da imagem postada na pergunta original (DGHI ...):
Para as cartas postadas como exemplo na pergunta original (FXIE ...)
Para a seguinte grade 5x5:
dá o seguinte:
Para isso, usei a Lista de Palavras Scrabble do Torneio TWL06 , já que o link na pergunta original não funciona mais. Este arquivo tem 1,85 MB, por isso é um pouco mais curto. E a buildDictionaryfunção lança todas as palavras com menos de 3 letras.
Aqui estão algumas observações sobre o desempenho disso:
É cerca de 10 vezes mais lento que o desempenho relatado da implementação do OCaml de Victor Nicollet. Se isso é causado pelo algoritmo diferente, pelo dicionário mais curto que ele usou, pelo fato de seu código ser compilado e o meu ser executado em uma máquina virtual Java ou pelo desempenho de nossos computadores (o meu é um Intel Q6600 @ 2.4MHz executando o WinXP), Eu não sei. Mas é muito mais rápido que os resultados das outras implementações citadas no final da pergunta original. Portanto, se esse algoritmo é superior ao dicionário trie ou não, não sei neste momento.
O método de tabela usado em checkWordTriplets()produz uma aproximação muito boa às respostas reais. Somente 1 em 3 a 5 palavras aprovadas serão reprovadas no checkWords()teste (consulte o número de candidatos versus o número de palavras reais acima).
Algo que você não pode ver acima: a checkWordTriplets()função leva cerca de 3,65 ms e, portanto, é totalmente dominante no processo de busca. A checkWords()função ocupa praticamente os restantes 0,05-0,20 ms.
O tempo de execução da checkWordTriplets()função depende linearmente do tamanho do dicionário e é praticamente independente do tamanho da placa!
O tempo de execução checkWords()depende do tamanho do quadro e do número de palavras não descartadas checkWordTriplets().
A checkWords()implementação acima é a primeira versão mais idiota que eu criei. Basicamente, não é otimizado. Mas, comparado a checkWordTriplets()isso, é irrelevante para o desempenho total do aplicativo, então não me preocupei. Porém , se o tamanho da placa aumentar, essa função ficará cada vez mais lenta e, eventualmente, começará a importar. Então, precisaria ser otimizado também.
Uma coisa legal desse código é sua flexibilidade:
Você pode alterar facilmente o tamanho da placa: Atualize a linha 10 e a matriz String transmitida para initializeBoard().
Ele suporta alfabetos maiores / diferentes e pode lidar com coisas como tratar 'Qu' como uma letra sem sobrecarga de desempenho. Para fazer isso, seria necessário atualizar a linha 9 e o par de lugares em que os caracteres são convertidos em números (atualmente simplesmente subtraindo 65 do valor ASCII)
Ok, mas acho que até agora este post está bom o suficiente. Definitivamente, posso responder a quaisquer perguntas que você possa ter, mas vamos passar para os comentários.
— Markus A.
Boa resposta. Eu gostaria de ver sua implementação em Java.
@MikkoP Done! :) Demorou cerca de 3 horas e 220 linhas de código. Boa maneira de passar uma tarde. Deixe-me saber se você tem dúvidas sobre como funciona ... :)
Obrigado por postar o código! Eu tentei com meu próprio dicionário depois de adicionar as importações ausentes. Eu recebo um ArrayIndexOutOfBoundException na linha ok = possibleTriplets[entry.triplets[t]];. Hmm?
@MikkoP Atualmente, este código foi escrito para assumir que o dicionário contém apenas letras maiúsculas AZ. O ponto crucial está na linha 34: entry.letters[i] = (byte) letter - 65;simplesmente pega o valor ASCII e subtrai 65 ("A"). Se você tiver trema ou letras minúsculas em seu dicionário, isso fornecerá valores maiores que 31, que não são planejados pela configuração do tamanho do alfabeto na linha 9. Para oferecer suporte a outras letras, você deverá expandir esta linha para mapeá-los no intervalo permitido pelo tamanho do alfabeto.
@AlexanderN Você provavelmente está entendendo a lógica corretamente. Eu cometi um erro copiando carta grade ... Desculpe ... (fixo)
Surpreendentemente, ninguém tentou uma versão PHP disso.
Esta é uma versão PHP funcional da solução Python de John Fouhy.
Embora eu tenha tomado algumas dicas das respostas de todos os outros, isso é principalmente copiado de John.
Aqui está um link ao vivo, se você quiser experimentá-lo. Embora demore ~ ​​2s na minha máquina local, demore ~ ​​5s no meu servidor web. Em ambos os casos, não é muito rápido. Ainda assim, é bastante hediondo, portanto, posso imaginar que o tempo possa ser reduzido significativamente. Qualquer indicação de como fazer isso seria apreciada. A falta de tuplas do PHP tornou as coordenadas estranhas de se trabalhar e a minha incapacidade de compreender exatamente o que diabos está acontecendo não ajudou em nada.
EDIT : algumas correções levam menos de 1s localmente.
+1 @ "e minha incapacidade de compreender o que diabos está acontecendo não ajudou em nada." ri muito. Eu amo a honestidade!
— dna123
Eu não sei PHP, mas a primeira coisa que eu tentaria é içar '/ ['. implode ('', $ alfabeto). '] {3,} $ /' fora do loop. Ou seja, defina uma variável para isso e use a variável dentro do loop.
Tenho certeza de que o PHP mantém um cache global por thread de expressões regulares compiladas, mas tentarei assim mesmo.
@ Daniel: Aparentemente, é o meu servidor web. Isso não acontece quando eu corro localmente. Dar de ombros. Realmente não sinto vontade de caçar.
O que deve ser definido como o parâmetro 7. na função find_words no final?
Não está interessado em VB? :) Eu não pude resistir. Resolvi isso de maneira diferente do que muitas das soluções apresentadas aqui.
Carregando o dicionário e os prefixos de palavras em uma hashtable: 0,5 a 1 segundos.
Encontrando as palavras: média de 10 milissegundos.
EDIT: Os tempos de carregamento do dicionário no servidor host estão em execução de 1 a 1,5 segundos a mais que o meu computador doméstico.
Não sei o quanto os tempos se deteriorarão com a carga no servidor.
Eu escrevi minha solução como uma página da web em .Net. myvrad.com/boggle
Estou usando o dicionário referenciado na pergunta original.
As letras não são reutilizadas em uma palavra. Somente palavras com 3 caracteres ou mais são encontradas.
Estou usando uma hashtable de todos os prefixos e palavras exclusivas em vez de um trie. Eu não sabia sobre a Trie, então aprendi algo lá. A idéia de criar uma lista de prefixos de palavras além das palavras completas é o que finalmente reduziu meus tempos a um número respeitável.
Leia os comentários do código para obter detalhes adicionais.
Vou assumir aqui que você usou o sistema ap em vez de [x] [y] porque o último é bastante complexo no VB? Passei um dia tentando obter uma matriz dinâmica bidirecional dessa vez, ou seja: array (array (1, "olá"), 1, "olá", array ()), ainda não sei como fazer que: P
No PHP e no Perl 2, matrizes escuras são divertidas. Isso pode ser feito em VB, mas eu não chamaria isso de um processo divertido. Dim Arr (,) As Inteiro = {{1,1}, {0,0}}. O processo de PA surgiu de mim, colocando-me na grade e perguntando: 'para onde posso ir daqui?' Eu sei que é uma solução rígida, mas funciona aqui.
— Rvarcher 16/04/09
Ohh eu gosto do VB.NET ... tentei o URL, mas não funcionou. Eu tive que recriar seu código como Windows Forms e ele funciona. Obrigado.
— Ahmed Eissa
Assim que vi a declaração do problema, pensei em "Trie". Mas, como vários outros pôsteres fizeram uso dessa abordagem, procurei outra abordagem apenas para ser diferente. Infelizmente, a abordagem Trie tem melhor desempenho. Executei a solução Perl de Kent na minha máquina e demorou 0,31 segundos para executar, depois de adaptá-la para usar meu arquivo de dicionário. Minha própria implementação perl levou 0,54 segundos para ser executada.
Esta foi a minha abordagem:
Crie um hash de transição para modelar as transições legais.
Repita todas as 16 ^ 3 combinações possíveis de três letras.
No loop, exclua transições ilegais e repita visitas à mesma praça. Forme todas as seqüências legais de 3 letras e armazene-as em um hash.
Em seguida, percorra todas as palavras do dicionário.
Excluir palavras muito longas ou curtas
Deslize uma janela de três letras por cada palavra e veja se ela está entre os combos de três letras da etapa 2. Exclua as palavras que falham. Isso elimina a maioria das não correspondências.
Se ainda não for eliminado, use um algoritmo recursivo para ver se a palavra pode ser formada fazendo caminhos através do quebra-cabeça. (Esta parte é lenta, mas é chamada com pouca frequência.)
Imprima as palavras que encontrei.
Tentei sequências de 3 e 4 letras, mas as sequências de 4 letras atrasaram o programa.
No meu código, eu uso / usr / share / dict / words no meu dicionário. Ele é padrão no MAC OS X e em muitos sistemas Unix. Você pode usar outro arquivo, se quiser. Para quebrar um quebra-cabeça diferente, basta alterar a variável @puzzle. Isso seria fácil de adaptar para matrizes maiores. Você só precisa alterar o hash% transitions e o hash% legalTransitions.
A força dessa solução é que o código é curto e a estrutura de dados simples.
Aqui está o código Perl (que usa muitas variáveis ​​globais, eu sei):
A localização do dicionário mudou? Tentei encontrar as palavras do dicionário porque queria comparar minha solução com todos, mas não consegui encontrá-la no link fornecido em / usr / share / dict. Eu sei que é um tópico bastante antigo, mas será ótimo se você puder me apontar. Agradeço antecipadamente por sua ajuda.
Não tenho meu Mac à mão no momento. Tudo o que você precisa é de um arquivo com palavras em inglês, uma para uma linha, separadas por novas linhas. Você pode encontrar esse arquivo na internet. Um deles está aqui: mieliestronk.com/corncob_lowercase.txt, mas provavelmente existem listas com mais palavras que isso.
Muito obrigado pela resposta. Eu tinha encontrado isso nos arquivos do Ubuntu.
Eu sei que estou super atrasado, mas eu fiz um desses há um tempo atrás em PHP - apenas por diversão também ...
http://www.lostsockdesign.com.au/sandbox/boggle/index.php?letters=fxieamloewbxastu Encontradas 75 palavras (133 pts) em 0,90108 segundos
Dá alguma indicação do que o programa está realmente fazendo - cada letra é onde começa a examinar os padrões enquanto cada '.' mostra um caminho que ele tentou seguir. O mais '.' há quanto mais ele procurou.
Deixe-me saber se você quer o código ... é uma mistura horrível de PHP e HTML que nunca foi feita para ver a luz do dia, então não ouso postá-lo aqui: P
Passei 3 meses trabalhando em uma solução para o problema dos 10 melhores pontos densos 5x5 Boggle boards.
O problema agora está resolvido e apresentado com a divulgação completa em 5 páginas da web. Por favor entre em contato em caso de duvidas.
O algoritmo de análise da placa usa uma pilha explícita para percorrer pseudo-recursivamente os quadrados da placa através de um Gráfico de Palavras Acíclicas Dirigidas com informações diretas sobre filhos e um mecanismo de rastreamento de carimbo de data / hora. Essa pode ser a estrutura de dados de léxico mais avançada do mundo.
O esquema avalia cerca de 10.000 placas muito boas por segundo em um núcleo quádruplo. (9500+ pontos)
Página da Web pai:
Páginas da Web de componentes:
Painel de avaliação ideal - http://www.pathcom.com/~vadco/binary.html
Estrutura avançada do léxico - http://www.pathcom.com/~vadco/adtdawg.html
Algoritmo de análise de placa http://www.pathcom.com/~vadco/guns.html
Processamento em lote paralelo - http://www.pathcom.com/~vadco/parallel.html
- Esse conjunto abrangente de trabalho interessará apenas uma pessoa que exige o melhor.
— JohnPaul Adamovsky
Sua análise é interessante, mas seus resultados não são tecnicamente práticos. O jogo boggle 5x5 inclui um dado que contém as faces BJKQXZ, sua implementação exclui explicitamente todas essas letras e, portanto, a posição do tabuleiro não é realmente possível em um jogo Boggle real.
Seu algoritmo de pesquisa diminui continuamente a lista de palavras à medida que sua pesquisa continua?
Por exemplo, na pesquisa acima, existem apenas 13 letras nas quais suas palavras podem começar (reduzindo efetivamente para a metade o número de letras iniciais).
À medida que você adiciona mais permutações de letras, isso diminui ainda mais os conjuntos de palavras disponíveis, diminuindo a pesquisa necessária.
— jerebear
Eu teria que pensar mais em uma solução completa, mas como uma otimização útil, pergunto-me se vale a pena pré-calcular uma tabela de frequências de digramas e trigramas (combinações de 2 e 3 letras) com base em todas as palavras do seu dicionário e use-o para priorizar sua pesquisa. Eu iria com as letras iniciais das palavras. Portanto, se o seu dicionário contiver as palavras "Índia", "Água", "Extremo" e "Extraordinário", sua tabela pré-calculada poderá ser:
Em seguida, procure esses digramas na ordem de semelhança (primeiro EX, depois WA / IN)
Primeiro, leia como um dos designers de linguagem C # resolveu um problema relacionado: http://blogs.msdn.com/ericlippert/archive/2009/02/04/a-nasality-talisman-for-the-sultana-analyst.aspx .
Assim como ele, você pode começar com um dicionário e o canonacalize palavras criando um dicionário a partir de uma matriz de letras classificadas em ordem alfabética para uma lista de palavras que podem ser escritas a partir dessas letras.
Em seguida, comece a criar as possíveis palavras do quadro e procure-as. Suspeito que isso o levará muito longe, mas certamente existem mais truques que podem acelerar as coisas.
— RossFabricant
Sugiro fazer uma árvore de letras com base em palavras. A árvore seria composta de estruturas de letras, assim:
Então você constrói a árvore, com cada profundidade adicionando uma nova letra. Em outras palavras, no primeiro nível, haveria o alfabeto; então, de cada uma dessas árvores, haveria outras 26 entradas, e assim por diante, até que você soletrasse todas as palavras. Segure-se nessa árvore analisada, e todas as respostas possíveis serão mais rápidas para procurar.
Com essa árvore analisada, você pode encontrar soluções rapidamente. Aqui está o pseudo-código:
Isso pode ser acelerado com um pouco de programação dinâmica. Por exemplo, na sua amostra, os dois 'A's estão ao lado de um' E 'e um' W ', que (a partir do momento em que eles os atingem) seriam idênticos. Não tenho tempo suficiente para realmente explicar o código para isso, mas acho que você pode entender a ideia.
Além disso, tenho certeza de que você encontrará outras soluções se pesquisar no Google para "Boggle solver".
Apenas por diversão, eu implementei um no bash. Não é super rápido, mas razoável.
Hilário. Eu quase postei a mesma pergunta há alguns dias devido ao mesmo jogo! No entanto, não o fiz, porque apenas pesquisei no Google por python boggle solver e obtive todas as respostas que eu poderia desejar.
— physicsmichael
Eu não sabia que o nome popular era "boggle", mas encontrei algumas coisas no google, só estava curioso para ver o que as pessoas inventariam no SO. :)
Percebo que o tempo dessa pergunta chegou e se foi, mas desde que eu estava trabalhando em um solucionador e me deparei com isso enquanto pesquisava no Google, pensei em publicar uma referência à minha, pois parece um pouco diferente de outras.
Eu escolhi ir com uma matriz plana para o tabuleiro de jogo e fazer caçadas recursivas de cada letra no tabuleiro, atravessando de vizinho válido para vizinho válido, estendendo a busca se a lista atual de letras se um prefixo válido em um índice. Ao percorrer a noção da palavra atual, há uma lista de índices no quadro, não letras que compõem uma palavra. Ao verificar o índice, os índices são convertidos em letras e a verificação é feita.
O índice é um dicionário de força bruta que se parece um pouco com um trie, mas permite consultas Pythonic ao índice. Se as palavras 'gato' e 'atender' estiverem na lista, você poderá obter isso no dicionário:
Portanto, se a current_word for 'ca', você saberá que é um prefixo válido porque 'ca' in dretorna True (continue a travessia do quadro). E se a palavra atual for 'cat', você saberá que é uma palavra válida porque é um prefixo válido e'cat' in d['cat'] retorna True também.
Se você sentir isso, é permitido um código legível que não parece muito lento. Como todo mundo, a despesa neste sistema é a leitura / construção do índice. Resolver a placa é praticamente barulho.
O código está em http://gist.github.com/268079 . É intencionalmente vertical e ingênuo, com muita verificação explícita de validade, porque eu queria entender o problema sem criá-lo com um monte de magia ou obscuridade.
— cdent
Eu escrevi meu solucionador em C ++. Eu implementei uma estrutura de árvore personalizada. Não tenho certeza se pode ser considerado um trie, mas é semelhante. Cada nó possui 26 ramificações, 1 para cada letra do alfabeto. Atravesso os galhos do painel de boggle em paralelo com os galhos do meu dicionário. Se o ramo não existir no dicionário, paro de procurá-lo no quadro do Boggle. Eu converto todas as letras do quadro para ints. Então 'A' = 0. Como são apenas matrizes, a pesquisa é sempre O (1). Cada nó armazena se completa uma palavra e quantas palavras existem em seus filhos. A árvore é podada à medida que as palavras reduzem a busca repetida pelas mesmas palavras. Eu acredito que a poda também é O (1).
Carrega dicionário de 178.590 palavras em <1 segundo.
Resolve Boggle 100x100 (boggle.txt) em 4 segundos. ~ 44.000 palavras encontradas.
A resolução de um Boggle 4x4 é muito rápida para fornecer uma referência significativa. :)
Fast Boggle Solver Repositório GitHub
Dado um quadro Boggle com N linhas e colunas M, vamos assumir o seguinte:
N * M é substancialmente maior que o número de palavras possíveis
N * M é substancialmente maior que a palavra mais longa possível
Sob essas suposições, a complexidade desta solução é O (N * M).
Penso que comparar os tempos de execução deste quadro de exemplo de muitas maneiras erra o objetivo, mas, por uma questão de perfeição, esta solução é concluída em <0,2s no meu moderno MacBook Pro.
Esta solução encontrará todos os caminhos possíveis para cada palavra no corpus.
— mon4goos
Esta solução também fornece instruções para pesquisar no quadro especificado
Eu implementei uma solução no OCaml . Ele pré-compila um dicionário como um trie e usa frequências de seqüência de duas letras para eliminar bordas que nunca poderiam aparecer em uma palavra para acelerar ainda mais o processamento.
Ele resolve seu quadro de exemplo em 0,35 ms (com um tempo de inicialização adicional de 6 ms, relacionado principalmente ao carregamento do teste na memória).
As soluções encontradas:
Isso é bom, mas todos os tempos publicados aqui envolvem qualquer momento de "inicialização" para carregar o dicionário na memória, portanto, comparar o 0,35 com os outros momentos está longe de ser preciso. Além disso, você está usando um dicionário diferente? Você está perdendo algumas palavras. De qualquer maneira, +1
— Paolo Bergantino 13/05
O tempo de inicialização leva 6ms, então você está procurando 6,35ms para uma execução completa. Estou usando meu /usr/share/dictdicionário local e algumas palavras estão realmente ausentes (como EMBOLE).
Uma solução JavaScript Node.JS. Calcula todas as 100 palavras exclusivas em menos de um segundo, incluindo a leitura do arquivo do dicionário (MBA 2012).
["FAM", "TUX", "TUB", "FAE", "ELI", "ELM", "ELB", "TWA", "TWA", "SERRA", "AMI", "SWA" , "SWA", "AME", "MAR", "SEW", "AES", "AWL", "AWE", "MAR", "AWA", "MIX", "MIL", "AST", " ASE "," MAX "," MAE "," MAW "," MEW "," AWE "," MES "," AWL "," MENTIRA "," LIM "," AWA "," AES "," MAS " , "BLO", "WAS", "WAE", "WEA", "LEI", "LEO", "LOB", "LOX", "MAE", "ÓLEO", "OLM", "WEA", " WAE "," WAX "," WAF ","MILO", "ORIENTE", "WAME", "TWAS", "TWAE", "EMIL", "WEAM", "OIME", "AXIL", "WEST", "TWAE", "MEMBRO", "WASE" "," WAST "," BLEO "," STUB "," BOIL "," BOLE "," LIME "," SAWT "," LIMA "," MESA "," MEWL "," AXLE "," FAME ", "ASEM", "MILE", "AMIL", "SEAX", "SEAM", "SEMI", "SWAM", "AMBO", "AMLI", "AXILE", "AMBLE", "SWAMI", "AWEST" "," AWEST "," LIMAX "," LIMES "," LIMBU "," LIMBO "," EMBOX "," SEMBLE "," EMBOLE "," WAMBLE "," FAMBLE "]LESTE "," WAME "," TWAS "," TWAE "," EMIL "," WEAM "," OIME "," AXIL "," WEST "," TWAE "," MEMBRO "," WASE "," WAST " , "BLEO", "STUB", "BOIL", "BOLE", "LIME", "SAWT", "LIMA", "MESA", "MEWL", "AXLE", "FAME", "ASEM", " MILE "," AMIL "," SEAX "," SEAM "," SEMI "," SWAM "," AMBO "," AMLI "," AXILE "," AMBLE "," SWAMI "," AWEST "," AWEST " , "LIMAX", "LIMES", "LIMBU", "LIMBO", "EMBOX", "SEMBLE", "EMBOLE", "WAMBLE", "FAMBLE"]LESTE "," WAME "," TWAS "," TWAE "," EMIL "," WEAM "," OIME "," AXIL "," WEST "," TWAE "," MEMBRO "," WASE "," WAST " , "BLEO", "STUB", "BOIL", "BOLE", "LIME", "SAWT", "LIMA", "MESA", "MEWL", "AXLE", "FAME", "ASEM", " MILE "," AMIL "," SEAX "," SEAM "," SEMI "," SWAM "," AMBO "," AMLI "," AXILE "," AMBLE "," SWAMI "," AWEST "," AWEST " , "LIMAX", "LIMES", "LIMBU", "LIMBO", "EMBOX", "SEMBLE", "EMBOLE", "WAMBLE", "FAMBLE"]"TWAE", "EMIL", "WEAM", "OIME", "AXIL", "WEST", "TWAE", "Membro", "WASE", "WAST", "BLEO", "STUB", "BOIL "," BOLE "," LIME "," SAWT "," LIMA "," MESA "," MEWL "," AXLE "," FAME "," ASEM "," MILE "," AMIL "," SEAX ", "SEAM", "SEMI", "SWAM", "AMBO", "AMLI", "AXILE", "AMBLE", "SWAMI", "AWEST", "AWEST", "LIMAX", "LIMES", "LIMBU "," LIMBO "," EMBOX "," SEMBLE "," EMBOLE "," WAMBLE "," FAMBLE "]"TWAE", "EMIL", "WEAM", "OIME", "AXIL", "WEST", "TWAE", "Membro", "WASE", "WAST", "BLEO", "STUB", "BOIL "," BOLE "," LIME "," SAWT "," LIMA "," MESA "," MEWL "," AXLE "," FAME "," ASEM "," MILE "," AMIL "," SEAX ", "SEAM", "SEMI", "SWAM", "AMBO", "AMLI", "AXILE", "AMBLE", "SWAMI", "AWEST", "AWEST", "LIMAX", "LIMES", "LIMBU "," LIMBO "," EMBOX "," SEMBLE "," EMBOLE "," WAMBLE "," FAMBLE "]"WEST", "TWAE", "LIMB", "WASE", "WAST", "BLEO", "STUB", "BOIL", "BOLE", "LIME", "SAWT", "LIMA", "MESA "," MEWL "," AXLE "," FAME "," ASEM "," MILE "," AMIL "," SEAX "," SEAM "," SEMI "," SWAM "," AMBO "," AMLI ", "AXILE", "AMBLE", "SWAMI", "AWEST", "AWEST", "LIMAX", "LIMES", "LIMBU", "LIMBO", "EMBOX", "SEMBLE", "EMBOLE", "WAMBLE "," FAMBLE "]"WEST", "TWAE", "LIMB", "WASE", "WAST", "BLEO", "STUB", "BOIL", "BOLE", "LIME", "SAWT", "LIMA", "MESA "," MEWL "," AXLE "," FAME "," ASEM "," MILE "," AMIL "," SEAX "," SEAM "," SEMI "," SWAM "," AMBO "," AMLI ", "AXILE", "AMBLE", "SWAMI", "AWEST", "AWEST", "LIMAX", "LIMES", "LIMBU", "LIMBO", "EMBOX", "SEMBLE", "EMBOLE", "WAMBLE "," FAMBLE "]SAWT "," LIMA "," MESA "," MEWL "," AXLE "," FAME "," ASEM "," MILE "," AMIL "," SEAX "," SEAM "," SEMI "," SWAM " , "AMBO", "AMLI", "AXILE", "AMBLE", "SWAMI", "AWEST", "AWEST", "LIMAX", "LIMES", "LIMBU", "LIMBO", "EMBOX", " SEMBLE "," EMBOLE "," WAMBLE "," FAMBLE "]SAWT "," LIMA "," MESA "," MEWL "," AXLE "," FAME "," ASEM "," MILE "," AMIL "," SEAX "," SEAM "," SEMI "," SWAM " , "AMBO", "AMLI", "AXILE", "AMBLE", "SWAMI", "AWEST", "AWEST", "LIMAX", "LIMES", "LIMBU", "LIMBO", "EMBOX", " SEMBLE "," EMBOLE "," WAMBLE "," FAMBLE "]LIMAX "," LIMES "," LIMBU "," LIMBO "," EMBOX "," SEMBLE "," EMBOLE "," WAMBLE "," FAMBLE "]LIMAX "," LIMES "," LIMBU "," LIMBO "," EMBOX "," SEMBLE "," EMBOLE "," WAMBLE "," FAMBLE "]
— Charlie Liang Yuan
Então, eu queria adicionar outra maneira PHP de resolver isso, já que todo mundo adora PHP. Gostaria de fazer um pouco de refatoração, como usar uma correspondência de expressão expressa no arquivo do dicionário, mas agora estou carregando o arquivo inteiro do dicionário em uma lista de palavras.
Eu fiz isso usando uma ideia de lista vinculada. Cada nó tem um valor de caractere, um valor de localização e um próximo ponteiro.
O valor da localização é como descobri se dois nós estão conectados.
Portanto, usando essa grade, eu sei que dois nós estão conectados se a localização do primeiro nó for igual à localização dos segundos nós +/- 1 para a mesma linha, +/- 9, 10, 11 para a linha acima e abaixo.
Eu uso recursão para a pesquisa principal. Retira uma palavra da wordList, localiza todos os pontos de partida possíveis e, em seguida, localiza recursivamente a próxima conexão possível, lembrando que ela não pode ir para um local que já está usando (e é por isso que adiciono $ notInLoc).
De qualquer forma, eu sei que ele precisa de refatoração e gostaria de ouvir pensamentos sobre como torná-lo mais limpo, mas produz os resultados corretos com base no arquivo de dicionário que estou usando. Dependendo do número de vogais e combinações no tabuleiro, leva de 3 a 6 segundos. Eu sei que uma vez que eu pregar os resultados do dicionário, isso reduzirá significativamente.
Sei que estou muito atrasado na festa, mas implementei, como exercício de codificação, um solucionador de problemas em várias linguagens de programação (C ++, Java, Go, C #, Python, Ruby, JavaScript, Julia, Lua, PHP, Perl) e Eu pensei que alguém poderia estar interessado naqueles, então deixo o link aqui: https://github.com/AmokHuginnsson/boggle-solvers
— AmokHuginnsson
Aqui está a solução Usando palavras predefinidas no kit de ferramentas NLTK O NLTK possui o pacote nltk.corpus, no qual temos um pacote chamado words e ele contém mais de 2Lakhs palavras em inglês que você pode simplesmente usar no seu programa.
Depois de criar sua matriz, converta-a em uma matriz de caracteres e execute este código
— lava kumar
Aqui está minha implementação em java: https://github.com/zouzhile/interview/blob/master/src/com/interview/algorithms/tree/BoggleSolver.java
A criação da tentativa levou 0 horas, 0 minutos, 1 segundos, 532 milissegundos A
pesquisa de palavras levou 0 horas, 0 minutos, 0 segundos, 92 milissegundos
Nota: Eu usei o dicionário e a matriz de caracteres no início deste tópico. O código foi executado no meu MacBookPro, abaixo estão algumas informações sobre a máquina.
Versão da ROM de inicialização do GB : MBP81.0047.B0E
Versão SMC (sistema): 1.68f96
— Robin Zou
Eu também resolvi isso com Java. Minha implementação tem 269 linhas e é muito fácil de usar. Primeiro, você precisa criar uma nova instância da classe Boggler e depois chamar a função de resolução com a grade como parâmetro. Demora cerca de 100 ms para carregar o dicionário de 50 000 palavras no meu computador e encontra as palavras em 10 a 20 ms. As palavras encontradas são armazenadas em um ArrayList foundWords,.
Eu resolvi isso em c. Demora cerca de 48 ms para rodar na minha máquina (com cerca de 98% do tempo gasto carregando o dicionário do disco e criando o trie). O dicionário é / usr / share / dict / american-english que possui 62886 palavras.
— matzahboy
Eu resolvi isso perfeitamente e muito rápido. Coloquei-o em um aplicativo Android. Veja o vídeo no link da Play Store para vê-lo em ação.
O Word Cheats é um aplicativo que "quebra" qualquer jogo de palavras no estilo matriz. Este aplicativo foi desenvolvido para me ajudar a trapacear no misturador de palavras. Ele pode ser usado para pesquisas de palavras, quebra-cabeças, palavras, busca de palavras, quebra de palavras, boggle e muito mais!