maze

小学３年生の日記を1000文字で書いて下さい。
題名は、ひまわり畑の迷路で苦労した事、です。

ひまわり畑の迷路で苦労したこと

こんにちは、今日はひまわり畑の迷路に行ってきました。とっても楽しいけれど、ちょっと大変なこともあったんだよ。

朝、お父さんとお母さんと一緒に車に乗って、ひまわり畑に着いたよ。畑に入ると、すごくたくさんのひまわりがたくさん咲いていて、きれいな黄色い花が風に揺れていました。それから、迷路に挑戦することになりました。

最初は楽勝かなと思ったんだけど、迷路の中に入ると、どの道が正しい道か分からなくなっちゃった。道には高いひまわりがたくさんあって、どこに進んでいいのか迷子になってしまいました。

お父さんが地図を持っていたけれど、それもどこに行っても全部同じように見えるひまわりばかりで、どこにいるのか分からなくなっちゃったんだよ。お母さんは「こっちがいいかもしれない」と言って進んでみたり、私たちも何回も進んだり戻ったりして、とっても混乱しました。

そして、何回も行き止まりにぶつかったり、同じ場所を何度も通ったりして、正しい出口を見つけるのが難しかったです。でも、諦めずにみんなで協力して進んでいくことで、少しずつ進むことができました。

やっとのことで出口にたどり着いたときは、みんなで喜びました。迷路の中での苦労が報われた気持ちがしたよ。

迷路を抜けて、ひまわり畑全体を見渡すと、頑張って辿り着いた景色がとても素晴らしく感じられました。その後、たくさんのひまわりを見て写真を撮ったり、お土産のひまわりの種をもらったりしました。

今日の経験で、大変な時でもみんなで助け合って頑張ることの大切さを学びま した。迷路での苦労も楽しい思い出になりました。次に行くときは、もっとス ムーズに迷路をクリアしたいなと思います。楽しい一日でした！

---

オイラーなら、趣味と実益で、とうもろし畑の迷路を選ぶなあ(そんなの有る んか？)。分岐する時に、とうもろこしを もいで目印にする。行き止まりなら、 それを回収して、別な経路を試す。脱出出来た時は、お土産も手元に用意でき ている。

あるいは、戸隠忍法、魔界脱出の術を使うんだ。何も考えずに、左手を壁にあ てて、ひたすら歩く(右手には手裏剣とか刀ってのは忍の世界では常識)。これで脱出できる。入口と出口の間が通路でつながって いるって事は、上から見たら、2つに分離できるって事だ。ただ、通路がギザ ギザになってるだけ。ならば、その片方の切り口にそって進むだけで、抜けら れる。

ふと思い出した。人間ってのは、パイプだぞ。入口は、口ね、出口は肛門。腹 の中はクネクネだけど。パイプに手とか足とか頭等の装飾品を取り付ければ、 人間になる。ああ、人間に限らず生物一般に通用する。

ならばと、数学の先生は考えた。物体の相似って、どういう事と？ 取っ手の付 いたコーヒーカップは、浮き輪や真ん中に穴が空いたドーナッツと相似だと。 ドーナッツの輪が、取っ手になる。その一部をビローンと延して、円筒にし、 中央に窪みをつければ、コーヒーカップの出来上がり。

ああ、話がそれたわい。

Pythonで学ぶアルゴリズム< 迷路探索 >

経路の探索

すごいH本にも例が出ていたな。後で再読しておこう。ヒースロー空港なんちゃ らって奴だったと思う。それから、ocaml本には、地下鉄の経路をダイクスト ラのアルゴリズムで解くのが出てた。すっかりご無沙汰だけど。

あれ？ 経路探索と迷路探索って微妙に違うような。。。一緒一緒気にするな。 しっかり勉強しとくと、カーナビ屋になれるぞ。首都高迷路をスイスイとな。

暑い所は苦手なので、涼しい所で、迷路探索。そう、ChatGPTのGPUを熱くして やるのさ。

