Solving Programming Puzzles without using your Brain
This post is a write-up of a solution to part of a programming puzzle I did yesterday. It’s a little different than the usual “solution + theory” approach, though: I’m going to talk about the actual steps you’d need to take to get to the solution (i.e. what to google, what intermediate code looks like, etc.). Often write ups like this are presented as finished artefacts, with little info on the tricks or techniques the author used to jog their intuition into figuring out the puzzle (or where some intermediate step requires a leap of insight). In actual fact, this particular puzzle requires almost no insight at all: I’m going to show how to get to a working solution without understanding any of the theory behind it!
Spoilers ahead for the google foobar problem “Distract the Guards”.
The Problem
We’re interested in a particular type of sequences of pairs of numbers. These sequences are generated from a starting pair and like so:
If and are equal, the sequence stops.
Otherwise, the smaller number is subtracted from the larger, and then the smaller is doubled, and the sequence continues with these two numbers.
Here’s an example starting with 3 and 5:
3, 5
6, 2
4, 4
---- done ----Once it hits 4, 4, the first condition is met, and the
sequence stops. Not all of these sequences stop, however:
1, 4
2, 3
1, 4
---- done ---- As you can see, in this case we loop back around to
1, 4: our task is to figure out, given a pair of numbers,
whether the sequence generated by them loops forever, or stops at some
point.
Step 1: Write a Dumb Solution
This step is crucial: before trying to figure out any of the deep mathematics behind the problem, write the dumbest thing that could work. You’re going to need it, anyway, to test your faster versions against, and besides, it might be good enough as-is!
def sequence(n,m):
while n != m:
yield (n,m)
if n < m:
m -= n
n *= 2
else:
n -= m
m *= 2
def loops(xs):
seen = set()
for x in xs:
if x in seen:
return True
else:
seen.add(x)
return False
def solution(n,m):
return loops(sequence(n,m))The first function actually generates the sequence we’re interested in: it uses python’s generators to do so. The second function is just a generic function that checks a sequence for duplicates. Finally, the last function answers the question we’re interested in.
Step 2: Graph it
Next, we want to try and spot some patterns in the answers the function generates. Remember, we’re not really interested in figuring out the theory at this point: if we find out that a loop only happens when both numbers are even (for instance), that’s good enough for us and we can stop there!
We humans are pattern-matching machines: to leverage our abilities, though, we will need to visualise the data somehow. In this case, I’m going to plot a simple scatter graph to the terminal, using the following code (I apologise for my terrible indentation style):
print(
'\n'.join(
''.join(
'*' if solution(x,y) else ' '
for x in range(1,81)
)
for y in range(100,0,-1)
)
)And we get the following output:
Output
*************************** ******************************* ********************
**************************** *** *********** ******************************* ***
************* *************** **************************************************
****************************** *************************************************
******************************* ************************************************
******************************** *********************** ******* ***************
********************************* **********************************************
** *************************** *** *********************************************
*********************************** ********************************************
************ ******* *************** *******************************************
***** *********************** ******* *************** *************** **********
************************************** *****************************************
*************************************** ****************************************
******** ******************* *********** ***************************************
***************************************** **************************************
****************************************** ******* *********************** *****
*********** *************** *************** ************************************
******************************************** ***********************************
********************************************* **********************************
************** *********** ******************* *************** *****************
*********************************************** *******************************
************************************************ ***************************** *
***************** ******* *********************** *************************** **
********** *********************** *************** ************************* ***
*************************************************** *********************** ****
**** *************** *** ******************* ******* ********************* *****
***************************************************** ******************* ******
****************************************************** ***************** *******
*********************** ******************************* *************** ********
******************************************************** ************* *********
********* ******************************* *************** *********** **********
********************** *** ******************************* ********* ***********
*********************************************************** ******* ************
************************************************************ ***** *************
********************* ******* ******************************* *** **************
************** *********************** *********************** * ***************
*************************************************************** ****************
******* *********** *********** *************** ************* * ***************
* *********************************************************** *** **************
** ********************************************************* ***** *************
*** *************** *************** *********************** ******* ************
**** ***************************************************** ********* ***********
***** *************************************************** *********** **********
****** *********** ******************* ***************** ************* *********
******* *********************************************** *************** ********
******** *************** ******* ********************* ***************** *******
********* ******* *********************** *********** ******************* ******
********** ***************************************** ********************* *****
*********** *************************************** *********************** ****
************ *** *************************** ***** ************************* ***
************* *************** ******************* *************************** **
****** ******* ********************************* ************* *************** *
*************** ******************************* *******************************
**************** ***************************** *********************************
***************** *************************** **********************************
** *********** *** ******* ******* ********* ***** *********************** *****
******************* *********************** ************************************
******************** ********************* *************************************
***** ******* ******* ******************* *********** *************** **********
********************** ***************** ***************************************
*********************** *************** ****************************************
******** *** *********** ************* ***************** ******* ***************
************************* *********** ******************************************
************************** ********* *******************************************
*********** *************** ******* *********************** ********************
**** *************** ******* ***** ********* ******************************* ***
***************************** *** **********************************************
********** *** *************** * ********************* ******* *****************
******************************* ************************************************
***************************** * ***********************************************
* ******* ******* *********** *** *************** *************** **************
** ************************* ***** *********************************************
*** *********************** ******* ********************************************
**** *** *********** ***** ********* ******* *********************** ***********
***** ******************* *********** *************************************** **
****** ******* ********* ************* *************** ******************* *****
******* *************** *************** ******************************* ********
******** ************* ***************** *************************** ***********
********* *********** ******************* *********************** **************
** *** *** ********* ***** ******* ******* ******************* *********** *****
*********** ******* *********************** *************** ********************
************ ***** ************************* *********** ***********************
***** ******* *** *********** *************** ******* *********************** **
************** * ***************************** *** *****************************
*************** ******************************* ********************************
*** *** ***** * ******* ******* *********** *** *************** ***************
* *********** *** *********************** ******* ******************************
** ********* ***** ******************* *********** *****************************
*** ******* ******* *************** *************** ****************************
**** ***** ********* *********** ******************* *********************** ***
***** *** *********** ******* *********************** *************** **********
** *** * ***** ******* *** *********** *************** ******* *****************
******* *************** ******************************* ************************
***** * *********** *** *********************** ******* ***********************
* *** *** ******* ******* *************** *************** **********************
** * ***** *** *********** ******* *********************** *************** *****
*** ******* *************** ******************************* ********************
* * *** *** ******* ******* *************** *************** *******************
* *** ******* *************** ******************************* ******************
* *** ******* *************** ******************************* *****************There’s a clear pattern there, but it might be easier to see if we inverted it, plotting those things which don’t loop:
Output
* *
* * * *
* *
*
*
* * *
*
* * *
*
* * *
* * * * *
*
*
* * *
*
* * *
* * *
*
*
* * * *
* *
* *
* * * *
* * * *
* *
* * * * * *
* *
* *
* * *
* *
* * * *
* * * *
* *
* *
* * * *
* * * *
*
* * * * * * *
* * *
* * *
* * * * *
* * *
* * *
* * * * *
* * *
* * * * *
* * * * *
* * *
* * *
* * * * *
* * * *
* * * * *
* * *
* *
* *
* * * * * * * *
* *
* *
* * * * * *
* *
* *
* * * * * *
* *
* *
* * * *
* * * * * *
* *
* * * * * *
*
* * *
* * * * * * *
* * *
* * *
* * * * * * *
* * * *
* * * * * *
* * * *
* * * *
* * * *
* * * * * * * * *
* * * *
* * * *
* * * * * * *
* * * *
* *
* * * * * * * * * *
* * * * *
* * * * *
* * * * *
* * * * * *
* * * * * *
* * * * * * * * *
* * *
* * * * * * *
* * * * * * *
* * * * * * * *
* * * *
* * * * * * * * *
* * * * *
* * * * * * For this kind of thing it’s also worth getting familiar with gnuplot.
Step 3: Reduce The Space
The clearest pattern in the graph above is the straight lines coming
from the origin. This tells me, straight away, that we have an
opportunity for optimisation if we wanted to memoize. We can’t yet be
sure, but it looks like every point belongs to one of these
straight lines. That means that once we find a non-looping pair like
3, 5, we can extend that line out to 6, 10 and
9, 15, etc.
We can also see that the graph has a symmetry through the line
x = y. This means that if 3, 5 doesn’t loop,
neither does 5, 3.
Both of these techniques allow us to reduce the arguments to a canonical form, making the memoization table smaller, also. In code:
from fractions import Fraction
def canonical(n,m):
f = Fraction(n,m) if n <= m else Fraction(m,n)
return (f.numerator, f.denominator)
memo_dict = {}
def solution(n,m):
c = canonical(n, m)
try:
return memo_dict[c]
except KeyError:
r = loops(sequence(*c))
memo_dict[c] = r
return rStep 4: Test
Now that we have our faster version, we want to be able to quickly check that it’s equivalent to the slow. While Python is usually great for programming puzzles, this step in particular is crying out for something like QuickCheck: without it, we’ll have to roll our own.
from random import randrange
for _ in range(1000):
x, y = randrange(1,10000), randrange(1,10000)
if solution_new(x,y) != solution_old(x,y):
print(x,y)We’re not looking for certainty here, just something that will quickly spot an error if one exists.
Step 5: More Sophisticated Patterns
Now that we’ve made some of the more obvious optimisations, it’s time to move on to finding another pattern in the output. To do this, we’ll use oeis.org. We want to find if the pairs which pass our test follow some sequence which has a simple generating function which we can adapt into a test.
Since the things we’re testing are pairs, rather than individual numbers, we’ll have to fix one of them and see if there’s a pattern in the other.
print([x for x in range(1,101) if not solution(1, x)])This prints the following sequence:
[1, 3, 7, 15, 31, 63]And when we search for it on oeis, we get this as the top result:
0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767,
65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215,
33554431, 67108863...And looking at the comments under the sequence, we see the following:
Numbers n for which the expression 2^n/(n+1) is an integer. - Paolo P. Lava, May 12 2006
A test for members of the sequence, all packaged up for us!
But how do we generalise to pairs other than 1? Well, as a total guess, we can see that 1 appears in one place in the formula: why not replace that with the other member of the pair?
After that, we get the following function to test:
def solution(n,m):
nc, mc = canonical(n,m)
return bool((2 ** mc) % (nc + mc))And it works!
Step 6: Look For Algorithms
This last step is pretty straightforward: see if there’s an algorithm
already out there that solves your problem. In our case, taking the
modulus is still pretty slow, but it turns out that modular
exponentiation (i.e. computing expressions of the form
x^y mod z) can be done faster
than the naive way. In fact, python provides this algorithm as a
function in the standard library, making our last version of the
function the following:
def solution(n,m):
nc, mc = canonical(n,m)
return bool(pow(2, mc, nc + mc))I’m not sure if this function is fully correct, but it was accepted as a solution to the puzzle.
Anyway, in conclusion: you can get quite far through a programming puzzle by applying some educated guesses and googling!