11 Homework 7A

Due:

Tuesday, 2/20 at 9PM

This assignment may be done with an approved PARTNER.

This assignment is entirely AUTOGRADED.

What to Download:

hw7a.rkt

Please start with this file, filling in where appropriate, and submit your homework to the HW7A assignment on Gradescope. This page has additional information, and allows us to format things nicely.

11.1 Mazes

In this assignment, we are going to define and then refine a program that generates mazes. Our mazes will be grids of cells, which can have one of four things in them: a wall, nothing (empty space), the player, or the exit. There should be only one player and exit in the maze. We can define what is in a cell as:

There are various ways to define a grid; for this assignment, we’ll represent a grid as a list of positions paired with cells (another mechanism would be a two-dimensional list, etc). We can define that as:

Note that we define Posn~ to be the contract for a Posn struct with two natural numbers. Structs can have any data in them, so, for example, (Posn String Boolean) is a valid contract (however potentially unhelpful).

One interesting feature of this representation (has good and bad consequences) is that it is easy to be missing certain cells. Sometimes having so-called "sparse" representations is very useful (sparse vectors show up in machine learning contexts: in that case, where only a few values are non-zero), but usually, it’s important to define how they should be intrepreted. For a maze, it seems sensible to say that any cell that is not explicitly represented is a wall.

11.2 Problem 1

First, let’s figure out how to generate mazes. We’d like you to start by designing a function random-maze that taken a natural number dimension as argument and generates a dimension by dimension grid by randomly placing elements. You may find it useful to define a helper to select randomly from a list using random and list-ref.

You can write basic unit tests on this, just to ensure the function runs, by checking the length of the output – i.e., (check-expect (length (random-maze 3)) 9).

11.3 Problem 2

If you look at some generated mazes (which is going to not be fun: we’ll come back to this in Problems 3-6) — (random-maze 10), for example — you might notice a problem: you can have multiple players, multiple exits! Define a predicate single-player-exit? that takes a Maze and checks if it has only one player and exit.