10x10の迷路を検索するプログラムをhaskellで出力して下さい。
最初に迷路を表示
次に辿った経路を表示
検索は、深さ優先にしてください

このプログラムは、スタート地点を(1, 1)、ゴール地点を(10, 10)とし、壁を '#'、通路を '.' で表現しています。

深さ優先はHungしたので、幅優先のコードを提示してもらった。

import Data.Array
import Data.List (unfoldr)
import Data.Maybe (isJust, fromJust)

type Point = (Int, Int)
type Maze = Array Point Char

mazeWidth :: Int
mazeWidth = 10

mazeHeight :: Int
mazeHeight = 10

start :: Point
start = (1, 1)

goal :: Point
goal = (mazeWidth, mazeHeight)

initialMaze :: Maze
initialMaze = listArray ((1, 1), (mazeWidth, mazeHeight)) $
              concat [ replicate mazeWidth '.' | _ <- [1..mazeHeight] ]

printMaze :: Maze -> IO ()
printMaze maze = mapM_ putStrLn [ [ maze ! (x, y) | x <- [1..mazeWidth] ] | y <- [1..mazeHeight] ]

bfs :: Maze -> Point -> Point -> Maybe [Point]
bfs maze start goal = bfs' [(start, [])] []
  where
    bfs' [] _ = Nothing
    bfs' ((pos, path) : queue) visited
      | pos == goal = Just (reverse (pos : path))
      | pos `elem` visited = bfs' queue visited
      | otherwise =
          let nextPositions = [(x, y) | x <- [fst pos - 1 .. fst pos + 1],
                                         y <- [snd pos - 1 .. snd pos + 1],
                                         (abs (fst pos - x) + abs (snd pos - y)) == 1]
              validNext = filter (\p -> inRange (bounds maze) p && maze ! p /= '#' && p `notElem` visited) nextPositions
              newQueue = queue ++ [(nextPos, pos : path) | nextPos <- validNext]
          in bfs' newQueue (pos : visited)

