Back to Questions
2.2k
views1
comment
Code Jam Round 3 2010
f#functionalasync

Hi,

First, sorry for my poor english, it's not my native language.

I have discovered F# a while ago, and I'm trying to domesticate it [:)] a not so easy task, I'm not used to functional paradigm.

Searching for trials, I found this problem quite interesting Hot Dog Proliferation and tried to solve it.

I've got a working solution for the small sample file with the code posted after, but for the large file, it doesn't work at all. My approach is too "brute-forced" and eventually it will also solve the large sample but it will took ages [:(]

There is a first version of my code:

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

open System
open System.Collections.Generic
open System.IO
 
type Dict = Dictionary<int, int>
 
let writeContent(path : string) (results : #seq<string>) =
    use sw = new StreamWriter(path)
    results |> Seq.iter sw.WriteLine
 
let readContent(path : string) =
    use sr = new StreamReader(path)
    [
    for case in 1 .. sr.ReadLine() |> int do
        yield new Dict(seq {
            for corner in 1 .. sr.ReadLine() |> int do
                let values = sr.ReadLine().Split([|' '|]) |> Array.map int
                yield values.[0], values.[1]
        } |> dict)
    ]
 
let solve index (case : Dict) =
    async {
        let addHelper key =
            if case.ContainsKey key
                then case.[key] <- case.[key] + 1
                else case.Add(key, 1)
        let rec loop moveCnt =
            match case |> Seq.tryFind (fun kvp -> kvp.Value > 1) with
            | Some kvp ->
                case.[kvp.Key] <- case.[kvp.Key] - 2
                addHelper (kvp.Key - 1)
                addHelper (kvp.Key + 1)
                loop (moveCnt + 1L)
            | None ->
                sprintf "Case #%d: %d" (index + 1) moveCnt
        return loop 0L
    }
 
"C-small-practice.in"
//"C-large-practice.in"
|> readContent
|> List.mapi solve
|> Async.Parallel // not sure Async is useful
|> Async.RunSynchronously
|> Seq.iter (printfn "%s")

And the second (better [:D]) version:

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

open System.Diagnostics
open System.IO
 
type Stopwatch with
    static member inline Time func param =
        let sw = Stopwatch.StartNew() in
        let result = func param in
        printfn "%A" sw.Elapsed
        result
 
type StreamReader with
    member inline private t.ReadInt() = t.ReadLine() |> int
    member inline private t.ReadData() =
        let data = t.ReadLine().Split([|' '|]) |> Array.map int in
        data.[0], data.[1]
    static member inline ParseFile (path : string) =
        seq {
            use sr = new StreamReader(path) in
            for case in 1 .. sr.ReadInt() ->
            seq {
                for corner in 1 .. sr.ReadInt() ->
                sr.ReadData()
            } |> Map.ofSeq
        }
 
let inline cornerValue corner street =
    match Map.tryFind corner street with
    | None -> 1
    | Some value -> value + 1
     
let inline moveAt corner street =
    let prev, next = corner - 1, corner + 1 in
    street
    |> Map.add prev (cornerValue prev street)
    |> Map.add corner (street.[corner] - 2)
    |> Map.add next (cornerValue next street)
 
let stabilize street =
    let rec loop moves street =
        match Map.tryFindKey (fun _ v -> v > 1) street with
        | None -> moves
        | Some corner ->
            loop (moves + 1L) (moveAt corner street)
    in loop 0L street
 
"C-small-practice.in"
//"C-large-practice.in"
|> StreamReader.ParseFile
//|> Seq.map (Stopwatch.Time stabilize)
|> Seq.map stabilize
|> Seq.iteri (fun i -> printfn "Case #%d: %d\n" (i + 1))

If you have remarks, advices, etc. I will be glad to read them !

But it's not the primary purpose of my post, on Code Jam there is also how to solve the problem, or at least observations leading towards the "good path"
Note sure if it's my lack of knowledge in english, in mathematical concepts or something else but even if I manage to globally understand the solution I didn't success in applying in or finding the right structure for data (I thought of a (int * int) list for the Segments acting like a stack-like container)
And I don't point the second approach they give (Part "Adding one pile" in the link above) which seems really adapted with the use of a (int * int * int) list "Stack-like" stuff ... maybe ? I imagine [:^)]
If it's a good way, an explanation of how to handle overlaping (detection, resolving) particularly but not necessarily precisely (not sure it'll sound good in english [:$]) will be necessary.

There is also few documentation on google for "chip firing games" or they are full of formulas which are far away of my understanding

So, any information, explanation, start of guidance or something else which can lead me to a little better (for my comprehension and for my code)

Again, sorry for having to decypher this post.

Regards !

.

Nothing relevant to say about your post yet, I just wanted to thank you for making me notice the code jam web site.

I must have been living under a rock, how could I miss this site?

I may take a look at this problem some time later this summer.

By on 6/15/2011 2:13 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