Add freecell

3 files changed, 409 insertions, 10 deletions

diff --git a/Makefile b/Makefile
index 932d30f..f8c597c 100644
--- a/Makefile
+++ b/Makefile
@@ -8,6 +8,7 @@ LDLIBS = -lcurses
 -include config.mk
 
 OBJS += 2048.o
+OBJS += freecell.o
 OBJS += play.o
 OBJS += snake.o
 
diff --git a/freecell.c b/freecell.c
new file mode 100644
index 0000000..0334edc
--- /dev/null
+++ b/freecell.c
@@ -0,0 +1,389 @@
+/* Copyright (C) 2019, 2021  C. McEnroe <june@causal.agency>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <assert.h>
+#include <ctype.h>
+#include <curses.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <termios.h>
+#include <time.h>
+#include <unistd.h>
+
+typedef unsigned uint;
+typedef unsigned char byte;
+
+typedef byte Card;
+enum {
+	A = 1,
+	J = 11,
+	Q = 12,
+	K = 13,
+	Rank = 0x0F,
+	Suit = 0x30,
+	Color = 0x10,
+	Club = 0x00,
+	Diamond = 0x10,
+	Spade = 0x20,
+	Heart = 0x30,
+};
+
+enum { StackCap = 52 };
+struct Stack {
+	byte len;
+	Card cards[StackCap];
+};
+static void push(struct Stack *stack, Card card) {
+	assert(stack->len < StackCap);
+	stack->cards[stack->len++] = card;
+}
+static Card pop(struct Stack *stack) {
+	if (!stack->len) return 0;
+	return stack->cards[--stack->len];
+}
+static Card peek(struct Stack *stack) {
+	if (!stack->len) return 0;
+	return stack->cards[stack->len-1];
+}
+
+enum {
+	Foundation,
+	Cell = Foundation + 4,
+	Tableau = Cell + 4,
+	Stacks = Tableau + 8,
+};
+static struct Stack stacks[Stacks];
+
+struct Move {
+	byte dst;
+	byte src;
+};
+
+enum { QCap = 16 };
+static struct {
+	struct Move moves[QCap];
+	uint r, w, u;
+} q;
+static void enq(byte dst, byte src) {
+	q.moves[q.w % QCap].dst = dst;
+	q.moves[q.w % QCap].src = src;
+	q.w++;
+}
+static void deq(void) {
+	struct Move move = q.moves[q.r++ % QCap];
+	push(&stacks[move.dst], pop(&stacks[move.src]));
+}
+static void undo(void) {
+	uint len = q.w - q.u;
+	if (!len || len > QCap) return;
+	for (uint i = len-1; i < len; --i) {
+		struct Move move = q.moves[(q.u+i) % QCap];
+		push(&stacks[move.src], pop(&stacks[move.dst]));
+	}
+	q.r = q.w = q.u;
+}
+
+// https://rosettacode.org/wiki/Deal_cards_for_FreeCell
+static uint lcgState;
+static uint lcg(void) {
+	lcgState = (214013 * lcgState + 2531011) % (1 << 31);
+	return lcgState >> 16;
+}
+static void deal(uint game) {
+	lcgState = game;
+	struct Stack deck = {0};
+	for (Card i = A; i <= K; ++i) {
+		push(&deck, Club | i);
+		push(&deck, Diamond | i);
+		push(&deck, Heart | i);
+		push(&deck, Spade | i);
+	}
+	for (uint stack = 0; deck.len; ++stack) {
+		uint i = lcg() % deck.len;
+		Card card = deck.cards[i];
+		deck.cards[i] = deck.cards[--deck.len];
+		push(&stacks[Tableau + stack%8], card);
+	}
+}
+
+static bool win(void) {
+	for (uint i = Foundation; i < Cell; ++i) {
+		if (stacks[i].len != 13) return false;
+	}
+	return true;
+}
+
+static bool valid(uint dst, Card card) {
+	Card top = peek(&stacks[dst]);
+	if (dst < Cell) {
+		if (!top) return (card & Rank) == A;
+		return (card & Suit) == (top & Suit)
+			&& (card & Rank) == (top & Rank) + 1;
+	}
+	if (!top) return true;
+	if (dst >= Tableau) {
+		return (card & Color) != (top & Color)
+			&& (card & Rank) == (top & Rank) - 1;
+	}
+	return false;
+}
+
+static void autoEnq(void) {
+	Card min[] = { K, K };
+	for (uint i = Cell; i < Stacks; ++i) {
+		for (uint j = 0; j < stacks[i].len; ++j) {
+			Card card = stacks[i].cards[j];
+			if ((card & Rank) < min[!!(card & Color)]) {
+				min[!!(card & Color)] = card & Rank;
+			}
+		}
+	}
+	for (uint src = Cell; src < Stacks; ++src) {
+		Card card = peek(&stacks[src]);
+		if (!card) continue;
+		if (min[!(card & Color)] < (card & Rank)-1) continue;
+		for (uint dst = Foundation; dst < Cell; ++dst) {
+			if (valid(dst, card)) {
+				enq(dst, src);
+				return;
+			}
+		}
+	}
+}
+
+static void moveSingle(uint dst, uint src) {
+	if (!valid(dst, peek(&stacks[src]))) return;
+	q.u = q.w;
+	enq(dst, src);
+}
+
+static uint freeCells(uint cells[static Stacks], uint dst) {
+	uint len = 0;
+	for (uint i = Cell; i < Stacks; ++i) {
+		if (i == dst) continue;
+		if (!stacks[i].len) cells[len++] = i;
+	}
+	return len;
+}
+
+static uint moveDepth(uint src) {
+	struct Stack stack = stacks[src];
+	if (stack.len < 2) return stack.len;
+	uint n = 1;
+	for (uint i = stack.len-2; i < stack.len; --i, ++n) {
+		if ((stack.cards[i] & Color) == (stack.cards[i+1] & Color)) break;
+		if ((stack.cards[i] & Rank) != (stack.cards[i+1] & Rank) + 1) break;
+	}
+	return n;
+}
+
+static void moveColumn(uint dst, uint src) {
+	uint depth;
+	uint cells[Stacks];
+	uint free = freeCells(cells, dst);
+	for (depth = moveDepth(src); depth; --depth) {
+		if (free < depth-1) continue;
+		if (valid(dst, stacks[src].cards[stacks[src].len-depth])) break;
+	}
+	if (depth < 2 || dst < Tableau) {
+		moveSingle(dst, src);
+		return;
+	}
+	q.u = q.w;
+	for (uint i = 0; i < depth-1; ++i) {
+		enq(cells[i], src);
+	}
+	enq(dst, src);
+	for (uint i = depth-2; i < depth-1; --i) {
+		enq(dst, cells[i]);
+	}
+}
+
+static void curse(void) {
+	initscr();
+	cbreak();
+	noecho();
+	keypad(stdscr, false);
+	struct termios term;
+	tcgetattr(STDOUT_FILENO, &term);
+	term.c_iflag &= ~IXON;
+	tcsetattr(STDOUT_FILENO, TCSANOW, &term);
+	curs_set(0);
+	start_color();
+	use_default_colors();
+	init_pair(1, COLOR_BLACK, COLOR_WHITE);
+	init_pair(2, COLOR_RED, COLOR_WHITE);
+	init_pair(3, COLOR_GREEN, -1);
+}
+
+static void drawCard(bool hi, int y, int x, Card card) {
+	if (!card) return;
+	move(y, x);
+	attr_set(hi ? A_REVERSE : A_NORMAL, (card & Color) ? 2 : 1, NULL);
+	switch (card & Suit) {
+		break; case Club: addstr("\u2663");
+		break; case Diamond: addstr("\u2666");
+		break; case Spade: addstr("\u2660");
+		break; case Heart: addstr("\u2665");
+		break; default:;
+	}
+	switch (card & Rank) {
+		break; case A: addstr(" A");
+		break; case 10: addstr("10");
+		break; case J: addstr(" J");
+		break; case Q: addstr(" Q");
+		break; case K: addstr(" K");
+		break; default: {
+			addch(' ');
+			addch('0' + (card & Rank));
+		}
+	}
+	attr_set(A_NORMAL, 0, NULL);
+}
+
+static void drawStack(bool hi, int y, int x, const struct Stack *stack) {
+	for (uint i = 0; i < stack->len; ++i) {
+		drawCard(hi && i == stack->len-1, y++, x, stack->cards[i]);
+	}
+}
+
+enum {
+	Padding = 1,
+	CardWidth = 3,
+	CardHeight = 1,
+	CellX = Padding,
+	CellY = 2*CardHeight,
+	FoundationX = CellX + 4*(CardWidth+Padding),
+	FoundationY = CellY,
+	TableauX = CellX,
+	TableauY = CellY + 2*CardHeight,
+};
+
+static uint game;
+static uint srcStack = Stacks;
+
+static void draw(void) {
+	erase();
+	static char buf[256];
+	if (!buf[0]) snprintf(buf, sizeof(buf), "Game #%u", game);
+	if (win()) {
+		snprintf(
+			buf, sizeof(buf),
+			"Game #%u win! Press any key to view the scoreboard.",
+			game
+		);
+	}
+	attr_set(A_NORMAL, 3, NULL);
+	mvaddstr(0, Padding, buf);
+	for (uint i = 0; i < Stacks; ++i) {
+		int y, x;
+		char key;
+		if (i < Cell) {
+			y = FoundationY;
+			x = FoundationX + (i-Foundation) * (CardWidth+Padding);
+			key = '_';
+		} else if (i < Tableau) {
+			y = CellY;
+			x = CellX + (i-Cell) * (CardWidth+Padding);
+			key = '1' + i-Cell;
+		} else {
+			y = TableauY;
+			x = TableauX + (i-Tableau) * (CardWidth+Padding);
+			key = "QWERASDF"[i-Tableau];
+		}
+		if (i < Tableau) {
+			mvaddch(y, x+1, COLOR_PAIR(3) | key);
+		} else {
+			mvaddch(y + 8*CardHeight, x+1, COLOR_PAIR(3) | key);
+		}
+		if (i < Cell) {
+			drawCard(false, y, x, peek(&stacks[i]));
+		} else {
+			drawStack(i == srcStack, y, x, &stacks[i]);
+		}
+	}
+}
+
+static bool quit;
+static void input(void) {
+	char ch = getch();
+	uint stack = Stacks;
+	switch (tolower(ch)) {
+		break; case 'Q'^'@': quit = true;
+		break; case '\33': srcStack = Stacks;
+		break; case 'u': case '\b': case '\177': undo();
+		break; case '1': case '!': stack = Cell+0;
+		break; case '2': case '@': stack = Cell+1;
+		break; case '3': case '#': stack = Cell+2;
+		break; case '4': case '$': stack = Cell+3;
+		break; case '_': case ' ': stack = Foundation;
+		break; case 'q': stack = Tableau+0;
+		break; case 'w': stack = Tableau+1;
+		break; case 'e': stack = Tableau+2;
+		break; case 'r': stack = Tableau+3;
+		break; case 'a': stack = Tableau+4;
+		break; case 's': stack = Tableau+5;
+		break; case 'd': stack = Tableau+6;
+		break; case 'f': stack = Tableau+7;
+		break; case '\n': stack = srcStack;
+		break; case ERR: exit(EXIT_FAILURE);
+	}
+	if (stack == Stacks) return;
+
+	if (srcStack < Stacks) {
+		Card card = peek(&stacks[srcStack]);
+		if (stack == Foundation) {
+			for (; stack < Cell; ++stack) {
+				if (valid(stack, card)) break;
+			}
+			if (stack == Cell) return;
+		}
+		if (stack == srcStack) {
+			for (stack = Cell; stack < Stacks; ++stack) {
+				if (!stacks[stack].len) break;
+			}
+			if (stack == Stacks) return;
+		}
+		if (isupper(ch)) {
+			moveSingle(stack, srcStack);
+		} else {
+			moveColumn(stack, srcStack);
+		}
+		srcStack = Stacks;
+
+	} else if (stack >= Cell && stacks[stack].len) {
+		srcStack = stack;
+	}
+}
+
+uint playFreeCell(void) {
+	game = 1 + arc4random_uniform(32000);
+	curse();
+	deal(game);
+	while (!quit && !win()) {
+		while (q.r < q.w) {
+			deq();
+			draw();
+			refresh();
+			usleep(50000);
+			if (q.r == q.w) autoEnq();
+		}
+		draw();
+		input();
+	}
+	return win();
+}
diff --git a/play.c b/play.c
index 3c5f418..b895e9e 100644
--- a/play.c
+++ b/play.c
@@ -17,6 +17,7 @@
 #include <curses.h>
 #include <err.h>
 #include <fcntl.h>
+#include <locale.h>
 #include <stdbool.h>
 #include <stdio.h>
 #include <stdlib.h>
@@ -195,6 +196,7 @@ static void draw(const char *title, size_t new) {
 typedef uint Play(void);
 uint play2048(void);
 uint playSnake(void);
+uint playFreeCell(void);
 
 static const struct Game {
 	const char *name;
@@ -211,6 +213,10 @@ static const struct Game {
 		"snake", "Snake", "Eat food before it spoils to become long",
 		playSnake, false,
 	},
+	{
+		"freecell", "FreeCell", "Sort cards like it's 1995",
+		playFreeCell, true,
+	},
 };
 
 static const struct Game *menu(void) {
@@ -251,11 +257,20 @@ static const struct Game *menu(void) {
 	}
 }
 
+static void info(void) {
+	endwin();
+	printf(
+		"This program is AGPLv3 Free Software!\n"
+		"Code is available from <https://git.causal.agency/play>.\n"
+	);
+}
+
 int main(int argc, char *argv[]) {
-	const char *path = NULL;
+	setlocale(LC_CTYPE, "");
+	atexit(info);
 
-	int opt;
-	while (0 < (opt = getopt(argc, argv, "t:"))) {
+	const char *path = NULL;
+	for (int opt; 0 < (opt = getopt(argc, argv, "t:"));) {
 		switch (opt) {
 			break; case 't': path = optarg;
 			break; default:  return EX_USAGE;
@@ -281,7 +296,7 @@ int main(int argc, char *argv[]) {
 	curse();
 
 	const struct Game *game = menu();
-	if (!game) goto done;
+	if (!game) return 0;
 	erase();
 #ifdef __FreeBSD__
 	setproctitle("%s", game->name);
@@ -373,10 +388,4 @@ int main(int argc, char *argv[]) {
 	}
 
 	getch();
-done:
-	endwin();
-	printf(
-		"This program is AGPLv3 Free Software!\n"
-		"Code is available from <https://git.causal.agency/play>.\n"
-	);
 }