dig maze

[sakae@deb ~]$ dig @8.8.8.8 www.yahoo.co.jp

; <<>> DiG 9.16.42-Debian <<>> @8.8.8.8 www.yahoo.co.jp
   :
;; QUESTION SECTION:
;www.yahoo.co.jp.               IN      A

;; ANSWER SECTION:
www.yahoo.co.jp.        215     IN      CNAME   edge12.g.yimg.jp.
edge12.g.yimg.jp.       40      IN      A       182.22.24.124

;; Query time: 19 msec
;; SERVER: 8.8.8.8#53(8.8.8.8)

Uum .. ロードバランサーで一手に引受してて、ホットスタンバイ構成になっ てるんだろうね。と、素人が想像してますよ。

vbox$ host www.yahoo.co.jp
www.yahoo.co.jp is an alias for edge12.g.yimg.jp.
edge12.g.yimg.jp has address 182.22.24.124
vbox$ nslookup www.yahoo.co.jp
Server:         8.8.8.8
Address:        8.8.8.8#53

Non-authoritative answer:
www.yahoo.co.jp canonical name = edge12.g.yimg.jp.
Name:   edge12.g.yimg.jp
Address: 183.79.249.124

ソースをちら見してたら、アイリアスっぽいコマンドが出てた。懐かしいやっ ちゃ! OpenBSDはソースも簡単に閲覧できるので、三文の得。

話を戻して迷路のdig問題。相変わらずのエラー。

/tmp/digmaze/app/Main.hs:129:15-18: error:
    • Couldn't match expected type: UArray (Int, Int) Int
                  with actual type: STUArray RealWorld (Int, Int) Int
    • In the first argument of ‘printMaze’, namely ‘maze’
      In a stmt of a 'do' block: printMaze maze
      In the expression:
        do initRand
           maze <- stToIO createMaze
           putStrLn "Create MAZE"
           printMaze maze
    |
129 |     printMaze maze
    |               ^^^^

見た事ないな。何度か修正依頼をしてみたけど、解決に至らず。堂々巡りして る。奴に取っても未知の世界なんだろうね。関係すると思われる所を検索して みた。

stToIO

様々な配列その2（MArray編）

Haskellでエラトステネスの篩(STUArray)

第19回　配列でデータ・アクセスの効率を上げる

第20回　更新を高速化するためのSTモナド

難しいのは置いておいて、他にコンパイルエラーが無いか確認する。先へ進め の無線用語 go aheadを何十年ぶりぐらいに使ってみた。問題になってたmain を下記の様に縮小。

こんな事に気付いたのは、コンパイルに段階が有ると思うから。最初は全体を 見渡して、型の矛盾が無いか確認。それがOKなら、個々の関数の中に突入するっ ぽいからだ。まあ、永遠にコンパイルエラーに付き纏わる感じがするけど。

main :: IO ()
main = do
    initRand
    maze <- stToIO createMaze
    return ()

こんな風に、しといてコンパイルを実施すると

app/Main.hs:49:14: error:
    • No instance for (Random Direction)
        arising from a use of ‘randomRIO’
         :

新らしい種類のエラーに遭遇した。

こんな修正方法が有るとな。もう知らない事ばかり。

data Direction = UP | DOWN | LEFT | RIGHT deriving (Enum, Bounded, Show)

instance Random Direction where
  randomR (lo, hi) g =
    case randomR (fromEnum lo, fromEnum hi) g of
      (r, g') -> (toEnum r, g')
  random g = randomR (minBound, maxBound) g

簡単に言うと、ROMかRAMぐらいになるか。

haskellなデータなら何でも入いるBox型と、マシン寄りの特定な型のデータし か入れられないUBox型。

例を頂いてきた。

