ラガルトさんの試験問題をGolangで解いてみた

via: 人材獲得作戦・４ 試験問題ほか: 人生を書き換える者すらいた。
せっかくなので、GoogleのGolangを使って問題を解いてみました*1。言語自体の勉強しながらだったので、５時間くらいかかってしまいましたが、以下の感じでできました。
せっかくなので、flagやvectorなどのPackageを使ってみました。

package main

import (
	"bytes"
	"container/vector"
	"flag"
	"fmt"
	"io/ioutil"
	"strings"
)


var input_file string
var output_file string

func init() {
	flag.StringVar(&input_file, "input", "input.txt", "filename to input maze data.")
	flag.StringVar(&output_file, "output", "output.txt", "filename to output result data.")
}


func read() ([]byte, bool) {
	bytes, error := ioutil.ReadFile(input_file)
	if error != nil {
		println(error.String())
		return bytes, false
	}
	return bytes, true
}

func write(result []byte) (bool) {
	error := ioutil.WriteFile(output_file, result, 0666)
	if error != nil {
		println(error.String())
		return false
	}
	return true
}


type Maze struct {
	lines [][]byte
	row, col int
	dists []int
	start, goal int
}

func (p *Maze) init_maze(data []byte) {
	p.lines = bytes.Split(data, strings.Bytes("\n"), 0)
	for len(p.lines[len(p.lines) - 1]) == 0 {
		p.lines = p.lines[0:len(p.lines) - 1]
	}
	p.row = len(p.lines)
	p.col = len(p.lines[0])

	p.dists = make([]int, p.row * p.col)
	p.start = -1
	p.goal = -1
	for r := 0; r < p.row; r++ {
		for c := 0; c < p.col; c++ {
			index := r * p.col + c
			switch p.lines[r][c] {
				case '*':
					p.dists[index] = -3
				case 'S':
					p.start = index
					p.dists[index] = 0
				case 'G':
					p.goal = index
					p.dists[index] = -2
				default:
					p.dists[index] = -1
			}
		}
	}
}

func (p *Maze) print_distance() {
	for r := 0; r < p.row; r++ {
		for c := 0; c < p.col; c++ {
			index := r * p.col + c
			fmt.Printf("%2d", p.dists[index])
		}
		println()
	}
}

func (p *Maze) generate_next_indexes(index int, ch chan<- int) {
	calc_index := func(row, col int) (int) {
		return row * p.col + col
	}
	row := index / p.col
	col := index % p.col
	if row > 0 {
		ch <- calc_index(row - 1, col)
	}
	if col > 0 {
		ch <- calc_index(row, col - 1)
	}
	if row < p.row - 1 {
		ch <- calc_index(row + 1, col)
	}
	if col < p.col - 1 {
		ch <- calc_index(row, col + 1)
	}
	close(ch)
}

func (p *Maze) next_list(prev *vector.IntVector) (*vector.IntVector, bool) {
	next := new(vector.IntVector)
	last := false
	for value := range prev.Iter() {
		index := int(value)
		ch := make(chan int)
		go p.generate_next_indexes(index, ch)

		for i := range ch {
			d := p.dists[index] + 1
			switch p.dists[i] {
				case -1:
					p.dists[i] = d
					next.Push(i)
				case -2:
					p.dists[i] = d
					last = true
			}
		}
	}
	return next, last
}

func (p *Maze) solve_distance() {
	list := new(vector.IntVector)
	list.Push(p.start)

	for true {
		next, last := p.next_list(list)
		if last {
			break
		}
		list = next
	}
}


func (p *Maze) draw_prev(index int) (int, bool) {
	d := p.dists[index]

	ch := make(chan int)
	go p.generate_next_indexes(index, ch)
	for i := range ch {
		switch p.dists[i] {
			case 0:
				return -1, true
			case d - 1:
				r := i / p.col
				c := i % p.col
				p.lines[r][c] = '$'
				return i, false
		}
	}
	return -1, true
}

func (p *Maze) draw_result() {
	index := p.goal
	for true {
		next, last := p.draw_prev(index)
		if last {
			break
		}
		index = next
	}
}

func solve(data []byte) ([]byte) {
	maze := new(Maze)
	maze.init_maze(data)

	fmt.Printf("row=%d,col=%d\n", maze.row, maze.col)

	maze.solve_distance()
	//maze.print_distance()
	maze.draw_result()

	return bytes.Join(maze.lines, strings.Bytes("\n"))
}

func main() {
	flag.Parse()

	bytes, read_ok := read()
	if !read_ok {
		return
	}
	result := solve(bytes)
	write_ok := write(result)
	if !write_ok {
		return
	}
	println("completed.")
	return
}

以下を Makefileに保存し、gomakeでビルドできます。

include $(GOROOT)/src/Make.$(GOARCH)

TARG=maze
GOFILES=\
	main.go

include $(GOROOT)/src/Make.cmd

*1:Windowsなので、Portable Ubuntuで動かしました