bluebones.net

August 4, 2022August 4, 2022

The 138 Terminal Positions of Tic-Tac-Toe

Also known as Noughts and Crosses.

A Rust program to generate all terminal positions of the game of Tic-Tac-Toe. Rotations, transpositions, games-still-in-progress and impossible board states are not shown.

github.com/bakert/boards

use std::collections::HashMap;

const EMPTY: char = ' ';
const X: char = 'X';
const O: char = 'O';

type Boards = HashMap;
type Board = [[char; 3]; 3];
type Representations = [String; 8];

trait BoardMethods {
    fn display(&self) -> String;
    fn is_terminal(&self) -> bool;
    fn representation(&self) -> String;
    fn all_representations(&self) -> Representations;
    fn rotate(&self) -> Board;
    fn transpose(&self) -> Board;
}

trait BoardsMethods {
    fn contains(&self, b: Board) -> bool;
    fn insert_board(&mut self, b: Board);
}

fn main() {
    test();
    let empty_board: Board = [[EMPTY; 3]; 3];
    let mut final_boards: Boards = HashMap::new();
    let boards: Vec = all_boards(empty_board, X);
    for board in boards {
        if board.is_terminal() && !final_boards.contains(board) {
            final_boards.insert_board(board);
        }
    }
    println!("{} unique terminal boards found\n", final_boards.len());
    for (_, board) in final_boards {
        println!("{}", board.display());
    }
}

fn all_boards(board: Board, to_play: char) -> Vec {
    let to_play_next: char = if to_play == X { O } else { X };
    let mut boards: Vec = Vec::new();
    for x in 0..board.len() {
        let row = board[x];
        for y in 0..row.len() {
            if board[x][y] == EMPTY {
                let mut b: Board = board.clone();
                b[x][y] = to_play;
                boards.push(b);
                if !b.is_terminal() {
                    boards.append(&mut all_boards(b, to_play_next));
                }
            }
        }
    }
    return boards;
}

impl BoardMethods for Board {
    fn display(&self) -> String {
        let mut s = String::new();
        for row in self {
            for square in row {
                s.push('|');
                s.push(*square);
            }
            s.push_str("|\n");
        }
        return s;
    }

    fn is_terminal(&self) -> bool {
        for i in 0..3 {
            if self[i][0] != EMPTY && self[i][0] == self[i][1] && self[i][1] == self[i][2] {
                return true;
            }
            if self[0][i] != EMPTY && self[0][i] == self[1][i] && self[1][i] == self[2][i] {
                return true;
            }
        }
        if self[0][0] != EMPTY && self[0][0] == self[1][1] && self[1][1] == self[2][2] {
            return true;
        }
        if self[0][2] != EMPTY && self[0][2] == self[1][1] && self[1][1] == self[2][0] {
            return true;
        }
        for row in self {
            for square in row {
                if *square == EMPTY {
                    return false;
                }
            }
        }
        return true;
    }

    fn all_representations(&self) -> Representations {
        let mut r: Representations = Default::default();
        r[0] = self.representation();
        r[1] = self.rotate().representation();
        r[2] = self.rotate().rotate().representation();
        r[3] = self.rotate().rotate().rotate().representation();
        r[4] = self.transpose().representation();
        r[5] = self.rotate().transpose().representation();
        r[6] = self.rotate().rotate().transpose().representation();
        r[7] = self.rotate().rotate().rotate().transpose().representation();
        return r;
    }

    fn representation(&self) -> String {
        let mut s = String::new();
        for row in self {
            for square in row {
                s.push(*square);
            }
        }
        return s;
    }

    fn rotate(&self) -> Board {
        let mut b: Board = [[EMPTY, EMPTY, EMPTY]; 3];
        for x in 0..self.len() {
            let row = self[x];
            for y in 0..row.len() {
                b[x][y] = self[row.len() - y - 1][x];
            }
        }
        return b
    }

    fn transpose(&self) -> Board {
        let mut b: Board = [[EMPTY, EMPTY, EMPTY]; 3];
        for x in 0..self.len() {
            let row = self[x];
            for y in 0..row.len() {
                b[y][x] = self[x][y];
            }
        }
        return b;
    }
}

