Namaran

Code daily. Without assist.

2026-10-03

Path.hs

type Pos = (Int, Int)

path :: [(Pos, Pos)] -> Pos -> [Pos]

幅優先探索は、スタート以外の各マスについて、そのマスへ初めて来たときの1つ前のマス(親)を記録します。(マス, 親) の組のリストとゴールを受け取り、スタートからゴールまでのマスを順に並べたリストを返す path を書いてください。スタートは親の記録が無いマスです。ゴールがスタートそのものなら、そのマス1つだけのリストを返します。

入力例 1

path [((0, 1), (0, 0)), ((1, 1), (0, 1)), ((1, 0), (0, 0))] (1, 1)

出力例 1

[(0,0),(0,1),(1,1)]

入力例 2

path [((0, 1), (0, 0)), ((1, 1), (0, 1)), ((1, 0), (0, 0))] (1, 0)

出力例 2

[(0,0),(1,0)]

入力例 3

path [] (2, 2)

出力例 3

[(2,2)]
Reference
type Pos = (Int, Int)

path :: [(Pos, Pos)] -> Pos -> [Pos]
path parents = reverse . go
  where
    go p = p : maybe [] go (lookup p parents)

ゴールから親をたどると、マスはゴール、その親、さらにその親、とスタートへ向かう順に並びます。参考実装の go はこの順にリストを作り、lookup が親を見つけられないマス、つまり親の記録が無いスタートに着いたところで止まります。求めるのはスタートからの経路なので、最後に reverse で向きを逆にします。

maybe [] go (lookup p parents) は、親が見つかれば go でその先をたどり、Nothing なら空リストで終える、という場合分けを1つの式で書いたものです。ゴールがスタートなら lookup は最初から Nothing を返すので、結果はゴール1マスだけのリストになります。

掲載したのは参考実装で、唯一の正解ではありません。case で Just と Nothing を分けて書いても、たどったマスを引数のリストの先頭に積んでいき、reverse を使わずに済ませてもかまいません。