Если у нас есть доска 4x4 с символами (которые могут повторяться) и какое-то случайное слово, нам нужно найти, можно ли найти это слово на доске. Теперь эту проблему довольно легко решить, не используя никаких причудливых вещей. Но с точки зрения обучения, как можно подойти к этой проблеме, когда мы должны учитывать следующие вещи:
- доска постоянна и не собирается меняться, поэтому допустим, что мы заинтересованы в использовании Reader для нее
- при поиске слова нам нужно сохранить набор посещенных плиток на доске, поэтому, скажем, мы заинтересованы в использовании для него состояния.
Первая идея заключалась в том, чтобы использовать что-то вроде этого:
findWord :: String -> Position -> ReaderT Board (State (S.Set Position)) -> Bool
input String — это оставшаяся часть слова, которое мы ищем
где Position (Int, Int) используется для определения того, где мы сейчас находимся на доске (и Set хранит, какие позиции мы посетили во время этого пути поиска)
Доска просто хранит информацию о символах в каждой позиции, для простоты ее можно представить как [[Char]]
возврат Bool предназначен для использования в качестве окончательного результата, чтобы сказать, содержит ли доска слово или нет
поиск на доске можно производить во всех направлениях (включая диагонали); слово не должно быть ни на горизонтальной линии, ни на диагональной линии - пока символы слова соединены на доске - решение верно.
Теперь о самой проблеме: если мы используем состояние для решения этой проблемы, как мы можем гарантировать, что функция вернется, как только слово будет найдено, и не продолжит поиск других путей? Например, если слово, которое мы ищем, — «ААААА», а поле — это просто 16 символов «А», то функция должна возвращаться примерно через 5 итераций и не продолжать поиск всех возможных путей (поскольку количество успешных пути огромны)?
Я ищу несколько советов о том, как решить эту проблему, используя одно обязательное ограничение: использование монады State. Ценна любая информация, будь то совет, псевдокод или даже работающее решение. Спасибо.