impl BoardsMethods for Boards {
    fn contains(&self, board: Board) -> bool {
        for repr in board.all_representations() {
            if self.contains_key(&repr) {
                return true;
            }
        }
        return false;
    }

    fn insert_board(&mut self, b: Board) {
        self.insert(b.representation(), b);
    }
}

fn test() {
    test_rotate();
    test_transpose();
}

fn test_rotate() {
    // XXX    _OX
    // OOO => _OX
    // ___    _OX
    let b: Board = [[X, X, X], [O, O, O], [EMPTY, EMPTY, EMPTY]];
    let rotated: Board = b.rotate();
    assert!(rotated[0] == [EMPTY, O, X]);
    assert!(rotated[1] == [EMPTY, O, X]);
    assert!(rotated[2] == [EMPTY, O, X]);
}

fn test_transpose() {
    // X_O    XO_
    // OX_ => _X_
    // __X    O_X
    let b: Board = [[X, EMPTY, O], [O, X, EMPTY], [EMPTY, EMPTY, X]];
    let transposed: Board = b.transpose();
    assert!(transposed == [[X, O, EMPTY], [EMPTY, X, EMPTY], [O, EMPTY, X]]);
}

July 21, 2022July 23, 2022

Set Up a New Mac (July 2022 Edition)

Updated from three years ago: https://bluebones.net/2019/07/set-up-a-new-mac/

