Project Euler — Problem 4 Solution

Problem

A palin­dromic num­ber reads the same both ways. The largest palin­drome made from the prod­uct of two 2-dig­it num­bers is 9009 = 91 x 99.

Find the largest palin­drome made from the prod­uct of two 3-dig­it num­bers.

Solution

open System.Linq

let isPalindromic n =
    let charArray = n.ToString().ToCharArray()
    let revCharArray = Array.rev charArray
    charArray.SequenceEqual(revCharArray)

let numbers = [100..999]
let products = numbers |> List.collect (fun x -> numbers |> List.map (fun y -> x * y))
let maxPalindromic = products |> Seq.filter isPalindromic |> Seq.max

In my solu­tion above, I first built a func­tion to check whether a giv­en num­ber is palin­dromic by com­par­ing the orig­i­nal and reversed char array rep­re­sent­ing the num­ber and see if they’re the same, i.e. 9009 is rep­re­sent­ed by the char array [‘9’;‘0′;‘0′;‘9′], and the reversed array is still [‘9′;‘0′;‘0′;‘9’].

Notice how I used the Array.rev func­tion in the isPalin­dromic func­tion, it returns a new array with all the ele­ments in reverse order. Anoth­er thing you might have noticed in this func­tion is that I used the Enumerable.SequenceEqual Linq exten­sion method to com­pare the two arrays, as I’ve men­tioned before, with F# being a first class cit­i­zens of the .Net fam­i­ly you’re free to use what­ev­er CLR library of your choice.

The rest of the solu­tion might be rel­a­tive­ly straight for­ward, how­ev­er, you might be won­der­ing what the List.collect func­tion does. Like the List.map func­tion, it applies a func­tion to each ele­ment in the list, except that each ele­ment pro­duces a list and all these lists are con­cate­nat­ed into a final list.

Now let’s see how the two dif­fers, say we have a list of num­bers from 1 to 10, and I want to find out the Carte­sian prod­uct of the list mul­ti­plied by itself, i.e. 1 * 1, 1 * 2, … 1 * 10, 2 * 1, 2 * 2… 10 * 10:

let numbers = [1..10]

// List.map returns an array of array containing results of 1 *  [1..10], 2 * [1..10], etc.
numbers |> List.map (fun x -> numbers |> List.map(fun y -> x * y));;
val it : int list list =
[[1; 2; 3; 4; 5; 6; 7; 8; 9; 10];
 [2; 4; 6; 8; 10; 12; 14; 16; 18; 20];
 [3; 6; 9; 12; 15; 18; 21; 24; 27; 30];
 [4; 8; 12; 16; 20; 24; 28; 32; 36; 40];
 [5; 10; 15; 20; 25; 30; 35; 40; 45; 50];
 [6; 12; 18; 24; 30; 36; 42; 48; 54; 60];
 [7; 14; 21; 28; 35; 42; 49; 56; 63; 70];
 [8; 16; 24; 32; 40; 48; 56; 64; 72; 80];
 [9; 18; 27; 36; 45; 54; 63; 72; 81; 90];
 [10; 20; 30; 40; 50; 60; 70; 80; 90; 100]]

// List.collect returns a 1-dimensional array instead
numbers |> List.collect (fun x -> numbers |> List.map (fun y -> x * y));;
val it : int list =
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 2; 4; 6; 8; 10; 12; 14; 16; 18; 20; 3; 6; 9;
 12; 15; 18; 21; 24; 27; 30; 4; 8; 12; 16; 20; 24; 28; 32; 36; 40; 5; 10; 15;
 20; 25; 30; 35; 40; 45; 50; 6; 12; 18; 24; 30; 36; 42; 48; 54; 60; 7; 14;
 21; 28; 35; 42; 49; 56; 63; 70; 8; 16; 24; 32; 40; 48; 56; 64; 72; 80; 9;
 18; 27; 36; 45; 54; 63; 72; 81; 90; 10; 20; 30; 40; 50; 60; 70; 80; 90; 100]