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

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

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

だいぶ手こずった。

```go:実装
package e17

import (
	"strconv"
	"strings"
)

// b の k 乗。整数版。
func powi(b, k int) int {
	if k < 0 {
		panic("k should not be negative.")
	}
	if k == 0 {
		return 1
	}
	n := powi(b, k/2)
	var r int
	if k%2 == 0 {
		r = 1
	} else {
		r = b
	}
	return n * n * r
}

// k桁の回文数の数
func pa(k, b int) int {
	if k == 1 {
		return b - 1
	}
	var mid int
	if k%2 == 1 {
		mid = b
	} else {
		mid = 1
	}
	return (powi(b, k/2) - powi(b, k/2-1)) * mid
}

// 文字列を逆順にする
func rev(s string) string {
	var b strings.Builder
	for i := len(s) - 1; 0 <= i; i-- {
		b.WriteByte(s[i])
	}
	return b.String()
}

//  0<x<m の base 進数での回文数の数
func impl(m, base int) int {
	if m <= base {
		return m - 1
	}
	s := strconv.FormatInt(int64(m), base)
	keta := len(s)
	shead := s[0 : keta/2]
	var mids []string
	if keta%2 == 1 {
		for i := 0; i < base; i++ {
			mids = append(mids, strconv.FormatInt(int64(i), base))
		}
	} else {
		mids = append(mids, "")
	}
	head64, _ := strconv.ParseInt(shead, base, 64)
	head := int(head64)
	count := 0
	for k := 1; k < keta; k++ {
		count += pa(k, base)
	}
	//keta桁の数で、前半が m の前半より小さい
	count += (head - powi(base, keta/2-1)) * len(mids)
	// keta桁の数で、前半が m の前半と等しい
	for _, mid := range mids {
		cand, _ := strconv.ParseInt(shead+mid+rev(shead), base, 64)
		if cand < int64(m) {
			count++
		}
	}
	return count
}

func solve(src string) string {
	nums := strings.Split(src, ",")
	lo, _ := strconv.Atoi(nums[0])
	hi, _ := strconv.Atoi(nums[1])
	base, _ := strconv.Atoi(nums[2])
	return strconv.Itoa(impl(hi, base) - impl(lo, base))
}
```

```go:テスト
package e17

import (
	"testing"
)

func TestPowi(t *testing.T) {
	var tests = []struct {
		b, k, want int
	}{
		{10, 0, 1},
		{1, 10, 1},
		{2, 10, 1024},
		{123, 3, 123 * 123 * 123},
	}
	for _, test := range tests {
		got := powi(test.b, test.k)
		if got != test.want {
			t.Errorf("powi(%d,%d) = %d, want %d", test.b, test.k, got, test.want)
		}
	}
}

func TestRev(t *testing.T) {
	var tests = []struct {
		s, want string
	}{
		{"abc", "cba"},
		{"", ""},
		{"a", "a"},
	}
	for _, test := range tests {
		got := rev(test.s)
		if got != test.want {
			t.Errorf("rev(%s) = %s, want %s", test.s, got, test.want)
		}
	}
}

func TestImpl(t *testing.T) {
	var tests = []struct {
		k, b, want int
	}{
		{10, 10, 9},
		{12, 10, 10},
		{19, 10, 10},
		{23, 10, 11},
		{100, 10, 18},
		{102, 10, 19},
	}
	for _, test := range tests {
		got := impl(test.k, test.b)
		if got != test.want {
			t.Errorf("impl(%d,%d) = %d, want %d", test.k, test.b, got, test.want)
		}
	}
}

func Test(t *testing.T) {
	var tests = []struct {
		name  string
		input string
		want  string
	}{
		{"0", "12,34,5", "5"},
		{"1", "10,11,10", "0"},
		{"2", "1,100,3", "18"},
		{"3", "11,12,10", "1"},
		// 中略
		{"33", "2099642384,2789567569,6", "14787"},
	}
	for _, test := range tests {
		got := solve(test.input)
		if got != test.want {
			t.Errorf("%v: solve(%q)=%q, want %q\n", test.name, test.input, got, test.want)
		}
	}
}
```

いろいろ手こずった。
ruby なら `n=str.to_i(base)` と書くところを、

```go:go
n64, _ := strconv.ParseInt(str, base, 64)
n := int(n64)
```

と書かざるを得ないところとか、思考が遮られる感じ。

整数用指数関数( `powi` )を用意したり。

実行は一瞬でとても速いけど、ruby でも一瞬なので、大差ない。