From daeee17ff71cf72a0270fd0c1b8eab59a3d5c12c Mon Sep 17 00:00:00 2001 From: "C. McEnroe" Date: Sat, 17 Apr 2021 20:03:26 -0400 Subject: Add freecell --- bin/.gitignore | 1 + bin/Makefile | 27 ++-- bin/README.7 | 6 +- bin/freecell.c | 389 ++++++++++++++++++++++++++++++++++++++++++++++++++++ bin/man6/freecell.6 | 50 +++++++ 5 files changed, 460 insertions(+), 13 deletions(-) create mode 100644 bin/freecell.c create mode 100644 bin/man6/freecell.6 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 + * + * 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 . + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +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 -- cgit 1.4.1