オフラインリアルタイムどう書く E27の参考問題「灯りと鏡」の実装例を、golang で。
問題 : http://nabetani.sakura.ne.jp/hena/orde27ligmir/
実装リンク集 : https://qiita.com/Nabetani/items/0b2f459ec128c89948f4
本番の会場で go を使う人は多くはないけど、たまにいる感じ。
計算量が多くなってしまったときに仕方なく go で攻めるとかで。
で。私の実装例は下記の通り：
実装
package e27r
import (
"sort"
"strings"
)
const mapsize = 5
type xytype struct {
x, y int
}
func (p xytype) inmap() bool {
return 0 <= p.x && p.x < mapsize && 0 <= p.y && p.y < mapsize
}
func (p xytype) add(q xytype) xytype {
return xytype{p.x + q.x, p.y + q.y}
}
func (p xytype) eq(q xytype) bool {
return p.x == q.x && p.y == q.y
}
func (p xytype) cell(m string) byte {
return m[p.x+p.y*(mapsize+1)]
}
func (p xytype) reflect(dir int) xytype {
return xytype{dir * p.y, dir * p.x}
}
func impl(src string) []xytype {
you := strings.Index(src, "Y")
youpos := xytype{x: you % (mapsize + 1), y: you / (mapsize + 1)}
visited := []xytype{youpos}
curpos := youpos
curdir := xytype{0, -1}
for {
if !curpos.inmap() {
return visited
}
switch curpos.cell(src) {
case '1':
curdir = curdir.reflect(-1)
case '0':
curdir = curdir.reflect(1)
case 'x':
return visited
}
visited = append(visited, curpos)
curpos = curpos.add(curdir)
if curpos.eq(youpos) && curdir.eq(xytype{0, -1}) {
return visited
}
}
}
func solve(src string) string {
visited := impl(src)
r := map[string]bool{}
for _, v := range visited {
r[string(v.x+v.y*mapsize+int('a'))] = true
}
keys := []string{}
for k := range r {
keys = append(keys, k)
}
sort.Strings(keys)
return strings.Join(keys, "")
}
テスト
package e27r
import "testing"
func Test(t *testing.T) {
var tests = []struct {
name string
input string
want string
}{
{"0", "x...x/.1.0./..0../.Y.../0..x.", "ghilnqs"},
{"1", "..Y../...../...../...../.....", "c"},
{"2", "..x../..Y../...../...../.....", "h"},
{"3", "..Y.x/..1x0/11.../....0/1..1.", "c"},
{"4", "....1/....Y/...../...../.....", "ej"},
{"5", ".10../x.1../x.1x./.Y.1./...0.", "bcghlq"},
{"6", "0.x10/00..x/x0x.0/....0/...Y1", "deinsx"},
{"7", "1.01./01Y.1/..1.1/..10./0.0..", "abcfgh"},
{"8", "x..../x1x../0...0/....Y/.1..0", "klmnot"},
{"9", "...../..10./.1Y1./.01../.....", "hilmnqr"},
{"10", "...../..10./x.11./...../..Y..", "hilmnrw"},
{"11", "...../x.10x/...../x.Y1x/.....", "himnqrs"},
{"12", "..010/...Y1/..0../0.x../.....", "defghij"},
{"13", "1.0../...../.0x../Y.1x./..1..", "abcfhkp"},
{"14", "...../101../0.0../..Y../.....", "fgklmqrv"},
{"15", "1.0../00.../.x..0/0.Y1./...10", "abcfghmr"},
{"16", "x101./1..../.Y.x./..01./.00.1", "bcghlmrs"},
{"17", "x11../x.x../.0.01/..x../...Y.", "bcglmnsx"},
{"18", "..1.0/x0.x./0.0../x...Y/.10.1", "cdehjmnot"},
{"19", "..x.0/.0.../1..0x/1..1./Y.00.", "klmnpqrsu"},
{"20", "0.1.0/.0.xY/0...0/01..1/x00.x", "cdehjmrwx"},
{"21", "...0./.0.0./..101/...10/..01Y", "mnpqrstwxy"},
{"22", "10..0/.Y.0./0..1./....x/000..", "abfghiklmn"},
{"23", "10..1/...../.1010/110.1/x..Yx", "lmnopqrstx"},
{"24", "110../....1/x1..x/0.0.0/....Y", "bcghlmrsty"},
{"25", "x.101/1..../..001/010Yx/..1.1", "cdehijmnos"},
{"26", "x.111/x10../...0./00.1x/x.Y.1", "ghklmnqrsw"},
{"27", "11.../....0/11..1/1.1../.Y..1", "fghijlmnoqv"},
{"28", "...x1/.1.0./11.1./.01../Y..x.", "cghiklmnpqru"},
{"29", ".0.../110x./11..0/01.x./..Y.x", "ghklmnopqrtw"},
{"30", ".01.0/.110x/0...0/.01Y./x.1x.", "cdeghilmnqrs"},
{"31", ".1100/..1.0/1.11Y/0..1./.0..0", "hijklmnopqrs"},
{"32", "1..00/..11./.100./1..Y1/.....", "abcdfhikmnps"},
{"33", "1.0../.11x0/.00.x/Y.10./.10x0", "abcfghklmpqr"},
{"34", "11110/11.../.x.../.0111/0.Y0.", "deijnorstwxy"},
{"35", "...1./.1.0x/10..0/0Y.11/.0.x0", "ghiklmnopqrst"},
{"36", "...10/x111./0x.11/.0.../0.0Y.", "dehijmnorswxy"},
{"37", ".1x../.x1.0/0x.x./x11.1/x0Y.1", "hijmoqrstvwxy"},
{"38", "x.x../x110./1.1.0/0.Y.1/0.00x", "hiklmnopqrstx"},
{"39", "...0./11.00/10..x/..0.1/Y0.10", "ghiklmnpqsuvwx"},
{"40", ".110./....0/x..../.0001/11.Y.", "cdfghijmnorstx"},
{"41", "1.00./....1/.1.../0...0/0..1Y", "abcfhkmpqrstwy"},
{"42", ".1.01/..x../..100/..Y../...01", "bcdgilmnoqrstvxy"},
{"43", "1...0/Y..../...../...../0...1", "abcdefjkoptuvwxy"},
{"44", "x1..0/1..0./.Yx../0...1/.0.1.", "bcdefghijklnopqrstvwx"},
{"45", "1...0/.1.0./..1../..01./Y0..1", "abcdefghijklmnopqrstuvwxy"},
}
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)
}
}
}
最近仕事で go を書くことが多くなってきたけど、まだ手に馴染んでいない。
ruby でいうところの ary.uniq.sort を書くのが大変だった。
この辺りが go の弱点だと思う。 Go++ に期待。
実装戦略はふつうに光の筋をたどっている感じ。まあそれしかないと思う。
終了条件は、 ruby版, python版と異なり、真面目にやっている。
xytype を定義したけど、そういう趣旨の組み込み型があったりしないのかなぁと思いつつ、調べずに書いた。
複素数型があるのは知っているんだけど、整数じゃないので使わなかった。
困らないけど、なんとなくね。