pinch-points 0.8.0

//! Brute-force puzzle validation (spec §5.4): search signpost placements
//! against the headless sim until one meets the level's goal.
//!
//! The search is depth-first over placement counts 0..=inventory. Candidate
//! tiles are pruned to tiles crabs actually cross in a run under the current
//! placements, since a signpost nobody walks over cannot change the
//! outcome, and the candidate set is recomputed at each depth so placements
//! that open new paths are still found.

use crate::sim::board::{Board, TileKind};
use crate::sim::direction::Direction;
use crate::sim::level::{Level, PuzzleOutcome};

/// A signpost as an instruction: where it goes and which way it points.
///
/// The same triple is a solution step, a hint, and a line in a level file,
/// so it is one name rather than three spellings.
pub type Placement = (u8, u8, Direction);

/// Boards a budgeted search may simulate before it gives up.
///
/// Counted in simulations rather than seconds, so a board costs the same
/// budget on every machine and in every build profile. Each simulation is
/// itself bounded by the board's [`Level::deadline`], which makes this a
/// ceiling on total work rather than merely on visits.
///
/// Sized from both ends, and both ends were measured.
///
/// The ceiling is there for the boards nobody vetted: an author's own
/// level, which can be any size, any shape, and unsolvable in ways that
/// take far longer to prove than to draw. A sealed 12x9 board with six
/// crabs ran past ten minutes unbudgeted; at this ceiling it gives up in 48
/// seconds of a release build (2026-08-15), on the editor's background
/// thread, which is a wait rather than a freeze.
///
/// The floor is the campaign.
/// `no_campaign_level_grants_a_post_it_does_not_need` proves a level's
/// inventory minimal under this number, and proving no *three*-post answer
/// exists costs roughly the cube of the tiles the crabs cross. At 50,000
/// that proof consumed the whole budget on any board big enough to need
/// four posts: of 140 boards built to need one, 101 gave up. Gulls eating
/// the crabs they meet makes a placement fail later and deeper, and four
/// gull levels needed a million (six to twelve seconds each).
pub const DEFAULT_NODE_BUDGET: u32 = 1_000_000;

/// How hard a search may work before it admits defeat.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Effort {
    /// Give up after this many boards simulated.
    Budget(u32),
    /// Search until the answer is certain, however long that takes. For
    /// callers that can wait and need the truth: level authoring and CI.
    Exhaustive,
}

/// What a search found, and when it found nothing, whether that is a proof.
///
/// The distinction is what a budget is for. "No solution" is a claim about
/// the level; "gave up" is a claim about the search, and an editor that
/// prints the first when it means the second tells an author their level is
/// broken when it may be fine.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum SolveOutcome {
    /// Placements meeting the level's goal, using as few posts as possible.
    Found(Vec<Placement>),
    /// Every placement within the inventory was tried, and none wins.
    Unsolvable,
    /// The budget ran out first. Says nothing about whether a solution exists.
    GaveUp,
}

/// Search for a signpost set (within the level's inventory) that meets the
/// level's goal, under [`DEFAULT_NODE_BUDGET`]. Prefers fewer posts.
pub fn solve(level: &Level) -> SolveOutcome {
    solve_with(level, Effort::Budget(DEFAULT_NODE_BUDGET))
}

/// [`solve`], with the ceiling named by the caller.
pub fn solve_with(level: &Level, effort: Effort) -> SolveOutcome {
    let mut search = Search::new(level, effort);
    for depth in 0..=level.posts {
        let mut board = level.board();
        if let Some(mut placements) = search.search_at(&mut board, depth) {
            placements.reverse();
            return SolveOutcome::Found(placements);
        }
        if search.gave_up {
            return SolveOutcome::GaveUp;
        }
    }
    SolveOutcome::Unsolvable
}

