{"id":35,"date":"2024-06-21T02:45:03","date_gmt":"2024-06-21T02:45:03","guid":{"rendered":"https:\/\/think-twice.me\/?p=35"},"modified":"2024-06-21T02:45:03","modified_gmt":"2024-06-21T02:45:03","slug":"solving-rush-hour","status":"publish","type":"post","link":"https:\/\/think-twice.me\/?p=35","title":{"rendered":"Solving rush-hour"},"content":{"rendered":"\n

For those who\u2019ve been inspired by last programming challenge<\/a>, I thought I\u2019d give annotations on a programming exercise I\u2019ve created.<\/p>\n\n\n\n

The challenge: code an AI to solve Rush Hour, you can\u00a0play Rush Hour\u00a0online<\/a>\u00a0if you\u00a0aren\u2019t familiar with how the game works. If you want to follow along, you can find\u00a0my solution<\/a> on github.<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Let me start with the high-level thought process.<\/p>\n\n\n\n

How to solve it?<\/h6>\n\n\n\n

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.<\/p>\n\n\n\n

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\u2019t turn ever] depending if their size). Some boards have more vehicles, so if we estimate 10 vehicles at 5 positions that\u2019s 5^10 < 10 million.  So yes, brute force is in.<\/strong><\/em><\/p>\n\n\n\n

The general solution:<\/h6>\n\n\n\n

Because \u201cbrute force\u201d is such a general mechanism, there really is a lot of reusable code in the solution. In my solution I\u2019ve pulled out the reusable logic into genericSearch.js<\/em>. The idea is that a whole host of puzzles follow the same form: Given an Initial state try to get to End State.<\/p>\n\n\n\n

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).<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

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].<\/p>\n\n\n\n

Initial state \u2013 Brain Dead Simple<\/h6>\n\n\n\n

I know a lot of engineers who would be tempted to represent the game of rush hour with at least a half dozen classes (\u201cso we have vehicle base class, which has car or truck subclasses, and we\u2019d need a class for the board and legal moves\u201d).<\/p>\n\n\n\n

And that is a valid way to go about it. I went with a minimalist solution\u2013 a\u00a0nested array 36 characters. Brain dead simple.<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n
\n

It seems that perfection is attained, not when there is nothing more to add, but when there is nothing more to take away.<\/p>\nAntoine de Saint Exupery<\/cite><\/blockquote>\n\n\n\n

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\u2019t be represented in state. Adjacent characters of the same value represent the same car.<\/p>\n\n\n\n

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\u2019ll have to define that logic later.<\/p>\n\n\n\n

Some of the advantages of representing the board state as an array of characters:<\/p>\n\n\n\n