(1.0+2.0)+((3.0+(4.0-5.0))/(6.0-((7.0/8.0)-9.0)))
(NOTE: This post is extremely old. I know this is horrible, horrible code, but I leave it up there for the kids.)
The challenge: calculate all numbers between 1900 and 2100 with exactly one operator between the sequential numbers 123456789 with as many brackets as desired.
The reward: points
Being a data guy I know a fair bit about Excel, MySQL, star schema data marts, statistics, and split tests - but very little on how to properly program in scripting languages; form, modularization, unit testing, etc… It is something I’m working on. I think that even though I came to the problem with a vastly inferior tool set for the job (as anyone could see from my unedited Ruby code) I was able to employ a couple of cool tricks to solve the problem.
When I first approached the problem many of the solutions had already been worked out by patio11 over at hacker news. He had calculated 192 of the 201 solutions. What I love about this problem is just how simply it can be stated. Yet, without some clever trick, it would take a long time to find out if there is even a solution for each number.
I believe I was the first to calculate 200 of the solutions - there are actually 201 solutions between 1900 and 2100, but when I finished coding the program I was so high on results coming in through the first pass that I completely missed that fact until I talked about the problem with Ben Coe the next day.
I decided to not even look at the code already posted in the discussion of the problem because I was afraid I would end up going down the same path as others before me.
I approached it like this:
- Forget about trying to brute forcing the problem. If it were possible to brute force it in any reasonable amount of time, then it would be solved by now. (This turned out to be wrong.)
- Brackets must be important, otherwise the solution would have been found by now. (This turned out to be right.)
- Use randomness! The possible combinations are so large that even if you randomly assign operators and nested brackets a million times, who cares? The duplication rate would be so small that it didn’t really matter. (This turned out to be the cincher.)
Here was my first pass: http://pastie.org/776041
(you may notice me trying to find 1911, one of the unsolved ones when I first attempted the problem)
In order to avoid potential memory leaks (and to make sure my script was still running correctly) I just made a controlling processes that restarted the ruby script with ‘system “ruby numbers.rb”’ and counted the number of files in the storage directory with ‘system “ls -l num\ | egrep -c ‘^-‘”’. Here is where I should have checked for 201 files, rather than 200, but in the end it didn’t matter. I ended up rewriting “numbers.rb” to dynamically change the weighting of the operators, but it only marginally helped. What I should have done is rewrote it to dynamically change the weighting of the bracket placement rates. But despite these shortcomings I ended up finding the numbers in less than 8 hours of computing.
I told Toronto hacker friends and coworkers Ben Coe and Justin Giancola about the problem.
We talked genetic algorithms over beers, dismissing them, but on the bus ride home Ben came up with an amazing solution (which he implemented in Java, but it doesn’t really matter what language you choose). Later, Justin implemented a Common Lisp solution that has astonishingly little lines of code. Ben continues the story in Part Two of Three here: Ben’s Awesome solution. (If you’re a Lisp nerd and just want to jump to Part three of three by Justin it can be found here: Justin’s wicked small Lisp solution)
Rot13 Spoiler on Ben’s solution: Ora’f cebtenz pnyphyngrf gur nafjref svir gubhfnaq gvzrf snfgre guna zvar
