Как найти список возможных слов из буквенной матрицы [Boggle Solver]
в последнее время я играл в игру на моем iPhone под названием Scramble. Некоторые из вас могут знать эту игру как испуг. По сути, когда игра начинается, вы получаете матрицу букв так:
F X I E
A M L O
E W B X
A S T U
цель игры состоит в том, чтобы найти как можно больше слов, которые могут быть сформированы путем связывания букв вместе. Вы можете начать с любой буквы, и все буквы, которые ее окружают, являются честной игрой, а затем, как только вы перейдете к следующей букве, все буквы, которые окружают эту букву честная игра, за исключением любых ранее использованных букв. Так что в сетке выше, например, я мог бы придумать слова LOB,TUX,SEA,FAME и т. д. Слова должны быть не менее 3 символов, и не более NxN символов, которые были бы 16 в этой игре, но могут варьироваться в некоторых реализациях. Хотя эта игра забавная и захватывающая, я, по-видимому, не очень хорош в этом, и я хотел немного обмануть, сделав программу, которая дала бы мне наилучшие слова (the длиннее слово тем больше очков вы получите).
образец Boggle http://www.boggled.org/sample.gif
я, к сожалению, не очень хорошо разбираюсь в алгоритмах или их эффективности и так далее. Моя первая попытка использует словарь такие, как этот (~2.3 MB) и выполняет линейный поиск, пытаясь сопоставить комбинации со словарными записями. Это занимает очень долгое время, чтобы найти возможные слова, и так как вы получаете только 2 минуты за круглый, он просто не адекватен.
мне интересно посмотреть, могут ли какие-либо Stackoverflowers придумать более эффективные решения. Я в основном ищу решения с использованием Big 3 Ps: Python, PHP и Perl, хотя все, что связано с Java или C++, тоже круто, так как скорость важна.
ТЕКУЩИЕ РЕШЕНИЯ:
- Адам Розенфилд, питон, ~20s
- John Fouhy, Python, ~3s
- Kent Fredric, Perl, ~1s
- Дариус Бэкон, питон, ~1s
- rvarcher, VB.NET (видео по ссылке), ~1s
- Paolo Bergantino, PHP (видео по ссылке), ~5s (~2s локально)
награда:
я добавляю щедрость к этому вопросу, как мой способ сказать спасибо всем людям, которые скинулись со своими программами. К сожалению, я могу дать только принятый ответ одному из вас, поэтому я буду измерять, кто имеет самый быстрый boggle solver через 7 дней и наградит победителя щедростью.
награды. Спасибо всем, кто участвовал.
Comments