Tracks
/
Elm
/
Exercises
/
Maze Maker

# Maze Maker

Learning Exercise

## Introduction

### Random

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 (Random.int -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 (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)]
``````

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 `Random.map`:

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

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

``````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]
``````

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 =
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]
``````

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)
[ 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)))]
``````

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.

## Instructions

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.

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

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

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