(5/5)

EECS281Games™ is developing a new puzzle game that they want to bring to the market in the next few weeks.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Introduction: The Puzzle

EECS281Games™ is developing a new puzzle game that they want to bring to the market in the next few weeks. They’ve already built the engine and designed thousands of levels, but they realized that they’re not sure how to solve many of them! What’s worse, they think some of them are unsolvable!

You are tasked with developing a C++ program that will take as input a sample map and some command-line flags indicating how your program will behave. You will process the map, check that the input is valid, then output information about the puzzle’s solvability and a description of the puzzle’s solution (if it has any).

The game is played on a grid, filled with open space and walls that block player movement. Here is a small sample input that your program could receive:

2 4 7

// A simple example puzzle

// 2 colors (A, B)

// 4x7 grid @..A..b

.a.#B## ####...

?..B.^^

The goal of the game is for the player to get from their starting location (marked with @) to the target (marked with ?), by pressing buttons (a, b, ..., z and ^) that open and close doors (A, B, ..., Z) that stand in their way.

The player’s available moves are to travel one tile north, east, south, or west (up, right, down, or left) as long as there’s no wall (#) or closed door (A, B, ..., Z when closed) in their way. The player cannot move diagonally, or step off of the grid (you can imagine the specified map is surrounded by impassable walls).

The valid map symbols:

@ is the player starting position. A valid input has exactly one @.
? is the target position. A valid input has exactly one ?.
. represents an open space that the player can stand in.
# represents a wall. The player cannot move into a #.
A, B, C, ..., Z are doors. The player can only move onto them when they are open. They all start closed. The letter marking the door is called its “color” (in the game, the doors are displayed with different colors).
a, b, c, ..., z are buttons. The player can always move onto them, which causes them to trigger when they are active. Buttons all start active. Each button opens the corresponding type of door (an a opens the A doors, b opens the B doors, c opens the C doors, ), and simultaneously closes all other types of doors.
^ is a trap. It’s like a special button that starts inactive. Stepping on a trap closes all

Doors and Buttons

The maps aren’t just simple mazes -- they include special puzzle elements called “buttons” and “doors”. When the player moves onto an active button (e.g. b), it gets triggered:

B doors open; all other doors close
b buttons become inactive; all other buttons and traps become active.
Informally, buttons open doors of the same color and close everything

When the player moves onto an active trap (^), it gets triggered:

All doors
All buttons become active; all traps become
Informally, traps close all the

Example Input

2 4 7

// A simple example puzzle

// 2 colors (A, B)

// 4x7 grid @..A..b

.a.#B## ####...

?..B.^^

With the game’s rules in mind, let’s see how the above puzzle can be solved:

Walk east and south to the a, which opens the A

Walk north and then 5 east through the A door into the upper right room and stand on the b button, which closes the A doors and opens the B
Walk 2 west, 3 south (going through the first B door), then west (through the second B door) until you reach the target (avoiding the traps, which would have closed the B doors).

Solving Puzzles

Your program will attempt to find a solution to the puzzle, and present it as output. The exact details of this process will be described in the next section, but it won’t make sense unless you read this section first. Our goal is to take a map as input and find a sequence of moves (moving north, east, south, and west, or triggering buttons/traps) that bring us to the target, or confirm that this isn’t possible. There’s no obvious strategy to solving these puzzles- we have to make a lot of decisions and the “best” decision in each case is not obvious or clear.

So instead of trying to cleverly reason about how to best solve these puzzles, we’ll just try to make every possible move and see where that gets us. This is possible because of a few observations relating to the player’s state.

The player has a position in the grid (row, col) (the top left corner is position (0, 0) and the bottom right is (height-1, width-1)). The player’s initial position is wherever the @ symbol is in the input grid. In addition, there is an active button color: the color of the last trap/button pressed. The initial color is ^, since all doors start closed.

The player’s complete state is the combination of their color and position (row and column).

In other words, you can think of the player as being inside of a 3D maze, instead of a 2D maze. The number of “rooms” in this maze is equal to the number of colors + 1. Room 0 is the ^ room. Room 1 is where you go after pressing button a; room 1 has no A walls. Room 2 is where you go after pressing button b, etc. Room 0 has no traps; the traps exist in all other rooms. Think about saving memory here; see the “Tips” section later on.

The player’s state tells us everything about where they are and whether they can win.

First, how the player got to their state S doesn’t affect whether or how they can win; only the state S itself (and the map) does. If you know how to get from state S to the target, then any method to get from the start to state S will work.

Secondly, there are at most (number of colors) * width * height possible states. Together, these two observations lead to the following strategy:

We know how to get to the initial location (we start there).
If we know how to get to a location S, and T is just one move away from S (for example, pressing a button or moving north/east/south/west) then we know how to get to T: get to S, then perform that one move. For example, if the current location is (row 0, col 0) and you move east, you arrive at location (row 0, col 1).
If we repeatedly “learn” how to get to each possible state, then we will either learn a way to the target, or find out that one doesn’t

In more detail:

The initial state is “reachable”. Recall that a “state” is composed of a color, row, and
Create a reachable_collection that will hold the “reachable” states (it starts with just the initial state in it).
Take the “next state” from reachable_collection. Call this current_state.
Find the states next_state_1, next_state_2, etc. that you can reach in one step from

current_state. Add them to reachable_collection, but only if they have never been added before.

Repeat from step 3 until you’ve found the target, or the reachable_collection is empty.

Based on the observations above, once we’ve completed this process, we will have either found the target, or every state that can possibly be reached will have been in the reachable_collection at some point. Thus, we can use it to decide whether or not the puzzle is solvable.

(5/5)

Use CA10RAM to get 10%* Discount.