Project Euler – Problem 61 Solution

Problem

Tri­an­gle, square, pen­tag­o­nal, hexag­o­nal, hep­tag­o­nal, and octag­o­nal num­bers are all fig­u­rate (polyg­o­nal) num­bers and are gen­er­at­ed by the fol­low­ing for­mu­lae:

image

The ordered set of three 4-dig­it num­bers: 8128, 2882, 8281, has three inter­est­ing prop­er­ties.

  1. The set is cyclic, in that the last two dig­its of each num­ber is the first two dig­its of the next num­ber (includ­ing the last num­ber with the first).
  2. Each polyg­o­nal type: tri­an­gle (P3,127=8128), square (P4,91=8281), and pen­tag­o­nal (P5,44=2882), is rep­re­sent­ed by a dif­fer­ent num­ber in the set.
  3. This is the only set of 4-dig­it num­bers with this prop­er­ty.

Find the sum of the only ordered set of six cyclic 4-dig­it num­bers for which each polyg­o­nal type: tri­an­gle, square, pen­tag­o­nal, hexag­o­nal, hep­tag­o­nal, and octag­o­nal, is rep­re­sent­ed by a dif­fer­ent num­ber in the set.

Solution

(see full solu­tion here),

The tricky thing here (at least for me) was to remem­ber that the six 4-dig­it num­bers have to come from dif­fer­ent sets, but not nec­es­sar­i­ly in the order of P3, P4, … P8. Once that is cleared up, the rest is fair­ly straight for­ward. In the solu­tion linked above, I first cre­at­ed a set of func­tions for gen­er­at­ing tri­an­gle, square, pen­tag­o­nal, … octag­o­nal num­bers:

image

Since the ques­tion con­cerns only 4-dig­it num­bers, so for effi­cien­cy sake let’s gen­er­ate the desired 4 dig­it num­bers ahead of time and safe them for lat­er use:

image

The is4digit pred­i­cate func­tion is self-explana­to­ry. nat­u­ral­Num­bers is an infi­nite sequence of inte­gers start­ing from 1, we use this sequence to gen­er­ate the fig­u­rate num­bers we need, but only keep those that are actu­al­ly 4 dig­its.

So far so good, we have all the fig­u­rate num­bers in an array where [0] => P3, [1] => P4, and so on.

 

Next, cre­ate per­mu­ta­tions of the fig­u­rate num­bers such that we exhaust all pos­si­ble sequence of fig­u­rate num­bers:

P3 => P4 => P5 => P6 => P7 => P8

P3 => P4 => P6 => P7 => P8 => P5

P4 => P3 => P5 => P6 => P7 => P8

image

(P.S. the per­mute func­tion here comes from the Common.fs source file in the solu­tion)

 

To find the answer to the prob­lem, we process each per­mu­ta­tion to find our answer, take a moment to under­stand this code:

image

 

The processPer­mu­ta­tion func­tion process­es one per­mu­ta­tion of the fig­u­rate num­bers and the ter­mi­na­tion con­di­tions for the inner loop func­tion are:

1. we have one num­ber from each fig­u­rate num­ber set and that the last 2 dig­its of the last num­ber = first 2 dig­its of first num­ber

Image

2. we have one num­ber from each fig­u­rate num­ber set but last 2 dig­its of last num­ber <> first 2 dig­its of first num­ber (so close!)


image

3. one of the fig­u­rate num­ber set in the sequence doesn’t con­tain a num­ber whose first 2 dig­its = the last 2 dig­its of the num­ber select­ed from the last fig­u­rate num­ber set (short-cir­cuit­ed)

Image

 

For each num­ber in the cur­rent set of fig­u­rate num­bers we build up a new pred­i­cate func­tion – e.g. if x = 1282 then the pred­i­cate func­tion would find 4-dig­it num­bers whose first two dig­it = 82 – and use it to process the next set of fig­u­rate num­bers in the sequence.

The loop func­tion returns int list option where the int list rep­re­sents the cyclic fig­u­rate num­bers we’re look­ing for, so all that’s left is to unpack the option type and then sum the list.

image

 

This solu­tion took 17ms to find the solu­tion on my machine.