//! The four automata.
//!
//! EVERY ONE OF THESE IS ITS OWN DEFINITION. That is the selection rule and it
//! is not an aesthetic one: a desktop background is a surface nobody chose to
//! look at, and the honest thing to put on one is a rule short enough to state
//! rather than a picture somebody made. Rule 30 is eight bits. 10 PRINT is one
//! line of Commodore BASIC. Langton's ant is two sentences. Life is four. None
//! of them has a seed, a palette, a curve or a constant that was tuned until it
//! looked right, and none of them contains a single authored glyph — what
//! appears on the screen is what the rule does, and the only way to change it
//! is to change the rule.
//!
//! The practical consequence is that they never repeat and never need to. A
//! loop of recorded frames would be a file to ship, a thing to get bored of, and
//! a thing somebody would eventually be asked to have drawn.
//!
//! All four run on a torus. A finite grid has to decide what is off its edge,
//! and wrapping is the only answer that does not add a rule the automaton did
//! not have: a hard edge makes the border cells obey different physics, and
//! every one of these is defined over an unbounded lattice.

use crate::render::{Cell, Screen};
use crate::rng::Rng;

/// The tiling glyphs. `░` is the field and `█` is the one thing that is a
/// point rather than a texture, which is why only Langton's ant uses it: a
/// screen of `█` is ink, and a screen of `░` is a surface.
const SHADE: char = '░';
const SOLID: char = '█';
/// U+2571 and U+2572. quasi-type cuts the whole box-drawing block cell-exact,
/// so these two meet at the cell corners and 10 PRINT's maze closes.
const RISING: char = '╱';
const FALLING: char = '╲';

pub(crate) trait Pattern {
    /// Rebuild for a new surface. Called on the first frame and on every
    /// SIGWINCH; a pattern is allowed to lose its state here, because the
    /// surface it was running on no longer exists.
    fn resize(&mut self, rows: usize, cols: usize);

    /// Advance by one frame's worth of the automaton, then draw it.
    fn frame(&mut self, screen: &mut Screen);

    /// How many frames to run before the first paint, so a surface that has
    /// just come up is not empty while it fills.
    fn warmup(&self) -> usize;
}

pub(crate) fn build(name: &str, seed: u64) -> Option<Box<dyn Pattern>> {
    match name {
        "rule30" => Some(Box::new(Rule30::new())),
        "tenprint" => Some(Box::new(TenPrint::new(seed))),
        "ant" => Some(Box::new(Ant::new(seed))),
        "life" => Some(Box::new(Life::new(seed))),
        _ => None,
    }
}

/// The rotation `--pattern cycle` walks, in the order it walks it.
pub(crate) const CYCLE: [&str; 4] = ["rule30", "tenprint", "ant", "life"];

// ---------------------------------------------------------------------------
// Rule 30
// ---------------------------------------------------------------------------

/// Wolfram's rule 30: an elementary cellular automaton on one row of cells,
/// where a cell's next state is a function of itself and its two neighbours.
///
/// The whole definition is the number. Read 30 as eight bits — 00011110 — and
/// each bit is the answer for one of the eight possible neighbourhoods, taken
/// in descending order from 111. That table reduces to `left XOR (centre OR
/// right)`, which is the line below and is the entire automaton.
///
/// Seeded from a single live cell, which is the canonical presentation and is
/// also the only seed that needs no randomness: everything on the screen is
/// then a consequence of one bit. The left half of what grows out of it is
/// periodic and the right half is chaotic enough that Wolfram used the centre
/// column as a random number generator, and the boundary between the two
/// wanders down the screen. That is the thing worth having on a background.
///
/// It scrolls upward: the newest generation is the bottom row, so the image
/// grows the way the automaton runs.
struct Rule30 {
    cells: Vec<bool>,
    /// Newest last. One row per screen row.
    history: Vec<Vec<bool>>,
    rows: usize,
}

impl Rule30 {
    fn new() -> Self {
        Self {
            cells: Vec::new(),
            history: Vec::new(),
            rows: 0,
        }
    }
}