/// One search, and the fuel it has left.
struct Search<'a> {
    level: &'a Level,
    /// Simulations remaining, or `None` when the caller asked for certainty.
    fuel: Option<u32>,
    /// Set the moment fuel runs out, so "found nothing" can be told apart
    /// from "proved there is nothing".
    gave_up: bool,
    /// Signpost sets already explored and found wanting, each held in a
    /// fixed order so that the same set reached by a different route is
    /// recognised as the same set.
    ///
    /// Signposts are a *set*: placing A then B leaves exactly the board
    /// that placing B then A leaves. The search walks orderings, so without
    /// this it explores all `depth!` of them: six wasted subtrees out of
    /// seven at three posts, twenty-three out of twenty-four at four.
    ///
    /// Ordering the candidates instead would be cheaper and is not sound
    /// here: the candidate set is recomputed at each depth from the board as
    /// it now stands, so a tile can become worth trying only *because* an
    /// earlier signpost sent a crab across it.
    ///
    /// Cleared between depths, and that is not housekeeping: the search runs
    /// once per inventory size, and a set that failed with one post left to
    /// spend says nothing about the same set with two. Carrying the memo
    /// across those runs made `Both Lanes` unsolvable.
    ///
    /// Keyed by `(x, y, Direction::id)` so the set can be sorted and hashed
    /// without asking a sim type to grow orderings it has no other use
    /// for.
    seen: std::collections::HashSet<Vec<(u8, u8, u8)>>,
    /// The signposts standing right now, in placement order.
    placed: Vec<Placement>,
    /// The board every simulation is played on, kept from node to node.
    ///
    /// Neither [`Search::wins`] nor [`Search::visited_placeable_tiles`] may
    /// play the node's own board: that board is the position the search has
    /// to be able to back out to. A `clone` apiece is an allocation per
    /// `Vec` on it, twice per node; [`Board::copy_from`] writes the same
    /// copy into this one and keeps its buffers.
    ///
    /// Never live across a recursive call: each user fills it, reads its
    /// answer out, and is finished with it before recursing, so one board
    /// serves the whole search rather than one per depth.
    sim: Board,
    /// Scratch for [`Search::visited_placeable_tiles`]: one flag per tile,
    /// resized to the board and refilled per call.
    visited: Vec<bool>,
    /// Candidate-tile buffers, handed back here as each level unwinds.
    ///
    /// This one does need a buffer per depth: `run` reads its candidates
    /// for as long as it is looping over them, and that loop spans its
    /// recursive calls. The depth is the level's inventory, so the pool
    /// settles at a handful of buffers and stops growing.
    tile_pool: Vec<Vec<(u8, u8)>>,
    /// Scratch for the memo key, so that a node the memo already holds
    /// costs a lookup and nothing else. Only a node that is new to the memo
    /// allocates, and that allocation is the memo's own entry.
    key: Vec<(u8, u8, u8)>,
}

impl<'a> Search<'a> {
    fn new(level: &'a Level, effort: Effort) -> Self {
        Search {
            level,
            fuel: match effort {
                Effort::Budget(nodes) => Some(nodes),
                Effort::Exhaustive => None,
            },
            gave_up: false,
            seen: std::collections::HashSet::new(),
            placed: Vec::new(),
            sim: level.board(),
            visited: Vec::new(),
            tile_pool: Vec::new(),
            key: Vec::new(),
        }
    }

    /// Charge one simulation to the budget. Once it returns false it returns
    /// false forever, and every caller unwinds without simulating again: a
    /// spent search must stop promptly, not merely stop eventually.
    fn charge(&mut self) -> bool {
        if self.gave_up {
            return false;
        }
        if let Some(fuel) = self.fuel.as_mut() {
            match fuel.checked_sub(1) {
                Some(left) => *fuel = left,
                None => {
                    self.gave_up = true;
                    return false;
                }
            }
        }
        true
    }

    /// Does this exact board win on its own, by the level's own reckoning?
    ///
    /// The judge is [`Level::outcome`], the same one the game uses, rather
    /// than a copy of the all-crabs rule: a Beach Day stage asks for a
    /// number banked, or for nobody eaten, and a solver that only knows how
    /// to bank every crab reports "no solution" for beatable stages.
    fn wins(&mut self, board: &Board) -> bool {
        if !self.charge() {
            return false;
        }
        self.sim.copy_from(board);
        self.level.play_out(&mut self.sim).0 == PuzzleOutcome::Won
    }

    /// Tiles any creature arrives at during a run of the current board: the
    /// only places a new signpost could matter. Gulls count too: a solution
    /// may hinge on steering a gull away from the crabs. Restricted to empty,
    /// signpost-free tiles (the only legal placements).
    ///
    /// Answers into `tiles` rather than into a fresh `Vec`, so that the
    /// caller can lend the same buffer to node after node.
    fn visited_placeable_tiles(&mut self, board: &Board, tiles: &mut Vec<(u8, u8)>) {
        tiles.clear();
        if !self.charge() {
            return;
        }
        self.sim.copy_from(board);
        self.visited.clear();
        self.visited.resize(
            self.sim.width() as usize * self.sim.height() as usize,
            false,
        );
        for _ in 0..Level::deadline(&self.sim) {
            self.sim.tick_idle();
            for crab in self.sim.crabs() {
                self.visited[crab.tile as usize] = true;
            }
            for gull in self.sim.gulls() {
                self.visited[gull.tile as usize] = true;
            }
            if self.sim.crabs().is_empty() {
                break;
            }
        }
        for (x, y, kind) in board.tiles() {
            if self.visited[usize::from(board.index_of(x, y))]
                && kind == TileKind::Empty
                && board.signpost_at(x, y).is_none()
            {
                tiles.push((x, y));
            }
        }
    }

    /// One whole search at a fixed inventory size.
    ///
    /// Within a single call, "how many are placed" and "how many are left"
    /// add to a constant, so the placed set alone identifies a node and the
    /// memo is exact. Across calls it is not, so the memo starts empty.
    fn search_at(&mut self, board: &mut Board, depth: u8) -> Option<Vec<Placement>> {
        self.seen.clear();
        self.placed.clear();
        self.run(board, depth)
    }

