Weekend Programming Challenge, Issue-11 – Solution


Image

The solution of this Problem is the good old flood fill algorithm.

Python is dominating this time, out of 10 solutions we got 6 were written in Python, 2 in C# and 2 in C++.

Here are all submissions: https://github.com/OLIMEX/WPC/tree/master/ISSUE-11

6 Comments (+add yours?)

  1. Dylan
    Jun 03, 2013 @ 19:53:03

    I may have been fastest to submit, but it had a bug (printed last size rather than biggest). The version on GitHub fixes that but also looks for largest region of connected same characters.

    Plus I wasted time trying to think up a ‘new’ algorithm, implementable on microcontrollers with limited memory, using bitmaps (perhaps run-length encoded) of both the previous and current lines as well as some sort of “painting” to work out largest connected regions.

    And then I realised there was an easier way (and I took the easiest).

    Now to learn tkinter 😉

    Reply

  2. Snaksa
    Jun 03, 2013 @ 20:07:32

    Very good solutions! Solution 8 is very simple and clean. I love it! I didn’t realize that we can just write the maze in a variable or read it from file. I was wondering how is it possible to read from console without realizing there is simpler way to do it :D. Maybe the other solutions are also good but I can’t comment them simply because I don’t know Python :D.

    Greetings!

    Reply

  3. DrWheetos
    Jun 04, 2013 @ 18:19:48

    Interesting that some solutions check the diagonal neighbours and some don’t. I came across this as I wrote my solution but the instructions didn’t specifically state whether diagonal cells should be considered as neighbours. Anyway, a fun problem to consider. Cheers Oli

    Reply

    • Dylan
      Jun 05, 2013 @ 00:21:27

      In my case, the Manhattan distance metric was easier, so I rolled with it.

      Including diagonals: abs(x-a) == 1 or abs(y-b) == 1 as the condition, instead of sum == 1.

      And yes, it was lovely to see a clean C solution too. But the OO Python was just as enjoyable to me.

      Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: