2048/2048.c

/*
 * 2048, by afrangry
 * Copyright (c) 2023 Afrangry Hill <donotcalllist@privacyrequired.com>
 * This work is free. You can redistribute it and/or modify it under the
 * terms of the Do What The Fuck You Want To Public License, Version 2,
 * as published by Sam Hocevar. See the COPYING file for more details.
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

#if defined(MSDOS) || defined(_WIN16)
#define HAVE_CONIO_H 1
#elif defined(_WIN32) || defined(_WIN64)
#define HAVE_WINDOWS_H 1
#elif defined(__unix) || defined(__unix__) || defined(__APPLE__) || \
	defined(__MACH__)
#include <unistd.h>
#define HAVE_TERMIOS_H 1
#include <termios.h>
static struct termios old = { 0, 0, 0, 0, '\0', 0, 0, 0 };
static struct termios new = { 0, 0, 0, 0, '\0', 0, 0, 0 };
#define HAVE_ANSI_ESCAPE_CODE 1
#endif

#if defined(HAVE_CONIO_H)
#include <conio.h>
#endif

#if defined(HAVE_WINDOWS_H)
#include <windows.h>
#endif

#define N 4
typedef struct arr_t {
	int x; /* position on x-axis from left to right */
	int y; /* position on y-axis from top to bottom */
} arr_t; /* position in a 2D map with x and y value */
enum ctrl { UP, LEFT, DOWN, RIGHT, QUIT, UNDEFINED };

static int hiscore = 0; /* highest score of user */
static int hinum = 0; /* highest number of user */
static int score = 0; /* score of current game */
static int number = 0; /* highest number of current game */

static int getindex(int *, int, int *) /*@*/;
static int *arr2ptr(/*@returned@*/ int *, arr_t) /*@*/;
static arr_t ptr2arr(int *, int *) /*@*/;
/*@unused@*/ static int
tty_break(void) /*@globals old, new@*/ /*@modifies new@*/;
static int tty_getch(void) /*@*/;
/*@unused@*/ static int tty_fix(void) /*@globals old*/ /*@modifies nothing@*/;
static void tty_cls(void) /*@globals old, new@*/ /*@modifies new@*/;
static void map_init(int *map) /*@modifies *map@*/;
static void cpymap(int *dst, int *) /*@modifies *dst@*/;
static void trans(int *map, int) /*@modifies *map@*/;
static void prtwelcome(void) /*@globals fileSystem, hiscore, hinum@*/
	/*@modifies fileSystem@*/;
static int moveup1(int *map, int *ptr) /*@modifies *map, *ptr@*/;
static void asgn_if_src_true(int *dst, int) /*@modifies *dst@*/;
static int moveup(int *map) /*@modifies *map@*/;
static int eat1(int *map, int *ptr) /*@globals score@*/
	/*@modifies *map, *ptr, score@*/;
static int eat(int *map) /*@globals score@*/ /*@modifies *map, score@*/;
static int upeat(int *map) /*@globals score@*/ /*@modifies *map, score@*/;
static void puttb(void) /*@globals fileSystem@*/ /*@modifies fileSystem@*/;
static void putm(void) /*@globals fileSystem@*/ /*@modifies fileSystem@*/;
static void putnumline(int *, int) /*@globals fileSystem@*/
	/*@modifies fileSystem@*/;
static void prt(int *) /*@globals fileSystem@*/ /*@modifies fileSystem@*/;
static int genrnd(int *map) /*@globals internalState@*/
	/*@modifies internalState, *map@*/;
static int calhinum(int *) /*@*/;
static int same_as_follower(int *, int *) /*@*/;
static int is_over(int *) /*@*/;
static enum ctrl input_to_ctrl(char) /*@*/;
static int ctrl_to_trans(enum ctrl) /*@*/;
static int turn(int *map) /*@globals internalState, fileSystem, score@*/
	/*@modifies internalState, fileSystem, score, *map@*/;
static void game(int *map) /*@globals internalState, fileSystem, score@*/
	/*@modifies internalState, fileSystem, score, *map@*/;
static void gg(int *)
	/*@globals internalState, fileSystem, number, hinum, score, hiscore@*/
	/*@modifies internalState, fileSystem, number, hinum, score, hiscore@*/;

