For those who’ve been inspired by last programming challenge, I thought I’d give annotations on a programming exercise I’ve created.
The challenge: code an AI to solve Rush Hour, you can play Rush Hour online if you aren’t familiar with how the game works. If you want to follow along, you can find my solution on github.
Let me start with the high-level thought process.
How to solve it?
The most naive approach is a brute-force solution, trying every move, filtering out backtracking. Some simple math will let us rule this possibility in or out.
The only state in Rush Hour the positions of the cars. Thus the number of possible game states is equal to the number of possible arrangements of cars. We can approximate an upper bound of the latter by multiplying the number of possible spaces each car could move to (this ignores cars being on top of each other, hence upper-bound). In the above board we see 8 vehicles, and each vehicle can only ever occupy 4 or 5 squares [they can’t turn ever] depending if their size). Some boards have more vehicles, so if we estimate 10 vehicles at 5 positions that’s 5^10 < 10 million. So yes, brute force is in.
The general solution:
Because “brute force” is such a general mechanism, there really is a lot of reusable code in the solution. In my solution I’ve pulled out the reusable logic into genericSearch.js. The idea is that a whole host of puzzles follow the same form: Given an Initial state try to get to End State.
The docblock below is the interface to genericSearch that is used by the solver, but this same search function could be used by any number of puzzles (triangle peg game, sudoku, etc).
Thus, to write the program (after having written genericSearch.js) all I must do is to make those 5 parameters [and any helpers to go along].
Initial state – Brain Dead Simple
I know a lot of engineers who would be tempted to represent the game of rush hour with at least a half dozen classes (“so we have vehicle base class, which has car or truck subclasses, and we’d need a class for the board and legal moves”).
And that is a valid way to go about it. I went with a minimalist solution– a nested array 36 characters. Brain dead simple.
It seems that perfection is attained, not when there is nothing more to add, but when there is nothing more to take away.
Antoine de Saint Exupery
Because every car is at least 2 in size, this string notation suffices to convey both the position and bearing of vehicles, everything we need. Since the exit is always in the same spot, that needn’t be represented in state. Adjacent characters of the same value represent the same car.
We have our first parameter, initial state. However, we have skimped in our state, by not defining what a vehicle is or orientation in the state object we’ll have to define that logic later.
Some of the advantages of representing the board state as an array of characters:
- It’s trivial to serialize. Serialization is key to making sure we don’t backtrack when searching for solutions.
- It’s very easy to input.
- It’s very easy to output and debug. At the end to see the solution found I can simply “play” the states and watch the characters move.
- At any given moment it’s trivial to determine if a space is vacant of any vehicles.
- Certain impossible board-states are prevented automatically (e.g. a misconfigured initial state could not result in overlapping vehicles).
Some of the disadvantages:
- We must determine every car on the board and which direction it’s facing. This is non-trivial (let’s call “trivial” something that I code correctly on my first try).
- Moving a vehicle is kind of “dirty.” By moving vehicles by overwriting the board state it’d be easy make bugs that create weird board states (vehicle with size one).
- Certain impossible board-states are prevented automatically (e.g. a misconfigured board state could not result in a vehicle with no bearing)
Parameter 2 – Possible moves
Each vehicle may move forward, or backward (assuming its path is unobstructed). To keep things simple, we can say a vehicle can only move 1 square at a time and represent longer travels as multiple moves.
This definition introduces a few more functions (getVehicles, canGoForward, canGoBackward), which I won’t put into the post. See the full code for that. The reason I exclude them is because I don’t have any particularly elegant solution to those tasks.
Parameter 3 – Apply move
Again I have no magic to work on this one so I won’t show the 15 lines. In fact, it feels like the least dry piece of the code to me, and it makes me want to refactor the most. The number of occurrences of -1 are too numerous (6) and speak to casual coding.
So don’t get me wrong, I don’t want to say anybody should hold this code up as an amazing example of good code. What I hoped to illustrate is how a problem that seems daunting can actually be broken down into 19 functions, the longest being 23 lines.
The Gimmes
I have two functions left. One is how to uniquely represent the state as a string. The other is win condition. The former is easy: JSON.stringify. The latter is easy as well.
And we’re done! Now I’ve left our the genericSearch.js, which honestly was perhaps the most fun, but this post is long enough. If your thirst isn’t quenched try playing around with it yourself.
Takeaways
- Keep the pure & reusable code in a separate file (or separate function) from your 1-time, implementation-dependent code
- Maybe 2 classes would have come in handy. Despite being small, the code doesn’t seem as friendly as I’d want. If I had kept state as an object of objects I would never have to define string -> state mapping.
- Unit tests would have been a good way to allow such a refactoring to be less painful.