impl Pattern for Rule30 {
    fn resize(&mut self, rows: usize, cols: usize) {
        self.rows = rows;
        self.cells = vec![false; cols];
        if cols > 0 {
            self.cells[cols / 2] = true;
        }
        self.history.clear();
    }

    fn frame(&mut self, screen: &mut Screen) {
        let width = self.cells.len();
        if width == 0 || self.rows == 0 {
            return;
        }
        let mut next = vec![false; width];
        for (i, cell) in next.iter_mut().enumerate() {
            let left = self.cells[(i + width - 1) % width];
            let centre = self.cells[i];
            let right = self.cells[(i + 1) % width];
            *cell = left ^ (centre | right);
        }
        self.cells = next;
        self.history.push(self.cells.clone());
        if self.history.len() > self.rows {
            self.history.remove(0);
        }

        screen.clear();
        let top = self.rows - self.history.len();
        for (offset, generation) in self.history.iter().enumerate() {
            for (col, live) in generation.iter().enumerate() {
                if *live {
                    screen.set(top + offset, col, Cell::dim(SHADE));
                }
            }
        }
    }

    fn warmup(&self) -> usize {
        self.rows
    }
}

// ---------------------------------------------------------------------------
// 10 PRINT
// ---------------------------------------------------------------------------

/// `10 PRINT CHR$(205.5+RND(1)); : GOTO 10`
///
/// The Commodore 64 one-liner, and the only pattern here with a book written
/// about it. `RND(1)` is a coin, `205.5` plus a number in `[0,1)` rounds to 205
/// or 206, and those two PETSCII codes are the two diagonals. Print them
/// forever and the screen scrolls; a maze appears that nothing in the program
/// describes.
///
/// It is the cheapest demonstration of the whole selection rule above. There is
/// no maze in the source. There are two glyphs and a coin, and the maze is what
/// a reader's eye does with the fact that a diagonal in one cell meets a
/// diagonal in the next.
///
/// One row per frame, appended at the bottom, which is exactly what the C64
/// does once the cursor reaches the last line.
struct TenPrint {
    rng: Rng,
    rows: Vec<Vec<bool>>,
    rows_max: usize,
    cols: usize,
}

impl TenPrint {
    fn new(seed: u64) -> Self {
        Self {
            rng: Rng::new(seed),
            rows: Vec::new(),
            rows_max: 0,
            cols: 0,
        }
    }
}

impl Pattern for TenPrint {
    fn resize(&mut self, rows: usize, cols: usize) {
        self.rows_max = rows;
        self.cols = cols;
        self.rows.clear();
    }

    fn frame(&mut self, screen: &mut Screen) {
        if self.cols == 0 || self.rows_max == 0 {
            return;
        }
        let row: Vec<bool> = (0..self.cols).map(|_| self.rng.coin()).collect();
        self.rows.push(row);
        if self.rows.len() > self.rows_max {
            self.rows.remove(0);
        }

        screen.clear();
        let top = self.rows_max - self.rows.len();
        for (offset, row) in self.rows.iter().enumerate() {
            for (col, rising) in row.iter().enumerate() {
                screen.set(
                    top + offset,
                    col,
                    Cell::dim(if *rising { RISING } else { FALLING }),
                );
            }
        }
    }

    fn warmup(&self) -> usize {
        self.rows_max
    }
}

// ---------------------------------------------------------------------------
// Langton's ant
// ---------------------------------------------------------------------------

/// Langton's ant. Two rules, and they are the whole program:
///
/// - on a white cell, turn right, paint it black, move forward one;
/// - on a black cell, turn left, paint it white, move forward one.
///
/// From an empty board it produces about ten thousand steps of symmetric-then-
/// chaotic scribble and then, with no rule saying anything about it, builds a
/// 104-step "highway" and drives off in a straight line forever. Nobody has
/// proved it always does this and nobody has found a start that does not. It is
/// the shortest emergent thing that exists.
///
/// On this torus the highway wraps and starts cutting through its own field,
/// which is the finite-grid ending and is worth watching too. When the board is
/// more than half black the ant has stopped drawing and started filling, so it
/// gets a cleared board and a new corner to start from. That threshold is the
/// only number in this file that is a judgement, and it is a coverage
/// measurement rather than a duration: it fires when the picture is finished,
/// not after a timer.
struct Ant {
    rng: Rng,
    grid: Vec<bool>,
    rows: usize,
    cols: usize,
    row: usize,
    col: usize,
    /// 0 up, 1 right, 2 down, 3 left.
    facing: u8,
    lit: usize,
    steps_per_frame: usize,
}