/*
 * get index of pointer
 * 'arr': pointer to first element of array
 * 'arrsize': size of array
 * 'ptr': pointer
 */
static int /* return index of pinter, -1 when failed */
getindex(int *arr, int arrsize, int *ptr) /*@*/
{
	int i = 0;

	for (i = 0; i < arrsize; i++) {
		if (&arr[i] == ptr) {
			return i;
		}
	}
	return -1;
}

/*
 * convert arr type to pointer in array
 * 'start': pointer to first element of array
 * 'arr': arr to be converted
 */
static int * /* return pointer to given arr */
arr2ptr(/*@returned@*/ int *start, arr_t arr) /*@*/
{
	return &start[arr.x + N * arr.y];
}

/*
 * convert pointer in array to arr type
 * 'start': pointer to first element of array
 * 'ptr': pointer to be converted
 */
static arr_t /* return arr of given pointer */
ptr2arr(int *start, int *ptr) /*@*/
{
	arr_t arr = { 0, 0 }; /* arr of given tile */
	int ptrindex =
		getindex(start, N * N, ptr); /* index of pointer in array */

	arr.x = ptrindex % N;
	arr.y = ptrindex / N;
	return arr;
}

/*
 * changes terminal behavior to not wait for enter, not echo
 */
static int /* return 0 on success, -1 otherwise */
tty_break(void) /*@globals new, old@*/ /*@modifies new@*/
{
#if defined(HAVE_CONIO_H)
	return 0;
#elif defined(HAVE_WINDOWS_H)
	return 0;
#elif defined(HAVE_TERMIOS_H)
	if (tcgetattr(0, &old) == -1) {
		return -1;
	}
	new = old;
	new.c_lflag &= ~ICANON;
	new.c_lflag &= ~ECHO;
	if (tcsetattr(0, TCSANOW, &new) == -1) {
		return -1;
	}
	return 0;
#else
	return 0;
#endif
}

/*
 * get single character without waiting for enter or echoing
 * equivalent to getchar() if not supported by system
 */
static int /* return input character, EOF on failure */
tty_getch(void) /*@globals old, new*/ /*@modifies new@*/
{
#if defined(HAVE_CONIO_H)
	return getch();
#elif defined(HAVE_WINDOWS_H)
	HANDLE hStdin = GetStdHandle(STD_INPUT_HANDLE);
	INPUT_RECORD irInputRecord;
	DWORD dwEventsRead;
	CHAR cChar;

	while (ReadConsoleInputA(hStdin, &irInputRecord, 1,
				 &dwEventsRead)) /* Read key press */
		if (irInputRecord.EventType == KEY_EVENT &&
		    irInputRecord.Event.KeyEvent.wVirtualKeyCode != VK_SHIFT &&
		    irInputRecord.Event.KeyEvent.wVirtualKeyCode != VK_MENU &&
		    irInputRecord.Event.KeyEvent.wVirtualKeyCode !=
			    VK_CONTROL) {
			cChar = irInputRecord.Event.KeyEvent.uChar.AsciiChar;
			ReadConsoleInputA(
				hStdin, &irInputRecord, 1,
				&dwEventsRead); /* Read key release */
			return cChar;
		}
	return EOF;
#elif defined(HAVE_TERMIOS_H)
	int ch;

	if (tty_break() == -1) {
		return EOF;
	}
	ch = getchar();
	if (tty_fix() == -1) {
		return EOF;
	}
	return ch;
#else
	return getchar();
#endif
}

/*
 * restore terminal behavior to original state
 */
static int /* return 0 on success, -1 otherwise */
tty_fix(void) /*@globals old*/ /*@modifies nothing@*/
{
#if defined(HAVE_CONIO_H)
	return 0;
#elif defined(HAVE_WINDOWS_H)
	return 0;
#elif defined(HAVE_TERMIOS_H)
	return tcsetattr(0, TCSANOW, &old);
#else
	return 0;
#endif
}

/*
 * clear terminal screen
 */
