Is anyone still doing good, old-fashioned machine learning or programming? Or is everyone prompting and trying to tame LLMs (and asking themselves why)?
Here’s a small programming challenge, an old-fashioned 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. Long story short, I couldn’t solve any of the puzzles, so I decided to use a brute-force approach, similar to what we are trying to do with intelligence.
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
- AI-ish approaches, such as optimization or neural networks are allowed.
- 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
torchin 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.