Go
golang
どう書く
yhpg

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

オフラインリアルタイムどう書く 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 の手習いとしては、構造体とメンバ関数(?)を、問題解決のためとしては初めて書いた。