As my regular reader knows, I have a weakness for coding puzzles, especially ones that lend themselves to Linq solutions. Sites like projecteuler.net hold a fatal attraction for me. Once in, I get absorbed, and can spend hours and hours on the problems.
For this reason, I have tried my best to avoid LeetCode, as it’s another great place to lose yourself for a long time. However, someone posted a video of his solution to problem #200, and it got the better of me. The problem is that, given a 2D array of chars, each of which can be 0 to represent water or 1 to represent land, find out how many islands there are, where cells are only considered to be connected horizontally or vertically, not diagonally.
His solution used Python, and implemented a breadth-first algorithm. Without looking too closely at his code, I decided to give it a go in C#.
The first attempt
My first attempt (which didn’t work properly, but was abandoned due to my Linq epiphany, see below) was to walk the dry land cells in each row in turn, checking the cells above and to the left (which have already been visited) to see if they are dry land. If so, the current cell can be put in the same island. The code looked something like this…
char[,] islands = {
{'1','1','1','0','0'},
{'1','1','0','0','0'},
{'1','1','0','0','0'},
{'0','0','0','1','1'},
};
int rows = islands.GetLength(0);
int cols = islands.GetLength(1);
int[,] results = new int[rows, cols];
int maxIslands = 0;
// Go through and check each cell
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (IsLand(islands, row - 1, col)) {
results[row, col] = results[row - 1, col];
} else if (IsLand(islands, row, col - 1)) {
results[row, col] = results[row, col - 1];
} else if (IsLand(islands, row, col)) {
results[row, col] = ++maxIslands;
}
}
}
Console.WriteLine($"Total islands: {maxIslands}");
static bool IsLand(char[,] islands, int row, int col) {
try {
return islands[row, col] == '1';
} catch {
return false;
}
}
After setting up a sample set of cells, lines 8 and 9 get the number of rows and columns. We then create an array that will contain the island number for each cell (or 0 if it’s water).
The main work is done in the nested for loop on lines 13 to 23. This uses the utility method IsLand to make the code cleaner. We check all dry cells to see if the cell above is land, and if so, set the current cell to be in the same island. If the cell above were water, then we check the cell to the left. If neither are dry, then we have reached a new island, so we add increase the counter and set the current cell to the new island number.
This worked moderately well, although not completely. I had to stop in the middle, so didn’t get chance to work out what needed tweaking before I realised that the algorithm wouldn’t work in all cases. If we had a set of cells like this…
0 1 1 1
…then the top-right cell would get put in a new island #1. The bottom-left cell would also be put in a new island #2, as it isn’t touching any previously-checked dry land. This meant that when we checked the bottom-right cell, we would assign it to the island above (ie #1, the number of the top-right cell). However, it is also touching the bottom-left cell, which is in island #2.
In order to get around this, I would have to check for this situation and merge the two islands. I had an idea how this could be done, when something started niggling in the back of my mind.
The epiphany
I love Linq. I can’t imagine coding without it, and tend to look at every problem as a potential candidate for Linq. Whilst contemplating this puzzle, I realised that what we are doing is the sort of set operation that Linq excels at. However, unlike the regular set operation that are solved with methods like Select, Where that operate on a single element at a time, this one required knowledge of the rest of the problem data as well. How was I going to handle this.
At this stage, I thought of Aggregate, which is one of those Linq methods that I don’t use very often, but find incredibly powerful when I do.
In simple terms, Aggregate is a bit like Select, in that it iterates over every element in the input, but unlike Select, you get access to a running accumulated value as well. Although the accumulator is normally used to keep something like a running total of what’s gone on before, I could use it to keep the current state of the solution, meaning that whilst processing a single element, I knew what had happened to previously processed elements.
With a little fiddling, I came up with the following code…
List<List<(int, int)>> islands = cells.Cast<char>()
.Select((val, n) => (val, n))
.Where(c => c.val == '1')
.Select(c => (c.n / cells.GetLength(1), c.n % cells.GetLength(1)))
.Aggregate(new List<List<(int, int)>>(), (List<List<(int, int)>> acc, (int row, int col) cell) => {
List<(int, int)>? above = acc.FirstOrDefault(i => i.Contains((cell.row - 1, cell.col)));
List<(int, int)>? left = acc.FirstOrDefault(i => i.Contains((cell.row, cell.col - 1)));
if (above != null && left != null) {
if (above == left) {
above.Add(cell);
} else {
above.AddRange(left);
above.Add(cell);
acc.Remove(left);
}
} else if (above != null) {
above.Add(cell);
} else if (left != null) {
left.Add(cell);
} else {
acc.Add(new List<(int, int)> { cell });
}
return acc;
});
This isn’t actually as complex as it looks at first!
Lines 1 to 4 just mould the data into a more usable form. We take the whole 2D array as a 1D array of chars, then select the cell value along with its index (0, 1, 2, …). Line 3 filters out the water, as that doesn’t interest us at all, and line 4 converts the index of the 1D array to a pair of co-ordinates that correspond to the dry cells in the 2D array. Dumping the output of those few lines would give…
(0, 0) (0, 1) (0, 2) (1, 0) (1, 1) (2, 0) (2, 1) (3, 3) (3, 4)
If you compare that with the original 2D array, you see it’s just the co-ordinates of the dry cells.
Then we call Aggregate, passing an empty list of lists as the initial value. The idea is that each individual list will be a collection of cells that make up an island.
The code inside the lambda checks both the cells above and to left of the current one, to see if they are already in an island. We do this by looking for an island that contains each of these two cells. We then act as follows…
1) If both islands are non-null (meaning that both the above and left cells are in islands), then we check if the two islands are the same. If so, we just add the current cell to one of them (doesn’t matter which as they are the same). If they are different, then we have hit the problem mentioned above, so we add the cells in the island containing the left cell to the island containing the right cell, then remove the left island.
2) The next two clauses (lines 16 to 19) are for when exactly one of the two neighbouring cells is non-null. We just add the current cell to that island.
3) Line 21 is for the only other option, that this is a new island
Once we have iterated over all cells, we are left with a collection of lists, where each list represents one island. We can dump these out very easily…
Console.WriteLine($"Islands: {islands.Count}");
islands.ForEach(l => Console.WriteLine($"{string.Join(", ", l.Select(c => $"({c.Item1}, {c.Item2})"))}"));
This gives the expected output…
Islands: 2 (0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (2, 0), (2, 1) (3, 3), (3, 4)
Took me a little while to get this one working, but it was an excellent exercise in reminding myself how to use Aggregate.
My code also ended up quite a bit shorter than the Python solution I saw.
Be First to Comment