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

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

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

だいぶ手こずった。

実装

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))
}

テスト

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

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

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

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

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