Back to Questions
1.0k
views2
comments
"Cedric's Challenge"
f#compiler

I saw this post on Reddit, and I've been practicing my (rather poor) skills on f#: [link:beust.com]

My solution is:

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

#light

let rec digits (x: int) =
    seq { 
        match x with
        | _ when x < 10 -> yield x
        | _ -> yield x % 10
               yield! digits(x / 10)
    }

let noRepeatedDigits (x: int) =
    if x < 11 then
        true
    else 
        let seen = Array.create 10 false
        let isDup d =
            if seen.[d] then
                true
            else begin
                seen.[d] <- true
                false
            end
        match Seq.tryfind isDup (digits(x)) with
        | Some(_) -> false
        | _ -> true

let biggestJump l =
    let prev = ref (List.hd l)
    let diff a x = 
        let r = max a (x - !prev)
        prev := x
        r 
    List.fold_left diff 0 (List.tl l)    

let answer max = 
    let l = [ 1 .. max ] |> List.filter noRepeatedDigits
    (l, List.length l, biggestJump l)

Some questions:

Is the "let rec" and "yield!" the best way to implement digits? I kinda guessed and kept poking at it until I got something the compiler accepted.

The Seq.tryfind was my attempt at working around not being able to break out of a loop. It seems there must be an easier way to do this.

Any feedback is appreciated. Still working on trying to figure out a lot of F#.

.

Hello, gavin..
This task is simply to solve in terms of streams:

  • generate all combinations C<sup>m</sup><sub>n </sub>m in 1..limit
  • permute them to collect all possible numbers with
  • sort them all filter out duplicate numbers (f.e. numbers with leading zero)
  • convert resulted sequence to form like (1st,2nd),(2nd,3rd),...
  • calculate distance for each pair and select max
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

#light

let rec distribute elt = function
  | (hd :: tl) as list -> 
    (elt :: list) :: (List.map (fun x -> hd :: x) (distribute elt tl))
  | [] -> [ [elt] ]

let rec permute = function
  | x :: rest -> List.flatten (List.map (distribute x) (permute rest))
  | [] -> [ [] ]

//generate unordered sequence of lists with unique digits (leading '0' is possible)
//all lists have same length (lim)
let gen lim =
  let rec gen r k =
    seq {
          for i in k..9 do
            let r' = i::r
            if List.length r' = lim then yield r'
            else yield! gen r' (i+1)
    }
  gen [] 0

let l2n l = List.fold_left (fun r n -> r*10+n) 0 l

let f (dist,len) (a,b) = max (b - a) dist, len+1

let u_seq lim =
  seq {
        for i in 1..lim do
          for s in gen i do
            yield! permute s
  }

u_seq 4 |> Seq.map l2n |> Set.of_seq |> Seq.pairwise |> Seq.fold f (0,1)

P.S. if you replace u_seq with function able to generate ordered permutations (let name it o_seq)
then rest of the program is yet simpler:

1
2
3

let (--) i j = (l2n i) - (l2n j)
let f (dist,len) (a,b) = max (b -- a) dist, len+1
o_seq 4 |> Seq.pairwise |> Seq.fold f (0,1)
By on 7/2/2008 5:38 AM ()

I guess one of the problems I'm having with F# is that there are so many ways to achive the same thing :) It bothered me that I was using mutable state, but it took a while for me to realize I could use a tuple for the state: 

1
2
3
4
5

let biggestJump l =
    let diff (a,x) y =
        max a (y - x), y
    let x,_ = List.fold_left diff (0, (List.hd l)) (List.tl l)
    x
By on 6/29/2008 7:05 PM ()

    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