DSA Homework
Due date:
2048 (DFS using a stack)
Outlines
Problem definition
2048 has been a popular game since its debut in March, 2014.
Before you start, you should get familiar with the game. Here is some references:
In this homework, your mission is to write a program to identify an action sequence (consisting of the four actions of east, south, west, north) that can lead the game from its initial map to its desirable final map of at least one element of 2048.
Suggested approach
As instructed in the class, you can use stack-based DFS (depth-first search) to find the action sequence. For details, please refer to the slides and recording of our coverage of the homework.
On the other hand, if you prefer, you can also use recursive backtracking (which uses an implicit stack) to achieve the same goal. (Try google.)
Input/output formats
In an input file, the first line is N, the number of cases of 2048 game for your program to run. And each 4 following lines is an initial map for 2048 game. In other words, there should be 4*N+1 lines in an input file. For example, the following input file has N=10:
<![CDATA[
10
0 4 2 2
2 0 0 2
0 0 2 0
4 0 2 0
0 2 0 2
2 0 4 2
0 0 0 16
16 0 0 2
0 2 32 4
8 4 16 0
0 0 0 0
2 0 0 0
2 0 0 0
0 0 2 0
0 4 2 0
0 2 16 2
0 0 0 64
2 4 0 0
0 0 8 0
16 0 0 16
2 0 64 4
0 0 2 2
2 0 2 0
2 4 8 2
0 0 0 4
2 0 0 0
2 0 2 0
0 2 0 2
16 2 0 2
4 0 0 2
4 0 0 0
4 0 2 8
0 2 32 8
0 0 2 0
2 2 0 4
4 0 0 0
1024 4 1024 2
4 8 4 8
64 32 64 32
4 2 4 2
]]>
For each case, you need to identify the action sequence to generate the final map. If you can find an action sequence to reach the final map (with at least one element of 2048), you should print the action sequence as well as the final map. For instance, a typical output for the first case of the above input file is shown next. (Note that the action and the final map may not be unique.)
<![CDATA[
Action:
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 2 0 3 0 0 1 0 0 0 0 0 0 1 0 1 0 0 1 1 3 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 2 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 3 0 0 0 0 0 0 0 1 1 1 2 1 0 0 1 0 1 0 1 0 0 0 0 1 2 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 2 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 3 0 0 0 1 0 1 1 1 0 1 2 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 2 0 1 0 1 2 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 1 1 0 0 3 0 0 0 1 0 1 0 0 2 0 3 0 1 0 1 0 2 1 0 0 0 0 0 0 1 1 1 2 1 2 0 3 0 2 1 2 0 0 0 0 0 0 0 0 0 0 2 1 0 1 1 1 3 0 1 3 1 1 2 0 3 0 1 1 3 0 1 0 1 0 2 1 0 0 0 1 0 1 0 0 0 2 2 3 0 1 0 1 0 0 0 0 0 1 2 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 1 3 0 1 0 1 3 0 0 0 0 0 0 0 1 2 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 3 0 0 2 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 3 0 0 0 0 0 0 0 1 0 1 1 3 0 0 0 1 0 1 1 3 2 0 1 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0 1 0 1 0 0 1 0 1 0 0 1 3 0 1 0 1 1 0 2 1 0 0 0 1 0 0 0 0 3 0 0 1 2 1 0 1 0 1 0 0 0 0 0 0 0 2 1 2 1 0 0 0 2 0 1 0 1 1 0 0 0 0 1 0 0 0 1 0 1 1 1 2 1 2 0 3 0 2 1 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 1 1 1 0 0 1 0 1 0 2 1 0 1 0 0 3 0 1 0 0 3 0 1 0 0 0 1 3 1 0 1 0 1 0 0 1 0 1 1 0 2 1 0 1 0 0 3 0 1 0 1 1 0 0 1 1 3 2 0 1 0 0 0 0 0 1 0 1 1 0 1 3 0 0 0 1 3 2 1 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 1 2 1 0 0 0 1 0 1 1 2 0 0 0 1 0 0 0 0 0 0 0 1 0 1 3 0 1 1 1 0 0 0 1 2 3 0 3 0 0 2 1 0 3 0 1 2 0 1 1 1 1 1 0 1 3 0 1 0 2 1 0 1 3 1 1 2 3 0 1 0 1 0 2 1 0 1 0 0 3 0 3 3 3 3 2 3 1 2 1 3 0 1 0 1 0 1 0 1 1 2 1 0
Final:
4 32 2 8
256 16 128 2
4 2 8 2048
16 128 16 4
]]>
On the other hand, if the desired final map cannot be found (such as the last case of the above input file), then you should print -1 for the action and the final map:
<![CDATA[
Action:
-1
Final:
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
]]>
An example output file of the above input file will be provided by TA soon.
Requirements
- Limits:
- Max time: 1 minute (total time limit for N=10000).
- Max memory: 256 MB.
- Max submissions: 20 times each week.
- You can simply use DFS (exhaustive search) to finish this homework. If you are interested in strategies to speed up the search, here are some clues.
- Note that each map of the game has 16 elements of values ranging from $2^1=2$ to $2^{11}=2048$. As a result, we can use a 64-bit unsigned integer (the data type of "unsigned long long") to represent a map, and each element is characterized by a 4-bit unsigned integer (with values ranging from 0 to 15) to represent its exponent.
- How to convert a map to a number in "unsigned long long" (and vice versa):
$$
\left[
\begin{matrix}
2 & 256 & 32 & 2\\
0 & 4 & 64 & 0\\
0 & 2 & 0 & 2048\\
8 & 512 & 0 & 0\\
\end{matrix}
\right]
=
\left[
\begin{matrix}
2^1 & 2^8 & 2^5 & 2^1\\
2^{-\infty} & 2^1 & 2^6 & x\\
2^{-\infty} & 2^1 & 2^{-\infty} & 2^{11}\\
2^3 & 2^9 & 2^{-\infty} & 2^{-\infty}\\
\end{matrix}
\right]
\Longrightarrow
\left[
\begin{matrix}
1 & 8 & 5 & 1\\
-\infty & 1 & 6 & -\infty\\
-\infty & 1 & -\infty & 11\\
3 & 9 & -\infty & -\infty\\
\end{matrix}
\right]
\Longrightarrow
A=
\left[
\begin{matrix}
1 & 8 & 5 & 1\\
0 & 1 & 6 & 0\\
0 & 1 & 0 & 11\\
3 & 9 & 0 & 0\\
\end{matrix}
\right]
$$
$$
=
\left[
\begin{matrix}
0001_2 & 1000_2 & 0101_2 & 0001_2\\
0000_2 & 0001_2 & 0110_2 & 0000_2\\
0000_2 & 0001_2 & 0000_2 & 1011_2\\
0011_2 & 1001_2 & 0000_2 & 0000_2\\
\end{matrix}
\right]
\Longrightarrow
\underbrace{0000}_{A[3,3]} \:
\underbrace{0000}_{A[3,2]} \:
\underbrace{1001}_{A[3,1]} \:
\underbrace{0011}_{A[3,0]} \:
\underbrace{1011}_{A[2,3]} \:
\underbrace{0000}_{A[2,2]} \:
\underbrace{0001}_{A[2,1]} \:
\underbrace{0000}_{A[2,0]} \:
\underbrace{0000}_{A[1,3]} \:
\underbrace{0110}_{A[1,2]} \:
\underbrace{0001}_{A[1,1]} \:
\underbrace{0000}_{A[1,0]} \:
\underbrace{0001}_{A[0,3]} \:
\underbrace{0101}_{A[0,2]} \:
\underbrace{1000}_{A[0,1]} \:
\underbrace{0001}_{A[0,0]}
$$
So the last number can be represented as an integer in "unsigned long long" format (64 bits). Note that you can shift $A[m,n]$ to the left by $4(4m+n)$ and do a summation to get the integer in "unsigned long long" format.
- TA will provide a function nextMap() to generate the next map based on the current map and the given action. To use the function, please add the following function prototype in your main program:
unsigned long long nextMap(unsigned long long map, int action);
where map is the current map, and action=0, 1, 2, 3 corresponding to the action of east, south, west, north, respectively. The function is available as a static library lib.a. It is quite easy to use the library by the following command:
g++ -std=c++11 -O2 myProgram.cpp lib.a
- Program usage: Your program should take standard input and generate standard output:
myProgram < input.txt > output.txt
Datasets
- Open test sets
