1// SPDX-License-Identifier: MIT
2// SPDX-FileCopyrightText: �� 2014 Maurits van der Schee
3
4/* Console version of the game "2048" for GNU/Linux */
5
6#include <common.h>
7#include <cli.h>
8#include <command.h>
9#include <rand.h>
10#include <linux/delay.h>
11
12#define SIZE 4
13static uint score;
14
15static void getColor(uint value, char *color, size_t length)
16{
17	u8 original[] = {
18		8, 255, 1, 255, 2, 255, 3, 255,
19		4, 255, 5, 255, 6, 255, 7, 255,
20		9, 0, 10, 0, 11, 0, 12, 0, 13,
21		0, 14, 0, 255, 0, 255, 0};
22	u8 *scheme = original;
23	u8 *background = scheme + 0;
24	u8 *foreground = scheme + 1;
25
26	if (value > 0) {
27		while (value >>= 1) {
28			if (background + 2 < scheme + sizeof(original)) {
29				background += 2;
30				foreground += 2;
31			}
32		}
33	}
34	snprintf(color, length, "\033[38;5;%d;48;5;%dm", *foreground,
35		 *background);
36}
37
38static void drawBoard(u16 board[SIZE][SIZE])
39{
40	int x, y;
41	char color[40], reset[] = "\033[0m";
42
43	printf("\033[H");
44	printf("2048.c %17d pts\n\n", score);
45
46	for (y = 0; y < SIZE; y++) {
47		for (x = 0; x < SIZE; x++) {
48			getColor(board[x][y], color, 40);
49			printf("%s", color);
50			printf("       ");
51			printf("%s", reset);
52		}
53		printf("\n");
54		for (x = 0; x < SIZE; x++) {
55			getColor(board[x][y], color, 40);
56			printf("%s", color);
57			if (board[x][y] != 0) {
58				char s[8];
59				s8 t;
60
61				snprintf(s, 8, "%u", board[x][y]);
62				t = 7 - strlen(s);
63				printf("%*s%s%*s", t - t / 2, "", s, t / 2, "");
64			} else {
65				printf("   ��   ");
66			}
67			printf("%s", reset);
68		}
69		printf("\n");
70		for (x = 0; x < SIZE; x++) {
71			getColor(board[x][y], color, 40);
72			printf("%s", color);
73			printf("       ");
74			printf("%s", reset);
75		}
76		printf("\n");
77	}
78	printf("\n");
79	printf("        ���, ���, ���, ��� or q        \n");
80	printf("\033[A");
81}
82
83static int8_t findTarget(u16 array[SIZE], int x, int stop)
84{
85	int t;
86
87	/* if the position is already on the first, don't evaluate */
88	if (x == 0)
89		return x;
90	for (t = x - 1; t >= 0; t--) {
91		if (array[t]) {
92			if (array[t] != array[x]) {
93				/* merge is not possible, take next position */
94				return t + 1;
95			}
96			return t;
97		}
98
99		/* we should not slide further, return this one */
100		if (t == stop)
101			return t;
102	}
103	/* we did not find a */
104	return x;
105}
106
107static bool slideArray(u16 array[SIZE])
108{
109	bool success = false;
110	int x, t, stop = 0;
111
112	for (x = 0; x < SIZE; x++) {
113		if (array[x] != 0) {
114			t = findTarget(array, x, stop);
115			/*
116			 * if target is not original position, then move or
117			 * merge
118			 */
119			if (t != x) {
120				/*
121				 * if target is not zero, set stop to avoid
122				 * double merge
123				 */
124				if (array[t]) {
125					score += array[t] + array[x];
126					stop = t + 1;
127				}
128				array[t] += array[x];
129				array[x] = 0;
130				success = true;
131			}
132		}
133	}
134	return success;
135}
136
137static void rotateBoard(u16 board[SIZE][SIZE])
138{
139	s8 i, j, n = SIZE;
140	int tmp;
141
142	for (i = 0; i < n / 2; i++) {
143		for (j = i; j < n - i - 1; j++) {
144			tmp = board[i][j];
145			board[i][j] = board[j][n - i - 1];
146			board[j][n - i - 1] = board[n - i - 1][n - j - 1];
147			board[n - i - 1][n - j - 1] = board[n - j - 1][i];
148			board[n - j - 1][i] = tmp;
149		}
150	}
151}
152
153static bool moveUp(u16 board[SIZE][SIZE])
154{
155	bool success = false;
156	int x;
157
158	for (x = 0; x < SIZE; x++)
159		success |= slideArray(board[x]);
160
161	return success;
162}
163
164static bool moveLeft(u16 board[SIZE][SIZE])
165{
166	bool success;
167
168	rotateBoard(board);
169	success = moveUp(board);
170	rotateBoard(board);
171	rotateBoard(board);
172	rotateBoard(board);
173	return success;
174}
175
176static bool moveDown(u16 board[SIZE][SIZE])
177{
178	bool success;
179
180	rotateBoard(board);
181	rotateBoard(board);
182	success = moveUp(board);
183	rotateBoard(board);
184	rotateBoard(board);
185	return success;
186}
187
188static bool moveRight(u16 board[SIZE][SIZE])
189{
190	bool success;
191
192	rotateBoard(board);
193	rotateBoard(board);
194	rotateBoard(board);
195	success = moveUp(board);
196	rotateBoard(board);
197	return success;
198}
199
200static bool findPairDown(u16 board[SIZE][SIZE])
201{
202	bool success = false;
203	int x, y;
204
205	for (x = 0; x < SIZE; x++) {
206		for (y = 0; y < SIZE - 1; y++) {
207			if (board[x][y] == board[x][y + 1])
208				return true;
209		}
210	}
211
212	return success;
213}
214
215static int16_t countEmpty(u16 board[SIZE][SIZE])
216{
217	int x, y;
218	int count = 0;
219
220	for (x = 0; x < SIZE; x++) {
221		for (y = 0; y < SIZE; y++) {
222			if (board[x][y] == 0)
223				count++;
224		}
225	}
226	return count;
227}
228
229static bool gameEnded(u16 board[SIZE][SIZE])
230{
231	bool ended = true;
232
233	if (countEmpty(board) > 0)
234		return false;
235	if (findPairDown(board))
236		return false;
237	rotateBoard(board);
238	if (findPairDown(board))
239		ended = false;
240	rotateBoard(board);
241	rotateBoard(board);
242	rotateBoard(board);
243
244	return ended;
245}
246
247static void addRandom(u16 board[SIZE][SIZE])
248{
249	int x, y;
250	int r, len = 0;
251	u16 n, list[SIZE * SIZE][2];
252
253	for (x = 0; x < SIZE; x++) {
254		for (y = 0; y < SIZE; y++) {
255			if (board[x][y] == 0) {
256				list[len][0] = x;
257				list[len][1] = y;
258				len++;
259			}
260		}
261	}
262
263	if (len > 0) {
264		r = rand() % len;
265		x = list[r][0];
266		y = list[r][1];
267		n = ((rand() % 10) / 9 + 1) * 2;
268		board[x][y] = n;
269	}
270}
271
272static int test(void)
273{
274	u16 array[SIZE];
275	u16 data[] = {
276		0, 0, 0, 2,	2, 0, 0, 0,
277		0, 0, 2, 2,	4, 0, 0, 0,
278		0, 2, 0, 2,	4, 0, 0, 0,
279		2, 0, 0, 2,	4, 0, 0, 0,
280		2, 0, 2, 0,	4, 0, 0, 0,
281		2, 2, 2, 0,	4, 2, 0, 0,
282		2, 0, 2, 2,	4, 2, 0, 0,
283		2, 2, 0, 2,	4, 2, 0, 0,
284		2, 2, 2, 2,	4, 4, 0, 0,
285		4, 4, 2, 2,	8, 4, 0, 0,
286		2, 2, 4, 4,	4, 8, 0, 0,
287		8, 0, 2, 2,	8, 4, 0, 0,
288		4, 0, 2, 2,	4, 4, 0, 0
289	};
290	u16 *in, *out;
291	u16 t, tests;
292	int i;
293	bool success = true;
294
295	tests = (sizeof(data) / sizeof(data[0])) / (2 * SIZE);
296	for (t = 0; t < tests; t++) {
297		in = data + t * 2 * SIZE;
298		out = in + SIZE;
299		for (i = 0; i < SIZE; i++)
300			array[i] = in[i];
301		slideArray(array);
302		for (i = 0; i < SIZE; i++) {
303			if (array[i] != out[i])
304				success = false;
305		}
306		if (!success) {
307			for (i = 0; i < SIZE; i++)
308				printf("%d ", in[i]);
309			printf(" = > ");
310			for (i = 0; i < SIZE; i++)
311				printf("%d ", array[i]);
312			printf("expected ");
313			for (i = 0; i < SIZE; i++)
314				printf("%d ", in[i]);
315			printf(" = > ");
316			for (i = 0; i < SIZE; i++)
317				printf("%d ", out[i]);
318			printf("\n");
319			break;
320		}
321	}
322	if (success)
323		printf("All %u tests executed successfully\n", tests);
324
325	return !success;
326}
327
328static int do_2048(struct cmd_tbl *cmdtp, int flag, int argc,
329		   char *const argv[])
330{
331	struct cli_ch_state cch_s, *cch = &cch_s;
332	u16 board[SIZE][SIZE];
333	bool success;
334
335	if (argc == 2 && strcmp(argv[1], "test") == 0)
336		return test();
337
338	score = 0;
339
340	printf("\033[?25l\033[2J\033[H");
341
342	memset(board, 0, sizeof(board));
343	addRandom(board);
344	addRandom(board);
345	drawBoard(board);
346	cli_ch_init(cch);
347	while (true) {
348		int c;
349
350		c = cli_ch_process(cch, 0);
351		if (!c) {
352			c = getchar();
353			c = cli_ch_process(cch, c);
354		}
355		switch (c) {
356		case CTL_CH('b'): /* left arrow */
357			success = moveLeft(board);
358			break;
359		case CTL_CH('f'): /* right arrow */
360			success = moveRight(board);
361			break;
362		case CTL_CH('p'):/* up arrow */
363			success = moveUp(board);
364			break;
365		case CTL_CH('n'): /* down arrow */
366			success = moveDown(board);
367			break;
368		default:
369			success = false;
370		}
371		if (success) {
372			drawBoard(board);
373			mdelay(150);
374			addRandom(board);
375			drawBoard(board);
376			if (gameEnded(board)) {
377				printf("         GAME OVER          \n");
378				break;
379			}
380		}
381		if (c == 'q') {
382			printf("            QUIT            \n");
383			break;
384		}
385	}
386
387	printf("\033[?25h");
388
389	return 0;
390}
391
392U_BOOT_CMD(
393	2048,	2,	1,	do_2048,
394	"The 2048 game",
395	"Use your arrow keys to move the tiles. When two tiles with "
396	"the same number touch, they merge into one!"
397);
398