學習軌道
/
Elm
Elm
/
練習
/
迷宮製造者
迷宮製造者

迷宮製造者

學習練習

簡介

隨機

在 Elm 這類純函式語言中,以相同引數呼叫的函式必定會回傳相同的值。 因此,型別簽章為rand : Int的函式只能實作成rand = 4,這對產生隨機整數來說可不是好兆頭。

那麼,我們要如何在 Elm 中產生隨機值呢? 我們可以把問題拆成兩半:首先用Random.Generator a描述我們想產生的值,然後再產生一個值。

產生值的第一種方法,是透過initialSeed : Int -> Seed建立Random.Seed,接著使用step : Generator a -> Seed -> ( a, Seed ),它會回傳一個值和一個新的種子。 請注意,這兩個函式都是純函式,所以用相同的引數呼叫兩次會得到相同的值。

產生值的第二種方法,是使用generate : (a -> msg) -> Generator a -> Cmd msg,但這只能在 Elm 應用程式內進行。 在這種情況下,Elm 執行環境除了使用step之外,還可能動用外部、非純的資源來產生種子。

接下來,我們會把焦點放在產生器上。

為了方便示範,讓我們假設我們已經用initialSeed和step定義了一個函式generate : Int -> Generator a -> List a,它能從某個產生器產生若干個值。

Random模組提供了兩個基本的產生器,用來在特定範圍內產生整數和浮點數:

generate 5 (Random.int -5 5)
    --> [0, 3, -5, 5, 0]

generate 3 (Random.float 0 5)
    --> [1.61803, 3.14159, 2.71828]

這些值可以組合成元組,或組合成值的陣列:

generate 2 (Random.list 3 (Random.int 0 3))
    --> [[0, 3, 3], [1, 3, 2]]

generate 2 (Random.pair (Random.int 0 3) (Random.float 10 10.3))
    --> [(0, 10.23412), (2, 10.17094)]

elm-community/random-extra套件提供了很多產生器,可用於各種資料結構:字串、日期、字典、陣列、集合等等。

我們可以使用Random.constant建立只會回傳單一值的產生器:

generate 4 (Random.constant "hello")
    --> ["hello", "hello", "hello", "hello"]

我們可以使用Random.uniform,以相同的機率從給定的元素中隨機挑選:

generate 5 (Random.uniform Red [Green, Blue])
    --> [Red, Blue, Blue, Green, Red]

Random.uniform接受兩個引數(Red和[Green, Blue]),以保證至少有個值可以挑選,因為單一一個陣列可能是空的。

我們也可以使用Random.weighted微調機率:

generate 5 (Random.weighted (80, Red) [(15, Green), (5, Blue)])
    --> [Red, Red, Green, Red, Red]

這些值不需要加總到 100,它們無論如何都會被重新正規化。

我們可以用Random.map觸及產生器的內部:

generate 3 (Random.int 1 6 |> Random.map (\n -> n * 10))
    --> [30, 60, 10]

我們也可以使用Random.map2一路到Random.map5,來組合更多產生器:

position =
    Random.map3
      (\x y z -> Position x y z)
      (Random.float -100 100)
      (Random.float -100 100)
      (Random.float -100 100)

generate 1 position
    --> [Position 33.788 -98.321 10.0845]

對於更複雜的用途,我們有Random.andThen : (a -> Generator b) -> Generator a -> Generator b,它可以用某個產生器產生的值來建立另一個產生器:

bool = Random.uniform True [False]

failHalfOfTheTime : Generator a -> Generator (Maybe a)
failHalfOfTheTime generator =
    bool
        |> Random.andThen
            (\boolResult ->
                if boolResult then
                    Random.map Just generator

                else
                    Random.constant Nothing
            )

generate 6 (Random.int 0 1 |> failHalfOfTheTime)
    --> [Nothing, Just 1, Just 0, Nothing, Just 1, Nothing]

有時候,定義一個會自我遞迴的產生器是很有用的。 在這些情況下,你可能需要用Random.lazy來避免編譯器無限展開產生器。

type Peano
    = Zero
    | Next Peano


peano : Generator Peano
peano =
    Random.uniform (Random.constant Zero)
        [ Random.map Next (Random.lazy (\_ -> peano))
        ]
        |> Random.andThen identity

