Posted: Fri Sep 18, 2015 10:33 pm
I was not looking forward to this one, but I had to do it since it's a major choke point in the map and I wanted access to the next challenges.
It wasn't as bad as I feared, even though I have little experience with this kind of problems.
I preprocessed the image (automatically) to one with only 3 colours: For each pixel, if the colour was close enough to an "ideal" colour white or green, the pixel was set to the ideal colour. Otherwise, black. The thresholds were chosen so that two balls never ended up in the same connected component (that is, they were always separated by a series of 8-connected black pixels), and to avoid splitting a ball into multiple components. I couldn't fully avoid the last case, as there were some mini-components of at most 2 pixels.
Then, spiral eating time. I started at the solid ball at the top. I tried all "nearby" circle centers, as well as a couple of radiuses, and tried to find a circle that covered all pixels from the next ball in the spiral (and none from future balls). Here I accepted multiple connected components, one large and several small ones (max size 2), and disallowed multiple colours and regions crossing the circle boundaries. This step wasn't too bad, it was done with flood fills and "distance from circle center compared to radius"-checks. Luckily, it was a short process to go from "tweaking the algorithm to chop off balls correctly" to getting the whole bitstream without errors.
It took me some moments to find the encoding and the answer, but the first step was naturally much harder.
It wasn't as bad as I feared, even though I have little experience with this kind of problems.
I preprocessed the image (automatically) to one with only 3 colours: For each pixel, if the colour was close enough to an "ideal" colour white or green, the pixel was set to the ideal colour. Otherwise, black. The thresholds were chosen so that two balls never ended up in the same connected component (that is, they were always separated by a series of 8-connected black pixels), and to avoid splitting a ball into multiple components. I couldn't fully avoid the last case, as there were some mini-components of at most 2 pixels.
Then, spiral eating time. I started at the solid ball at the top. I tried all "nearby" circle centers, as well as a couple of radiuses, and tried to find a circle that covered all pixels from the next ball in the spiral (and none from future balls). Here I accepted multiple connected components, one large and several small ones (max size 2), and disallowed multiple colours and regions crossing the circle boundaries. This step wasn't too bad, it was done with flood fills and "distance from circle center compared to radius"-checks. Luckily, it was a short process to go from "tweaking the algorithm to chop off balls correctly" to getting the whole bitstream without errors.
It took me some moments to find the encoding and the answer, but the first step was naturally much harder.