CODEWITHSUNDEEP
listhaskellrecursionmaze
raselc
raselc

Reputation: 43

Haskell back tracking recursion

I am implementing this in haskell.

https://www.cs.bu.edu/teaching/alg/maze/

I able to reach the get the list when the "goal" is reached but if the goal is not accessible, the list is not updated. For example 

...#@                           !!!#@
..#..                           !!#..
.##.#     it should return      !##.#
...#.                           !!!#.

My code as follows

path maze x y
    | x >= length (head maze) = (False, maze)
    | y >= length maze = (False, maze)
    | x < 0 = (False, maze)
    | y < 0 = (False,maze)
    | check maze x y '+' = (False, maze)
    | check maze x y '#' = (False,maze)
    | check maze x y '!' = (False, maze)
    | check maze x y 'G' = (True,maze)
    | fst east = (True,snd east)
    | fst south = (True, snd south)
    | fst west = (True, snd west)
    | fst north = (True, snd north)
    | fst noWay = (True, snd noWay)
    | otherwise = (False, maze)
            where 
                    noWay = path (changeVal maze x y '!') x (y+1)
                    north = path(changeVal maze x y '+') x (y-1)
                    south = path (changeVal maze x y '+') x (y+1)
                    east = path (changeVal maze x y '+') (x+1) y
                    west = path (changeVal maze x y '+') (x-1) y

I am not getting the result. I am new in Haskell, can anyone give me a boost so that i could solve this silly problem.

Upvotes: 4

Views: 395

Answers (1)

&#216;rjan Johansen
&#216;rjan Johansen

Reputation: 18199

Immediately, the cause of your problem seems to be that

| otherwise = (False, maze)

uses the original maze instead of returning an updated one. However, even replacing it by snd noWay won't give you the output you want. (I think it will only mark with !s the part southward from your starting point.)

There is a greater problem: When continuing to the next recursive step, your function is not keeping the marks placed by the previous step, but instead starting from the original maze again. Instead, the next recursive step needs to start with the final maze markings produced by the previous one. E.g. (seeing as your guards go east -> south -> west -> north) you need south to leave off where east finished, with something like

south = path (snd east) x (y+1)

If you fix up all your directions similarly, then you don't need noWay. (There will be no unmarked places left to check by that point.) Instead if the north case fails, then it will have marked everything except your initial point, so you can do

| otherwise = (False, changeVal (snd north) x y '!')

Upvotes: 2

Related Questions