Categories
Programming

Islands.swift

Back in undergrad, I did a lot of programming challenges – the sort of thing that shows up as a somewhat-contrived question in an interview. Great way to learn about automated testing, though, as in a school environment it’s basically an automated test suite where you aren’t allowed to see the tests.1

I’ve been wanting to brush up on algorithms a bit, and figured this would be a good way to do it. This time around, though, I’m using Swift; C++ was a fine language to learn, but I have exactly no desire to use it anymore.

So, the first problem I found whilst aimlessly googling was “Islands”. Given a grid of some sort (could be [[Bool]], although in this case I’ve done one as [[Character]], with '1' and '0' being the inputs2), count the number of islands in it.

An island, in this case, is any contiguous collection of '1' is in the grid, while all the the '0's are ocean.

Step One: Ask Questions

First question: what does ‘contiguous’ mean? Can we move diagonally, or only in the four cardinal directions?

Only the four cardinal directions, in this example.

Alright. Next, what happens at the edges? Do we Asteroids-style loop around, or is it just ‘out of bounds == ocean’?

Out of bounds is ocean.

Excellent! Means we don’t have any literal edge cases.

Final question before I start actually digging into the problem, how are we hooking into the test case?

protocol Islands { func numIslands(_ grid: [[Character]]) -> Int }

Alright, simple enough. Let’s get cracking.

Step Two: Brainstorm

My first thought upon seeing a grid is “flood fill.” Now, this isn’t quite a flood fill, because the whole point is that it’s not all interconnected, but that at least gives me a starting point – for a flood fill, you want recursion. And you want to remember where you’ve been, so you can make a base case – otherwise, you’ll just loop forever. O(infinity) isn’t really ideal.

So, what’s the actual algorithm here?

Simple enough: for each point on the grid, check if it’s part of a new island. If it is, add one to our count of islands; if it isn’t, don’t. Move on to the next point on the grid.

Now, how do we check if it’s a new island? Also pretty simple: check if we’ve been here before; if we have, it’s not a new island. Then check if it’s an island; if it isn’t, it’s also not a new island. And, now that we know it’s a new island, we go recursive – mark that we’ve been to this spot, and flood fill our way across the neighboring tiles on the grid until we run out of island.

Step Three: Code

class Solution: Islands { private var visited: [[Bool]] = [] // (1) private var grid: [[Character]] = [] // (2) @discardableResult private func isNewIsland(x: Int, y: Int) -> Bool { // (3) guard x >= 0 else { return false } guard y >= 0 else { return false } guard x < grid.count else { return false } guard y < grid[0].count else { return false } if (visited[x][y]) { return false } visited[x][y] = true if (grid[x][y] == "1") { // visit all neighbors isNewIsland(x: x+1, y: y) isNewIsland(x: x-1, y: y) isNewIsland(x: x, y: y+1) isNewIsland(x: x, y: y-1) return true } else { return false } } func numIslands(_ grid: [[Character]]) -> Int { // (4) // precondition checks guard grid.count > 0 else { return 0 } guard grid[0].count > 0 else { return 0 } // reset visited state let subItem = Array<Bool>(repeating: false, count: grid[0].count) self.visited = Array<Array<Bool>>(repeating: subItem, count: grid.count) self.grid = grid var islandCount = 0 for i in 0..<grid.count { for j in 0..<grid[i].count { if isNewIsland(x: i, y: j) { islandCount = islandCount + 1 } } } return islandCount } }

Let’s go through this bit by bit.

