condor-pathfinding-grid 0.4.0

//! Private candidate contract: optimal-path counting for static weighted grids.
//!
//! **Hypothesis:** counting how many distinct cost-optimal paths connect two
//! cells (the tractable analogue of the upstream `count_paths` idea) exposes
//! tie-density evidence for symmetry-reduction work without materializing any
//! path set.
//!
//! **Non-negotiable behavior:** the count is over paths with exactly the
//! established Dijkstra-optimal cost; counting all simple paths is
//! intentionally out of scope (combinatorial). Counts saturate at `u64::MAX`;
//! the standard invalid/found/no-path outcome and [`BudgetWatch`] apply.
//!
//! **Evidence and promotion:** ordinary `grid_core` route
//! (`just test-fast grid_core`, `just clippy-target grid_core`). Not a
//! [`crate::Pathfinder`], so grid conformance and the bench lane do not cover
//! it directly: promotion is a product-need decision (G-GRID sign-off) plus a
//! small bench-lane extension bounding counting overhead against a single
//! Dijkstra query. This remains
//! private: no feature, fixture, target, or separate harness route.

use std::{cmp::Ordering, collections::BinaryHeap};

use crate::{
    grid::Grid,
    search::{BudgetWatch, GridSearchError, SearchOutcome, SearchRequest, SearchStats},
};

/// Count summary: the optimal cost and how many distinct paths realize it.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct OptimalPathCount {
    /// Exact optimal path cost between the requested endpoints.
    pub cost: usize,
    /// Number of distinct optimal paths, saturating at `u64::MAX`.
    pub paths: u64,
}

/// Result type for optimal-path counting.
pub type OptimalPathCountResult =
    Result<SearchOutcome<OptimalPathCount, SearchStats>, GridSearchError>;

/// Candidate counter of distinct cost-optimal paths between two cells.
///
/// Cost model: sums per-cell `traversal_cost` on 4-connected edges, matching
/// [`super::dijkstra::Dijkstra`].
#[derive(Debug, Default, Clone, Copy)]
pub struct ShortestPathCount;

impl ShortestPathCount {
    /// Stable algorithm identifier for logs and future portfolio wiring.
    pub const NAME: &str = "count-optimal-paths";

    /// Counts distinct optimal paths for `request`.
    pub fn count(&self, grid: &Grid, request: SearchRequest) -> OptimalPathCountResult {
        crate::search::validate_request(grid, request)?;
        let Some(start_index) = grid.index_of(request.start) else {
            return Ok(SearchOutcome::no_path(SearchStats { visited_nodes: 0 }));
        };
        let Some(goal_index) = grid.index_of(request.goal) else {
            return Ok(SearchOutcome::no_path(SearchStats { visited_nodes: 0 }));
        };

        if request.start == request.goal {
            return Ok(SearchOutcome::found(
                OptimalPathCount { cost: 0, paths: 1 },
                SearchStats { visited_nodes: 1 },
            ));
        }

        let watch = BudgetWatch::start(request.budget);
        let mut frontier = BinaryHeap::from([FrontierEntry {
            cost_so_far: 0,
            index: start_index,
        }]);
        let mut best_costs: Vec<Option<usize>> = vec![None; grid.cell_count()];
        let mut path_counts: Vec<u64> = vec![0; grid.cell_count()];
        let mut visited_nodes = 0usize;

        best_costs[start_index] = Some(0);
        path_counts[start_index] = 1;

        // Positive entry costs make the optimal DAG acyclic in settle order, so
        // counts are final when a node is settled.
        while let Some(entry) = frontier.pop() {
            if best_costs[entry.index] != Some(entry.cost_so_far) {
                continue;
            }

            visited_nodes += 1;
            if let Err(reason) = watch.check(visited_nodes) {
                return Err(crate::search::budget_error(reason));
            }

            let current = grid.point_from_index(entry.index);
            for neighbor in grid.neighbors4(current) {
                let neighbor_index = grid
                    .index_of(neighbor)
                    .expect("walkable neighbors must exist inside the grid");
                let edge_cost = grid
                    .traversal_cost(neighbor)
                    .expect("walkable neighbors must have a traversal cost");
                let Some(next_cost) = entry.cost_so_far.checked_add(edge_cost) else {
                    continue;
                };

                match best_costs[neighbor_index] {
                    Some(best) if next_cost > best => {}
                    Some(best) if next_cost == best => {
                        path_counts[neighbor_index] =
                            path_counts[neighbor_index].saturating_add(path_counts[entry.index]);
                    }
                    _ => {
                        best_costs[neighbor_index] = Some(next_cost);
                        path_counts[neighbor_index] = path_counts[entry.index];
                        frontier.push(FrontierEntry {
                            cost_so_far: next_cost,
                            index: neighbor_index,
                        });
                    }
                }
            }
        }

        let Some(goal_cost) = best_costs[goal_index] else {
            return Ok(SearchOutcome::no_path(SearchStats { visited_nodes }));
        };

        Ok(SearchOutcome::found(
            OptimalPathCount {
                cost: goal_cost,
                paths: path_counts[goal_index],
            },
            SearchStats { visited_nodes },
        ))
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct FrontierEntry {
    cost_so_far: usize,
    index: usize,
}

impl Ord for FrontierEntry {
    fn cmp(&self, other: &Self) -> Ordering {
        other
            .cost_so_far
            .cmp(&self.cost_so_far)
            .then_with(|| other.index.cmp(&self.index))
    }
}

impl PartialOrd for FrontierEntry {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

#[cfg(test)]
mod tests {
    use crate::{
        algorithms::shortest_path_count::{OptimalPathCount, ShortestPathCount},
        grid::{Cell, Grid},
        point::Point,
        search::SearchRequest,
    };

    #[test]
    fn open_rectangle_counts_lattice_paths() {
        let grid = Grid::new(3, 3).expect("grid dimensions are valid");
        let outcome = ShortestPathCount
            .count(
                &grid,
                SearchRequest::new(Point::new(0, 0), Point::new(2, 2)),
            )
            .expect("endpoints are walkable");
        assert_eq!(
            outcome.path().copied(),
            Some(OptimalPathCount { cost: 4, paths: 6 })
        );
    }

    #[test]
    fn corridor_counts_one_path() {
        let mut grid = Grid::new(5, 5).expect("grid dimensions are valid");
        for y in 0..5 {
            if y != 2 {
                grid.set_cell(Point::new(2, y), Cell::Blocked)
                    .expect("valid grid edit");
            }
        }
        let outcome = ShortestPathCount
            .count(
                &grid,
                SearchRequest::new(Point::new(0, 2), Point::new(4, 2)),
            )
            .expect("endpoints are walkable");
        assert_eq!(outcome.path().map(|count| count.paths), Some(1));
    }

    #[test]
    fn reports_when_no_path_exists() {
        let mut grid = Grid::new(3, 3).expect("grid dimensions are valid");
        for x in 0..3 {
            grid.set_cell(Point::new(x, 1), Cell::Blocked)
                .expect("valid grid edit");
        }
        let outcome = ShortestPathCount
            .count(
                &grid,
                SearchRequest::new(Point::new(0, 0), Point::new(2, 2)),
            )
            .expect("endpoints are walkable");
        assert!(!outcome.is_found());
    }
}