static void
tty_cls(void) /*@globals fileSystem@*/ /*@modifies fileSystem@*/
{
#if defined(HAVE_CONIO_H)
	return clrscr();
#elif defined(HAVE_WINDOWS_H)
	HANDLE hStdOut;
	CONSOLE_SCREEN_BUFFER_INFO csbi;
	DWORD count;
	DWORD cellCount;
	COORD homeCoords = { 0, 0 };

	hStdOut = GetStdHandle(STD_OUTPUT_HANDLE);
	if (hStdOut == INVALID_HANDLE_VALUE) {
		return;
	}

	/* Get the number of cells in the current buffer */
	if (!GetConsoleScreenBufferInfo(hStdOut, &csbi)) {
		return;
	}
	cellCount = csbi.dwSize.X * csbi.dwSize.Y;

	/* Fill the entire buffer with spaces */
	if (!FillConsoleOutputCharacter(hStdOut, (TCHAR)' ', cellCount,
					homeCoords, &count)) {
		return;
	}

	/* Fill the entire buffer with the current colors and attributes */
	if (!FillConsoleOutputAttribute(hStdOut, csbi.wAttributes, cellCount,
					homeCoords, &count)) {
		return;
	}

	/* Move the cursor home */
	SetConsoleCursorPosition(hStdOut, homeCoords);
#elif defined(HAVE_ANSI_ESCAPE_CODE)
	printf("\033[2J");
	printf("\033[%d;%dH", 1, 1);
#else
	return;
#endif
}

/*
 * fill map with 0
 */
static void
map_init(int *map) /*@modifies *map@*/
{
	int i = 0;
	int j = 0;

	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			arr_t tmparr = { 0, 0 }; /* temp arr */

			tmparr.x = j;
			tmparr.y = i;
			*arr2ptr(map, tmparr) = 0;
		}
	}
}

/*
 * copy source map to destination map
 * 'dst': pointer to first element of destination map
 * 'src': pointer to first element of source map
 */
static void
cpymap(int *dst, int *src) /*@modifies *dst@*/
{
	int i = 0;
	int j = 0;

	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			*dst = *src;
			src++;
			dst++;
		}
	}
}

/*
 * rotate the map clockwise for a given time, persumes square map
 * 'map': pointer to first element of map
 * 'times': given time to rotate
 */
static void
trans(int *map, int times) /*@modifies *map@*/
{
	int tmp[N][N] = { { 0 } }; /* temp map */
	int *ptrtmp = &tmp[0][0]; /* pointer to temp map */
	int *curmap = map; /* current pointer to temp map, iteration */
	int i = 0;
	int j = 0;

	if (times == 0) {
		return;
	}
	map_init(ptrtmp);
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			arr_t maparr = ptr2arr(map, curmap); /* current arr of
								map */
			arr_t tmparr = { 0, 0 }; /* current arr of temp map */

			tmparr.x = N - maparr.y - 1;
			tmparr.y = maparr.x;
			*arr2ptr(ptrtmp, tmparr) = *curmap;
			curmap++;
		}
	}
	cpymap(map, ptrtmp);
	trans(map, times - 1);
}

/*
 * print welcome screen
 */
static void
prtwelcome(void) /*@globals fileSystem, hiscore, hinum@*/
/*@modifies fileSystem@*/
{
	(void)puts("-------------------------");
	(void)puts("|         2048          |");
	(void)puts("|-----------------------|");
	(void)printf("|  High Score: %8d |\n", hiscore);
	(void)printf("| High Number: %8d |\n", hinum);
	(void)puts("|-----------------------|");
	(void)puts("|    w=Up     s=Down    |");
	(void)puts("| a=Left d=Right q=Quit |");
	(void)puts("-------------------------");
	(void)puts("Press space to continue... ");
}

/*
 * move given tile up until border or another non-empty tile
 * 'map': pointer to first element of map
 * 'ptr': pointer to tile to be moved
 */
