Back to Questions
1.0k
views3
comments
Help wrap my head around a Project Euler problem
f#

I've been working through the Project Euler problems to help figure out F#, and so far it's going pretty well. I have run into a roadblock, though, specifically on a problem dealing with the products of various digits in a number.

The first thing I did was wrote a little function to pull out a sequence of digits:

1
2
3
4
5
6
7
8
9
10

let digits = Seq.unfold 

                (fun x -> if x >= 1I then

                                Some(x % 10I, x / 10I)

                            else

                                None)

That seems nice and clean and F# friendly to me, but I don't really know for sure. Are there any improvements I could make to it? Is it possible to replace the Seq.unfold with a sequence expression instead? Also, could it be more generic?

My real problem is building a tails function (that is, a sequence that gives back smaller and smaller tails from another sequence... or list, if necessary). This is what I've tried, but I can't get it to work at all:

1
2
3
4
5
6
7
8
9

let tails = Seq.unfold

                (fun x -> if Seq.nonempty(x) then

                                Some(x, Seq.tail_cons(x))

                            else

                                None)

Now, assuming I can get at all the tails, it should be relatively easy to get the product of the first 5 elements in each... I think. I haven't actually tried that one yet, I need to get at the lists first.

.

This doesn't answer your question directly, but here's how I would apporach the problem:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#light
open Microsoft.FSharp.Core.Operators.Checked

let rawData =
    "73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450"

let charToInt c =
    match c with
    | '0' -> Some 0 | '1' -> Some 1 | '2' -> Some 2
    | '3' -> Some 3 | '4' -> Some 4 | '5' -> Some 5
    | '6' -> Some 6 | '7' -> Some 7 | '8' -> Some 8
    | '9' -> Some 9
    | _ -> None


let rec createProductList l =
    match l with
    | i1 :: i2 :: i3 :: i4 :: i5 :: tail -> 
        (i1 * i2 * i3 * i4 * i5) :: createProductList (i2 :: i3 :: i4 :: i5 :: tail)
    | _ -> []

let heighestProduct = 
    rawData.ToCharArray() 
    |> Seq.choose charToInt
    |> List.of_seq
    |> createProductList
    |> List.fold_left (fun acc x -> if x > acc then x else acc) 0

If I've understood the problem correctly: we tread the 1000 digit number as string data for convience, then we turn this into a sequence of integers, to get at the individual digits which seem to be the important part for this problem. From here its fairly straight forward to turn this into a list of the products each five consecutive digits set - this is the createProductList function, then we use a fold function to find the maxium of these.

The answer I get is 40824, but I couldn't see an answer to this problem, so I've no way to check this.

Cheers,
Rob

By on 12/29/2007 4:57 AM ()

Ah, that's actually pretty helpful and gave me a good idea of how to make my approach work. Your solution was correct.

Here's what I came up with:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#light

open Microsoft.FSharp.Math

let big = 731671..420752963450I

let digits = Seq.unfold 

                (fun x -> if x >= 1I then

                                Some(x % 10I, x / 10I)

                            else

                                None)

let take n (l:'a list) = 

    if l.Length < n then 

        l 

    else 

        Seq.of_list(l) |> Seq.take 5 |> List.of_seq

let tails l = 

    let rec recTails l1 =

        match l1 with

        | h :: t -> t :: recTails(t)

        | _ -> []

    l :: recTails(l)

let highestGroup = 

    digits big

    |> List.of_seq

    |> tails

    |> List.map(fun x -> take 5 x)

    |> List.map(fun x-> List.fold_left(fun acc y -> y * acc) 1I x)

    |> List.fold_left(fun acc x -> if x > acc then x else acc) 0I

print_any highestGroup

It's a bit uglier than I'd like, but I did figure out (from your code, actually) how to approach the "tails" and "take" functions I wanted to use.

On to the next problem! It's amazing how much time I spend trying to figure out what type inference errors actually mean. :)

By on 12/29/2007 8:01 PM ()

<quote> <i>It's amazing how much time I spend trying to figure out what type inference errors actually mean. :) <i></quote> Please feel free to send examples of particularly obscure error messages to "fsbugs AT microsoft DOT com"... Screen shots of Visual Studio (if you are using it) are a great way to do this. Kind regards, don

By on 12/30/2007 2:35 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper