Problem #61 asks
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.
There are several things to look out for when writing a solution to this problem. 1) If the last two digits of a number are less than ten it cannot be part of a chain (because the question doesn’t allow numbers of the form 0XXX). 2) it doesn’t matter what type of number you start out with: because it’s a cyclical chain if you find one number you’ll find the others. 4) Don’t throw out duplicate numbers if they only differ by type: just because a triangle number and a heptagonal number are the same doesn’t mean that you can throw one away they can be valid parts of different chains. 4) Recursion.
Because we are told that the chain of numbers we’re looking for is cyclical a recursive approach is perhaps the easiest to write. We use a tiny class to keep track of the first two digits, the last two digits, the type of number (tri,hep,oct etc) and lastly the value of the number itself (so we can calculate the sum of the chain later). We generate all numbers of all types between 1,000 and 10,000 using this class and put them into a list. We then strip invalid numbers from the list; those with ending digits less than 10 so if a number ends with 09 then it cannot be part of a valid chain. Then we just loop through this giant list. To get the next number in the chain we make sure we don’t already have a number of that type in the chain and we don’t have a number with that value in the chain. If the number is a valid new addition to the solution chain we attempt to find the next number to the chain using the same rules. If a chain cannot be found with 6 members or the required cyclical property then we go up a level and remove the last number added and continue to check for a valid chain. Eventually using this solution we’ll find the chain and if we don’t stop with the first chain we’ll get all permutations of the chain; still we only need the first one because the sum of the numbers in the chain are all going to be the same regardless of the order they appear in.
Solution written in mono/c# and runs in less than 1/10th of a second.
using System;
using System.Diagnostics;
using System.Collections.Generic;
namespace Problem61
{
public class ChainNum
{
public int starts = 0;
public int ends = 0;
public int num = 0;
public int type = 0;
public ChainNum (int i,int t)
{
num = i;
starts = i/100;
ends = i % 100;
type = t;
}
}
class MainClass
{
public static List<ChainNum> Nums = new List<ChainNum>();
public static Stopwatch sw = new Stopwatch();
public static void Main (string[] args)
{
sw.Start();
FillLists();
List<ChainNum> inv = new List<ChainNum>();
foreach (ChainNum c in Nums)
{
if (c.ends < 10)
inv.Add(c);
}
foreach (ChainNum c in inv)
{
Nums.Remove(c);
}
foreach(ChainNum n in Nums)
{
var c = new List<ChainNum>();
c.Add(n);
var sol = BuildSolution(1,c);
int count = 0;
if (sol != null)
{
foreach (ChainNum s in sol)
count += s.num;
}
if (count != 0)
{
Console.WriteLine(count);
break;
}
}
sw.Stop();
Console.WriteLine(sw.Elapsed);
}
public static List<ChainNum> BuildSolution (int level, List<ChainNum> solution)
{
if (level > 6)
return null;
if (solution.Count == 6 && solution[0].starts == solution[5].ends)
return solution;
if (solution.Count == 6)
return null;
foreach (ChainNum c in Nums)
{
bool alreadyhastypeornumber = false;
foreach(ChainNum temp in solution)
{
if (temp.type == c.type || temp.num == c.num)
alreadyhastypeornumber = true;
}
if (alreadyhastypeornumber)
continue;
else
{
if (solution[solution.Count-1].ends == c.starts)
{
solution.Add(c);
var sol = BuildSolution(level++,solution);
if (sol != null)
return sol;
else
solution.Remove(c);
}
}
}
return null;
}
public static void FillLists ()
{
int i = 1;
while(TriangleNum(i) < 10000)
{
if (TriangleNum(i) > 1000)
Nums.Add(new ChainNum(TriangleNum(i),3));
i++;
}
i = 0;
while(SquareNum(i) < 10000)
{
if (SquareNum(i) > 1000)
Nums.Add(new ChainNum(SquareNum(i),4));
i++;
}
i = 0;
while(PentagonalNum(i) < 10000)
{
if (PentagonalNum(i) > 1000)
Nums.Add(new ChainNum(PentagonalNum(i),5));
i++;
}
i = 0;
while(HexagonalNum(i) < 10000)
{
if (HexagonalNum(i) > 1000)
Nums.Add(new ChainNum(HexagonalNum(i),6));
i++;
}
i = 0;
while(HeptagonalNum(i) < 10000)
{
if (HeptagonalNum(i) > 1000)
Nums.Add(new ChainNum(HeptagonalNum(i),7));
i++;
}
i = 0;
while(OctagonalNum(i) < 10000)
{
if (OctagonalNum(i) > 1000)
Nums.Add(new ChainNum(OctagonalNum(i),8));
i++;
}
}
public static int TriangleNum (int n)
{
return (n*(n+1))/2;
}
public static int SquareNum (int n)
{
return n*n;
}
public static int PentagonalNum (int n)
{
return (n*(3*n-1))/2;
}
public static int HexagonalNum (int n)
{
return n*(2*n-1);
}
public static int HeptagonalNum (int n)
{
return (n*(5*n -3))/2;
}
public static int OctagonalNum (int n)
{
return n*(3*n -2);
}
}
}