static int /* return 1 if change is made, 0 otherwise */
moveup1(int *map, int *ptr) /*@modifies *map, *ptr@*/
{
	arr_t curarr = ptr2arr(map, ptr); /* arr of ptr */
	arr_t tmp = { 0, 0 }; /* temp arr for tile up 1 of curarr */
	int *ptrtmp = NULL; /* pointer to tile up 1 of curarr */

	if (curarr.y == 0) {
		return 0;
	}
	if (*ptr == 0) {
		return 0;
	}
	tmp.x = curarr.x;
	tmp.y = curarr.y - 1;
	ptrtmp = arr2ptr(map, tmp);
	if (*ptrtmp > 0) {
		return 0;
	}
	*ptrtmp = *ptr;
	*ptr = 0;
	(void)moveup1(map, ptrtmp);
	return 1;
}

/*
 * assign src to dst if src is true, otherwise do nothing
 * 'dst': pointer to destination to be assigned
 * 'src': source
 */
static void
asgn_if_src_true(int *dst, int src) /*@modifies *dst@*/
{
	if (src == 1) {
		*dst = src;
	}
}

/*
 * recursively move all tiles up until border or non-empty tile
 * 'map': pointer to first element of map
 */
static int /* return 1 if change is made, 0 otherwise */
moveup(int *map) /*@modifies *map@*/
{
	int flag = 0; /* 1 if change is made, 0 otherwise */
	int i = 0;
	int j = 0;

	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			arr_t tmp = { 0, 0 }; /* temp arr for current tile */
			int *ptrtmp = NULL; /* pointer to current tile */

			tmp.x = i;
			tmp.y = j;
			ptrtmp = arr2ptr(map, tmp);
			asgn_if_src_true(&flag, moveup1(map, ptrtmp));
		}
	}
	return flag;
}

/*
 * if tile up 1 of given tile is the same as given tile,
 * double tile up 1 and clear given tile
 * 'map': pointer to first element of map
 * 'ptr': pointer to tile to eat up 1
 */
static int /* return 1 if change is made, 0 otherwise */
eat1(int *map, int *ptr) /*@globals score@*/ /*@modifies *map, *ptr, score@*/
{
	arr_t curarr = ptr2arr(map, ptr); /* arr of ptr */
	int *ptrcur = ptr; /* ptr, redundant */
	arr_t uparr = { 0, 0 }; /* arr of tile up 1 of curarr */
	int *ptrup = NULL; /* pointer tile up 1 of curarr */

	if (*ptr == 0) {
		return 0;
	}
	uparr.x = curarr.x;
	uparr.y = curarr.y - 1;
	ptrup = arr2ptr(map, uparr);
	if (*ptrcur != *ptrup) {
		return 0;
	}
	*ptrup += *ptrcur;
	*ptrcur = 0;
	score += *ptrup;
	return 1;
}

/*
 * recursively eat all tiles up, tiles that have eaten do not eat again.
 * start from top to bottom
 * 'map': pointer to first element of map
 */
static int /* return 1 if change is made, 0 otherwise */
eat(int *map) /*@globals score@*/ /*@modifies *map, score@*/
{
	int flag = 0; /* 1 if change is made, 0 otherwise */
	int i = 0;
	int j = 0;

	for (i = 0; i < N; i++) {
		for (j = 1; j < N; j++) {
			arr_t tmp = { 0, 0 }; /* temp arr of current tile */
			int *ptrtmp = NULL; /* temp pointer to current tile */

			tmp.x = i;
			tmp.y = j;
			ptrtmp = arr2ptr(map, tmp);
			asgn_if_src_true(&flag, eat1(map, ptrtmp));
		}
	}
	return flag;
}

/*
 * one operation of moving up and eating tiles
 * 'map': pointer to first element of map
 */
static int /* return 1 if change is made, 0 otherwise */
upeat(int *map) /*@globals score@*/ /*@modifies *map, score@*/
{
	int haschanged = 0; /* 1 if change is made, 0 otherwise */

	asgn_if_src_true(&haschanged, moveup(map));
	asgn_if_src_true(&haschanged, eat(map));
	asgn_if_src_true(&haschanged, moveup(map));
	return haschanged;
}

/*
 * print top and bottom border of map
 */
static void
puttb(void) /*@globals fileSystem@*/ /*@modifies fileSystem@*/
{
	int i = 0;

	for (i = 0; i < N * 6 + 1; i++) {
		(void)putchar('-');
	}
	(void)putchar('\n');
}

/*
 * print middle border of map
 */
