オフラインリアルタイムどう書く 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秒ぐらいで、結構速い。