オフラインリアルタイムどう書く F06 の実装例( Go )

オフラインリアルタイムどう書く F06 の実装例( Go )

問題 : http://nabetani.sakura.ne.jp/hena/ordf06numit/
実装リンク集 : https://qiita.com/Nabetani/items/deda571c9451bd7d3175

実装

package f06

import (
    "strconv"
    "strings"
)

func implNoMemo(root, target int) int {
    if root == target {
        return 1
    }
    if root < target {
        return 0
    }
    return implNoMemo(root/2-10, target) + implNoMemo(root*2/3, target)
}

func solveNoMemo(src string) string {
    split := strings.Split(src, ",")
    root, _ := strconv.Atoi(split[0])
    target, _ := strconv.Atoi(split[1])
    return strconv.Itoa(implNoMemo(root, target))
}

func impl(root, target int, memo map[int]int) int {
    if root == target {
        return 1
    }
    if root < target {
        return 0
    }
    val, contains := memo[root]
    if contains {
        return val
    }
    c := impl(root/2-10, target, memo) + impl(root*2/3, target, memo)
    memo[root] = c
    return c
}

func solve(src string) string {
    split := strings.Split(src, ",")
    root, _ := strconv.Atoi(split[0])
    target, _ := strconv.Atoi(split[1])
    memo := make(map[int]int)
    return strconv.Itoa(impl(root, target, memo))
}

テスト

package f06

import (
    "testing"
)

func Test(t *testing.T) {
    var tests = []struct {
        name  string
        input string
        want  string
    }{
        {"0", "123,4", "5"},
        {"1", "1,1", "1"},
        {"2", "2,1", "1"},
        {"3", "3,3", "1"},
        // 中略
        {"30", "5745432,1032", "1287"},
    }
    for _, test := range tests {
        got := solve(test.input)
        //got := solveNoMemo(test.input)
        if got != test.want {
            t.Errorf("%v: solve(%q)=%q, want %q\n", test.name, test.input, got, test.want)
        }
    }
}

やはり、再帰呼び出ししつつメモ化の一択。
とはいえ、折角 Go なので、メモ化なしも用意してみた。

今回はサクッと書けた。
問題が簡単すぎるのか、私が慣れたのか。

簡単なので見どころはあまりないんだけど、一応再帰を描いたのは初めてかな。

ちなみに、メモ化ありだと0.01秒ぐらい。
メモ化なしでも0.89秒ぐらいで、結構速い。