gumi Inc. が Developers Summit 2018 の会場で配布しているクイズを掲載しています。
あなたはプログラマーとして、とあるゲーム開発プロジェクトに配属された。 プロジェクトに配属され、はじめに与えられた業務は、次のような ASCII アートで記述された迷路を入力として受け取り、点数を出力するコマンドを作成することだった。 この業務には前任者がいたようだが、現在は連絡がとれない。幸いなことにコードは残されているようだ。
maze.txt:
WWWWWWWWWW
WSWW 1 W
W WWW W
W 1 W
W 1WWWW W
W W 1 W
W 1 W W
W WWW1WWW
W W 1 1GW
WWWWWWWWWW
| 記号 | 意味 |
|---|---|
| S | スタート地点 |
| G | ゴール地点 |
| 空白スペース | 通路 |
| W | 壁 |
| 1 | 通過すると得点を得る通路 |
- S から開始する
- G を目指す
- 一度に上下左右いずれかに一マスだけ移動できる
- 一度通過した通路は再び通れない
- W は通過できない
- 1 を通過で一点加算
gumimaze.exs:
defmodule Gumimaze do
def read() do
lines = "maze.txt" |> File.read!() |> String.trim() |> String.split("\n")
for {line, y} <- Enum.with_index(lines), {c, x} <- Enum.with_index(String.to_charlist(line)), into: %{} do
{{x, y}, c}
end
end
def solve(maze) do
{x, y} = elem(Enum.find(maze, fn {_, v} -> v == ?S end), 0)
try do
walk(maze, x, y, %{}, 0)
catch
pt -> pt
end
end
defp walk(maze, x, y, walked, pt) do
walked = Map.put(walked, {x, y}, true)
for {x2, y2} <- [{x + 1, y}, {x, y + 1}, {x - 1, y}, {x, y - 1}] do
case {walked[{x2, y2}], maze[{x2, y2}]} do
{true, _} -> :walked
{_, ?W} -> :wall
{_, ?\s} -> walk(maze, x2, y2, walked, pt)
{_, ?1} -> walk(maze, x2, y2, walked, pt + 1)
{_, ?G} -> throw(pt)
end
end
end
end
Gumimaze.read() |> Gumimaze.solve() |> IO.puts()gumimaze.go:
package main
import (
"fmt"
"io/ioutil"
"strings"
)
type Location struct {
x, y int
}
func read() (map[Location]rune, Location) {
content, err := ioutil.ReadFile("maze.txt")
if err != nil {
panic(err)
}
lines := strings.Split(strings.TrimRight(string(content), "\n"), "\n")
maze := make(map[Location]rune)
start := Location{}
for y, line := range lines {
for x, c := range line {
location := Location{x: x, y: y}
maze[location] = c
if c == 'S' {
start.x = x
start.y = y
}
}
}
return maze, start
}
func solve(maze map[Location]rune, start Location) int {
walked := make(map[Location]bool)
point, _ := walk(maze, start, walked, 0)
return point
}
func walk(maze map[Location]rune, current Location, walked map[Location]bool, point int) (int, bool) {
walked[current] = true
dirs := []Location{
Location{x: current.x + 1, y: current.y},
Location{x: current.x, y: current.y + 1},
Location{x: current.x - 1, y: current.y},
Location{x: current.x, y: current.y - 1},
}
for _, loc := range dirs {
if walked[loc] {
continue
}
switch maze[loc] {
case 'W':
continue
case ' ':
p, ok := walk(maze, loc, walked, point)
if ok {
return p, ok
}
case '1':
p, ok := walk(maze, loc, walked, point+1)
if ok {
return p, ok
}
case 'G':
walked[current] = false
return point, true
}
}
walked[current] = false
return 0, false
}
func main() {
fmt.Println(solve(read()))
}あなたは連絡の取れない前任者から業務を引き継ぐため、前任者のコードを読み解く必要がある。 コマンド実行時に何が出力されるか予測せよ。 Elixir か Go いずれか一つでよい。
あなたはコードを読み解き、コマンドの動作確認を終えたが、本件の担当プランナーからコマンドの仕様変更を依頼された。 ルールに従ってゴールした際、最大の点数を獲得するよう前任者のコードを修正せよ。 Elixir か Go いずれか一つでよい。
あなたは本件の担当プランナーから依頼された仕様変更を無事に完遂し空き時間ができた。
暇つぶしに迷路探索を並列化せよ。
Elixir か Go いずれか一つでよい。
Elixir であれば軽量プロセスを使用し、Go であれば goroutine を使用すること。
Mission2 と Mission3 の回答は、次の手順で行ってください。
- 前述のコードを Gist や Wandbox などに記録する
- 前述の URL を本記事のコメント欄か、ハッシュタグ #devsumi_gumimaze を付与し Twitter へ投稿する
Developers Summit 2018 終了後、回答例を本記事に掲載予定です。
- テクニカルコンサルタント 募集要項 主に Elixir を使用
- インフラエンジニア 募集要項 主に Go を使用
全ルートを探索し、最大の点数を獲得する。
defmodule Gumimaze do
def read() do
lines = "maze.txt" |> File.read!() |> String.trim() |> String.split("\n")
for {line, y} <- Enum.with_index(lines), {c, x} <- Enum.with_index(String.to_charlist(line)), into: %{} do
{{x, y}, c}
end
end
def solve(maze) do
{x, y} = elem(Enum.find(maze, fn {_, v} -> v == ?S end), 0)
walk(maze, x, y, %{}, 0)
end
defp walk(maze, x, y, walked, pt) do
walked = Map.put(walked, {x, y}, true)
pts = for {x2, y2} <- [{x + 1, y}, {x, y + 1}, {x - 1, y}, {x, y - 1}] do
case {walked[{x2, y2}], maze[{x2, y2}]} do
{true, _} -> 0
{_, ?W} -> 0
{_, ?\s} -> walk(maze, x2, y2, walked, pt)
{_, ?1} -> walk(maze, x2, y2, walked, pt + 1)
{_, ?G} -> pt
end
end
Enum.max(pts)
end
end
Gumimaze.read() |> Gumimaze.solve() |> IO.puts()package main
import (
"fmt"
"io/ioutil"
"strings"
)
type Location struct {
x, y int
}
func read() (map[Location]rune, Location) {
content, err := ioutil.ReadFile("maze.txt")
if err != nil {
panic(err)
}
lines := strings.Split(strings.TrimRight(string(content), "\n"), "\n")
maze := make(map[Location]rune)
start := Location{}
for y, line := range lines {
for x, c := range line {
location := Location{x: x, y: y}
maze[location] = c
if c == 'S' {
start.x = x
start.y = y
}
}
}
return maze, start
}
func solve(maze map[Location]rune, start Location) int {
walked := make(map[Location]bool)
point := walk(maze, start, walked, 0)
return point
}
func walk(maze map[Location]rune, current Location, walked map[Location]bool, point int) int {
walked[current] = true
dirs := []Location{
Location{x: current.x + 1, y: current.y},
Location{x: current.x, y: current.y + 1},
Location{x: current.x - 1, y: current.y},
Location{x: current.x, y: current.y - 1},
}
pts := make([]int, len(dirs))
for i, loc := range dirs {
if walked[loc] {
pts[i] = 0
continue
}
switch maze[loc] {
case 'W':
pts[i] = 0
case ' ':
pts[i] = walk(maze, loc, walked, point)
case '1':
pts[i] = walk(maze, loc, walked, point+1)
case 'G':
pts[i] = point
}
}
maxp := 0
for _, pt := range pts {
if maxp < pt {
maxp = pt
}
}
walked[current] = false
return maxp
}
func main() {
fmt.Println(solve(read()))
}探索経路ごとに Process を Spawn する.
defmodule Gumimaze do
defmodule WalkersState do
defstruct count: 0, point: 0
end
def read() do
lines = "maze.txt" |> File.read!() |> String.trim() |> String.split("\n")
for {line, y} <- Enum.with_index(lines), {c, x} <- Enum.with_index(String.to_charlist(line)), into: %{} do
{{x, y}, c}
end
end
def solve(maze) do
{x, y} = elem(Enum.find(maze, fn {_, v} -> v == ?S end), 0)
spwan_walker(self(), maze, x, y, %{}, 0)
wait_for_finishing_walker(%WalkersState{})
end
defp spwan_walker(receiver, maze, x, y, walked, pt) do
send receiver, :start
spawn_link(fn -> walk(receiver, maze, x, y, walked, pt) end)
end
defp wait_for_finishing_walker(walkers_state) do
receive do
:start ->
wait_for_finishing_walker(%{walkers_state | count: walkers_state.count + 1})
{:finish, point} ->
walkers_state = %{walkers_state | count: walkers_state.count - 1, point: max(walkers_state.point, point)}
case walkers_state.count do
0 -> walkers_state.point
_count -> wait_for_finishing_walker(walkers_state)
end
end
end
defp walk(receiver, maze, x, y, walked, pt) do
walked = Map.put(walked, {x, y}, true)
point = for {x2, y2} <- [{x + 1, y}, {x, y + 1}, {x - 1, y}, {x, y - 1}] do
case {walked[{x2, y2}], maze[{x2, y2}]} do
{true, _} -> 0
{_, ?W} -> 0
{_, ?\s} -> spwan_walker(receiver, maze, x2, y2, walked, pt); 0
{_, ?1} -> spwan_walker(receiver, maze, x2, y2, walked, pt + 1); 0
{_, ?G} -> pt
end
end
send receiver, {:finish, Enum.max(point)}
end
end
Gumimaze.read() |> Gumimaze.solve() |> IO.puts()