Project Euler No. 61
In my spare time, I love to solve programming problems. Even though I’m not a computer science major, I still get a rush whenever I manage to solve a complicated problem by breaking it down. I recently completed Project Euler’s Problem #61. Simply put, you had to find a set of six cyclical numbers, each from a set of four-digit polygonal numbers.
You can view my completed Gist if you just want the answer but to find out how I solved it using Python, read on. Here I’ll explain snippets and how my thinking worked, but you won’t see my very rudimentary type checking nor my comments.
To begin, I knew I had to create six lists, one for each set of polygonal numbers. Easy! So we get:
triangle = []
square = []
pentagonal = []
hexagonal = []
heptagonal = []
octagonal = []Using algebra, I could find out what values would give me four digit numbers for each of the sets of polygonal numbers (i.e. 999 < the formula for polygonal number < 10000). I came to several different values, and used that to populate the lists as so:
for n in range(45, 140+1):
i = n*(n + 1)/2
triangle.append(i)
for n in range(32, 99+1):
i = n**2
square.append(i)
for n in range(26, 81+1):
i = n*(3*n - 1)/2
pentagonal.append(i)
for n in range(23, 70+1):
i = n*(2*n - 1)
hexagonal.append(i)
for n in range(21, 63+1):
i = n*(5*n - 3)/2
heptagonal.append(i)
for n in range(19, 58+1):
i = n*(3*n - 2)
octagonal.append(i)I prefer to use the +1 notation just to make it explicit to myself where the range will stop (I always get confused in Python, as the lower bound is inclusive, but the upper bound is not).
Next I knew I would have to find a way to tell if two numbers were cyclical or not. It essentially came down to needing to know the last two and first two digits, which you could do with division and the modulo operation easily. Since we need the last two digits, we could use modulo of 100, returning for instance 89 in the case of 7689%100. For the first two, we could divide by 100. However, since that would return a floating point number, I made sure to cast it as an integer, so we would get 76 in the case of int(7689/100). I wrote the following function for ease:
def is_cyclical(n, m):
if (n%100 == int(m/100)):
return True
else:
return FalseNext, I needed a way to find cyclicals of one number in any given list. I wrote this function, which searches for any numbers that are cyclical in one list as compared to the base number. Thus, I could iterate over my first list, comparing each number to numbers in the second list. I wrote this small function:
def find_cyclicals(haystack, needle):
cyclicals = []
for item in haystack:
if is_cyclical(needle, item):
cyclicals.append(item)
return cyclicalsThe nice part is that this item returns a list, even if it finds none or only one matching result, allowing me to easily iterate and then add it to the sets of numbers I’m constructing. My next move was to start generating these sets of cyclical numbers. But how? I knew that the numbers wouldn’t be in a nice order (i.e. triangular, followed by square, etc.) and could be in any order. I finally thought to just permute through every single option possible. It sounds way too intensive, but it’s surprisingly not and the program finishes up nicely. I found the itertools library, which made it easy to create a list of permutations of 0 through 5:
import itertools
...
permutations = list(itertools.permutations(range(0, 5+1)))This creates a list of tuples of every permutation of (0, 1, 2, 3, 4, 5). To use this list, I figured I’d have to use a master list of sorts. Easily enough, I made a shapes list as so:
shapes = [triangle, square, pentagonal, hexagonal, heptagonal, octagonal]So as I went through the list of permutations, I could call, for instance shapes[4], and always get the heptagonal list, ensuring I had every combination possible.
Now came the hard part. Actually making the lists! Using my permutations list, I made a for loop:
for perm_list in permutations:I then defined an empty list to hold our groups as we went. This made sure the list got reset as we went. Then I picked our first list as the root, where from each list would then be generated. For instance, if our first list was the triangle list, a triangle number would be the first element in each of the lists. Then I simply moved through each item in the root and started building the list. I was having an issue with lists like [aabb, [bbcc, bbdd]] so I opted to instead make a list like [[aabb, bbcc], [aabb, bbdd]] to make it easier later.
for perm_list in permutations:
cyclical_groups = []
root = shapes[perm_list[0]]
for item in root:
for number in find_cyclicals(shapes[perm_list[1]], item):
cyclical_groups.append([item, number])But then how to build the list from there? Easy peasy, I made another function that then finds the next set of cyclical numbers, given an already-made list, another list to compare it to, and a length:
def process_cyclicals(array, length):
for item in array:
for number in find_cyclicals(
shapes[perm_list[length-1]], item[length-2]):
item.append(number)
array = [x for x in array if len(x) == length]
return arrayThe second to last line made it easier to compute by killing any “branches” that didn’t have enough items. So for instance, if a third-level cyclical number couldn’t be found, that item was removed entirely as it would only have two items and not three. As the program traversed through the possibilities, it encountered less and less, making it easier to do. So all I had to do was then loop through this new function.
for perm_list in permutations:
cyclical_groups = []
root = shapes[perm_list[0]]
for item in root:
for number in find_cyclicals(shapes[perm_list[1]], item):
cyclical_groups.append([item, number])
for n in range(3,6+1):
cyclical_groups = process_cyclicals(cyclical_groups, n)But wait! What about saving our six-length lists, the ones that go through a complete cycle? To do that, I defined a new list before this for perm_list loop called possibilities:
possibilities = []
for perm_list in permutations:
...Then I updated process_cyclicals like so:
def process_cyclicals(array, length):
for item in array:
for number in find_cyclicals(
shapes[perm_list[length-1]], item[length-2]):
item.append(number)
array = [x for x in array if len(x) == length]
if length == 6:
for possibility in array:
if len(possibility) == 6:
possibilities.append(possibility)
return arrayBasically, when we’re finally on the last level, length = 6, we then see if any of the lists match the length requirement, and append them to the possibilities list. That way we don’t lose them as we iterate over perm_list.
Finally having iterated over perm_list, all that was left was to make sure the first and last numbers of the list were cyclical. In a simple one-liner, we redefine possibilities like so:
possibilities = [x for x in possibilities if is_cyclical(x[-1], x[0])]Basically finding where the last number is cyclical with the first. I was surprised to see at first that the list contained six different lists – but each had the same numbers, just in a different order. Remember that our conditions are still satisfied as long as the list is [aabb, bbcc, ccdd, ddee, eeff, ffaa]. It doesn’t matter really, though, if we have something like [ddee, eeff, ffaa, aabb, bbcc, ccdd]. Still the same! So I went ahead and picked the first one, and printed the sum:
print sum(possibilities[0])For the final answer which I leave as a surprise to you! Either try your own solution or run the code. This problem is rated at 20% difficulty on Project Euler, though I was proud to solve it in about two hours with only a minimal math and computer science background. There are still tons of places for me to improve and refactor this code, namely in the way I permute through the lists. Ideally, my possibilities would redefine itself to only have one item, not six. But, as it stands, it gets the problem done and does it relatively quickly (the answer is produced in about 3.7 seconds on my 1.3GHz MacBook Air).