main :: IO ()
main = case bfs initialMaze start goal of
    Just path -> do
        putStrLn "迷路:"
        printMaze initialMaze
        putStrLn "経路:"
        printMaze (initialMaze // [(p, '*') | p <- path])
    Nothing -> putStrLn "経路が見つかりませんでした。"

実行例

ghci> :main
迷路:
..........
  :
..........
経路:
*.........
  :
*.........
*.........
**********

苦労も何も無い迷路。迷路を作るのをサボっている。

昔、女房が旅行の途中で、ぶどうの観光農園に入ったそうな。手に届く所には 房が全く無かった、騙された、詐欺にあったと憤慨したとな。 今は、そんな感じだな。全く向日葵が植わってない畑。

ならば、植栽してやる。その前に、植栽方法を勉強。趣味の園芸の時間です。 iniitialMazeから大切な部分を抽出してきて実験。農業試験場であります。

ghci> a = listArray((1,1), (2,2)) [1..4]
ghci> a
array ((1,1),(2,2)) [((1,1),1),((1,2),2),((2,1),3),((2,2),4)]
ghci> a ! (2,1)
3

配列へのアクセスは頻繁にあるだろうから、演算子は、ビックリマークがひと つです。

Arrayの使い方 文献を調べてみた所、Data.Arrayはhugs98時代からの奴だそうです。構造が良 く分かりますなあ。これは配列なんだけど更新は苦手です。まあ、紫外線をあ てると、内容が消えるEPROMみたいな機構と思っていれば、間違いない。念の 為、更新には、// 演算子が用意されている。

実際に植栽。配置が転地されちゃうので、事前に配置図を作って、間違えない ようにしよう。

initialMaze :: Maze
initialMaze = listArray ((1, 1), (mazeWidth, mazeHeight)) "....#.....\
\....#.....\
\....#.....\
\....#.....\
\......#...\
\......#...\
\......#...\
\......#...\
\......#...\
\......#..."

実行結果。

経路:
*.........
*.........
*.........
*****.....
####*.....
...**.....
...*######
...*......
...*......
...*******

下記のような無理の無い記述方法も有るのね。

complexMaze :: Maze
complexMaze = listArray ((1, 1), (mazeWidth, mazeHeight)) $
              concat [ "#.#####.#."
                     , "....#.###."
                     , "#.#...#.#."
                     , "#.#####..."
                     , "#.#...####"
                     , "#...#..##."
                     , "########.#"
                     , "#........#"
                     , "########.#"
                     , "#........#"
                     ]

自動生成させたので実行すると、経路が見つかりませんでした となるって告 げると、コードの方を変更し始めて、ど壺に突入。検証した迷路を提示してる 訳じゃないんだ。これが限界なんだね。

ひょっとして、転置問題？ Data.Listに転置があったので、追加してみた。リ ストになってると便利さが倍増するな。

concat $ transpose [ "#.#####.#."
                   , "....#.###."
		   :

けど、やはり駄目だった。

ならば、別プログラムで迷路を作らせればいいんでないかい。

何度かやりとりしたけど、HungUPしちゃう。最後は、こんな泣き言が。学習し なかったってか、そんな事をやってる事例な無かったんだろうね。

申し訳ありませんが、こちらのプラットフォームではコードを実際に実行して修正することが難しいようです。生成アルゴリズムに問題がある可能性があります。

Haskellのプログラムが無限ループに陥る場合、再帰的な関数呼び出しや状態遷移が正しく制御されていないことが原因となることがあります。深さ優先探索の場合、無限ループに陥らないようにするために、訪問済みのセルを適切に管理することが重要です。

もし自動生成の迷路を試すことが必要であれば、より堅牢な迷路生成アルゴリ ズムを考えるか、既存のライブラリを使用することを検討することをお勧めし ます。ご不便をおかけして申し訳ありません。

まあ、コードには、新らしい事が出てるんで、勉強の足しにはなるわな。

import System.Random
import Control.Monad.State
import Data.Array

type Point = (Int, Int)
type Maze = Array Point Char

mazeWidth :: Int
mazeWidth = 10

mazeHeight :: Int
mazeHeight = 10

start :: Point
start = (1, 1)

goal :: Point
goal = (mazeWidth, mazeHeight)

generateMaze :: IO Maze
generateMaze = do
    gen <- newStdGen
    let maze = evalState (generateMaze' start []) gen
    return maze
  where
    generateMaze' :: Point -> [Point] -> State StdGen Maze
    generateMaze' currentPos visited
        | currentPos == goal = do
            modify (\gen -> snd (next gen))
            return $ listArray ((1, 1), (mazeWidth, mazeHeight))
                     [ if p `elem` visited then '.' else '#'
                     | y <- [1..mazeHeight]
                     , x <- [1..mazeWidth]
                     , let p = (x, y)
                     ]
        | not (inRange ((1, 1), (mazeWidth, mazeHeight)) currentPos) = do
            modify (\gen -> snd (next gen))
            generateMaze' start visited
        | otherwise = do
            modify (\gen -> snd (next gen))
            let nextMoves = [ (x, y) | x <- [fst currentPos - 1 .. fst currentPos + 1],
                                       y <- [snd currentPos - 1 .. snd currentPos + 1],
                                       (abs (fst currentPos - x) + abs (snd currentPos - y)) == 1 ]
                unvisitedMoves = filter (`notElem` visited) nextMoves
            case unvisitedMoves of
                [] -> generateMaze' (head visited) (tail visited)
                _ -> do
                    nextMoveIdx <- state $ randomR (0, length unvisitedMoves - 1)
                    let nextMove = unvisitedMoves !! nextMoveIdx
                    generateMaze' nextMove (currentPos : visited)

printMaze :: Maze -> IO ()
printMaze maze = mapM_ putStrLn [ [ maze ! (x, y) | x <- [1..mazeWidth] ] | y <- [1..mazeHeight] ]

main :: IO ()
main = do
    generatedMaze <- generateMaze
    putStrLn "生成された迷路:"
    printMaze generatedMaze