Homework 5

Due Date Tuesday 10/13 at 9:00pm (Week 5)

Purpose To practice with functions that operate on lists; begin a multi-stage project.

Finger Exercises

Exercise 1 From HTDP, 160

Graded Exercises

Exercise 3 Design the function powerlist which returns all possible sublists of a list of numbers. A sublist of a list is any list whose items appear in the same relative order that they do in the initial list and all of the items appear in the initial list. Assume the initial list given to powerlist contains no duplicates.

Exercise 4 Design the function intersection, which given a non-empty list of list of numbers returns the numbers that appear in every sublist. Assume each inner list does not repeat numbers. Note that while the outer list is non-empty, inner lists may be empty.

Sokoban

We’re going to build Sokoban, a logic/puzzle game created in 1981, over the next few weeks. There are many variations on this game in existence, so we’ll be adding features as we go. Adding features may mean that you have to redesign earlier parts of your code, so the cleaner your initial design is, the easier it will be to modify later. Spending time early on careful, clean design will pay off!

A Sokoban level is played on a rectangular grid of square cells. For now we’ll only consider a few kinds of cells; we’ll add more later. Several things could be in a cell: nothing at all, the player, a brick wall, a crate, a trophy, or a target. (We’ll add more possible things in later assignments.) Here is an example board:

The goal of the game is to get all the colored trophies onto their similarly colored targets: in the example above, there are only blue trophies and targets, but in general there could be multiple colors (your game should support four colors; our implementation uses red, green, blue and yellow). Some things in the game can move: crates, trophies, and the player. Others are fixed: the targets, and brick walls. You can play the original, classic version of the game at https://www.mathsisfun.com/games/sokoban.html, but be aware that this version only has movable crates, which behave like the trophies in our version of the game (i.e. the crates need to be placed on the targets).

Exercise 5 Design data definitions sufficient to describe the board state. The board above can indeed be thought of as rectangular: there are just a lot of blank cells and the brick walls just happen to enclose a smaller region of the board. You will need several helper data definitions. Note that different boards could easily be of different sizes, so your definitions should not limit themselves to a specific size of board. Be sure to follow the design recipe for all of them, and create sufficient examples.

Exercise 6 Design a function board->image to render a game board as an image. You do not need to use precisely the same images as we have here, but if you’d like to, you may copy these images and use them:

Your function should use a constant CELL-SIZE to allow for drawing the board at different sizes.

Exercise 7 Design a function level-won? that detects if the player has won the level: check that every target has a trophy on top of it, whose color matches the target’s color. Note: you can design Sokoban levels where there are more trophies than targets, so you do not need to check if every trophy is on a target. (The converse, where there are more targets than trophies, is simply an unwinnable board.)

Exercise 8 Design a tiny big-bang program that lets the player move in any direction. For now, ignore the rules of the game: a player can move to any adjacent empty cell.

Some hints for your data design:

• Describing a rectangular grid is best done using a list of lists. You can (and should!) use the (list ...) notation to make writing examples easier.

• Your data definitions will likely contain one or more enumerations. You may find it convenient to use 1-character-long strings as the values of your enumerations, so that when you write examples of boards, the examples themselves will naturally be written in a grid of characters in your source code, such that it’s visually pretty easy to see what the board should look like.