두 번째 미로에서 상태 모나드를 사용하여 단어 찾기

Question

4x4 문자 (반복 될 수 있음)와 임의의 단어가있는 경우 해당 단어를 보드에서 찾을 수 있는지 찾아야합니다. 이제이 문제는 멋진 것들을 사용하지 않고 해결하기가 쉽습니다. 그러나이 문제에 접근 할 수있는 방법을 학습 관점에서 우리는 고려 이런 일이있을 때 :

• 보드 그래서 우리는 그것을
• 때를 Reader를 사용에 관심이 말할 수, 일정 변경하지 않을 것입니다

  findWord :: String -> Position -> ReaderT Board (State (S.Set Position)) -> Bool 
  

  : 그래서 우리가

첫 번째 아이디어 상태 사용에 관심이 말할 수 있습니다, 우리는 보드에 방문 타일 세트를 유지할 필요가 단어를 검색하면이 같은 것을 사용하는 것이 었습니다

입력 문자열은 검색 할 단어의 나머지 부분입니다.

여기서 Position은 (Int, Int)가 현재 보드에있는 위치를 식별하는 데 사용되며 (Set는이 검색 경로에서 방문한 위치를 저장합니다.)

보드 단순히 편의를 위해 각 위치에서의 문자에 대한 정보를 저장하고 같이 [숯불]

가 복귀 BOOL 생각할 수는 보드가 포함되어있는 경우라고하는 최종 결과로서 사용하는 것을 의미 단어 또는 아니요

보드에서 검색 할 수 있습니다. 모든 방향으로 만들어졌다 (그래서 대각선이 포함되어있다). 단어가 수평선 또는 대각선 중 하나 일 필요는 없습니다. 단어의 문자가 보드에 연결되어있는 한 해결책은 유효합니다.

실제 문제는 다음과 같습니다. State를 사용하여이 문제를 해결하면 단어가 발견되는 즉시 함수가 반환되고 다른 경로를 검색하지 않도록 어떻게 할 수 있습니까? 예를 들어 우리가 찾고자하는 단어가 "AAAAA"이고 보드가 단순히 "A"의 16 개 문자이면 함수는 5 회 반복 후에 반환해야하며 가능한 모든 경로를 검색하지 않습니다 (왜냐하면 경로가 거대하다)?

하나의 제약 조건을 사용하여이 문제에 접근하는 방법에 대한 몇 가지 팁을 찾고 있습니다 : 상태 모나드 사용. 어떤 정보라도 가치가 있습니다. 조언이나 의사 코드 또는 작업 솔루션 일 수도 있습니다. 감사.

Answer 1

Bool을 반환하는 대신 변압기 스택에 다른 모나드를 사용하여 바로 가기 계산 기능을 명시하는 것이 좋습니다. Maybe는 :

findWord :: String -> Position -> ReaderT Board (StateT (S.Set Position) Maybe)() 

나는이 자동으로 각 실패 후 상태를 다시 바람을 가지고 스택의 적절한 지점이라고 생각합니다.

지금, 당신은 차례로 목록의 각 옵션을 테스트하고 정지 (A Maybe 기반 스택) 성공 첫 번째 하위 옵션에, 또는 전체 msum 경우 실패 할합니다 (MonadPlus 클래스에서) msum을 사용할 수 있습니다 아무 것도하지 않습니다. 예 : something like

msum $ map (findWord remainingString) listOfNeighboringPositions