読者です 読者をやめる 読者になる 読者になる

オフラインリアルタイムどう書く E05 golang で解く

問題はこちら

qiita.com

実装はRuby版を写しただけなので10分くらいだけど、テスト部分で死んで発表時にはちゃんと動いてませんでした。

せっかくなのでgoroutine使ってみたけど書き方がこれでいいのかしら……という不安が。
メモ化で早くなるとは思うんですけどメモ化 + goroutineはなんとなく不幸な未来が待ってそうな気がしてやってません。

共通部分

package yhpg

// Case represents each case.
type Case struct {
    No       int
    Input    string
    Expected string
    Actual   string
}

// Tester shows each case is correct or not.
type Tester interface {
    Test() bool
    SuccessDetail() string
    FailedDetail() string
}

E05

package yhpg

import (
    "fmt"
    "strconv"
    "strings"
)

type E05 struct {
    *Case
    solved bool
}

func (c E05) Test() bool {
    return c.solve()
}

func (c E05) SuccessDetail() string {
    return fmt.Sprintf("No.%2d OK\n", c.No)
}
func (c E05) FailedDetail() string {
    tmpl := "No.%2d NG\ninput   : %q\nexpected: %q\nactual  : %q"
    ret := fmt.Sprintf(tmpl, c.No, c.Input, c.Expected, c.Actual)
    fmt.Println(ret)
    return ret
}

type Plate struct {
    H []string
    M []string
    L []string
}

func NewPlates() []Plate {
    plates := []Plate{
        Plate{H: []string{"H", "M"}, M: []string{"M", "L"}, L: []string{"L"}},
        Plate{H: []string{"H", "L"}, M: []string{"M"}, L: []string{"M", "L"}},
        Plate{H: []string{"H", "L"}, M: []string{"H", "M"}, L: []string{"L"}},
        Plate{H: []string{"H"}, M: []string{"H", "M"}, L: []string{"M", "L"}},
        Plate{H: []string{"H"}, M: []string{"M", "L"}, L: []string{"H", "L"}},
        Plate{H: []string{"H", "M"}, M: []string{"M"}, L: []string{"H", "L"}},
        Plate{H: []string{"H"}, M: []string{}, L: []string{"L"}},
        Plate{H: []string{}, M: []string{"M"}, L: []string{"L"}},
        Plate{H: []string{"H"}, M: []string{"M"}, L: []string{}},
    }

    return plates
}

func (c *E05) solve() bool {
    if c.solved {
        return c.Actual == c.Expected
    }
    c.solved = true

    plates := NewPlates()

    is := strings.Split(c.Input, "")
    ps := []Plate{}
    for i := 0; i < len(is); i++ {
        tmp, _ := strconv.Atoi(is[i])
        ps = append(ps, plates[tmp-1])
    }
    ret := ""
    if dfs(ps, 0, "H") {
        ret += "a"
    }
    if dfs(ps, 0, "M") {
        ret += "b"
    }
    if dfs(ps, 0, "L") {
        ret += "c"
    }
    if ret == "" {
        ret = "-"
    }
    c.Actual = ret
    return c.Actual == c.Expected
}
func (p *Plate) Next(row string) []string {
    switch row {
    case "H":
        return p.H
    case "M":
        return p.M
    case "L":
        return p.L
    }
    return []string{}
}

func dfs(plates []Plate, idx int, row string) bool {
    if idx >= len(plates) {
        return true
    }
    plate := plates[idx]
    n := plate.Next(row)
    for _, r := range n {
        if dfs(plates, idx+1, r) {
            return true
        }
    }
    return false
}

テストコード

package yhpg

import (
    "fmt"
    "testing"
)

func TestE05(t *testing.T) {
    ch := make(chan Tester)
    doneCh := make(chan bool)

    defer func() {
        close(ch)
        close(doneCh)
    }()
    count := 0
    test := func(input, expected string) {
        count++
        r := E05{
            Case: &Case{
                No:       count,
                Input:    input,
                Expected: expected,
            },
        }
        go func(ch chan Tester, t Tester) {
            t.Test()
            ch <- t
        }(ch, r)
    }
    /* ココから */

    /*0*/ test("1728398", "bc")
    /*1*/ test("789", "-")
    /*2*/ test("274", "ac")
    /*3*/ test("185", "abc")
    /*4*/ test("396", "ab")
    /*5*/ test("1278", "abc")
    /*6*/ test("7659832", "a")
    /*7*/ test("178", "bc")
    /*8*/ test("189", "ab")
    /*9*/ test("197", "a")
    /*10*/ test("278", "ac")
    /*11*/ test("289", "bc")
    /*12*/ test("297", "a")
    /*13*/ test("378", "ac")
    /*14*/ test("389", "b")
    /*15*/ test("397", "ab")
    /*16*/ test("478", "c")
    /*17*/ test("489", "bc")
    /*18*/ test("497", "ab")
    /*19*/ test("578", "bc")
    /*20*/ test("589", "b")
    /*21*/ test("597", "ac")
    /*22*/ test("678", "c")
    /*23*/ test("689", "ab")
    /*24*/ test("697", "ac")
    /*25*/ test("899", "b")
    /*26*/ test("7172", "ac")
    /*27*/ test("54787", "bc")
    /*28*/ test("83713", "bc")
    /*29*/ test("149978", "-")
    /*30*/ test("159735", "abc")
    /*31*/ test("1449467", "abc")
    /*32*/ test("9862916", "b")
    /*33*/ test("96112873", "ab")
    /*34*/ test("311536789", "-")
    /*35*/ test("281787212994", "abc")
    /*36*/ test("697535114542", "ac")

    /* ココまで */

    go func(doneCh chan bool) {
        for i := 0; i < count; i++ {
            tester := <-ch
            if tester.Test() {
                fmt.Print(tester.SuccessDetail())
            } else {
                t.Errorf(tester.FailedDetail())
            }
        }
        doneCh <- true
    }(doneCh)
    <-doneCh
}