Note, of course, that this will fail most of the time if you run (check-expect (single-player-exit? (random-maze N)) #t) for some N.

So, we’d like you to define a new maze generation function called random-maze-2 that takes dimension, calls random-maze with it, checks if single-player-exit? holds, and if not, generates another one. Try running this and see what happens – depending on how you generated things in Problem 1, this may take a long time, as most mazes will fail the property. If that’s the case, go back and revise your random generation in Problem 1 to generate fewer (or exactly 1!) player and exit until you can get random-maze-2 to work.

As before, you can include basic unit tests on random-maze-2 (checking, e.g., size of output) to ensure that it can run, which now means something stronger: it generates a maze that satisfies single-player-exit?.

11.4 Testing...

Writing down example mazes, and looking at the output of functions, is pretty unpleasant. Not only does our representation mean they do not naturally appear in any grid-like form, but there is a lot of noise from the structs. To fix that, we’d like you to define an alternate representation of the data in terms of S-Expressions, and define conversion functions between the S-Expression form and the definitions above. This is a particular instance of a more general, and extremely important, technique: defining support code that makes it easier to write testing and/or debugging code. By doing this, we can much more easily test and debug our code, which in turn makes it easier to write the code in the first place. In other words, a little bit of time spent here will avoid a ton of wasted time doing without.

If you haven’t seen S-Expressions before, they are defined as:

11.5 Problem 3

To do this, start by designing a pair of functions, sexp->cell and cell->sexp. You could choose any representation for the cells, but in this case, we require you to use symbols, (written as 'something), since the quote operator (See this page) will allow you to write / see very compact mazes. And in particular, you should use:

'X for a wall

'_ for empty / open space

'P for the player (start position)

'E for the exit (end position)

Your sexp->cell function should work for any S-Expression (to satisfy its signature), but may error if given one that cannot be converted to a Cell. Use (raise (make-invalid-sexp the-sexp-that-isnt-valid)) to signal an error, where the latter is a struct defined as:

This means you should use the techniques described in Lecture 13: More Recursive Data to write a signature that captures the fact that your function may raise an invalid-sexp error.

11.6 Problem 4

Now, to validate that your fuctions from Problem 3 work, design a function cell-roundtrip-prop that checks that a Cell, when converted to an S-Expression and back, is the same value. Use check-contract to validate that, indeed, this property holds. Why does the other direction not hold?

11.7 Problem 5

Now design sexp->maze and maze->sexp. Your S-Expression format, unlike the Maze representation, should be a list of lists, so you can use quote to write an example maze. So, for example, you should be able to convert the following example:

'((X X P)

(E X _)

(_ _ _))

IMPORTANT: you have to decide, when doing this, where your coordinates start from. In order to match with our test suite, you must have the top left be position 0,0, and have the rows be Y and the columns be X. So in the above, the P is at 2,0, and E is at 0,1.

Where that shows a simple maze where the solution involves starting at the top right, then going down around the bottom to reach the exit in the middle left.

Hint: for maze->sexp, once you find the maximum X & Y, build-list will likely be helpful. For sexp->maze, you may want to write a helper that acts like map, but passes the current position in the list in as well.

Note: go back and look at the output from Problem 1, now using your conversion: (maze->sexp (random-maze 10)) – notice how much easier it is to notice the issues you corrected in Problem 2?

11.8 Problem 6

As before, you want to validate your conversions with a round-trip property called maze-roundtrip-prop. Define it and then check it once with check-contract, but you may want to comment it the check-contract out while you work on the rest of the assignment as it can take a while to run!

11.9 Problem 7

There is still likely a problem with the mazes: unless you didn’t follow our directions, probably some of the time they are not solvable! i.e., there is no path from the player to the exit. It might be good if the mazes were hard, but not good if they are impossible! In this problem, we’d like you to define a predicate path-exists? that checks if there is a path from the player to the exit. There are various ways of doing this, but the easiest is via depth-first-search: first find the Posn~ of the player and the exit, and then define a helper function with two arguments: an accumulator with all the Posn~s visited so far and the current Posn~. If the current one has been visited or is a wall, it returns #f; if the current is the exit, it returns #t, otherwise, it finds all the neighbors (another helper) and ormaps a recursive call to them, adding the current Posn~ to the visited list.

Once you have that predicate, you can define a random-maze-3 that takes a dimension, calls random-maze-2, checks if there is a path from the player to the exit, and if not, calls it again.

As before, include basic unit tests on random-maze-3 to ensure that this can actually run, which now means you have a maze that can actually be solved.

11.10 Problem 8

If you look at some examples from random-maze-3, you might notice that while all have a path, sometimes the path is essentially trivial: just a few empty spaces separate the player from the exit. In this problem, we want you to revise your predicate that the path exists to create a function called path-length? that returns either #f or a natural number saying how long the path is if a path is found.

With the following contract:

You can have your function return Maybe Natural. Note that it is a relatively small change, since the accumulator list with the seen nodes is the path that has been traversed, so the length of that is the length if you reach the exit. The only significant change is that rather than using ormap to combine the recursive calls on the neighbors, you have to combine the Maybe Naturals: if there are no numbers, returning #f, if there are numbers, returning their minimum.

You can now define a random-maze-4 that ensures that the path is at least length, e.g., dimension (you can try longer, but if you try to make it too long, you may have a function that essentially never returns, since most generated mazes will fail).

11.11 Closing Thoughts

There are clear limits to essentially purely random generation for creating mazes: but regardless of the strategy to come up with the maze, the properties, like there being a path from the player to the exit, or that it have a certain minimum length, are properties that we wish to hold.

Indeed, even if the algorithm to generate the maze were very complicated (as, indeed, it might have to be to construct interesting examples), there are likely relatively simple invariants that can be expressed. For example: you could also express that you want there to be dead ends on the path, rather than just one long winding path to the exit. Changing the DFS function to return (the length of) all attempted paths would be relatively simple, as would checking that there were many that were long.