Algorithm for shape detection in 2d list

Learn
1

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 :fearful: 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)]
   ]
2

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

1 Like
3

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:

1 Like
4

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
5

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 :+1:

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 :sparkles:

6

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