Question 1
1. Background
2048 is a 2014 game developed by Gabriele Cirulli. The game consists of using arrow keys on the keyboard (left, right, up down) in order to slide all cells on a board in that particular direction. If, during the slide, two cells are identical, their values are summed together and the two cells are replaced with a new cell with twice the value.
Every move, a random cell of value 1 or 2 is also added to the board.
The game is complete once a 2048 cell appears on the board.
To understand the behaviour of the game, you can quickly play it here.
This exam question is relating to implementing the mechanism for sliding and merging cells on the board, with two exceptions:
- No random cells are added to the board each move (to keep the question simple)
- Instead of using decimal representations of numbers like the 2048 game, we will be using
std::stringto represent cells in their hexadecimal equivalent. This correlates to:
| 2048 game | 0x800 game |
|---|---|
| BLANK | "" |
| 1 | "0x1" |
| 2 | "0x2" |
| 4 | "0x4" |
| 8 | "0x8" |
| 16 | "0x10" |
| 32 | "0x20" |
| 64 | "0x40" |
| 128 | "0x80" |
| 256 | "0x100" |
| 512 | "0x200" |
| 1024 | "0x400" |
| 2048 | "0x800" |
2. Task
Your task is to implement a function that mutates a grid based on a particular keyboard command. The functions takes in a 2D std::array with size specified by a non-type template parameter, and a direction enum (one of left, right, up, or down).
It then slides the cells in that particular direction, merging it if necessary.
template <std::size_t size>void move_0x800(std::array<std::array<cell, size>, size>& g, Move direction)
Some notes on implementation and marking:
- 70% of the marks for this question are awarded for correct sliding functionality. A range of tests will be used to determine if you've implemented sliding correctly. Even if you don't get merging working, you can still get full marks for this section.
- 30% of the marks for this question are awarded for correct merging functionality. You should complete the sliding logic first. A range of tests will be used to determine if you've implemented merging correctly.
- There is no expectation that you successfully handle the "end"/goal state. You can just assume that no input will ever be passed in that actually generates a 0x800 cell.
3. Assumptions & Constraints
- There are no performance requirements or constraints for this question
- You can assume that all input is valid as per the spec
- You can assume that the grid size will be between 3 and 20
4. More help understanding the game
4.1. Sliding
Sliding behaviour is somewhat self explanatory and can be seen in the link to the 2048 game above. When you press a direction, E.G. left, every cell moves as far left as it can without colliding with the other.
An example of the before and after state for a slide left is below. (Please note: In these examples decimal numbers are used. In your examples you need to use the hex strings as described above).
Slide left
4.2. Merging
Whilst merging can be understood through playing with the game for a short moment, we will elaborate on it slightly.
From wikipedia: *"If a move causes three consecutive tiles of the same value to slide together, only the two tiles farthest along the direction of motion will combine. If all four spaces in a row or column are filled with tiles of the same value, a move parallel to that row/column will combine the first two and last two"*
An example of the before and after state for a slide down (which includes a merge) is below. (Please note: In these examples decimal numbers are used. In your examples you need to use the hex strings as described above).
Slide down
