Count "Islands" in a Matrix Using C#
Once in a while, a developer can be challenged by a new problem that puts him/her in the zone. This one happened recently and it's exhilarating! I have never encountered this problem before. Honest! And this is how I (eventually) solved it...
The problem presented to me showed a jagged array matrix of 0's and 1's. The "islands" are the 1's adjacent to each other up-, right-, down- and left-wise (not diagonal). I need to count the number of islands and print it out.
My initial version was to convert the jagged array matrix to a sparse matrix using a Dictionary<(int, int), bool> of coordinates. Using the sparse matrix, I would have only the essential data I need to count the islands. I could then create a loop to apply the traversal logic. The traversal logic was like a recursive depth-first search (DFS) function, which could be used to "build" an island of adjacent 1's, marking sparse matrix items as traversed along the way. Each island "built" were then added to a collection of islands. The final line was to basically count the items in the collection of islands. You can see this original code here: CountIslandConsoleAppProgram v1.
Problem solved, right? Well, I wanted to optimize it. Creating the sparse matrix required a loop on the original matrix. Then another loop would have to be created to consume the sparse matrix. I designed the sparse matrix to also be my store for traversed items. In fact, after reviewing my code, that was essentially its purpose: to store the traversed items. So what if I moved the code to "sparsify" in the original loop and used a HashSet<(int, int)> instead to maintain a collection of traversed items? The new version was exactly that, and you can can see the code's evolution right here: CountIslandConsoleAppProgram v2.
Was I done? Well, I wanted to optimize it further. Version 2 proved that there was really no need to prepare the data. I could have only one loop, in which the traversal could also be done directly. However, there were extra variables in my code that were not essential to solving the problem. In my loop and traversal functions, I was maintaining a couple of collections: one to represent an island and another to store the collection of islands. They were using up unnecessary memory. I could easily replace them with just a count variable and the program would still deliver the requirement: to count the number of islands in the matrix. You can see the final version here: CountIslandConsoleAppProgram v3.
I'm sure there are many ways to solve this problem. However, I am happy with the final version I have right now. It is efficient and easy to read. I used C# 7.3 and .Net Core 2.1. It worked and performed quite well. If you've worked on this problem before, share the other ways you did it using C#. ;-)
The problem presented to me showed a jagged array matrix of 0's and 1's. The "islands" are the 1's adjacent to each other up-, right-, down- and left-wise (not diagonal). I need to count the number of islands and print it out.
My initial version was to convert the jagged array matrix to a sparse matrix using a Dictionary<(int, int), bool> of coordinates. Using the sparse matrix, I would have only the essential data I need to count the islands. I could then create a loop to apply the traversal logic. The traversal logic was like a recursive depth-first search (DFS) function, which could be used to "build" an island of adjacent 1's, marking sparse matrix items as traversed along the way. Each island "built" were then added to a collection of islands. The final line was to basically count the items in the collection of islands. You can see this original code here: CountIslandConsoleAppProgram v1.
Problem solved, right? Well, I wanted to optimize it. Creating the sparse matrix required a loop on the original matrix. Then another loop would have to be created to consume the sparse matrix. I designed the sparse matrix to also be my store for traversed items. In fact, after reviewing my code, that was essentially its purpose: to store the traversed items. So what if I moved the code to "sparsify" in the original loop and used a HashSet<(int, int)> instead to maintain a collection of traversed items? The new version was exactly that, and you can can see the code's evolution right here: CountIslandConsoleAppProgram v2.
Was I done? Well, I wanted to optimize it further. Version 2 proved that there was really no need to prepare the data. I could have only one loop, in which the traversal could also be done directly. However, there were extra variables in my code that were not essential to solving the problem. In my loop and traversal functions, I was maintaining a couple of collections: one to represent an island and another to store the collection of islands. They were using up unnecessary memory. I could easily replace them with just a count variable and the program would still deliver the requirement: to count the number of islands in the matrix. You can see the final version here: CountIslandConsoleAppProgram v3.
I'm sure there are many ways to solve this problem. However, I am happy with the final version I have right now. It is efficient and easy to read. I used C# 7.3 and .Net Core 2.1. It worked and performed quite well. If you've worked on this problem before, share the other ways you did it using C#. ;-)
Comments
Post a Comment