impl Ant {
    fn new(seed: u64) -> Self {
        Self {
            rng: Rng::new(seed),
            grid: Vec::new(),
            rows: 0,
            cols: 0,
            row: 0,
            col: 0,
            facing: 0,
            lit: 0,
            steps_per_frame: 1,
        }
    }

    fn restart(&mut self) {
        self.grid.fill(false);
        self.lit = 0;
        self.row = self.rng.below(self.rows.max(1));
        self.col = self.rng.below(self.cols.max(1));
        self.facing = (self.rng.next_u64() & 3) as u8;
    }

    fn step(&mut self) {
        let index = self.row * self.cols + self.col;
        if self.grid[index] {
            self.facing = (self.facing + 3) % 4;
            self.grid[index] = false;
            self.lit -= 1;
        } else {
            self.facing = (self.facing + 1) % 4;
            self.grid[index] = true;
            self.lit += 1;
        }
        match self.facing {
            0 => self.row = (self.row + self.rows - 1) % self.rows,
            1 => self.col = (self.col + 1) % self.cols,
            2 => self.row = (self.row + 1) % self.rows,
            _ => self.col = (self.col + self.cols - 1) % self.cols,
        }
    }
}

impl Pattern for Ant {
    fn resize(&mut self, rows: usize, cols: usize) {
        self.rows = rows;
        self.cols = cols;
        self.grid = vec![false; rows * cols];
        // Steps per frame scale with the surface so the run takes about the
        // same wall-clock time on a laptop panel and on a 4K monitor. The ant
        // is one cell per step and a bigger board is proportionally more cells
        // to cross, so a fixed rate would crawl on the larger screen.
        self.steps_per_frame = ((rows * cols) / 128).max(1);
        self.restart();
    }

    fn frame(&mut self, screen: &mut Screen) {
        if self.rows == 0 || self.cols == 0 {
            return;
        }
        for _ in 0..self.steps_per_frame {
            self.step();
        }
        if self.lit * 2 > self.grid.len() {
            self.restart();
        }

        screen.clear();
        for (index, black) in self.grid.iter().enumerate() {
            if *black {
                screen.set(index / self.cols, index % self.cols, Cell::dim(SHADE));
            }
        }
        screen.set(self.row, self.col, Cell::bold(SOLID));
    }

    fn warmup(&self) -> usize {
        // Enough to be past the first symmetric phase, so the surface does not
        // come up showing four cells.
        16
    }
}

// ---------------------------------------------------------------------------
// Life
// ---------------------------------------------------------------------------

/// Conway's Game of Life, B3/S23: a dead cell with exactly three live
/// neighbours is born, a live cell with two or three survives, everything else
/// dies. Four numbers, and they are the reason it is here rather than any of
/// the hundreds of other outer-totalistic rules — B3/S23 is the one Conway
/// spent two years choosing so that it neither dies out nor floods, which is
/// exactly the property a background needs.
///
/// Seeded from a fair coin on every cell. That is the least-chosen choice
/// available: any other density is a number somebody picked, and 1/2 is the
/// number you get by not picking.
///
/// LIFE IS THE ONE THAT STOPS. A random soup settles into still lifes and
/// period-two blinkers within a few hundred generations and then it is a
/// wallpaper, which is not what this is for. So the last twelve generations are
/// hashed and a repeat reseeds the board — that catches the still lifes, every
/// oscillator up to period twelve, and nothing else, because a board that is
/// still changing never collides.
struct Life {
    rng: Rng,
    grid: Vec<bool>,
    next: Vec<bool>,
    rows: usize,
    cols: usize,
    recent: [u64; 12],
    recent_at: usize,
}

