与えられた迷路の最短経路を求める（Go言語）

以前 Ruby で解いたのの Go言語版です。Go言語のお勉強に移植してみました。

まずは実行結果。

$ go build solve_maze.go
$ time ./solve_maze
**************************
*S* *$$$$                *
*$* *$ *$ *************  *
*$*$$$* $  ************  *
*$$$ *  $$$$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$  *$$$$$$$$$$$$$$G  *
*  *$$$$$ *********** *  *
*    *        ******* *  *
*       *                *
**************************

real	0m0.002s
user	0m0.000s
sys	0m0.000s

この程度ならじつに一瞬で解けますね。

もとの Ruby 版とちがうのは、まず迷路ファイルの読み込みが Ruby ほど楽でないこと。それから最短距離を求めるのに幅優先探索を使うので、キューを特に実装しなくてはいけません（しかしこれはここで解決）。あとはオブジェクト指向プログラミングができないので、そこらをどうするかですね。文字列処理は多少面倒でしたが、思ったほど厄介ではありませんでした。

やはりわかりにくかったのは構造体のポインタですね。でもこれは Go で必須なので、慣れないといけない。

コード。
solve_maze.go

package main
import ("fmt"; "os"; "bufio"; "strings")

var field []string

type Step struct {
    x, y int
    parent *Step
}

func err_exit(e error) {
    fmt.Println(e.Error())
    os.Exit(1)
}

func read_maze() {
    f, err := os.Open("maze.txt")
    if err != nil {err_exit(err)}
    
    defer f.Close()
    
    scanner := bufio.NewScanner(f)
    for scanner.Scan() {
        field = append(field, scanner.Text())
    }
    if err := scanner.Err(); err != nil {err_exit(err)}
}

func next_step(st *Step, i int) *Step {
    x, y := st.x, st.y
    switch i {
    case 0: y--
    case 1: y++
    case 2: x--
    case 3: x++
    }
    return &Step{x, y, st}
}

func get(st *Step) string {
    return field[st.y][st.x : st.x + 1]
}

func set(st *Step, char string) {
    s := field[st.y]
    field[st.y] = s[:st.x] + char + s[st.x + 1:]
}

func finish(st *Step) {
    for i, s := range field {
        field[i] = strings.Replace(s, "@", " ", -1)
    }
    for st.parent != nil {
        set(st, "$")
        st = st.parent
    }
    for _, s := range field {
        fmt.Println(s)
    }
    os.Exit(0)
}

func main() {
    read_maze()
    
    queue := []*Step{&Step{x: 1, y: 1}}
    for {
        step := queue[0]
        queue = queue[1:]
        
        for i := 0; i < 4; i++ {
            next := next_step(step, i)
            switch get(next) {
            case "G":
                finish(step)
            case " ":
                set(next, "@")
                queue = append(queue, next)
            }
        }
    }
}

maze.txt

**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************

　
やはり Go言語はコードが読みやすいですよね。

この本を買ってお勉強しています。ひと通り読みましたが、他言語の経験のある人ならとてもわかりやすいのではないでしょうか。いい本だと思います。