Upgrade to latest OSX.
Restore home directory from Backblaze. (Or at least dotfiles, .ssh dir, .vim dir, bin directory, ~/Library/Application Support/Alfred 4/*, pwd.dsv.gpg, business, travel)
Alfred (and give it Accessibility access, add license key).
Dock: remove everything, hiding on, magnification on.
Sublime Text 4 (add license key, set "trim_trailing_white_space_on_save": true in sublime prefs, install Package Control, install Solarized Theme).
subl commandline sublime.
$ ln -s "/Applications/Sublime Text.app/Contents/SharedSupport/bin/subl" ~/u/bin/subl
sublime-git-ignorer: (1) add Package Control repo https://github.com/apc999/sublime-text-gitignore (2)
add package sublime-text-gitignore (3) use menu item : File->Exclude Git-ignored (4) Give this a keyboard shortcut in Sublime, Preferences, Key Bindings with { "keys": ["alt+shift+i"], "command": "exclude_ignored" }
Install FiraCode and add it to Sublime Text prefs with "font_face": "Fira Code".
Hide Desktop icons
$ defaults write com.apple.finder CreateDesktop false
$ killall Finder
Solarized theme for Terminal and make default in preferences.
“Use Option as Meta Key” in Terminal to make left Alt work as Esc.
Use Ctrl-f7 or the Keyboard, Shortcuts in System Preferences to give Full Keyboard Access so that tab takes you to every button in a dialog, etc.
Homebrew. (Installs OSX commandline tools.)
brew install mariadb
brew install npm
brew install gimme-aws-creds
brew install awscli
brew install kubectl
brew install sops
brew install kubectx
brew install apache2
brew install php
Discord.
Change all .txt to open with Sublime Text.
Show hidden files in Finder. Cmd-Shift-.
WhatsApp.
1Password.
Chrome. (Log in to Chrome to get uBlock Origin and other extensions.)
Skitch.
Backblaze.
Parallels Desktop + MTGO
npm install -g rtm-cli
Disable Ask Siri in System Preferences, Siri +Remove Ask Siri from touchbar in System Preferences, Keyboard, Customize Touch Bar…
Turn on “tap to click” in System Preferences, Trackpad.
Disable long-press (it’s wayyyyy too annoying when selecting text in Chrome): defaults write -g ApplePressAndHoldEnabled -bool false
Zoom.
Skype.
PyCharm (and Solarized theme).
GoLand (and Solarized theme).
WebStorm (and Solarized theme).
Spotify.

April 5, 2022April 5, 2022

Remove obsolete branches from git

Look up on the remote which branches have been deleted there and remove them from local.

git remote update origin --prune
git branch -vvv | grep gone | cut -d' ' -f3 | xargs -I{} git branch -D '{}'

January 23, 2022January 23, 2022

A few years ago I wrote a version of the tile game Qwirkle including some rudimentary AI – github.com/bakert/qwirkle. It’s surprising how many good scoring positions you miss in the normal run of play and how little it seems to matter if you give away a Qwirkle to your opponent. The code is open source/MIT licensed.

November 29, 2021November 29, 2021

The Dobble Algorithm

I played a few games of Dobble with my niece and got curious about the algorithm used to generate the cards. It turns out it’s not trivial and one of the best ways to interrogate it is as a finite projective plane.

I got the most useful information from www.101computing.net/the-dobble-algorithm which has actual code although the clearest explanation was on www.petercollingridge.co.uk/blog/mathematics-toys-and-games/dobble

The maximum number of possible cards is n^2 + n + 1 where n is the number of symbols per card minus one.

Number of Symbols on Card	Max Number of Cards
2	3
4	13
5	21
8	57
12	133

The number of symbols on the card doesn’t have to be a prime number plus one but the algorithms found online require that.

I thought it was pretty interesting that 8 symbols per card allows 57 cards but the game itself comes with 55 cards. Presumably because once you put one card in the center 54 is divisible by both 2 and 3 for even number of cards per player in the common cases. I wonder which two cards are missing but not enough to look through them all!

November 4, 2021

Emit logs in JSON format from fastapi/gunicorn, for DataDog

import logging

from pythonjsonlogger import jsonlogger

def init() -> None:
    log_in_json()
    map_levelname_to_status()

# Force all loggers to talk JSON rather than text so DataDog can parse the output.
def log_in_json() -> None:
    loggers = [
        logging.getLogger("uvicorn.access"),
        logging.getLogger("uvicorn.error"),
        logging.getLogger("uvicorn"),
        logging.getLogger(),
    ]
    for logger in loggers:
        for handler in logger.handlers:
            logger.removeHandler(handler)
        logger.level = logging.DEBUG
        log_handler = logging.StreamHandler()
        formatter = jsonlogger.JsonFormatter(
            "%(asctime)s %(levelname)s %(name)s %(message)s"
        )
        log_handler.setFormatter(formatter)
        logger.addHandler(log_handler)

# DataDog is expecting 'status' for log level but the python default is 'levelname'.
def map_levelname_to_status() -> None:
    old_factory = logging.getLogRecordFactory()

    def record_factory(*args: str, **kwargs: str) -> logging.LogRecord:
        record = old_factory(*args, **kwargs)
        record.status = record.levelname  # type: ignore
        return record

    logging.setLogRecordFactory(record_factory)

October 29, 2021

Fork of pystache

The excellent pystache library is now unusable due to changes in setuptools. For this reason with somewhat heavy heart we have forked pystache and dropped support for python 2. We will attempt to get it instated as the official (pypi) version. If you’re starting with a new project you might prefer to use chevron but if you need a version of pystache you can find our fork at https://github.com/PennyDreadfulMTG/pystache.

arise	2315
bludy (when “arise” hits nothing)	168
canty (when the “a” in arise hits but out of place)	154
denet (when the “e” in arise hits but out of place)	121
until (when the “i” hits but out of place)	107
hotel (“r” and “e” out of place)	100
muton (“s” out of place)	80
metal (“e” and “a” out of place)	79
plunk (“r” and “i” out of place)	78
north (“r” out of place)	64
could (“e” in correct place)	63
duroy (“a” and “r” out of place)	62
malty (“a”, “e” and “r” out of place)	61
lanch (“a” and “s” out of place)	61
clout (“i” in correct place)	51
count (“r” in correct place, and after “bludy” when only the “u” hits)	48
blaud (“e” in correct place, “a” in wrong place)	47
plant (“i” in correct place, “s” in wrong place)	44
spelt (“s” and “e” in wrong place)	41
lipid (“i” and “e” in wrong place, or after “until” with “i” in right place)	35

Posts

The 138 Terminal Positions of Tic-Tac-Toe

Set Up a New Mac (July 2022 Edition)

Remove obsolete branches from git

Best Guesses in Wordle

Better Wordle Solver

Wordle Solver

Qwirkle

The Dobble Algorithm

Emit logs in JSON format from fastapi/gunicorn, for DataDog

Fork of pystache