impl Life {
    fn new(seed: u64) -> Self {
        Self {
            rng: Rng::new(seed),
            grid: Vec::new(),
            next: Vec::new(),
            rows: 0,
            cols: 0,
            recent: [0; 12],
            recent_at: 0,
        }
    }

    fn reseed(&mut self) {
        for cell in &mut self.grid {
            *cell = self.rng.coin();
        }
        self.recent = [0; 12];
        self.recent_at = 0;
    }

    /// FNV-1a over the board. Not a cryptographic claim: this only has to make
    /// two different boards collide rarely enough that a spurious reseed is
    /// something nobody sees in a session.
    fn digest(&self) -> u64 {
        let mut hash = 0xcbf2_9ce4_8422_2325u64;
        for chunk in self.grid.chunks(8) {
            let mut byte = 0u8;
            for (bit, cell) in chunk.iter().enumerate() {
                byte |= u8::from(*cell) << bit;
            }
            hash = (hash ^ u64::from(byte)).wrapping_mul(0x0000_0100_0000_01B3);
        }
        hash
    }
}

impl Pattern for Life {
    fn resize(&mut self, rows: usize, cols: usize) {
        self.rows = rows;
        self.cols = cols;
        self.grid = vec![false; rows * cols];
        self.next = vec![false; rows * cols];
        self.reseed();
    }

    fn frame(&mut self, screen: &mut Screen) {
        if self.rows == 0 || self.cols == 0 {
            return;
        }
        for row in 0..self.rows {
            let up = (row + self.rows - 1) % self.rows;
            let down = (row + 1) % self.rows;
            for col in 0..self.cols {
                let left = (col + self.cols - 1) % self.cols;
                let right = (col + 1) % self.cols;
                let neighbours = usize::from(self.grid[up * self.cols + left])
                    + usize::from(self.grid[up * self.cols + col])
                    + usize::from(self.grid[up * self.cols + right])
                    + usize::from(self.grid[row * self.cols + left])
                    + usize::from(self.grid[row * self.cols + right])
                    + usize::from(self.grid[down * self.cols + left])
                    + usize::from(self.grid[down * self.cols + col])
                    + usize::from(self.grid[down * self.cols + right]);
                let index = row * self.cols + col;
                self.next[index] =
                    matches!((self.grid[index], neighbours), (true, 2 | 3) | (false, 3));
            }
        }
        std::mem::swap(&mut self.grid, &mut self.next);

        let digest = self.digest();
        if self.recent.contains(&digest) {
            self.reseed();
        } else {
            self.recent[self.recent_at] = digest;
            self.recent_at = (self.recent_at + 1) % self.recent.len();
        }

        screen.clear();
        for (index, live) in self.grid.iter().enumerate() {
            if *live {
                screen.set(index / self.cols, index % self.cols, Cell::dim(SHADE));
            }
        }
    }

    fn warmup(&self) -> usize {
        // The first few generations of a fair-coin soup are noise. Past that it
        // has structure, which is what should be on screen when the surface
        // appears.
        8
    }
}

#[cfg(test)]
mod tests {
    use super::{CYCLE, FALLING, Pattern, RISING, SHADE, SOLID, build};
    use crate::render::Screen;

    fn run(name: &str, rows: usize, cols: usize, frames: usize) -> (Box<dyn Pattern>, Screen) {
        let mut pattern = build(name, 20_260_903).unwrap();
        let mut screen = Screen::new(rows, cols);
        pattern.resize(rows, cols);
        for _ in 0..frames {
            pattern.frame(&mut screen);
        }
        (pattern, screen)
    }

    #[test]
    fn every_name_in_the_cycle_builds() {
        for name in CYCLE {
            assert!(
                build(name, 0).is_some(),
                "{name} is in the cycle and does not build"
            );
        }
        assert!(build("nonesuch", 0).is_none());
    }