static void
putm(void) /*@globals fileSystem@*/ /*@modifies fileSystem@*/
{
	int i = 0;

	(void)putchar('|');
	for (i = 0; i < N * 6 - 1; i++) {
		(void)putchar('-');
	}
	(void)putchar('|');
	(void)putchar('\n');
}

/*
 * print given row of map with numbers
 * 'map': pointer to first element of map
 * 'line': row to print
 */
static void
putnumline(int *map, int line) /*@globals fileSystem@*/
/*@modifies fileSystem@*/
{
	int i = 0;

	(void)putchar('|');
	for (i = 0; i < N; i++) {
		arr_t tmp = { 0, 0 }; /* temp arr of current tile */
		int *ptrtmp = NULL; /* pointer to current tile */

		tmp.x = i;
		tmp.y = line;
		ptrtmp = arr2ptr(map, tmp);
		if (*ptrtmp != 0) {
			(void)printf("%5d|", *ptrtmp);
		} else {
			(void)printf("     |");
		}
	}
	(void)putchar('\n');
}

/*
 * print map
 * 'map': pointer to first element of map
 */
static void
prt(int *map) /*@globals fileSystem@*/ /*@modifies fileSystem@*/
{
	int i = 0;

	puttb();
	putnumline(map, 0);
	for (i = 1; i < N; i++) {
		putm();
		putnumline(map, i);
	}
	puttb();
}

/*
 * randomly generate 2 or 4 in empty tile in map, 90% 2, 10% 4
 * 'map': pointer to first element of map
 */
static int /* return 1 if no empty tiles left, 0 otherwise */
genrnd(int *map) /*@globals internalState@*/ /*@modifies internalState, *map@*/
{
	int rnd = rand() % 10 == 0 ? 4 : 2; /* random number, 90% 2 and 10% 4
					     */
	int cnt = 0; /* count of empty tiles in map */
	arr_t empty[N * N] = { { 0, 0 } }; /* array of arr of empty tiles in
					      map */
	int i = 0;
	int j = 0;

	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			arr_t tmp = { 0, 0 }; /* temp arr of current tile */
			int *ptrtmp = NULL; /* pointer to current tile */

			tmp.x = j;
			tmp.y = i;
			ptrtmp = arr2ptr(map, tmp);
			if (*ptrtmp > 0) {
				/*@innercontinue@*/
				continue;
			}
			empty[cnt] = tmp;
			cnt++;
		}
	}
	if (cnt == 0) {
		return 1;
	}
	*arr2ptr(map, empty[rand() % cnt]) = rnd;
	return 0;
}

/*
 * calculate highest number of current game
 * 'map': pointer to first element of map
 */
static int /* return highest number of current game */
calhinum(int *map) /*@*/
{
	int num = 0; /* current highest number */
	int i = 0;
	int j = 0;

	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			arr_t tmp = { 0, 0 }; /* temp arr of current tile */
			int *ptrtmp = NULL; /* temp pointer to current tile */

			tmp.x = j;
			tmp.y = i;
			ptrtmp = arr2ptr(map, tmp);
			if (*ptrtmp <= num) {
				/*@innercontinue@*/
				continue;
			}
			num = *ptrtmp;
		}
	}
	return num;
}

/*
 * check if given tile is the same number as adjacent right or down tile
 * 'map': pointer to first element of map
 * 'ptr': pointer to given tile
 */
static int /* return 1 if the same, 0 otherwise */
same_as_follower(int *map, int *ptr) /*@*/
{
	arr_t tmp = ptr2arr(map, ptr); /* temp arr of given tile */

	if (tmp.x < N - 1) {
		arr_t tmpright = { 0, 0 }; /* temp arr of right of given tile
					    */

		tmpright.x = tmp.x + 1;
		tmpright.y = tmp.y;
		if (*ptr == *arr2ptr(map, tmpright)) {
			return 1;
		}
	}
	if (tmp.y < N - 1) {
		arr_t tmpdown = { 0, 0 }; /* temp arr of down of given tile */

		tmpdown.x = tmp.x;
		tmpdown.y = tmp.y + 1;
		if (*ptr == *arr2ptr(map, tmpdown)) {
			return 1;
		}
	}
	return 0;
}