  1. visited is key – we need to know where we’ve been. Unlike the folks making the problem statement, I actually know what my data type is – [[Bool]]
  2. This… is mostly for ease of passing it around. While I could write up my isNewIsland function in a purely-functional sense, with it taking in the coordinates, visited state, and grid, and then outputting the result… well, that’s kinda silly, really.
  3. isNewIsland is the bulk of the work. Let’s go through it.
    • The first four lines are checking that we’ve got valid input. This saves us from needing to check the range every time we call the method; if we try to do something that we can’t, it’ll just return false. Admittedly, I’m not checking that the grid properly exists before using it, but that’s what private is for – this is an implementation detail.
    • Next, check if we’ve visited this spot before. If we have, we’re done – it’s not a new island!
    • Before we go any further, mark this spot as visited! Important, because we may be recursing shortly, and we don’t want to get caught in an infinite loop.
    • Check if this is an island at all. If it isn’t, we’re done – this wasn’t a new island. If it is, though, we recurse. This is where the @discardableResult comes in – since we’ve got an early bail-out for “we’ve already visited this spot”, we know we’ll never be checking the same island twice, so we actually don’t care about the result of checking the neighboring spaces, we just need it to happen… so that they get marked as visited. And after we’re done marking the whole island as visited, we can finally return true, telling the caller (if they’re listening!) that this was a new island.
  4. Finally, our implementation of numIslands. Mostly it’s just checking for valid inputs – Swift can enforce at compile-time that nobody tries to pass us anything completely the wrong type, but it can’t force people to give us a grid with dimensions greater than 0 in either direction, so we need to check that ourselves. After that, we set up our visited as all-false, copy the grid, and loop through it, counting up our islands.

Step Four: Test

This part, I will mostly leave to your imagination; for myself, I just hit ‘run’ and let the automated tests do their thing. In an interview, Step Two should also include coming up with some test cases and running through them on your pseudo code – and remember to include one or two invalid inputs!

After that, if your tests pass, you could talk about changes you might make. Given my numerous remarks about [[Character]] instead of [[Boolean]], my thought would be to make it generic – have a grid of [[T]] and take a (T) -> Bool closure that tells you whether or not a grid point is an island. I’d also want to comment up the code a bit more, which I’ve neglected to do in this case as I’m writing a blog post around it instead.

Now, having already spoiled the answer, I’ll go ahead and mention that I tried this out at LeetCode; while this one may not be the most fun for you in the immediate wake of my explainer, they’ve got plenty of other solutions you could take a crack at, and a variety of languages to use. Give it a go, it’s kinda fun!

  1. Basically, the inverse of an “opaque box” analysis, if you think about it.
  2. And by “I’ve done one” I mean “the site that gave the example,” because I… wouldn’t use [[Character]] to represent a [[Bool]].
Categories
Technology

Reversi: A Postmortem

Spring quarter consisted of two things: beginning the internship, and an “intro to programming” course. Which, at first glance, seems like it would’ve been a “coast to an easy A” kind of thing for me, but that wasn’t my goal. And, to quote the Dean of UCI’s Graduate Division, “grad school is for you.”

So, at the start of the quarter, I sat down to figure out what my goals for this class would be, and came up with two things. The first, which I won’t be writing about, was to get a bit more teaching experience – in the vein of “guiding people to asking the right questions,” rather than just showing them the answers.

Second, and the topic of this post, was that I wanted to learn Vapor. The professor was kind enough to let me do this – instead of doing the course project (an online game of Reversi) in Node, I did it in Vapor.

As a learning exercise, I’d say it was… okay.

What Went Well

I love Swift as a language. The type system just fits in my head, it aligns incredibly well with how I think.

In this case, that meant representing all the events to the server, and the responses from the server, as enums.

It also meant that I could have a solid Game class that represented the whole game board, with some neat logic, like getters that calculate the current score and if the game has ended. Pair those with a custom Codable implementation, and you’ve moved the majority of the logic to the server.

… and What Didn’t

The fact that I’m representing events to and from the server as enums, instead of using Vapor’s routing system, was a result of tacking on another thing I wanted to learn about, and trying to loosely hew to the nominal course objectives. The official version of the project used WebSockets for all the communication. Vapor supports WebSockets. Great combo, right?

Well, sure, but it meant I did almost nothing with the actual routing. Instead I re-implemented a lot of it by hand, and not in a very clean way. Vapor doesn’t scope things the way I expected – based on some experimentation, it instantiates a single copy of your controller class and reuses it, rather than having one per connection. So instead of having nice class-level storage of variables, and splitting everything up into functions with the main one handling routing, it all wound up crammed into the main function. Just so I could maintain the proper scope on variables. I’m still not happy about it.

What’s Next

I’d like to keep tinkering with Vapor. When I’ve got the time, I have a project in mind where it seems like a good fit.

In the meantime, I hope their documentation improves a lot. The docs they have are good tutorials, and cover their material well; they also, it feels like, leave out the lion’s share of the actual framework. By the end of the project, I’d given up on the docs and was just skimming through the source code on GitHub, trying to find the implementation of whatever I was trying to work with. (This, by the way, doesn’t work with Leaf, the templating engine – the docs are basically nonexistent, and the code is abstracted enough that you can’t really skim it, either.)

Complaints aside, I still like Vapor. I picked up a book on the framework, which seems like a pretty good reference on the topic.

And hey, it was a neat little project. (The JavaScript is a disorganized mess, but it’s also aggressively vanilla – while the rest of the class was learning about NPM, I decided to see how far I could get with no JS dependencies whatsoever. Answer: very.) Check it out, if you’d like: