Lessons from working 6 months on a math problem (and failing)

I'm a coder, most certainly not a mathematician. But when I saw the 17x17 challenge in late 2011, I couldn't resist having a crack at it. You can read a bit more on the problem itself here. Each day, I couldn't resist spending another day on it. Long story short, despite some temporary success, I didn't end up solving the problem. But I consider that time spent, about 6 months of full-time effort, to have been an incredibly worthwhile investment. Below is the furthest I got, a grid with 3 monochromatic rectangles (every corner of the rectangles marked is on the same colour). Still not zero which was the goal, but for a few months, it was the 'least broken' solution known.

It might not look like much, but it took crazy amounts of time to find the right colourings for those damn cells. The solution ended up being found by means of a SAT solver, but here's what I learned in the process of not finding it:

1. A problem which is easy to state can addict quite severely

I was able to get some people hooked on the problem just by explaining it to them in a few minutes. The same process probably happened with me and lots of others on the internet who got caught up with this problem over the years it took to solve. Maybe there's something there to learn about motivation, or perhaps asymmetries like this are just a rare occurence.

2. Optimisation with instant feedback is incredibly addictive

As I started writing code for this problem, I found out I could work on it for hours on end without distraction, quite unusual for me. I chalk this up to a tight feedback loop. Have an idea, implement it, get back a number. Think of ways to improve the number, start the cycle all over again. This is a cycle I would run dozens of times a day. Obviously more fundamental ideas would take more time to see the fruits of, and that's when I actually lost focus, but when the brain has been rewarded so richly with small cycles, it can afford to go a bit longer without reinforcement. This tells me that A/B testing or a similar numeric optimisation area would be quite motivating to me and I've made a mental note to go into this in the future.

3. There are some really big numbers out there

The space of possible colourings for the 17x17 problem is almost 10^174. Comprehending this number is beyond the human mind. If you took the number of all particles in the observable universe and squared it, you would still be a factor of 10^14 off.

While I can't say I grasped that number in the slightest, I do feel it has recalibrated my sense of what 'big' is. The earth's population which nears 7 billion now feels like a decidedly small number.

4. The value of optimisations at different levels of the stack

Once my basic strategy was set, a lot of the work came down to optimisation. I categorise that work into three fairly separate categories: mathematical, algorithmic, and implementation/hardware.

By mathematical optimisations, I mean ones where discovering a symmetry in the search space allowed me to prove that solving one case equated solving a whole class of cases, as each member of the class was equivalent to every other member. If I discovered a symmetry that folded 32 cases into one, I automatically had a 32x speedup.

Algorithmic optimisations are more pedestrian. A certain computation needs to be made, and finding a better way to compute it means speeding up the whole process, since as a rule these computations ran millions of times. By the end, I realised that indeed the best way is to have the code do almost nothing.

Implementation optimisations are ones that have to do with better mapping to hardware. For instance at some point I decided that Python wasn't going to cut it and I'd need to drop to C. By translating my algorithms unchanged into C I got about a 10x improvement. This was a very naive translation done in a day, without me having much experience in C past some classes in university.

Of course, I also cheated. I realised that my code spent a huge amount of time counting the set bits on a byte. I could implement that on my side, or get a CPU that implements that as a single instruction. I did spend quite some time implementing faster versions of it, mostly ending up with lookup tables, but at the end of the day, the i7 family of CPUs have POPCNT as a builtin. Moving to the i7 caused a big speedup, and using the popcnt builtin was another large boost to speed. Unfortunately I don't have exact data but it was certainly integer multiples of the previous level of performance.

The vast array of optimisation techniques I could bring to bear was definitely a surprise. Generally the mathematical optimisations tended to dominate whenever I could get them, but each optimisation level in aggregate yielded many orders of magnitude worth of improvement in my final result. While I don't have exact numbers, I do recall that a single run went from around 4 minutes to tens of ms, and then the mathematical optimisations reduced the amount of runs needed from a theoretical 2 * 10^20 to about 100 million. All in all, by the end I was able to do a complete run in a bit over a day on 2 cores of an i7. That run produced the matrix above, but unfortunately, no solution.

5. The interplay between thinking in code and thinking on paper

It's clear that an algorithmic breakthrough can be worth 1000 micro-optimisations. But sometimes the opposite happened. Glancing through the results of an algorithmic run showed a pattern I wasn't aware of. Taking that back to paper allowed me to make further theoretical breakthroughs that sped up runtime by additional orders of magnitude. So getting my hands dirty with code, besides giving non-trivial speedups, also hinted at mathematical symmetries not to be sneezed at.

6. Deep understanding of combinatorics and symmetries

In other words, I learned some math on the intuitive level. My knowledge of symbols is still probably poor, but I do have a mental toolkit on combinatorics developed that I trot out once in a while, and will probably invest more in in the future. I hear combinatorics is a good avenue to probability, and probability is something I really want to get good at.

7. Intuitive understanding of trees

Working through combinatorics, one cannot avoid getting very familliar with the tree data structure. It's not that I couldn't understand a tree before, but there is a whole other level of 'burnt in' that something can get when you keep digging those neural pathways day in and day out. It helped me work on parsers and grammars soon after, and to this day I think I use the tree structure to consider possible avenues of action in my current role as 'business guy'.

8. If your approach is wrong, hard work doesn't matter

Despite the enormous amount of work I put in, I bet on an early assumption that I knew would make or break the effort. I did this knowingly as I felt I couldn't beat more experienced mathematicians without cheating somehow. My assumption ended up being wrong, and therefore my code yielded no results. No matter how hard I worked, it wouldn't have made a difference.

This is always something to keep in mind when working on startups. If your high-order bit is set wrong, you can optimise the lower ones to infinity and while the final cause of death might be 'ran out of money', the effort may be finished before it starts for reasons like 'chose too small a market'.

9. If you're passionate enough, it may be the direct results that don't matter.

This is not to say that just because you might fail you shouldn't try. While working on this problem, I knew full well I could and probably would fail. But doing a mental check on the pleasure and learning I drew from the excercise, I constantly came up positive, such that actually finding a solution would be the icing on the cake. I feel the same way about my startup. I want it to succeed, in fact I'm doing my absolute best to ensure it does, but at the same time I know I'm already on the plus side in terms of experience gained such that if it all was to evaporate tomorrow, I'd still have been more than adequately rewarded for my efforts.

10. The immense joy of shutting everything out and falling into absolute focus

I consider my focus to be very fragile. It has taken many years of trial and error (or just aging) to approach some stable level of productivity, and even this is definitely not 100%. While working on the 17x17 however, I was able to experience something completely new for me: absolute focus approaching bliss. Some times I'd start working in the morning, and when my girlfriend would come back home in the evening I would feel like I'm waking up into reality, only to spend a few hours resting to start again next morning. There's something special to be said about that, regardless of all the other lessons above. My girlfriend did mention that I may be slipping into Uncle Petros territory, but thankfully I was able to stop on time to finish my PhD and move on.

I'd like to avoid closing a cliche worthy of a whiskey commercial such as "...Because sometimes, the journey is worth more than the destination...". Instead, I'll just say that I'd trade several of my minor successes for another failure this good. Maybe another problem will come and capture my imagination in a similar way in the future.

Fun aside: HN user TN1ck did up the actual 17x17 solution in d3.js and SVG/AngularJS, using the technique described in my previous post. Cool stuff!

Alexandros Marinos

I love to take the web to new places. Currently working on resin.io to bring web programming in contact with the physical world, so you can 'git push' JS to your devices.

comments powered by Disqus