Skip to content

Project Euler Problem 61

December 15, 2011

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
    
  • adding a static member to discriminated union in order to encapsulate number sequences generation and make them statically checked
  • 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)
    
  • elegantly chopping out a piece of an ordered sequence that members fulfill some condition
  • let generate figurate =
        Seq.initInfinite ((Figurate.Generator figurate) >> string)
        |> Seq.skipWhile (String.is4CharLong >> not)
        |> Seq.takeWhile String.is4CharLong
    
  • using type of records instead of raw tuples for better code readability
  • type Link = { Head:string; Tail:string; Poly:Figurate }
    .............................
    List.map (fun (h,t,f) -> {Head=h;Tail=t;Poly=f})
    
  • set operations and advanced tuple matching
  • 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
    
  • LINQ-like in memory queries within list comprehensions
  • [ 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
        ]
    
Advertisements

From → F#, Project Euler

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: