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


問題の名前 : きれいな四角
問題 : http://nabetani.sakura.ne.jp/hena/orde32rects/
実装リンク集 : https://qiita.com/Nabetani/items/bd16f3fa1d9e4d0d60ae

で。

会場でお見せした go の実装。

# 実装

```go:実装
package e32

import (
	"errors"
	"fmt"
	"log"
	"sort"
	"strconv"
	"strings"
)

const n = 0x1000
const wh = 36

type rectType struct {
	x, y, r, b int
}

func (r *rectType) size() int {
	return (r.r - r.x) * (r.b - r.y)
}

func mustAtoi(s string) int {
	i, err := strconv.ParseInt(s, 36, 32)
	if err != nil {
		log.Fatalln(err)
	}
	return int(i)
}

func createRect(s string) rectType {
	return rectType{
		x: mustAtoi(s[0:1]),
		y: mustAtoi(s[1:2]),
		r: mustAtoi(s[2:3]),
		b: mustAtoi(s[3:4]),
	}
}

func makeField(rects []rectType) map[int]int {
	f := map[int]int{}
	for ix, r := range rects {
		for y := r.y; y < r.b; y++ {
			for x := r.x; x < r.r; x++ {
				f[y*n+x] += (1 << uint(ix))
			}
		}
	}
	return f
}

func findRight(field map[int]int, x0, y0 int) (int, error) {
	val0 := field[x0+y0*n]
	for x := x0; x < wh+1; x++ {
		if val0 != field[x+y0*n] {
			return x, nil
		}
	}
	return 0, errors.New("no right end found")
}

func findBottom(field map[int]int, x0, y0 int) (int, error) {
	val0 := field[x0+y0*n]
	for y := y0; y < wh+1; y++ {
		if val0 != field[x0+y*n] {
			return y, nil
		}
	}
	return 0, errors.New("no bottom end found")
}

func hborder(field map[int]int, x0, x1, y0, y1 int) bool {
	val := field[y0*n+x0]
	for x := x0; x < x1; x++ {
		if field[y0*n+x] != val || field[y1*n+x] == val {
			return false
		}
	}
	return true
}

func vborder(field map[int]int, y0, y1, x0, x1 int) bool {
	val := field[y0*n+x0]
	for y := y0; y < y1; y++ {
		if field[y*n+x0] != val || field[y*n+x1] == val {
			return false
		}
	}
	return true
}

func samecol(field map[int]int, x0, y0, r, b int) bool {
	col := field[y0*n+x0]
	for y := y0; y < b; y++ {
		for x := x0; x < r; x++ {
			if col != field[y*n+x] {
				return false
			}
		}
	}
	return true
}

func isCleanRect(field map[int]int, x, y, r, b int) bool {
	return hborder(field, x, r, y, y-1) &&
		hborder(field, x, r, b-1, b) &&
		vborder(field, y, b, x, x-1) &&
		vborder(field, y, b, r-1, r) &&
		samecol(field, x, y, r, b)
}

func getRect(field map[int]int, x, y int) *rectType {
	r, err := findRight(field, x, y)
	if err != nil {
		return nil
	}
	b, err := findBottom(field, x, y)
	if err != nil {
		return nil
	}
	if isCleanRect(field, x, y, r, b) {
		return &rectType{x, y, r, b}
	}
	return nil
}

func solveImpl(rects []rectType) []rectType {
	fields := makeField(rects)
	res := []rectType{}
	for y := 0; y < wh; y++ {
		for x := 0; x < wh; x++ {
			rect := getRect(fields, x, y)
			if rect != nil {
				res = append(res, *rect)
			}
		}
	}
	return res
}

func solve(src string) string {
	srects := strings.Split(src, "/")
	rects := []rectType{}
	for _, s := range srects {
		rects = append(rects, createRect(s))
	}
	sizes := []int{}
	for _, r := range solveImpl(rects) {
		sizes = append(sizes, r.size())
	}
	sort.Ints(sizes)
	ssizes := []string{}
	for _, size := range sizes {
		ssizes = append(ssizes, fmt.Sprintf("%d", size))
	}
	return strings.Join(ssizes, ",")
}
```

