Add freecell

5 files changed, 460 insertions, 13 deletions

diff --git a/bin/.gitignore b/bin/.gitignore
index 24802157..f39282cd 100644
--- a/bin/.gitignore
+++ b/bin/.gitignore
@@ -10,6 +10,7 @@ dtch
 ever
 fbatt
 fbclock
+freecell
 glitch
 hilex
 hnel
diff --git a/bin/Makefile b/bin/Makefile
index e4ead85c..bf92d208 100644
--- a/bin/Makefile
+++ b/bin/Makefile
@@ -9,6 +9,7 @@ CFLAGS += -Wall -Wextra -Wpedantic -Wno-gnu-case-range
 
 LDLIBS.dtch = -lutil
 LDLIBS.fbclock = -lz
+LDLIBS.freecell = -lcurses
 LDLIBS.glitch = -lz
 LDLIBS.hnel = -lutil
 LDLIBS.modem = -lutil
@@ -54,18 +55,23 @@ BINS_LINUX += psfed
 BINS_TLS += relay
 BINS_TLS += typer
 
-BINS_ALL = ${BINS} ${BINS_BSD} ${BINS_LINUX} ${BINS_TLS}
+GAMES += freecell
+
+BINS_ALL = ${BINS} ${BINS_BSD} ${BINS_LINUX} ${BINS_TLS} ${GAMES}
 
 MANS = ${BINS:%=man1/%.1}
 MANS_BSD = ${BINS_BSD:%=man1/%.1}
+MANS_GAMES = ${GAMES:%=man6/%.6}
 MANS_LINUX = ${BINS_LINUX:%=man1/%.1}
 MANS_TLS = ${BINS_TLS:%=man1/%.1}
-MANS_ALL = ${BINS_ALL:%=man1/%.1}
+MANS_ALL = ${MANS} ${MANS_BSD} ${MANS_LINUX} ${MANS_TLS} ${MANS_GAMES}
 
 any: meta ${BINS}
 
 bsd: meta ${BINS_BSD}
 
+games: meta ${GAMES}
+
 linux: meta ${BINS_LINUX}
 
 tls: meta ${BINS_TLS}
@@ -117,15 +123,6 @@ setuid: bri
 	chown root bri
 	chmod u+s bri
 
-link:
-	install -d ${PREFIX}/bin ${MANDIR}/man1
-	ln -fs ${BINS_ALL:%=${PWD}/%} ${PREFIX}/bin
-	ln -fs ${MANS_ALL:%=${PWD}/%} ${MANDIR}/man1
-
-unlink:
-	rm -f ${BINS_ALL:%=${PREFIX}/bin/%}
-	rm -f ${MANS_ALL:%=${MANDIR}/%}
-
 install: ${BINS} ${MANS}
 	install -d ${PREFIX}/bin ${MANDIR}/man1
 	install ${BINS} ${PREFIX}/bin
@@ -136,6 +133,11 @@ install-bsd: ${BINS_BSD} ${MANS_BSD}
 	install ${BINS_BSD} ${PREFIX}/bin
 	install -m 644 ${MANS_BSD} ${MANDIR}/man1
 
+install-games: ${GAMES} ${MANS_GAMES}
+	install -d ${PREFIX}/bin ${MANDIR}/man6
+	install ${GAMES} ${PREFIX}/bin
+	install -m 644 ${MANS_GAMES} ${MANDIR}/man6
+
 install-linux: ${BINS_LINUX} ${MANS_BSD}
 	install -d ${PREFIX}/bin ${MANDIR}/man1
 	install ${BINS_LINUX} ${PREFIX}/bin
@@ -180,6 +182,9 @@ htmltags: *.[chly] mtags Makefile *.sh
 .pl.html:
 	sh html.sh man1/${<:.pl=.1} $< > $@
 
