Friday 24 April 2009

PROJECT EULER #68

Link to Project Euler problem 68

Consider the following "magic" 3-gon ring, filled with the numbers 1 to 6, and each line adding to nine.


Working clockwise, and starting from the group of three with the numerically lowest external node (4,3,2 in this example), each solution can be described uniquely. For example, the above solution can be described by the set: 4,3,2; 6,2,1; 5,1,3.

It is possible to complete the ring with four different totals: 9, 10, 11, and 12. There are eight solutions in total.

TotalSolution Set
94,2,3; 5,3,1; 6,1,2
94,3,2; 6,2,1; 5,1,3
102,3,5; 4,5,1; 6,1,3
102,5,3; 6,3,1; 4,1,5
111,4,6; 3,6,2; 5,2,4
111,6,4; 5,4,2; 3,2,6
121,5,6; 2,6,4; 3,4,5
121,6,5; 3,5,4; 2,4,6

By concatenating each group it is possible to form 9-digit strings; the maximum string for a 3-gon ring is 432621513.

Using the numbers 1 to 10, and depending on arrangements, it is possible to form 16- and 17-digit strings. What is the maximum 16-digit string for a "magic" 5-gon ring?


Thanks to Michael, my employer and mentor, I managed to see the wisdom of creating a data structure (an Ngon) to hold the data. Well there's hope for me yet. This is only the second time during these problems that I've made an object as part of the solution. The permutation code is lifted from here, although I must add that I read Knuth's "The Art of Computer Programming - pre-fascicle 3A" to understand the concepts involved.

using System;
using System.Collections.Generic;

namespace ProjectEuler
{
class Program
{
static void Main()
{
//Problem 68
DateTime start = DateTime.Now;
var numbers = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
var result = Permute(numbers);
List<long> allResults = new List<long>();
foreach (int[] ints in result)
{
Ngon newNgon = new Ngon(ints);
if (newNgon.IsMagic)
allResults.Add(newNgon.SolutionSet);
}
allResults.Sort();
Console.WriteLine(allResults[allResults.Count - 1]);
TimeSpan time = DateTime.Now - start;
Console.WriteLine("This took {0}", time);
Console.ReadKey();
}

public static List<int[]> Permute(int[] values)
{
List<int[]> permList = new List<int[]>();
permuteWorker(values, 0, values.Length, ref permList);
return permList;
}

private static void permuteWorker(int[] values, int start, int n, ref List<int[]> permList)
{
if (start == n - 1)
{
int[] thisValues = new int[values.Length];
values.CopyTo(thisValues, 0);
permList.Add(thisValues);
}
else
{
for (int i = start; i < n; i++)
{
int tmp = values[i];
values[i] = values[start];
values[start] = tmp;
permuteWorker(values, start + 1, n, ref permList);
values[start] = values[i];
values[i] = tmp;
}
}
}

public class Ngon
{
public List<int> Numbers { get; set; }
//we have a pentagon, with point at top, and 5 'external' numbers
//extending the sides of the pentagon to create 5 lines of numbers.
//we number the internal points 0 to 4, and the external ones 5 to 9.
//point 9 is always = 10. Numbers are clockwise with point 4 and point 9 at top.
public Ngon(int[] numbers)
{
Point0 = numbers[0];
Point1 = numbers[1];
Point2 = numbers[2];
Point3 = numbers[3];
Point4 = numbers[4];
Point5 = numbers[5];
Point6 = numbers[6];
Point7 = numbers[7];
Point8 = numbers[8];
Point9 = 10;
}
public int Point0 { get; private set; }
public int Point1 { get; private set; }
public int Point2 { get; private set; }
public int Point3 { get; private set; }
public int Point4 { get; private set; }
public int Point5 { get; private set; }
public int Point6 { get; private set; }
public int Point7 { get; private set; }
public int Point8 { get; private set; }
public int Point9 { get; private set; }

public int Line1Sum { get { return Point9 + Point4 + Point0; } }
public int Line2Sum { get { return Point5 + Point0 + Point1; } }
public int Line3Sum { get { return Point6 + Point1 + Point2; } }
public int Line4Sum { get { return Point7 + Point2 + Point3; } }
public int Line5Sum { get { return Point8 + Point3 + Point4; } }
public int Line1
{
get
{
int[] i = new int[3] { Point9, Point4, Point0 };
return 100 * i[0] + 10 * i[1] + i[2];
}
}
public int Line2
{
get
{
int[] i = new int[3] { Point5, Point0, Point1 };
return 100 * i[0] + 10 * i[1] + i[2];
}
}
public int Line3
{
get
{
int[] i = new int[3] { Point6, Point1, Point2 };
return 100 * i[0] + 10 * i[1] + i[2];
}
}
public int Line4
{
get
{
int[] i = new int[3] { Point7, Point2, Point3 };
return 100 * i[0] + 10 * i[1] + i[2];
}
}
public int Line5
{
get
{
int[] i = new int[3] { Point8, Point3, Point4 };
return 100 * i[0] + 10 * i[1] + i[2];
}
}
public bool IsMagic
{
get
{
if (Line1Sum == Line2Sum && Line1Sum == Line3Sum &&
Line1Sum == Line4Sum && Line1Sum == Line5Sum)
return true;
return false;
}
}

public long SolutionSet
{
get
{
int[] solutionSet = new int[5];
List<int> temp = new List<int>();
int min = 1000, index = 0;
temp.Add(Line1);
temp.Add(Line2);
temp.Add(Line3);
temp.Add(Line4);
temp.Add(Line5);
for (int i = 0; i < temp.Count; i++)
if (temp[i] < min)
{
min = temp[i];
index = i;
}
for (int i = 0; i < index; i++)
temp.Add(temp[i]);
temp.CopyTo(index, solutionSet, 0, 5);
string solution = "";
for (int i = 0; i < solutionSet.Length; i++)
solution += solutionSet[i];
return long.Parse(solution);
}
}
}
}
}

No comments: