new_contents: """
  Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are
  all figurate (polygonal) numbers and are generated by the following formulae:
  
      Triangle   P[3,n]=n(n+1)/2  --> 1, 3, 6, 10, 15, ...
      Square     P[4,n]=n2        --> 1, 4, 9, 16, 25, ...
      Pentagonal P[5,n]=n(3n−1)/2 --> 1, 5, 12, 22, 35, ...
      Hexagonal  P[6,n]=n(2n−1)   --> 1, 6, 15, 28, 45, ...
      Heptagonal P[7,n]=n(5n−3)/2 --> 1, 7, 18, 34, 55, ...
      Octagonal  P[8,n]=n(3n−2)   --> 1, 8, 21, 40, 65, ...
  
  The ordered set of three 4-digit numbers: 8128, 2882, 8281, has
  three interesting properties.
  
      1. The set is cyclic, in that the last two digits of each number is the
      first two digits of the next number (including the last number with the
      first).
      2. Each polygonal type: triangle (P[3,127]=8128), square (P[4,91]=8281),
      and pentagonal (P[5,44]=2882), is represented by a different number in the
      set.
      3. This is the only set of 4-digit numbers with this property.
  
  Find the sum of the only ordered set of six cyclic 4-digit numbers for which
  each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and
  octagonal, is represented by a different number in the set.
  """
  from itertools import count, permutations, dropwhile, takewhile
  from toolset import memoize
  
  def triangle(n): return (n*(n+1))/2
  def square(n): return n**2
  def pentagonal(n): return n*(3*n - 1)/2
  def hexagonal(n): return n*(2*n - 1)
  def heptagonal(n): return n*(5*n - 3)/2
  def octagonal(n): return n*(3*n - 2)
  
  @memoize
  def is_cyclic(x, y):
      """Are these four-digit numbers cyclic?"""
      # We can safely truncate to int as x and y come from the polygonal funcs.
      return str(int(x))[2:] == str(int(y))[:2]
  
  def is_all_cyclic(node):
      """Is the set of digits cyclic, including the last number with the first?"""
      x = len(node)
      return all(is_cyclic(node[i], node[(i+1)%x]) for i in range(x))
  
  def is_fourdigit(n):
      # We can safely truncate to int as x and y come from the polygonal funcs.
      return len(str(int(n))) == 4
  
  def fourdigit_polys(func):
      """Given a function representing a polygonal type, return all four-digit
      members of that type."""
      dw = dropwhile(lambda x: not is_fourdigit(x), (func(i) for i in count()))
      return list(takewhile(lambda x: is_fourdigit(x), dw))
  
  def polygon_dict():
      """Return a dict from polygon name to four-digit polygon numbers."""
      poly_funcs = [triangle, square, pentagonal, hexagonal, heptagonal, octagonal]
      return {f.__name__: fourdigit_polys(f) for f in poly_funcs}
  
  # For every way to order the polygonal types, perform depth-first search,
  # returning as soon as a solution is found.
  def problem61():
      polys = polygon_dict()
      perms = permutations(polys.keys())
      for perm in perms:
          # We will build up candidate solutions incrementally. The starting
          # nodes are therefore the members of polys[perm[0]].
          frontier = [[x] for x in polys[perm[0]]]
          while frontier:
              node = frontier.pop()
              z = len(node)
              if z == 6 and is_all_cyclic(node):
                  return sum(node)
              elif z < 6:
                  # Note that perm[z] contains the next polygonal type in this
                  # order, e.g. "pentagonal".
                  for y in polys[perm[z]]:
                      if is_cyclic(node[-1], y):
                          frontier.append(node + [y])
  
subject: Add problem61.py