オフラインリアルタイムどう書くE28の問題「増築の果ての隣室」の実装例を、go言語 で。
問題 : http://nabetani.sakura.ne.jp/hena/orde28sqst/
実装リンク集 : https://qiita.com/Nabetani/items/4e3fac2746ca05a93165
イベント : https://yhpg.doorkeeper.jp/events/81346
次回のイベントは 12/8。
詳しくは
https://yhpg.doorkeeper.jp/events/82699
を御覧ください。楽しいよ？
で。
実装例は以下の通り：
e28.go
package e28
import (
"fmt"
"strconv"
"strings"
)
type operation struct {
dir byte
count int
}
type room struct {
left, top int64
w int64
}
func (p room) bottom() int64 {
return p.top + p.w
}
func (p room) right() int64 {
return p.left + p.w
}
func getOps(src string) []operation {
r := []operation{}
for i := 0; i < len(src); i += 2 {
op := operation{src[i], int(src[i+1] - '0')}
r = append(r, op)
}
return r
}
func topOf(rooms []room) int64 {
r := rooms[0].top
for _, ro := range rooms {
c := ro.top
if c < r {
r = c
}
}
return r
}
func bottomOf(rooms []room) int64 {
r := rooms[0].bottom()
for _, ro := range rooms {
c := ro.bottom()
if r < c {
r = c
}
}
return r
}
func rightOf(rooms []room) int64 {
r := rooms[0].right()
for _, ro := range rooms {
c := ro.right()
if r < c {
r = c
}
}
return r
}
func leftOf(rooms []room) int64 {
r := rooms[0].left
for _, ro := range rooms {
c := ro.left
if c < r {
r = c
}
}
return r
}
func newrooms(rooms []room, op operation) []room {
t := topOf(rooms)
b := bottomOf(rooms)
r := rightOf(rooms)
l := leftOf(rooms)
ret := []room{}
for i := 0; i < op.count; i++ {
switch op.dir {
case 'N':
w := (r - l) / int64(op.count)
ret = append(ret, room{l + int64(i)*w, t - w, w})
case 'S':
w := (r - l) / int64(op.count)
ret = append(ret, room{l + int64(i)*w, b, w})
case 'W':
w := (b - t) / int64(op.count)
ret = append(ret, room{l - w, t + int64(i)*w, w})
case 'E':
w := (b - t) / int64(op.count)
ret = append(ret, room{r, t + int64(i)*w, w})
}
}
return ret
}
func build(base int64, ops []operation) []room {
r := []room{room{0, 0, base}}
for _, op := range ops {
r = append(r, newrooms(r, op)...)
}
return r
}
func hasIntersection(a0, a1, b0, b1 int64) bool {
if a0 < b0 {
return b0 < a1
}
if b0 < a0 {
return a0 < b1
}
return true
}
func isNeibour(a, b room) bool {
if a.top == b.bottom() || a.bottom() == b.top {
return hasIntersection(a.left, a.right(), b.left, b.right())
} else if a.left == b.right() || a.right() == b.left {
return hasIntersection(a.top, a.bottom(), b.top, b.bottom())
}
return false
}
func solve(src string) string {
split := strings.Split(src, "/")
ops := getOps(split[0])
myroom, _ := strconv.Atoi(split[1])
base := int64(1)
for _, op := range ops {
base *= int64(op.count)
}
rooms := build(base, ops)
ans := []string{}
for n, ro := range rooms {
if isNeibour(rooms[myroom-1], ro) {
ans = append(ans, fmt.Sprint(n+1))
}
}
return strings.Join(ans, ",")
}
e28_test.go
package e28
import "testing"
func Test(t *testing.T) {
var tests = []struct {
name string
input string
want string
}{
{"0", "N7N4E5/8", "1,7,12,13,14"},
{"1", "E1/1", "2"},
{"2", "N6/5", "1,4,6"},
{"3", "W5/3", "1,2,4"},
{"75", "N9S9S3S6N6S7N8W4E9W7E3N5W8S9E9E9W6N3N9W8/119", "73,74,78,113,120,122,123,124,131,132,133,134"},
}
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 版 https://qiita.com/Nabetani/items/bb4b06467dbe1cc6c6dd を移植した。
ruby だと
ruby
t = f.map(&:top).min
で済むところを
go
func topOf(rooms []room) int64 {
r := rooms[0].top
for _, ro := range rooms {
c := ro.top
if c < r {
r = c
}
}
return r
}
と書かなければならないとことかがつらい。
あと。
スライスにスライスを追加するイディオムが気持ち悪い気がする。
こんな
go
r = append(r, newrooms(r, op)...)
感じ。
あと関係ないけど。
なんで スペースじゃなくて TAB なんだろう。
スペースのほうがいいと思うんだけどなぁ。