Who is up for a programming challenge?

Is anyone still doing good, old-fashioned programming? Or is everyone prompting and trying to tame LLMs (and asking themselves why)?

Here’s a small programming challenge, a brain teaser and a balm for the soul.

Motivation

The other day, my son brought home a game from the library and asked me to play with him. After playing a while I realized that not only was it very engaging (and difficult), but it also posed an interesting mathematical problem.

The game is called Rush Hour, was invented by Nob Yoshigahara in the 1970s, and is produced by ThinkFun.

Like many other puzzles, this problem is PSPACE-complete.

I know there are many solutions out there, but I want to enjoy the process of solving it myself, so I’m not going to look at them. I hope you share that sentiment and adhere to the code of honor. If you show me your solution, I promise not to look at it until I finish mine.

Challenge description

The challenge is simple. Given the initial position of the cars on the board, find a sequence of moves that will lead the red car 🚗 to the exit of the maze.

I created a getting started template with a simple reference implementation of the game (without the solver), as well as a few examples with initial positions and solutions. Feel free to choose a different starting point if it better suits your needs.

Code of conduct

• Don’t look at existing solutions until you’ve tried it yourself. This implies the following:
• No cheating! No direct use of LLMs or code assistants. Just hard work and fun!

Prize

Personal satisfaction. Plus, I might invite you for coffee.

FAQ

• Do we really need a FAQ section? Maybe not.
• Why did you include torch in the dependencies? I was thinking ahead a bit. That’s admittedly opinionated; remove it if you like.
• What do you mean by “no direct use of LLMs”? Ideally, you wouldn’t use them at all, or at least you wouldn’t ask for the solution directly.
• Is this going to help me prepare for my next job interview? Unfortunately, no.
• Is it going to bring me fame, fortune, and recognition? No, I don’t think so. There are no vanity metrics, except maybe showing it off to your partner, spouse, or mom.
• Do I need to buy the game? No, you don’t have to, but if you want, it’s a lot of fun.
• Can I program it in MIT/GNU Scheme instead of Python? Absolutely! I’m a huge fan myself. Any language should work. However, natural languages are forbidden by the rules of the challenge.
• Can I use pen and paper instead? Yes you can. Send me a scan or a letter.
• Can I publish the results? Do I have to mention you in the credits? (yes, no). Unless you come up with a beautiful algorithm, discover a new mathematical theory or law of nature, or solve the P vs NP problem, then (yes, yes).
• When is the deadline? There are no deadlines. Whenever you see fit.

Solution

If you are really sure you want to see the solution, click below.