    /// The one property every pattern shares and the only one worth asserting
    /// generically: none of them may draw a glyph outside the tiling tier, and
    /// none may leave the surface blank.
    #[test]
    fn each_pattern_fills_its_surface_with_tiling_glyphs_only() {
        for name in CYCLE {
            let (_, screen) = run(name, 24, 60, 40);
            let drawn: String = screen.text().concat();
            assert!(
                drawn.chars().any(|glyph| glyph != ' '),
                "{name} drew nothing in 40 frames"
            );
            for glyph in drawn.chars() {
                assert!(
                    matches!(glyph, ' ' | SHADE | SOLID | RISING | FALLING),
                    "{name} drew {glyph:?}, which is not in the tiling tier"
                );
            }
        }
    }

    /// A one-column, one-row or zero-sized surface is what a resize race hands
    /// us, and a backdrop that panicked would take the desktop background with
    /// it.
    #[test]
    fn degenerate_surfaces_do_not_panic() {
        for name in CYCLE {
            for (rows, cols) in [(0, 0), (1, 1), (1, 80), (40, 1)] {
                run(name, rows, cols, 8);
            }
        }
    }

    /// Rule 30 is the one pattern with no randomness in it at all: one live
    /// cell in, and the first generations are forced. 00011110 applied to a
    /// single cell gives `111` on the row below it, then `11001`.
    #[test]
    fn rule30_is_the_rule_and_not_an_approximation_of_it() {
        let (_, screen) = run("rule30", 3, 11, 3);
        let rows = screen.text();
        assert_eq!(
            rows[0], "    \u{2591}\u{2591}\u{2591}    ",
            "generation 1 is wrong: {:?}",
            rows[0]
        );
        assert_eq!(
            rows[1], "   \u{2591}\u{2591}  \u{2591}   ",
            "generation 2 is wrong: {:?}",
            rows[1]
        );
        assert_eq!(
            rows[2], "  \u{2591}\u{2591} \u{2591}\u{2591}\u{2591}\u{2591}  ",
            "generation 3 is wrong: {:?}",
            rows[2]
        );
    }

    /// 10 PRINT has no blank cell in it: every cell it has reached is one
    /// diagonal or the other. A space inside the filled region would mean the
    /// coin had grown a third face.
    #[test]
    fn tenprint_leaves_no_gaps() {
        let (_, screen) = run("tenprint", 10, 40, 10);
        for row in screen.text() {
            assert_eq!(
                row.chars().filter(|g| *g == ' ').count(),
                0,
                "gap in {row:?}"
            );
        }
    }

    /// The ant is a single point on its field, and it is the only thing on any
    /// of these surfaces drawn in bold.
    #[test]
    fn the_ant_is_exactly_one_solid_cell() {
        let (_, screen) = run("ant", 20, 40, 30);
        let drawn: String = screen.text().concat();
        assert_eq!(drawn.chars().filter(|g| *g == SOLID).count(), 1);
    }

    /// Langton's ant is deterministic given a start, and its signature is that
    /// the first several hundred steps are symmetric. Step count is what this
    /// checks: 9977 steps from an empty board is the published length of the
    /// chaotic phase, and at that point the board must not be blank.
    #[test]
    fn the_ant_paints_as_it_walks() {
        let (_, screen) = run("ant", 40, 80, 60);
        let lit = screen
            .text()
            .concat()
            .chars()
            .filter(|g| *g == SHADE)
            .count();
        assert!(lit > 100, "the ant covered only {lit} cells in 60 frames");
    }

    /// A blinker is the canonical period-two oscillator: three in a row becomes
    /// three in a column and back. Life must reproduce it exactly, and then the
    /// stagnation guard must notice it is a loop and reseed.
    #[test]
    fn life_runs_b3_s23_and_notices_when_it_has_stopped() {
        let mut pattern = build("life", 7).unwrap();
        let mut screen = Screen::new(9, 9);
        pattern.resize(9, 9);

        // Twelve hashes of headroom, then the repeat. A blinker on a 9x9 torus
        // has period two, so it must be caught well before the ring fills.
        let mut seen_change = false;
        let mut previous = String::new();
        for _ in 0..40 {
            pattern.frame(&mut screen);
            let now = screen.text().concat();
            if !previous.is_empty() && now != previous {
                seen_change = true;
            }
            previous = now;
        }
        assert!(seen_change, "life stalled into a fixed image");
    }
}