Solves Project Euler #61, see https://projecteuler.net/problem=61 and http://www.columbia.edu/~ajl2217/2016/04/project-euler-61/

euler61.py

# -*- coding: utf-8 -*-
import itertools
from datetime import datetime

# Solves Project Euler #61, https://projecteuler.net/problem=61
# View a writeup at http://www.columbia.edu/~ajl2217/2016/04/project-euler-61/

startTime = datetime.now() # See how long this takes

# Triangle: n(n+1)/2
# Square: n^2
# Pentagonal: n(3n−1)/2
# Hexagonal: n(2n−1)
# Heptagonal: n(5n−3)/2
# Octagonal: n(3n−2)

# Find shape numbers such that 999 < number < 10000 (i.e. four digit numbers).
# Using algebra we can calculate the ranges as:
#   Triangle: 45 to 140
#   Square: 32 to 99
#   Pentagonal: 26 to 81
#   Hexagonal: 23 to 70
#   Heptagonal: 21 to 63
#   Octagonal: 19 to 58

triangle = []
square = []
pentagonal = []
hexagonal = []
heptagonal = []
octagonal = []
shapes = [triangle, square, pentagonal, hexagonal, heptagonal, octagonal]

def is_cyclical(n, m):
  # n and m are type Int
  # Returns Bool. True if n and m are cyclical,
  # i.e. the last two digits of n are the first two digits of m.
  if type(n) != int:
      return "n must be an integer, not type " + str(type(n))
  if type(m) != int:
      return "m must be an integer"
  if (n%100 == int(m/100)):
      return True
  else:
      return False

def find_cyclicals(haystack, needle):
    # haystack is type Array to search in
    # needle is type Int to compare to
    # Find cyclical numbers in haystack compared to needle.
    # Returns List.
    if type(haystack) != list:
        return "haystack must be a list"
    if type(needle) != int:
        return "needle must be an int"
    cyclicals = []
    for item in haystack:
        if is_cyclical(needle, item):
            cyclicals.append(item)
    return cyclicals

def process_cyclicals(array, length):
    # array is type Array of cyclical_groups
    # index is type Integer of the length desired
    # This function takes the array and then processes the cyclicals returned
    # from find_cyclicals. Then it makes sure that dead-ends are removed by
    # removing those whose length is insufficient (i.e. those who have no)
    # cyclical number found.
    # Returns type List.
    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 array


# Calculate triangles, squares, etc.
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)

# Let's try to construct the cyclical numbers, such that we get a sequence of
# six four-digit numbers that each uniquely belong to one of the six
# shape-classes established above. The final list should follow the pattern
# [aabb, bbcc, ccdd, ddee, eeff, ffaa].

possibilities = [] # Where we'll hold our six-number cycles
# To make sure that we generate the list in all permutations,
# since the numbers aren't necessarily in order. For instance, they could be
# ordered (5, 2, 4, 3, 1, 0)!
permutations = list(itertools.permutations(range(0, 5+1)))
for perm_list in permutations:
    cyclical_groups = [] # Here we "hydrate" our first list...
    # We take our root to which we compare other numbers
    root = shapes[perm_list[0]]
    for item in root:
        # Iterate over potential cyclical numbers
        for number in find_cyclicals(shapes[perm_list[1]], item):
            cyclical_groups.append([item, number])
            # Append them so we get a list like [xxyy, yyzz]

    for n in range(3,6+1):
        # Now we can go through the other numbers.
        cyclical_groups = process_cyclicals(cyclical_groups, n)
        # Once we get six length lists, they're moved to List possibilites

    # Then we start over with the next permutation! The list is reset,
    # "rehydrated" then processed.

# Now, to find the six-set list. Recall that the first and last numbers of the
# list must follow pattern [xxyy, yyzz, ... aaxx]. We'll get six lists, each of
# which match the criteria set out in Project Euler #61. All the numbers in all
# six lists will be equal, just arranged as [[a,b,c,d,e,f], [b,c,d,e,f,a], ...].
possibilities = [x for x in possibilities if is_cyclical(x[-1], x[0])]
print possibilities[0] # Just print the first one, though it doesn't matter
# which we pick.
print sum(possibilities[0]) # Sum them up!
print datetime.now() - startTime
# Takes about 3.7 seconds on a 1.3GHz MacBook Air