Categories
Review

“Test Driven Development by Example”

Kent Beck

‘By example’ books really aren’t my cup of tea—going back and forth between a book and the actual thing in order to follow along is too much overhead for either activity to work well, and just reading along without doing it myself leaves the book feeling rather anemic a lot of the time. That said, this book wasn’t terrible; I enjoyed Beck’s writing style throughout the whole first part, he did a good job livening it up with some personality so it didn’t feel like reading a WikiHow article. But where my interest really kicked in was in the third part, where it switched to more of a traditional Programming Book style, just dispensing a bunch of condensed advice.

There’s some good little tidbits in the earlier part, though; I think my favorite one was:

[Automated] tests are the Programmer’s Stone, transforming fear into boredom.

A great way to think about it! Write tests so that instead of worrying something will break as you continue working on it, you just go ‘meh, now I’ve gotta wait for the tests to run.’1

This was a quick read; if you’ve been doing some form of TDD, it probably won’t continua much that’s new, but it’s a nice way to get an overview. And if you aren’t doing TDD, go ahead and read it; as I said, it’s quick, and Beck makes a better case for TDD than I will in a single blog post. It’s available in the O’Reilly Library.

  1. Although, ideally, it’s not much of a wait – this is the benefit of unit tests, in particular, that you make them small and very quick to run, and with that you’re able to run the relevant segment of them after every change.
Categories
Review

“97 Things Every Programmer Should Know”

ed. Kevlin Henney

Reviewing a “collected wisdom” book like this is rather difficult, as not only is there not a single plot line throughout it, there’s not even a single core idea to it. It is, in fact, 97 core ideas, each told in a couple of pages. Which does make it easy to pick up and put down, and read in fits and starts. The quality and relevancy of the advice varied, although not in precisely the way you’d expect—there’s a fair few that, with what they referenced, felt very dated but gave advice that remains useful, and then there were a couple that felt dated and gave dated advice. Itself a useful reminder that, for all the field likes being the latest and greatest, newest shiniest, age does not mandate that a piece of wisdom has grown less useful over time.

So hey, the book club at work continues to provide interesting books to read, and this was another one. Give it a read – you can pick up a physical copy1 or read it online through the O’Reilly library.

  1. This is a Bookshop affiliate link – if you buy it from here, I get a little bit of commission. It won’t hurt my feelings if you buy it elsewhere; honestly, I’d rather you check it out from your local library, or go to a local book store. I use Bookshop affiliate links instead of Amazon because they distribute a significant chunk of their profits to small, local book stores.
Categories
Review

“The Clean Coder”

Robert Martin

Another book club book from work—and no, we’re not going through them that fast, I just forgot to write up the previous one until a while after the fact.

This one has a lot less to do with code style and a lot more to do with the career aspects of being a programmer. The subtitle, actually, does a great job of explaining it: “A Code of Conduct for Professional Programmers.” Less “write small chunks of code,” more “show up on time—you may think it doesn’t matter, but it does.” Martin does a great job of switching between giving advice and telling stories that explain how, exactly, he learned that painful lesson. It’s an effective technique—gives it a bit more of a storytelling flow, which helps the book maintain interest. Plus, humans are the storytelling ape; we’ve built entire religions around the idea of using stories to convey a message or impart some wisdom. He’s joining a proud tradition.

I found it a quite useful book, and as I’m writing this in advance of the book club discussion instead of weeks later, I’m looking forward to the discussion with my coworkers. Should be interesting. For now, let me put my opinion of the book like so: this should be required reading for every CS undergraduate program. Maybe hand it out with the diploma? It’s a whole lot of useful advice about the parts of the job that school doesn’t cover. If you’re new to the field, or even if you aren’t, I heartily recommend it. Check it out1—and, if you’ve got an O’Reilly membership, it’s available there as well.

  1. This is an Amazon affiliate link – if you buy it from here, I get a little bit of commission. It won’t hurt my feelings if you buy it elsewhere; honestly, I’d rather you check it out from your local library, or go to a local book store. I prefer Bookshop affiliate links to Amazon when possible, but in this case, the book wasn’t available there, so it’ll have to do.
Categories
Review

“Practical Object-Oriented Design in Ruby”

Sandi Metz

We’ve got a bit of a book club going at work, and this was the first read. We were inspired to read it by a conference talk she gave, where she went through the Gilded Rose kata and very clearly demonstrated the joys of refactoring well-tested code. Metz is a great communicator, and I highly recommend that talk as an entry point to her work.

This book, referred to as “POODR”, continues in the same style of “here’s some techniques you can use to write better code.” And, for the most part, it’s an excellent resource in that regard! Frankly, my only issues with it come down to Ruby not being my taste in languages, and it’s not as if I went into the book not knowing that it’d be in Ruby.

The largest chapter is on writing tests; compared to the rest, it looks rather intimidating. That said, I wound up skimming a lot of it—despite the assertion, earlier in the book, that type systems just add overhead and slow developers down, the majority of the chapter on testing is devoted to writing tests that… ensure you’ve got a type system. I remain unsold on these untyped/duck-typed languages; over here in Swift, I get all those unit tests for free, and the compiler forces me to run them every time I try to build. The time I spend writing tests is entirely spent writing tests for the business logic, not on making sure that I forgot a required method in a subclass.

Duck-typing also requires more faith in your fellow programmer—or even your future self—than I actually have. There’s a great description in the book of implicit object hierarchies, which struck me as being a beautiful academic concept, but will fall apart the moment the project gets larger than “a single developer, working on it continuously.” Add another developer, and they then have to read through the entire codebase to be sure they’ve got enough information to grasp those implicit types; take a break for a month, and you’ve got to reread it all to get back to the same place. And there’s no guarantee that the reading of everything will get you back to the same mindset that you had earlier, so those implicit types fall part pretty quickly. If you want to communicate an idea like that, you have to write it down—and why bother writing a comment when you can write that mental model into the code itself, and have the compiler check that it’s still being followed?

Don’t get me wrong, as I sit here writing only the things I didn’t like about the book. On the whole, I greatly enjoyed it, and found it full of useful ideas! It’s simply the way of human brains to engage more when we disagree than when we agree.

So, if you’re someone who spends time writing code, I do highly recommend this book. Just, y’know, keep in mind that it says Ruby on the cover, and Ruby has opinions about a few things that you may not agree with. You can get the book from its website, or if you (or your employer) have an O’Reilly subscription, it should be available in that library.

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: