Project Euler – Problem 68 Solution

Problem

Con­sid­er the fol­low­ing “mag­ic” 3-gon ring, filled with the num­bers 1 to 6, and each line adding to nine.

Work­ing clock­wise, and start­ing from the group of three with the numer­i­cal­ly low­est exter­nal node (4,3,2 in this exam­ple), each solu­tion can be described unique­ly. For exam­ple, the above solu­tion can be described by the set: 4,3,2; 6,2,1; 5,1,3.

It is pos­si­ble to com­plete the ring with four dif­fer­ent totals: 9, 10, 11, and 12. There are eight solu­tions in total.

image

By con­cate­nat­ing each group it is pos­si­ble to form 9-dig­it strings; the max­i­mum string for a 3-gon ring is 432621513.

Using the num­bers 1 to 10, and depend­ing on arrange­ments, it is pos­si­ble to form 16- and 17-dig­it strings. What is the max­i­mum 16-dig­it string for a “mag­ic” 5-gon ring?

Solution

(see full solu­tion here)

 

Before we go into details on the solu­tion, let’s first struc­ture the ques­tion in a way that’s easy for us to com­pute.

To con­struct the mag­ic cir­cle, be it for a 3-gon or a 5-gon ring, we can slice up the num­bers into pairs – e.g. A => [1; 2], B => [3; 4], C => [5; 6], D => [7; 8], E => [9; 10] – and the prob­lem becomes find­ing ways in which the num­bers can be per­mut­ed such that:

  1. a0 is the small­est amongst a0, b0, c0, d0, and e0
  2. the sums of a0 + a1 + b1, b0 + b1 + c1, … are the same

For exam­ple:

image

 

First, we’ll find the dif­fer­ent ways the num­bers 1 to 10 can be per­mut­ed, and for each per­mu­ta­tion slice the num­bers into pairs:

image

(this makes use of a per­mute func­tion defined in the Common.fs source file in the solu­tion).

 

Then we need a func­tion to sum a pair of num­ber with the last ele­ment in the adja­cent pair – e.g. a0 + a1 + b1:

image

 

For each per­mu­ta­tion, we need to check:

  1. if a0 is the small­est amongst the head ele­ments
  2. if the sums of the groups of 3 – i.e. a0 + a1 + b1, b0 + b1 + c1, etc. – are the same

image

This pred­i­cate func­tion allows us to find arrange­ments that meet our cri­te­ria. All that’s left is to turn the result groups of 15 num­bers into 16/17-dig­it strings and find the max­i­mum (see full solu­tion below).

 

Here’s the full solu­tion:

image

 

This solu­tion took 26s to exe­cute on my machine.