# Project Euler Problem 61

Project Euler Problem 61 solution is very interesting from many angles.

From purely algorithmic standpoint it can be abstracted the following way:

we are given a bag of **Figurate “links”** (like chain links) each belonging to one of few discriminated cases – **Triangle**, **Square**, etc.

Each link has the **head** and the **tail **conformant to a given pattern; if head of link **L2** is the same to tail of link **L1**, then **L1** and **L2** can be chained together as **L1->L2**. Chaining few links together **L1->L2->…->Ln->L1** allows building **rings** of links. A **good ring** is a ring of links of all **Figurate** cases where each case is represented only once. *Finding a good ring of links of given Figurates with conformant heads and tails solves the original problem*.

Given the pattern of generating Figurate links having head and tails as 2-digit splits of numbers belonging to correspondent figurate number sequence we can generate all conforming Triangles, Sqiares, …, Octagonals links. Now the task of finding a good ring can be expressed as a **“select many”** query against this bag of Figurate links that expresses “chainability” as well as Figurate case uniqueness via correspondent **where** clauses.

The code below figurally implements this abstraction. Few non-apparent considerations: although being conformant either heads or tails **to be linkable** cannot contain zeros as we use 4-digit numbers to produce heads and tails and a zero in any position would eventually require a chained head to begin with zero. Another opportunity for pruning our bag of links comes from the following consideration: if we form a set of all heads and a set of all tails, then chainable links should have head **and** tail belonging to the intersection of head and tail sets.

open System type String with static member is4CharLong x = (String.length x) = 4 static member hasNoZeros (x: String) = x.IndexOf('0') = -1 type Figurate = | Triangle | Square | Pentagonal | Hexagonal | Heptagonal | Octagonal static member Generator = function | Triangle -> fun n -> n * (n + 1) / 2 | Square -> fun n -> n * n | Pentagonal -> fun n -> n * (3 * n - 1) / 2 | Hexagonal -> fun n -> n * (2 * n - 1) | Heptagonal -> fun n -> n * (5 * n - 3) / 2 | Octagonal -> fun n -> n * (3 * n - 2) let generate figurate = Seq.initInfinite ((Figurate.Generator figurate) >> string) |> Seq.skipWhile (String.is4CharLong >> not) |> Seq.takeWhile String.is4CharLong |> Seq.filter String.hasNoZeros |> Seq.map (fun x -> (x.Substring(0,2), x.Substring(2), figurate)) |> Seq.toList type Link = { Head:string; Tail:string; Poly:Figurate } let problem061 () = let prune xs = let linkable = Set.intersect (xs |> List.map (fun (h,_,_) -> h) |> set) (xs |> List.map (fun (_,t,_) -> t) |> set) List.filter (fun (h,t,_) -> linkable.Contains h && linkable.Contains t) xs let links = [Triangle;Square;Pentagonal;Hexagonal;Heptagonal;Octagonal] |> List.collect generate |> prune |> List.map (fun (h,t,f) -> {Head=h;Tail=t;Poly=f}) let octagonal,others = List.partition (fun x -> x.Poly = Octagonal) links [ for i in octagonal do for j in others |> List.filter (fun x -> x.Head = i.Tail) do for k in others |> List.filter (fun x -> x.Head = j.Tail) do for l in others |> List.filter (fun x -> x.Head = k.Tail) do for m in others |> List.filter (fun x -> x.Head = l.Tail) do for n in others |> List.filter (fun x -> x.Head = m.Tail && x.Tail = i.Head) do if set [i.Poly;j.Poly;k.Poly;l.Poly;m.Poly;n.Poly] |> Set.count = 6 then yield i.Head + i.Tail yield j.Head + j.Tail yield k.Head + k.Tail yield l.Head + l.Tail yield m.Head + m.Tail yield n.Head + n.Tail ] |> List.map Int32.Parse |> List.sum

It would be interesting to use a F# 3.0 genuine LINQ expression in place of equivalent list comprehension above (see this post in Don Syme blog that gives grounds for this equivalence), I’ll definitely do it some day.

Anyways finding the solution takes only 31 ms on a mediocre laptop.

The solution’s code above demonstrates few useful F# features and programming techniques:

- augmenting type with extension methods/properties

type String with static member is4CharLong x = (String.length x) = 4 static member hasNoZeros (x: String) = x.IndexOf('0') = -1

type Figurate = | Triangle | Square | Pentagonal | Hexagonal | Heptagonal | Octagonal static member Generator = function | Triangle -> fun n -> n * (n + 1) / 2 | Square -> fun n -> n * n | Pentagonal -> fun n -> n * (3 * n - 1) / 2 | Hexagonal -> fun n -> n * (2 * n - 1) | Heptagonal -> fun n -> n * (5 * n - 3) / 2 | Octagonal -> fun n -> n * (3 * n - 2)

let generate figurate = Seq.initInfinite ((Figurate.Generator figurate) >> string) |> Seq.skipWhile (String.is4CharLong >> not) |> Seq.takeWhile String.is4CharLong

type Link = { Head:string; Tail:string; Poly:Figurate } ............................. List.map (fun (h,t,f) -> {Head=h;Tail=t;Poly=f})

let prune xs = let linkable = Set.intersect (xs |> List.map (fun (h,_,_) -> h) |> set) (xs |> List.map (fun (_,t,_) -> t) |> set) List.filter (fun (h,t,_) -> linkable.Contains h && linkable.Contains t) xs .............................. let octagonal,others = List.partition (fun x -> x.Poly = Octagonal) links

[ for i in octagonal do for j in others |> List.filter (fun x -> x.Head = i.Tail) do for k in others |> List.filter (fun x -> x.Head = j.Tail) do for l in others |> List.filter (fun x -> x.Head = k.Tail) do for m in others |> List.filter (fun x -> x.Head = l.Tail) do for n in others |> List.filter (fun x -> x.Head = m.Tail && x.Tail = i.Head) do if set [i.Poly;j.Poly;k.Poly;l.Poly;m.Poly;n.Poly] |> Set.count = 6 then yield i.Head + i.Tail yield j.Head + j.Tail yield k.Head + k.Tail yield l.Head + l.Tail yield m.Head + m.Tail yield n.Head + n.Tail ]