オフラインリアルタイムどう書く 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 を定義したけど、そういう趣旨の組み込み型があったりしないのかなぁと思いつつ、調べずに書いた。

複素数型があるのは知っているんだけど、整数じゃないので使わなかった。
困らないけど、なんとなくね。