Nerding Out – Solving the British Intelligence Challenge in 7 Seconds

Ever watch James Bond and thought, “No need for all those explosions and danger, I’d rather be that nerdy, brilliant Q character who sips on his tea and plays with the coolest gadgets ever!”? Well, the GCHQ (British intelligence agency) recently put out their Christmas challenge which some speculate is a recruiting challenge! Either way, put on your Q hat and enjoy the first of four puzzles in this year’s challenge…

It’s a grid-shading puzzle with row/column descriptors that ultimately deduce to a singular grid solution, kind of like sodoku or a crossword. To learn more about how to play, check out the original post from the GCHQ.

grid shading puzzle - low res version

Once I saw this post go up on a tech blog, I thought, “I bet I could write some code in LabVIEW to solve that quickly! I bet I could even make it look good!” Well, I had functional code in a matter of a few short hours… creating the final version with all the story telling, video shooting, and editing took about 16 hours (not counting the hours of idle thought that went into obsessing over this fascinating challenge).

HighRes

My first mistake: this could be brute forced quickly enough

In a 25×25 grid, you could generate every possible solution with a modern computer until all the row descriptors matched within a few hours, right? I mean, even my 6 month old Surface 3 had to be able to bang this out in less than a day, right? WRONG. Even as an electrical engineer, I overlooked the exponential nature of binary numbers. Let me explain…

The grid is 25 cells by 25 cells, totaling 625 cells altogether. This can be represented by a 625 bit number in the computer and therefore it has 2^625 possibilities. That’s ~10^188… or a truly gigantic number. Putting that in other terms, if were able to generate and check 1,000 possibilities per second, it would take more generations of our offspring than we can comprehend to process through every possibility of the puzzle.

My second mistake: the math behind this would be easy enough

While generating matching patterns for a given row descriptor, I found that some had many possible patterns and some had very few.  I thought, “I bet there’s a way to figure out how many patterns are possible based on the number of groups and empty spaces.” This led to a 2 day long journey that was fascinating enough to be its own blog post! To shorten that journey for you, the math relies on the number of groups, and, instead of the empty spaces, it’s related to the number of unspoken for spaces. In other words, in the figure below you’ll see empty spaces that have to be there because they’re next to a group, and then empty spaces that don’t have to be there.

With those “unspoken for” (not a mathematical term, just my brains expression) spaces, you can move around groups. One short equation for U (unspoken for spaces) is (empty spaces – # of groups). I figured out that it was related to U & G (# of groups) pretty early on, but I was still pretty lost. Another property I found was that if you switched U & G, you’d get the same result! If there were 2 groups and 5 unspoken for spaces OR 5 groups and 2 unspoken for spaces, either way you’d still get 21 possible patterns. The two banks of possible patterns would be different, but there were 21 possibilities! Strange, huh?

Ultimately, what led me to the solution was obsessing over the patterns across U & G. For example,

Groups Unspoken Possibilities
1 0 1
1 1 2
1 2 3
1 3 4
1 4 5
1 5 6
2 0 1
2 1 3
2 2 6
2 3 10
2 4 15
2 5 21
3 0 1
3 1 4
3 2 10
3 3 20
3 4 35
3 5 56

Look at those patterns in the possibilities column! Way too fishy, right?! So I plugged in the pattern into the all-powerful Google and found that they were known mathematical sequences with equations that described them.  They equations were similar enough to where I figured out it was actually a combinatoric pattern:

equatino

Thank you, Google!

Final Thoughts

This puzzle was way too much fun to think about and code. I really need to keep doing puzzles and projects to keep my brain happy. It was also a brilliant play by the GCHQ. They gave the world some fun puzzles and charity even benefited from it!

My brain thinks in too visual a way to use anything but LabVIEW for projects like this. Additionally, there were so many times where along the way I discovered something interesting because of how everything in LabVIEW was so easy to bring out to the front panel (GUI) instead of being hidden away in code.

Big thanks to my wife, my friend Sam, anyone who ever made LabVIEW better, my Microsoft Surface (and OneNote), and to all my fellow nerds out there!

More Stuff

I’ve uploaded the source code and went even nerdier for an article over at LabVIEW Maker Hub. Check it out here!

LabVIEW MakerHub – Source Code & More Details