Maze Maker
Maze Maker

Maze Maker

Learning Exercise



In a pure functional language like Elm, a function called with the same arguments must always return the same value. Therefore a function with the type signature rand : Int can only be implemented as rand = 4, which does not bode well for generating random integers.

So how do we generate random values in Elm? We split the problem in two: first, we describe the value that we want to generate with a Random.Generator a, then we generate a value.

The first way to generate a value is to create a Random.Seed via initialSeed : Int -> Seed and then use step : Generator a -> Seed -> ( a, Seed ), which returns a value and a new seed. Note that both of these functions are pure, so calling them twice with the same arguments will produce the same values.

The second way to generate a value is by using generate : (a -> msg) -> Generator a -> Cmd msg, but that can only be done inside an Elm application. In that case, the Elm runtime may use step as well as outside, non-pure resources to generate seeds.

From now on, we will focus on generators.

Let us pretend, for the sake of showing examples, that we have defined with initialSeed and step a function generate : Int -> Generator a -> List a that generates a number of values from a generator.

The Random module provides two basic generators for generating integers and floats within a specific range:

generate 5 ( -5 5)
    --> [0, 3, -5, 5, 0]

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

Those values can be combined into tuples, or into lists of values:

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

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

The elm-community/random-extra package provides a lot more generators for various data structures: strings, dates, dictionaries, arrays, sets, etc.

We can create generators that will only return a single value using Random.constant:

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

We can randomly pick from given elements with equal probability using Random.uniform:

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

Random.uniform takes two arguments (Red and [Green, Blue]) to guarantee that there is at least one value to pick from, since a single list could be empty.

We can also tweak the probabilities using Random.weighted:

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

The values do not need to add up to 100, they will get renormalized anyway.

We can reach the inside of a generator with

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

We can also use Random.map2 all the way to Random.map5 to combine more generators:

position =
      (\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]

For more complex uses, we have Random.andThen : (a -> Generator b) -> Generator a -> Generator b that can use the value generated by one generator to create another:

bool = Random.uniform True [False]

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

                    Random.constant Nothing

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

It is sometimes useful to define a generator self-recursively. In those cases, you might need to use Random.lazy to keep the compiler from unrolling the generator infinitely.

type Peano
    = Zero
    | Next Peano

peano : Generator Peano
peano =
    Random.uniform (Random.constant Zero)
        [ 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)))]

This example is a little heavy, so let's break it down.

Peano is a type that represents positive integers: Zero is 0, Next(Zero) is 1, Next(Next(Zero)) is 2, etc. We define peano to give us a random Peano number.

First of all, note that Random.lazy doesn't add anything to the logic, it merely prevents the compiler from writing peano into peano indefinitely.

We use Random.uniform to pick between zero (with 50% probability) and another Peano number plus one (with 50% probability). However, unlike with the previous example, Random.uniform is not picking from values (like Zero) but instead from generators (like Random.constant Zero) since we want to use peano itself. This means that Random.uniform will return a value of type Generator (Generator Peano), which is not want we need.

To "flatten" the generator, we pipe it into Random.andThen : (a -> Generator b) -> Generator a -> Generator b, where we want b to be Peano. Since Generator a is Generator (Generator Peano), a must be Generator Peano, and the function (a -> Generator b) must be of type (Generator Peano -> Generator Peano). We don't want to modify anything, so identity is the right choice.

Finally, what kind of numbers will peano produce? We know that it will produce 0 50% of the time, or another iteration of itself plus one 50% of the time. That means the numbers will be 0 (50% of the time), 1 (25% of the time), 2 (12% of the time), 3 (6% of the time), etc. peano can produce arbitrary large numbers, but with exponentially decreasing probability.


You are a maze researcher, working to design a new generation of dungeons and adventuring grounds.

You are a theoretician, which means you are not concerned with the physical layout of mazes (that is a task for maze engineers), but instead you care about their mathematical complexity: branching factor, maximum depth and such.

You decide to approach your next project with a random generation approach.

1. Start with the end

Any good maze is mostly dead ends.

Define the deadend generator so that it always generates the DeadEnd variant.

2. You can't catch flies with vinegar

Let's give adventurers a reason to venture in your mazes.

Define the treasure generator so that it generates either Gold, Diamond or Friendship with equal probability.

Then, define the room generator so that it wraps the values generated by treasure in the Room variant.

3. Branching out

And now for the heart and soul of a maze: branches.

The branch generator receives a Generator Maze argument, which is a generator able to generate an arbitrary maze.

Define the branch generator so that it generates a Branch variant containing several branches leading to mazes generated by its argument.

The number of branches should be between 2 and 4 (any more than that and the maze engineer would get angry), determined randomly with equal probability.

4. Amazing mazes

Time to do business.

Define the maze generator so that it generates a dead end 60% of the time, a treasure room 15% of the time and a branch 25% of the time. The branches should generate new mazes using maze recursively. Make sure to use deadend, room and branch in the generator.

Each branch contains on average 3 mazes, but only 25% of these will branch out again, which is less than one, so your generated mazes are likely to eventually end.

5. We have to go deeper

Your maze is nice, but it has some issues:

  1. 75% of the generated values don't have any branch at all, hardly real mazes
  2. Adventurers might find treasure rooms early in the maze and decide to stop exploring
  3. While deep mazes can be generated, they are not very likely: a maze of depth of 3 has an approximate 3% chance of being generated, a maze of depth 10 a 0.2% chance (the depth of a maze is calculated with MazeMakerSupport.mazeDepth)

Define the mazeOfDepth n generator so that it generates a maze of depth n. Only the deepest level 0 should contain dead ends or treasure rooms (with equal probability), all other levels should be a branch containing mazes of depth n - 1 generated recursively with mazeOfDepth. Make sure to use deadend, room and branch in the generator.

Edit via GitHub The link opens in a new window or tab
Elm Exercism

Ready to start Maze Maker?

Sign up to Exercism to learn and master Elm with 22 concepts, 83 exercises, and real human mentoring, all for free.