/*
 * check if game is over
 * 'map': pointer to first element of map
 */
static int /* return 1 if game is over, 0 otherwise */
is_over(int *map) /*@*/
{
	int i = 0;
	int j = 0;

	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			arr_t tmp = { 0, 0 }; /* temp arr of current tile */
			int *ptrtmp = NULL; /* temp pointer to current tile */

			tmp.x = j;
			tmp.y = i;
			ptrtmp = arr2ptr(map, tmp);
			if (*ptrtmp == 0) {
				return 0;
			}
			if (same_as_follower(map, ptrtmp) == 1) {
				return 0;
			}
		}
	}
	return 1;
}

/*
 * convert input character to ctrl enum
 * 'input': input character
 */
static enum ctrl /* return ctrl */
input_to_ctrl(char input) /*@*/
{
	switch (input) {
	case 'w':
		return UP;
	case 'a':
		return LEFT;
	case 's':
		return DOWN;
	case 'd':
		return RIGHT;
	case 'q':
		return QUIT;
	default:
		return UNDEFINED;
	}
}

/*
 * convert ctrl enum to rotation time
 * 'ctrl': input character
 */
static int /* return rotation time, -1 if ctrl is UNDEFINED or QUIT */
ctrl_to_trans(enum ctrl ctrl) /*@*/
{
	switch (ctrl) {
	case UP:
		return 0;
	case LEFT:
		return 1;
	case DOWN:
		return 2;
	case RIGHT:
		return 3;
	default:
		return -1;
	}
}

/*
 * one turn of game
 * 'map': pointer to first element of map
 */
static int /* return 1 if ended, 0 otherwise */
turn(int *map) /*@globals internalState, fileSystem, score@*/
/*@modifies internalState, fileSystem, score, *map@*/
{
	int haschanged = 0; /* 1 if change is made, 0 otherwise */
	char input = (char)tty_getch(); /* input character */
	enum ctrl tmp = input_to_ctrl(input); /* ctrl enum */
	int times = 0; /* rotation time */

	if (tmp == UNDEFINED) {
		return 0;
	}
	if (tmp == QUIT) {
		return 1;
	}
	times = ctrl_to_trans(tmp);
	trans(map, times);
	haschanged = upeat(map);
	trans(map, (4 - (int)tmp) % 4);
	if (haschanged == 0) {
		return 0;
	}
	tty_cls();
	(void)genrnd(map);
	prt(map);
	return 0;
}

/*
 * one game
 * 'map': pointer to first element of map
 */
static void
game(int *map) /*@globals internalState, fileSystem, score@*/
/*@modifies internalState, fileSystem, score, *map@*/
{
	int end = 0; /* 1 if game has ended, 0 otherwise */

	(void)genrnd(map);
	(void)genrnd(map);
	tty_cls();
	prt(map);
	while (end == 0 && is_over(map) == 0) {
		end = turn(map);
	}
}

/*
 * print gameover screen and update highest number and highest score
 * 'map': pointer to first element of map
 */
static void
gg(int *map)
/*@globals internalState, fileSystem, number, hinum, score, hiscore@*/
/*@modifies internalState, fileSystem, number, hinum, score, hiscore@*/
{
	number = calhinum(map);
	if (number > hinum) {
		hinum = number;
	}
	if (score > hiscore) {
		hiscore = score;
	}
	(void)printf(
		"Score: %8d High Number: %5d Press space to continue...\n",
		score, number);
}

int
main(void)
/*@globals internalState, fileSystem, number, hinum, score, hiscore@*/
/*@modifies internalState, fileSystem, number, hinum, score, hiscore@*/
{
	int map[N][N] = { { 0 } }; /* map of tiles */
	int *ptrmap = &map[0][0]; /* pointer to first element of map */

	map_init(ptrmap);
	srand((unsigned int)time(NULL));
	do {
		map_init(ptrmap);
		tty_cls();
		prtwelcome();
		if ((char)tty_getch() != ' ') {
			break;
		}
		game(ptrmap);
		gg(ptrmap);
	} while ((char)tty_getch() == ' ');
	tty_cls();
	return 0;
}