オフラインリアルタイムどう書く E19 の実装例
問題 : http://mtsmfm.github.io/2017/11/04/doukaku-e19.html
実装リンク集 : https://qiita.com/mtsmfm/items/67bf5c121ecbd9b5fab3
で。
https://qiita.com/Nabetani/items/feb89852b54886526c9f の１つ目を Go に移植した。苦しい感じ。
実装
package e19
import (
"strconv"
"strings"
)
func makeCards(l int) []int {
r := make([]int, l*2)
for i := 0; i < l; i++ {
r[i*2] = i + 1
r[i*2+1] = i + 1
}
return r
}
func appended(x []int, e int) []int {
x = append(make([]int, 0, len(x)+1), x...) // i mean copy
x = append(x, e)
return x
}
func toStr(x []int) string {
var b strings.Builder
b.Grow(len(x) * 3)
for _, e := range x {
if b.Len() != 0 {
b.WriteByte(',')
}
b.WriteString(strconv.Itoa(e))
}
return b.String()
}
func combination2(done map[string]bool, x0, y0, all []int, l int, proc func(x, y []int)) {
if 0 < len(all) {
x := append(make([]int, 0, len(x0)), x0...) // i mean copy
y := append(make([]int, 0, len(y0)), y0...) // i mean copy
if len(x) < l {
combination2(done, appended(x, all[0]), y, all[1:], l, proc)
}
if len(y) < l {
combination2(done, x, appended(y, all[0]), all[1:], l, proc)
}
} else {
sx0 := toStr(x0)
if !done[sx0] {
proc(x0, y0)
done[sx0] = true
}
}
}
func combination(all []int, l int, proc func(x, y []int)) {
combination2(make(map[string]bool), make([]int, 0), make([]int, 0), all, l, proc)
}
func toCode(x []int) string {
var b strings.Builder
b.Grow(len(x))
for _, e := range x {
if e%2 == 0 {
b.WriteByte('x')
} else {
b.WriteByte('o')
}
}
return b.String()
}
func solve(src string) string {
pats := strings.Split(src, ",")
l := len(pats[0])
all := makeCards(l)
cands := make([]string, 0)
combination(all, l, func(x, y []int) {
cx := toCode(x)
cy := toCode(y)
if pats[0] == cx && pats[1] == cy {
cands = append(cands, toStr(x)+","+toStr(y))
}
})
return strings.Join(cands, "|")
}
テスト
package e19
import (
"testing"
)
func Test(t *testing.T) {
var tests = []struct {
name string
input string
want string
}{
{"0", "xxoxo,oooxo", "2,2,3,4,5,1,1,3,4,5"},
{"1", "ooxxo,ooxxo", "1,1,2,2,5,3,3,4,4,5|3,3,4,4,5,1,1,2,2,5"},
{"2", "oxoxo,oxoxo", "1,2,3,4,5,1,2,3,4,5"},
{"3", "ooxoxx,oxxoxo", "1,3,4,5,6,6,1,2,2,3,4,5"},
// 中略
{"24", "oooooooooooo,xxxxxxxxxxxx", "1,1,3,3,5,5,7,7,9,9,11,11,2,2,4,4,6,6,8,8,10,10,12,12"},
}
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)
}
}
}
実装 82行。長い。
combination を書かざるを得なかったのが辛かった。
ruby 版では combination → uniq → rest_of としたが、Go 版は rest_of を書くのが面倒だったのと combination が独自実装だったので、rest_of に相当する処理を combination の中に入れた。uniq も combination の中に入れた。
combination2（名前が悪い）は combination の中に隠したほうが良かったね。
あと。
スライスのコピーのために append を呼んだり、副作用のない append がほしくて appended を作ったり。
実行すると 手元のマシンで 13秒ちょっと。ruby 版が61秒だったので、速い。速いけど、思ったほどではない感じ。
テストの実行に Goルーチンを入れたら2〜3倍ぐらい速くなるのではないかと思うけど試していない。