    fn run(&mut self, board: &mut Board, depth: u8) -> Option<Vec<Placement>> {
        // Somewhere we have already been, by another road. Nothing about
        // the board depends on how it was reached, so neither does the
        // answer. The leaves are asked too, and they are the ones that
        // matter: a set of `d` posts has up to `d` parents, each playing the
        // full board out again.
        self.key.clear();
        self.key
            .extend(self.placed.iter().map(|(x, y, dir)| (*x, *y, dir.id())));
        self.key.sort_unstable();
        if self.seen.contains(&self.key) {
            return None;
        }
        self.seen.insert(self.key.clone());
        if depth == 0 {
            return self.wins(board).then(Vec::new);
        }
        // Borrowed for the whole loop, recursive calls included, and handed
        // back at the end: see `tile_pool`.
        let mut tiles = self.tile_pool.pop().unwrap_or_default();
        self.visited_placeable_tiles(board, &mut tiles);
        let mut found = None;
        'candidates: for &(x, y) in &tiles {
            for dir in Direction::ALL {
                if self.gave_up {
                    break 'candidates;
                }
                if !board.place_signpost(0, x, y, dir) {
                    continue;
                }
                self.placed.push((x, y, dir));
                if let Some(mut placements) = self.run(board, depth - 1) {
                    placements.push((x, y, dir));
                    found = Some(placements);
                    break 'candidates;
                }
                self.placed.pop();
                board.remove_signpost(0, x, y);
            }
        }
        tiles.clear();
        self.tile_pool.push(tiles);
        found
    }
}

/// Convenience: validate a level exhaustively, returning the solution found
/// (also checks an authored level's claim that it is solvable).
pub fn validate(level: &Level) -> Result<Vec<Placement>, String> {
    match solve_with(level, Effort::Exhaustive) {
        SolveOutcome::Found(placements) => Ok(placements),
        SolveOutcome::Unsolvable => Err(format!("no solution within {} signposts", level.posts)),
        // Unreachable by construction: an exhaustive search has no budget to
        // run out of. Spelled out rather than waved through, so that adding a
        // second way to stop early cannot silently become "no solution".
        SolveOutcome::GaveUp => Err("search gave up".into()),
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn validate_reports_solvability_either_way() {
        let solvable = campaign_levels().remove(1);
        assert!(validate(&solvable).is_ok());
        // A castle sealed on all four sides cannot be solved.
        let text = "name: No\nposts: 1\ncrab: 0,0 R L common\nmap:\n\
+-+-+-+\n|. . .|\n+ +-+ +\n|.|0|.|\n+ +-+ +\n|. . .|\n+-+-+-+\n";
        let level = Level::parse(text).expect("parses");
        let err = validate(&level).unwrap_err();
        assert!(err.contains("no solution"), "{err}");
    }
    use crate::sim::campaign_levels;
    use crate::sim::level::PuzzleOutcome;

    #[test]
    fn solver_cracks_an_early_campaign_level() {
        // Level 2, "First Turn": one post, one crab.
        let levels = campaign_levels();
        let level = &levels[1];
        let SolveOutcome::Found(solution) = solve(level) else {
            panic!("level 2 is solvable");
        };
        assert!(solution.len() <= level.posts as usize);
        // Replay the found solution to be sure.
        let mut board = level.board();
        for &(x, y, dir) in &solution {
            assert!(board.place_signpost(0, x, y, dir));
        }
        let (outcome, _) = level.play_out(&mut board);
        assert_eq!(
            outcome,
            PuzzleOutcome::Won,
            "solver's answer must actually win"
        );
    }

    #[test]
    fn unsolvable_level_returns_none() {
        // A crab orbiting the border with zero posts and an unreachable
        // interior castle: provably unsolvable.
        let text = "\
name: Hopeless
posts: 0
crab: 0,0 R L common
map:
+-+-+-+-+-+
|. . . . .|
+ +-+-+-+ +
|. .|0|. .|
+ +-+-+-+ +
|. . . . .|
+-+-+-+-+-+
";
        let level = Level::parse(text).expect("parses");
        assert_eq!(solve(&level), SolveOutcome::Unsolvable);
    }

    /// The distinction the budget exists to make: the same hopeless board
    /// answers "no solution" when the search is allowed to finish, and "gave
    /// up" when it is not. Both are honest; only the first is a claim about
    /// the level.
    #[test]
    fn a_spent_budget_gives_up_rather_than_claiming_unsolvable() {
        let text = "\
name: Hopeless
posts: 2
crab: 0,0 R L common
map:
+-+-+-+-+-+
|. . . . .|
+ +-+-+-+ +
|. .|0|. .|
+ +-+-+-+ +
|. . . . .|
+-+-+-+-+-+
";
        let level = Level::parse(text).expect("parses");
        assert_eq!(
            solve_with(&level, Effort::Exhaustive),
            SolveOutcome::Unsolvable
        );
        assert_eq!(solve_with(&level, Effort::Budget(4)), SolveOutcome::GaveUp);
    }

    /// A budget must not cost correctness on a board it can afford: one
    /// simulation is enough to see that a level already won needs nothing.
    #[test]
    fn a_budget_large_enough_still_finds_the_answer() {
        let level = &campaign_levels()[1];
        assert_eq!(
            solve_with(level, Effort::Budget(DEFAULT_NODE_BUDGET)),
            solve_with(level, Effort::Exhaustive),
        );
    }
}