generate 12 peano
    --> [Zero, Next(Next(Zero)), Zero, Next(Zero), Zero, Zero, Next(Zero), Zero, Zero, Next(Zero), Next(Next(Next(Zero)))]

這個例子有點複雜,我們來拆解一下。

Peano是一種表示正整數的型別:Zero是 0,Next(Zero)是 1,Next(Next(Zero))是 2,依此類推。 我們定義peano來給我們一個隨機的Peano數字。

首先請注意,Random.lazy並沒有為邏輯增加任何東西,它只是防止編譯器把peano無限地寫進peano裡。

我們使用Random.uniform在零(50% 的機率)和另一個Peano數字加一(50% 的機率)之間做選擇。 不過,和前一個例子不同的是,Random.uniform挑選的不是值(例如Zero),而是產生器(例如Random.constant Zero),因為我們想使用peano本身。 這表示Random.uniform會回傳型別為Generator (Generator Peano)的值,而這並不是我們要的。

要把產生器「攤平」,我們將它餵進Random.andThen : (a -> Generator b) -> Generator a -> Generator b,其中我們希望b是Peano。 由於Generator a是Generator (Generator Peano),a必定是Generator Peano,而函式(a -> Generator b)的型別必定是(Generator Peano -> Generator Peano)。 我們不想修改任何東西,所以identity是正確的選擇。

最後,peano會產生什麼樣的數字呢? 我們知道它會有 50% 的機率產生 0,或者有 50% 的機率產生它自身的另一個疊代再加一。 也就是說,這些數字會是 0(50% 的機率)、1(25% 的機率)、2(12% 的機率)、3(6% 的機率)等等。 peano可以產生任意大的數字,但機率會以指數方式遞減。

說明

你是一位迷宮研究員,正在設計新一代的地城與冒險場地。

你是個理論家,也就是說,你不在意迷宮的實際配置(那是迷宮工程師的任務),你關心的是它們的數學複雜度:分支因子、最大深度之類的。

你決定以隨機生成的方式來進行下一個專案。

1. 從終點開始

任何好的迷宮大多都是死路。

定義deadend產生器,讓它總是生成DeadEnd變體。

2. 單靠醋抓不到蒼蠅

讓我們給冒險者一個願意踏入你迷宮探險的理由吧。

定義treasure產生器,讓它生成Gold、Diamond或Friendship的機率相同。

然後,定義room產生器,讓它把treasure生成的值包進Room變體裡。

3. 開枝散葉

現在來到迷宮的核心與靈魂:分支。

branch產生器會接收一個Generator Maze引數,那是一個能夠生成任意迷宮的產生器。

定義branch產生器,讓它生成一個Branch變體,裡面包含數個分支,這些分支會通往由它的引數生成的迷宮。

分支的數量應該介於 2 和 4 之間(再多下去迷宮工程師可是會生氣的),並以相同機率隨機決定。

4. 了不起的迷宮

該做正事了。

定義maze產生器,讓它有 60% 的機率生成死路、15% 的機率生成寶藏房間、25% 的機率生成分支。 分支應該遞迴地使用maze來生成新的迷宮。 請務必在產生器中使用deadend、room和branch。

每個分支平均包含 3 個迷宮,但其中只有 25% 會再次分支出去,也就是不到 1 個,所以你生成的迷宮最後很可能會結束。

5. 我們得再深入一層

你的maze很不錯,但它有幾個問題:

  1. 75% 的生成值完全沒有任何分支,稱不上是真正的迷宮
  2. 冒險者可能會在迷宮的早期就找到寶藏房間,然後決定停止探索
  3. 雖然可以生成很深的迷宮,但出現的機率不高:深度為 3 的迷宮大約有 3% 的機率會被生成,深度為 10 的迷宮則是 0.2%(迷宮的深度是用MazeMakerSupport.mazeDepth計算的)

定義mazeOfDepth n產生器,讓它生成深度為n的迷宮。 只有最深的一層0可以包含死路或寶藏房間(兩者機率相同),其他每一層都應該是一個分支,裡面包含用mazeOfDepth遞迴生成的深度為n-1的迷宮。 請務必在產生器中使用deadend、room和branch。

透過 GitHub 編輯 連結會在新視窗或分頁中開啟
Elm Exercism

準備好開始 迷宮製造者 了嗎?

註冊 Exercism,透過 28 個概念110 個練習 和真人引導來學習並精通 Elm,全部免費。