Namaran

Code daily. Without assist.

2026-10-03

Frontier.hs

import Data.List (nub)

maze :: [String]
maze = [ "..#"
       , "#.."
       , "..." ]

open :: (Int, Int) -> Bool
open (r, c) = r >= 0 && r < 3 && c >= 0 && c < 3 && maze !! r !! c == '.'

step :: [(Int, Int)] -> [(Int, Int)]
step ps = nub [ q | (r, c) <- ps
               , q <- [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]
               , open q ]

main :: IO ()
main = print (length (takeWhile (notElem (2, 0)) (iterate step [(0, 0)])))

これは何を出力するでしょうか?

Answer

4 です。

iterate step [(0, 0)] は、[(0, 0)]、それに step を1回適用したもの、2回適用したもの、と続く無限リストです。step は前線のどのマスからも上下左右の通れるマスへ1歩ずつ進めるので、k 番目の要素は、スタートからちょうど k 歩でいられるマスの集まりです。リストは無限でも、takeWhile は条件が初めて偽になった要素で止まり、その先は評価されません。

length が数えるのは、(2, 0) を含まない前線が先頭から何個続くかです。この数は (2, 0) を初めて含む前線の番号と等しく、その番号はゴールにちょうど着ける最小の歩数、すなわち最短距離です。

訪問済みのマスを記録していないので、前線には一度通ったマスへ戻る道も混ざります。それでも答えは変わりません。戻り道は前線に余計なマスを足すだけで、(2, 0) が初めて現れる番号を早めも遅らせもしないからです。訪問済みが無ければ正しく数えられない、と考えるとここで迷います。

迷路では (1, 0) が壁なので、スタートから真下へは進めません。(0, 0)、(0, 1)、(1, 1)、(2, 1)、(2, 0) と回り込む4歩が最短で、ゴールを含まない前線は0番から3番までの4個です。