Hatena::ブログ(Diary)

TopCoderとJ言語と時々F# このページをアンテナに追加 RSSフィード

2009-05-20

[][]TopCoder SRM 440 Div1 Medium in F#

F#で書いた。工夫した点?知りませんなぁ。


let maze = [".........";  "XXX.XXXX.";  ".XX.X....";  ".....XX.X"]
let sx, sy = 0, 0
let dx, dy = [1; -1; 0; 0], [0; 0; 1; -1]
let N, M = List.length maze, maze.[0].Length
let ex = Array2.init N M (fun _ _ -> 0.0)

let rec dfs1 x y px py =
    let l =
        [for i in 0..3 ->
            let nx = x + dx.[i]
            let ny = y + dy.[i]
            if (nx <> px || ny <> py) &&
               nx >= 0 && ny >= 0 && nx < M && ny < N &&
               maze.[ny].[nx] <> 'X' then
                dfs1 nx ny x y;
                ex.[ny, nx] + 1.0
            else 0.0]
    in ex.[y, x] <- 1.0 + List.fold_left (+) 0.0 l

let exsum = ref 0.0

let rec dfs2 x y px py sum =
    let nsum = sum + ex.[y, x]
    exsum := !exsum + nsum;
    [for i in 0..3 ->
        let nx = x + dx.[i]
        let ny = y + dy.[i]
        if (nx <> px || ny <> py) &&
           nx >= 0 && ny >= 0 && nx < M && ny < N &&
           maze.[ny].[nx] <> 'X' then
            dfs2 nx ny x y nsum] |> ignore

let rec count s c n =
    match s with
    | [] -> n
    | x::xs ->
        if x = c then count xs c (n + 1)
        else count xs c n

let expectedTime () =
    dfs1 sx sy -1 -1;
    dfs2 sx sy -1 -1 -ex.[sy, sx];
    let ct = List.fold_left (+) 0
                [for i in 0..N-1 -> count [for c in maze.[i] -> c] '.' 0]
    in !exsum / float ct

実行結果↓

> expectedTime ();;
val it : float = 167.2608696

2009-02-26

[][][][]Life

private class Life : IDisposable
{
    public Live()
    {
        while(this.Alive)
        {
            if(!this.WantToLive)
            {
                break;  // kill myself
            }
            if(this.Riajuu)
            {
                Life.Enjoy(this);    // 到達できないコードが検出されました
            }
        }
        this.Die();
    }
}
let rec Life state =
    match state with
    | Sinitai -> Die ()     (* kill myself *)
    | Riajuu -> Enjoy ()    (* This rule will never be matched *)
    | _ -> Life state
class Life(object):
    pass

全てくだらない思いつき。

2009-01-23

[]末尾再帰たんの行方を探ってみた

(* 再帰的な階乗の定義(F#) *)
let rec fact = function
    0 -> 1 | n -> n * fact (n-1)

コンパイルしてデコンパイル↓

public static int fact(int _arg1)
{
    switch (_arg1)
    {
        case 0:
            return 1;
    }
    return (_arg1 * fact(_arg1 - 1));
}

ま  さ  に  直  訳


(* 末尾再帰的な階乗の定義(F#) *)
let rec fact2 n res =
    if n = 0 then res else fact2 (n-1) (n*res)

コンパイルしてデコンパイル↓

public static int fact2(int n, int res)
{
    while (n != 0)
    {
        res = n * res;
        n--;
    }
    return res;
}

こいつぁすげぇや!

2009-01-21

[][]末尾再帰たん萌え

たとえばF#で階乗をつぎみたいに実装したとするよね↓

let fact n res =
    if n = 0 then res else fact (n-1) (n*res)

末尾再帰たんモエス

なんだけど、末尾再帰って最適化されちゃうんだよね?特にSchemeとかだと。

たとえばさっきの階乗をC風に書けば

int fact(int n, int res) {
    if(n == 0) return res;
    else return fact(n-1, n*res);
}

こんな感じだけど、もしこれがコンパイラとかによって最適化されちゃうとさ、

int fact(int n, int res) {
    while(true) {
        if(n == 0) return res;
        else {
            n = n-1;
            res = n*res;
        }
    }
}

みたいになるの?末尾再帰たんは居なくなっちゃうの?


「末尾再帰たんは、どこへいっちゃったの?」

――『きっと、どこか遠いところへいってしまったんだよ。』

「とおいところって、どこ?」

――『今はまだ分からないだろう。』

「もう会えないの?」

――『大人になって、いつかパフォーマンスを気にするときが来るだろう。そうすれば、きっと末尾再帰がどこへいってしまったのか分かるさ。』

「ぜったい?」

――『ああ。大人になってメモリの事情なんかを知るときっとね。』


まあ、具体的に末尾再帰がどう最適化されてるんだろうなっていうお話。

2009-01-16

[]マージソート書いてみた

ソース↓

let rec mergesort cmp l =
    let rec merge l1 l2 res =
        match (l1, l2) with
        ([], []) -> res
        | ([], l) | (l, []) -> (List.rev l) @ res
        | (m::ms, n::ns) ->
            if (cmp m n) < 1 then merge ms l2 (m::res)
            else merge l1 ns (n::res)
    in
    let split l n =
        let rec split' l left c =
            match (l, c) with
            (x::xs, c) ->
                if c < n then split' xs (x :: left) (c+1)
                else (List.rev left, x::xs)
            | _ -> failwith "invalid list"
        in split' l [] 0
    in
    match l with
    [] | [_] -> l
    | _ ->
        let m = List.length l / 2 in
        let left, right = split l m in
        merge (mergesort cmp left) (mergesort cmp right) [] |> List.rev

↑の動作確認↓

let t = [2;7;1;8;2;8;1;8;2;8;4;5;9;0;4;1]
mergesort (fun x y -> compare x y) t
mergesort (fun x y -> compare y x) t

let s = ["Sapporo"; "Sendai"; "Tokyo"; "Yokohama"; "Aichi"; "Kyoto"; "Kobe"; "Fukuoka"; "Naha"]
mergesort (fun (x:string) (y:string) -> compare x.Length y.Length ) s

↑の結果↓

[0; 1; 1; 1; 2; 2; 2; 4; 4; 5; 7; 8; 8; 8; 8; 9]
[9; 8; 8; 8; 8; 7; 5; 4; 4; 2; 2; 2; 1; 1; 1; 0]
["Kobe"; "Naha"; "Tokyo"; "Aichi"; "Kyoto"; "Sendai"; "Sapporo"; "Fukuoka"; "Yokohama"]