```go:テストランナー
package e32

// `go test -args data.json` で実行する

import (
	"encoding/json"
	"io/ioutil"
	"log"
	"os"
	"testing"
)

func TestAll(t *testing.T) {
	var data map[string]interface{}
	jsonBytes, err := ioutil.ReadFile(os.Args[1])
	if err != nil {
		log.Fatal(err)
	}
	json.Unmarshal(jsonBytes, &data)
	failCount := 0
	for _, item := range data["test_data"].([]interface{}) {
		i := item.(map[string]interface{})
		e := i["expected"].(string)
		s := i["src"].(string)
		a := solve(s)
		ok := e == a
		if !ok {
			t.Errorf("solve(%s) is %s, want %s", s, a, e)
		}
	}
	log.Println("Fail Count:", failCount)
}
```

冗長な感じなのはそういう言語なので仕方ない。

# 実装戦略

戦略としては

1. 地図を作る
2. 36×36回、左上隅の候補を決める
3. そこを左上隅としたきれいな矩形があるかどうか調べる
4. 結果をまとめる

という感じ。

(1)の地図は、各マスがn番目の矩形の内側なら $2^n$ を加えるという方式。このソースなら矩形31個まで対応。
64個を超えると面倒なことになるけどそうなったら `math/big` を使うんだと思う。
以降、マス目に入っている数字のことを「色」と呼ぶ。

(2)は単なる2重ループなので説明略。 

問題は(3)。(3) は `getRect` という関数になっている。この関数は

a. 右端を決める
b. 下端を決める
c. その矩形がきれいな矩形かどうかを調べる

とう三段階になっている。

(a)は、左上隅から、左上隅と違う色が出てくるまで右方向に調べる。
(b)は、同じように下向きに調べる。
(c)は、`isCleanRect` という関数になっている。この関数は

甲.外周があるかどうか調べる
乙.中がきれいになっているかどうか調べる

の二段階になっている。

(甲)は、矩形のぎりぎり外側が、全部矩形の内側と違う色になっているかどうかを調べる
(乙)は、矩形の内側が全部同じ色になっているかどうか調べる

という感じ。

最後に面積の列に変換して、整列して、コンマ区切りでつなげれば完成。

見返してみると無駄な計算をしている箇所があるけど、まあいいか。

地図を作っているので、座標の値が大きかったり浮動小数点だったりすると負ける。
計算量としては、地図の一辺の長さを L、矩形の数を R としたら $O\(L^2 \times R\)$ かな。


# 解説解題っぽいなにか

出題する前から難しいよねこれ、と思っていた。
でも、私が出したい問題の条件

* 計算機科学力は問われない
* 数学力も問われない
* シンプル
* 明快
* 紙とペンで解くのは簡単
* 実装方針が複数ある

を全て満たしていたので出してみた。

さらに

* コーナーケースがたくさんある

という楽しいおまけも付いていた。

コーナーケースとしては
[#11]( http://nabetani.sakura.ne.jp/hena/orde32rects/figs.html#11 )、[#18]( http://nabetani.sakura.ne.jp/hena/orde32rects/figs.html#18 )、[#24]( http://nabetani.sakura.ne.jp/hena/orde32rects/figs.html#24 ) 辺りが面白いと思っていたんだけど、わりと [#6]( http://nabetani.sakura.ne.jp/hena/orde32rects/figs.html#6 ) にやられている人が多かったと思う。

早めに問題が出来上がったので、図を頑張ってみた。面塗りにグラデーションを入れたり、マス目の大きさによって数字の大きさを変えたり。

# というわけで

というわけで、私の気が変わらなければこれにてオフラインリアルタイムどう書くは最終回。
以降は年に3〜4回のペースで不定期に[yokohama.rb]( https://yokohamarb.doorkeeper.jp/ )で簡単な問題を出題しようと思っている。