{-# LANGUAGE FlexibleContexts #-}

import Control.Monad.ST
import Data.Array.ST
import Data.Array.IO
import Data.Array.MArray

makeSTArray :: ST s (STArray s Int Int)
makeSTArray = make

makeSTUArray :: ST s (STUArray s Int Int)
makeSTUArray = make

makeIOArray :: IO (IOArray Int Int)
makeIOArray = make

makeIOUArray :: IO (IOUArray Int Int)
makeIOUArray = make

make :: MArray a Int m => m (a Int Int)
make = do
    arr <- newArray (5,11) 8
    val <- readArray arr 7
    writeArray arr 7 (negate val)
    return arr

目出度いアドレスを read modfy write してみる。

ghci> runSTArray $ makeSTArray
array (5,11) [(5,8),(6,8),(7,-8),(8,8),(9,8),(10,8),(11,8)]

STArrayはSTの中に巣篭りしてるんで、runSTArrayを使って取り出した。

ghci> xx <- makeIOArray
ghci> getBounds xx
(5,11)
ghci> readArray xx 7
-8

IOArrayの方は、ghciがdoの中で動いているんで、<- で、リンクしてから利用 してみた。結構難しいな。

埋め込みのprintを利用してみる。import Debug.Traceを思い出せ。

その前に、どこの仕込むかだな。そりゃ、一次受注のdigだろう。肝心のMaze は、天下り的に更に上位から壁だけの配列が用意されて渡ってくる。

天下りと言えば、今世間で話題になってる、こういう問題が有る。 シン大阪・関西万博へ ヘドロの埋立地を貸してあげるから、注目をあびる興業をやってみてって言う 大阪の金儲け算段。

今回の穴ほり問題も、同じ構図っぽい。

dig :: Maze -> (Int, Int) -> StdGen -> IO ()
dig maze (x, y) gen
  | null directions = return ()
  | otherwise = do
      let (dir, gen') = randomDirection directions gen
      let nextCell = move dir (x, y)
      let wallCell = move (opposite dir) (x, y)
      writeArray maze nextCell 0
      writeArray maze wallCell 0
      dig maze nextCell gen'
  where
    directions = shuffle [minBound..maxBound] gen

再帰関数なので、終了条件を確認。方向リストが空になったら終了。返り値は 無いけど。そりゃ、加工されたMazeがそれにあたる。

それ以外の時はMazeを更新しつつ、再帰する。Mazeに書き込む0は、通路って 意味だ。

再帰の停止性を確認しつつ、方向と座標を表示してみるか。traceの引数に変 数も指定した場合、括弧で包む。元の引数は削除する。何故なら、traceの返 値が第二引数になるから。

let nextCell = move
      (trace ("dir:  -> " ++ show dir) dir)
      (trace ("  (x,y) = " ++ show (x,y)) (x,y))

9x9の盤面で、中央の(5,5)から穴を堀り始めてみた。

ghci> :main
dir:  -> LEFT
  (x,y) = (5,5)
dir:  -> LEFT
  (x,y) = (3,5)
dir:  -> RIGHT
  (x,y) = (1,5)
 *** Exception: Error in array index

確かにエリア外に出てしまうな。更にwriteArrayをコメントにして例外しない ようにすると、永久ループになってしまう。方向リストがnullって条件で再帰 が終了なんだけど、そうなっていない。それを指摘したら、随分複雑なコード を提示してきた。

そのおかげで、コンパイルすら成功しない堂々巡りな世界に突入してしまった。 いわゆる自爆ってやつだ。地雷があちこちに仕掛けてあるからね。

丁度、万博会場と一緒。

オイラーが追従出来る所まで戻って再度作戦開始。新たなセッションを始めて みたのさ。

このHaskellコードは、永久ループに陥る問題を持っています。永久ループの原因は、dig関数でランダムな方向を選択するときに、すべての方向が既に探索済みの場合にも再帰呼び出しを続けてしまうことです。

この問題を解決するために、次のような修正が必要です：

dig関数内で、ランダムに選択した方向をリストから削除する必要があります。これにより、同じ方向を無限に選択し続ける問題が解消されます。

方向を選択する前に、各セルの周りの未探索の方向をチェックし、ランダムに選択できる方向があることを確認する必要があります。すべての方向が既に探索済みの場合、再帰呼び出しを終了します。

と、まっとうな指針を提示して来たけど、内容を伴っていない。ここからは自 分でガンバレ かな。なんだか、万博のゆく末を暗示してるぞ。