CODEWITHSUNDEEP
algorithmhaskelltraversal
Marcus Buffett
Marcus Buffett

Reputation: 1389

Board-traversing function in Haskell returning duplicates

I'm working on implementing Go (the game) in Haskell, but I can't seem to figure out how to write the function that finds the strings (groups of connected stones) on the board. What I have works if the stones are connected in a line or l-shape, but if they're in a square formation I start to get duplicates, and if it's a 3x3 square it just runs forever (or maybe just for a very long time). The full source code is here ( http://lpaste.net/113992 ) if anyone wants to help out. The problem as far as I can tell is that the function will reach the same square by two different paths, ex. (1,1) -> (2,1) -> (2,2), and (1,1) -> (1,2) -> (2,2), so (2,2) gets counted twice, here's the relevant code :

stringOfPiece :: Piece -> Game -> [Piece]
stringOfPiece piece game = recursiveStringFinder piece game [piece]

recursiveStringFinder :: Piece -> Game -> [Piece] -> [Piece]
recursiveStringFinder piece game piecesFound 
    | null adjacentUnfoundPieces = [piece]
    | otherwise = concat [recursiveStringFinder adjacentPiece game ([piece] ++ adjacentUnfoundPieces ++ piecesFound) | adjacentPiece <- adjacentUnfoundPieces] ++ [piece]
    where adjacentUnfoundPieces = [adjacentPiece | adjacentPiece <- findAdjacentPieces piece game, not $ adjacentPiece `elem` piecesFound]

Basically the stringOfPiece function is only there to call recursiveStringFinder with the extra argument (piecesFound). recursiveStringFinder takes three arguments; the piece it's currently on, the game which holds all the pieces, and the piecesFound argument which is all the pieces it has found so far. If there are neighbors, it returns [piece] (the current piece), combined with the results of calling recursiveStringFinder on the adjacentPieces. If there are not, it returns a list with a single element (the piece it's currently on). For example, if the board looked like this :

xxx
xxx
WWx

Where 'w' is white and x is empty, it would start at (1,1), see it has a neighbor, and return [recursiveStringFinder (2,1) game [(1,1)]] ++ [(1,1)], and recursiveStringFinder (2,1) game [(1,1)] would be [(2,1)], since there are no neighbors, so the result is [(1,1),(2,1)]. This algorithm works fine for the above board, and these, as examples :

xxx    Wxx    xWW
Wxx    Wxx    xWx
WWx    WWW    WWW

Basically it works when there's only one way to get to a given stone. It comes up with duplicates if it's given something like this :

WWx
WWx
xxx

I could just get rid of duplicates with 'nub', but there's a serious slowdown issue when the groups of stones become bigger (3x3, 2x4, etc). How can I modify my code so the same stone isn't reached more than once?

Upvotes: 0

Views: 224

Answers (1)

j_random_hacker
j_random_hacker

Reputation: 51226

I'm not good at reading functional code, but I think the problem is that you aren't threading the growing list of found pieces from the output of one child call into the next, meaning that e.g. knowledge of the list of extra pieces found by the first such call isn't available to its sibling subproblems. Currently, your

[recursiveStringFinder adjacentPiece game ([piece] ++ adjacentUnfoundPieces ++ piecesFound) | adjacentPiece <- adjacentUnfoundPieces]

effectively tries to solve all child subproblems "in parallel", which is broken.

This would be easy to fix with imperative code: you would simply pass (a reference to) a mutable piecesFound array (or hashtable, etc.) into the recursiveStringFinder function: then any updates to this are automatically seen by all future calls, including later sibling calls. To do this in functional code, you'll need to change the way you solve subproblems, from using that list comprehension (which assumes subproblem independence), to explicitly enforcing that subproblem i depends on subproblem i-1 being solved already. I think this will involve replacing the list comprehension with a single recursion that takes a list ("queue") of child pieces to try, and in each invocation pulls out the first item, tests whether it's been seen already, and processes it if not -- but I'm not sure.

Upvotes: 1

Related Questions