オフラインリアルタイムどう書く E18 の実装例( Go )

オフラインリアルタイムどう書く E18 の実装例( Go )

問題 : http://nabetani.sakura.ne.jp/hena/orde18twintri/
実装リンク集 : https://qiita.com/Nabetani/items/891d07f4d645ec00ce9a

三角形をすべて含む矩形の面積を S として、
O(S)ぐらいの遅い実装。

```go:実装
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)
}
```

```go:テスト
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 の手習いとしては、構造体とメンバ関数（？）を、問題解決のためとしては初めて書いた。