+freecell.html: freecell.c man6/freecell.6
+	sh html.sh man6/freecell.6 freecell.c > $@
+
 index.html: README.7 Makefile html.sh
 	sh html.sh README.7 Makefile html.sh > $@
 
diff --git a/bin/README.7 b/bin/README.7
index d83eafe7..c85a6ce0 100644
--- a/bin/README.7
+++ b/bin/README.7
@@ -1,4 +1,4 @@
-.Dd February 16, 2021
+.Dd April 17, 2021
 .Dt BIN 7
 .Os "Causal Agency"
 .
@@ -11,7 +11,7 @@ Various tools primarily targeting
 Darwin,
 .Fx
 and
-.Nx .
+.Ox .
 Some tools target Linux.
 .
 .Pp
@@ -34,6 +34,8 @@ watch files
 framebuffer battery indicator
 .It Xr fbclock 1
 framebuffer clock
+.It Xr freecell 6
+patience game
 .It Xr glitch 1
 PNG glitcher
 .It Xr hilex 1
diff --git a/bin/freecell.c b/bin/freecell.c
new file mode 100644
index 00000000..e0c749d1
--- /dev/null
+++ b/bin/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 <err.h>
+#include <locale.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <sysexits.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) {
+	setlocale(LC_CTYPE, "");
+	initscr();
+	cbreak();
+	noecho();
+	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 & 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('0' + (card & Rank));
+			addch(' ');
+		}
+	}
+	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:;
+	}
+	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);
+	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 void input(void) {
+	char ch = getch();
+	uint stack = Stacks;
+	switch (tolower(ch)) {
+		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;
+	}
+	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;
+	}
+}
+
+static void status(void) {
+	printf("Game #%u %s!\n", game, win() ? "win" : "lose");
+}
+
+int main(int argc, char *argv[]) {
+	game = 1 + time(NULL) % 32000;
+	uint delay = 50;
+	for (int opt; 0 < (opt = getopt(argc, argv, "d:n:"));) {
+		switch (opt) {
+			break; case 'd': delay = strtoul(optarg, NULL, 10);
+			break; case 'n': game = strtoul(optarg, NULL, 10);
+			break; default:  return EX_USAGE;
+		}
+	}
+	curse();
+	deal(game);
+	atexit(status);
+	while (!win()) {
+		while (q.r < q.w) {
+			deq();
+			draw();
+			refresh();
+			usleep(delay * 1000);
+			if (q.r == q.w) autoEnq();
+		}
+		draw();
+		input();
+	}
+	endwin();
+}
diff --git a/bin/man6/freecell.6 b/bin/man6/freecell.6
new file mode 100644
index 00000000..0e485a16
--- /dev/null
+++ b/bin/man6/freecell.6
@@ -0,0 +1,50 @@
+.Dd April 17, 2021
+.Dt FREECELL 6
+.Os
+.
+.Sh NAME
+.Nm freecell
+.Nd patience game
+.
+.Sh SYNOPSIS
+.Nm
+.Op Fl d Ar delay
+.Op Fl n Ar game
+.
+.Sh DESCRIPTION
+.Nm
+is a terminal FreeCell patience game.
+The arguments are as follows:
+.Bl -tag -width Ds
+.It Fl d Ar delay
+Set the delay in milliseconds
+between queued moves.
+The default is 50.
+.It Fl n Ar game
+Select the game number to play.
+.El
+.
+.Pp
+Moves are performed
+by typing a sequence of two keys.
+To automatically move a card
+to a free cell,
+type the same key twice.
+The keys are as follows:
+.Bl -tag -width Ds
+.It Ic Escape
+Cancel a pending move.
+.It Ic u , Backspace
+Undo the previous move.
+.It Ic 1 , 2 , 3 , 4
+Select the cells.
+.It Ic q , w , e , r , a , s , d , f
+Select the tableau cascades.
+.It Ic _ , Space
+Manually move
+the selected card
+to the foundations.
+.It Ic Shift
+Move a single card
+to an empty tableau cascade.
+.El