Advertisement
Guest User

Untitled

a guest
May 4th, 2016
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.53 KB | None | 0 0
  1.  
  2. type Board = [[Char]]
  3.  
  4. data Link = Link { pos :: (Int, Int)
  5. , vis :: [(Int, Int)]
  6. , mat :: [Char] } deriving Show
  7.  
  8. neighbors :: Board -> Int -> Int -> [(Int, Int)]
  9. neighbors b i j = [(x, y) | x <- [(i - 1) .. (i + 1)],
  10. y <- [(j - 1) .. (j + 1)],
  11. x > -1,
  12. y > -1,
  13. x < (length b),
  14. y < (length (b !! 0)) ]
  15.  
  16. initial :: Board -> [Char] -> [Link]
  17. initial b [] = []
  18. initial b (c:cs) =
  19. let possible = [(i, j) | i <- [0..((length b) - 1)],
  20. j <- [0..((length (b !! 0)) - 1)],
  21. ((b !! i) !! j) == c ]
  22. in map (\c -> Link { pos = c, vis = [c], mat = cs }) possible
  23.  
  24.  
  25. findSolution :: Board -> [Link] -> [Link] -> Bool
  26. findSolution _ [] [] = False
  27. findSolution b [] links = findSolution b links []
  28. findSolution _ ((Link { pos = (i, j), vis = vs, mat = []} ):xs) links = True
  29. findSolution b ((Link { pos = (i, j), vis = vs, mat = (m:ms)} ):xs) links =
  30. let ns = [Link { pos = (x, y), vis = [(x, y)] ++ vs, mat=ms } | (x, y) <- (neighbors b i j),
  31. (all (\v -> v /= (x, y)) vs),
  32. ((b !! x) !! y) == m ]
  33. in findSolution b xs (links ++ ns)
  34.  
  35.  
  36.  
  37. testBoard :: Board
  38. testBoard = [
  39. ['a', 'c', 'l', 'b'],
  40. ['r', 'e', 'b', 'u'],
  41. ['l', 'n', 'c', 's'],
  42. ['c', 'm', 'n', 'o']]
  43. --
  44. --
  45. theDoot :: Board -> [Char] -> Bool
  46. theDoot _ [] = True
  47. theDoot b xs =
  48. let starting = initial b xs
  49. in findSolution b starting []
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement