オフラインリアルタイムどう書く E18 の実装例( Go )
問題 : http://nabetani.sakura.ne.jp/hena/orde18twintri/
実装リンク集 : https://qiita.com/Nabetani/items/891d07f4d645ec00ce9a
三角形をすべて含む矩形の面積を S として、
O(S)ぐらいの遅い実装。
実装
package e18
import (
"fmt"
"strconv"
"strings"
)
func iabs(x int) int {
if x < 0 {
return -x
}
return x
}
type triangle struct {
x, y int
dir byte
h int
}
func (t triangle) contains(x, y int) bool {
dx := x - t.x
dy := y - t.y
switch t.dir {
case 'L':
return 0 <= dx && iabs(dy) <= dx && dx < t.h
case 'R':
return dx <= 0 && iabs(dy) <= -dx && -dx < t.h
case 'T':
return 0 <= dy && iabs(dx) <= dy && dy < t.h
case 'B':
return dy <= 0 && iabs(dx) <= -dy && -dy < t.h
default:
panic(struct{}{})
}
}
func (t triangle) minX() int {
switch t.dir {
case 'R':
return t.x - t.h + 1
case 'L':
return t.x
case 'T', 'B':
return t.x - t.h + 1
default:
panic(struct{}{})
}
}
func (t triangle) maxX() int {
switch t.dir {
case 'R':
return t.x
case 'L':
return t.x + t.h - 1
case 'T', 'B':
return t.x + t.h - 1
default:
panic(struct{}{})
}
}
func (t triangle) minY() int {
switch t.dir {
case 'R', 'L':
return t.y - t.h + 1
case 'T':
return t.y
case 'B':
return t.y - t.h + 1
default:
panic(struct{}{})
}
}
func (t triangle) maxY() int {
switch t.dir {
case 'R', 'L':
return t.x + t.h - 1
case 'T':
return t.y + t.h - 1
case 'B':
return t.y
default:
panic(struct{}{})
}
}
func intMin(a, b int) int {
if a < b {
return a
}
return b
}
func intMax(a, b int) int {
if a < b {
return b
}
return a
}
func parseTriangle(s string) triangle {
var t triangle
fmt.Sscanf(s, "%d,%d%c%d", &t.x, &t.y, &t.dir, &t.h)
return t
}
func impl(a, b triangle) int {
minx := intMin(a.minX(), b.minX())
miny := intMin(a.minY(), b.minY())
maxx := intMax(a.maxX(), b.maxX())
maxy := intMax(a.maxY(), b.maxY())
count := 0
for y := miny; y <= maxy; y++ {
for x := minx; x <= maxx; x++ {
if a.contains(x, y) && b.contains(x, y) {
count++
}
}
}
return count
}
func solve(src string) string {
split := strings.Split(src, "/")
var triangles [2]triangle
for i := 0; i < 2; i++ {
triangles[i] = parseTriangle(split[i])
}
count := impl(triangles[0], triangles[1])
return strconv.Itoa(count)
}
テスト
package e18
import (
"testing"
)
func Test(t *testing.T) {
var tests = []struct {
name string
input string
want string
}{
{"0", "7,0R6/3,1B5", "15"},
{"1", "1,6L4/4,9R9", "4"},
{"2", "0,2R4/1,3B4", "3"},
{"3", "1,2L4/1,2L5", "16"},
// 中略
{"46", "5621,8460T7612/2715,5697L8851", "861192"},
}
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)
}
}
}
130行以上書いてしまった。もう少しサボっても良かったか。
遅いアルゴリズムだけど、手元で実行すると 4秒弱。
たぶん数倍無駄があるruby版( https://qiita.com/Nabetani/items/c6dd56eeacebada2bad8 )が 1分弱なので、速いことは速い。
家で書いていると、のんびりしてしまうのが良くないね。
もっと追い込まれて書いたほうがよい気がする。
今回の収穫は Sscanf 。
意地悪されない限り、Sscanf を使えば多少複雑でもパースはOKになると思われる。
panic の引数に何を入れていいのかからなかったので、struct{}{} を入れてみたんだけど、普通どうするんだろ。
エラーメッセージの文字列入れるのかなぁ。
Go の手習いとしては、構造体とメンバ関数（？）を、問題解決のためとしては初めて書いた。