# Algorithm for shape detection in 2d list

Hi, I’ve been away from elm for a little bit and I’m having a lot of fun coding a little game in it to remember how it works. It was going swimmingly until I hit a silly algorithm roadblock, would anyone have an opinion on how I should progress?

It might be simple but for some reason I’ve been spending hours on it without a result Truth is I know how to proceed in an imperative manner (boo) but no amount of twisting foldl / foldr or coming up with my own little recursive attempts is helping. Is it actually hard or am I missing the forest for the tree?

Here is the data and what I would like to get back:

``````data : List (List Int)
data =
[ [ 1, 1, 0, 0, 1 ]
, [ 1, 1, 0, 0, 0 ]
, [ 0, 1, 0, 1, 1 ]
, [ 0, 0, 0, 1, 1 ]
]

goal : List (List (Int, Int))
goal =
[ [(0,0), (1,0), (1, 0), (1, 1), (2, 1)]
, [(4,0)]
, [(3,2), (4,2), (3,3), (4,3)]
]
``````

I made an attempt here, with a few explanations. Hope it helps! https://ellie-app.com/rbYhTBcVvmfa1

1 Like

TYSM! I tried to implement flooding but I couldn’t wrap my head around a functional version if it. I’ve gotten rusty. I’ll study it

1 Like

Writing a flood algorithm in a recursive/functional style was the interview question given to me aged 18 applying to Cambridge University to study Computer Science. I did get to the right answer with a bit of prompting, but hell of a question to throw at someone that has never even done any FP before!

Its not really too hard once you see the general outline of it:

``````shouldFill x y grid = ... check if coords x, y should be filled

fillAt x y grid = ... color the pixel filled at x, y

{-| Start a fill at (x, y) -}
fill x y grid =
if shouldFill grid x y then
grid |> fillAt x y |> fill (x+1) y |> fill (x-1) y |> fill x (y+1) |> fill x (y-1)
else
grid
``````

Note: this won’t be very efficient, and might overflow the stack! But its a good place to start.

1 Like

Thanks! Yeah, I don’t know why I hadn’t managed to do it : I made a recursive flood function in JS for a game about… a month ago? But anyway I’m glad it’s not a silly mistake but a serious CS question

The example linked by @lydell includes a `visited` Set to match against, which is probably better for the efficiency and the overflow, yeah, but it’s cool to see bare bones of the flood algorithm

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.