use std::{fmt::Debug, hash::Hash};
use hashbrown::HashSet;
use log::{debug, warn};
use crate::{
block::{Block, Line},
board::{Board, LineDirection, LinePosition, Point},
cache::{cache_info, Cached, GrowableCache},
solver::line::{self, LineSolver, UnsolvableLine},
utils::{
abs_sub,
rc::{MutRc, ReadRc, ReadRef},
},
};
#[derive(Debug)]
pub struct Solver<B>
where
B: Block,
{
board: MutRc<Board<B>>,
cache_rows: Option<LineSolverCache<B>>,
cache_cols: Option<LineSolverCache<B>>,
}
trait JobQueue<T> {
fn push(&mut self, job: T);
fn pop(&mut self) -> Option<T>;
fn extend<I: IntoIterator<Item = T>>(&mut self, jobs: I) {
for job in jobs {
self.push(job);
}
}
}
struct SmallJobQueue<T> {
vec: Vec<T>,
}
impl SmallJobQueue<LinePosition> {
fn with_point(point: Point) -> Self {
Self {
vec: vec![LinePosition::Column(point.x), LinePosition::Row(point.y)],
}
}
}
impl<T> JobQueue<T> for SmallJobQueue<T>
where
T: PartialEq + Copy + Debug,
{
fn push(&mut self, job: T) {
self.vec.push(job);
}
fn pop(&mut self) -> Option<T> {
let top_job = self.vec.pop()?;
self.vec.retain(|&x| x != top_job);
debug!("Solving {:?}", top_job);
Some(top_job)
}
}
struct LongJobQueue<T> {
vec: Vec<T>,
visited: HashSet<T>,
}
impl LongJobQueue<LinePosition> {
fn with_height_and_width(height: usize, width: usize) -> Self {
let rows = 0..height;
let columns = 0..width;
let mut jobs: Vec<_> = columns
.map(LinePosition::Column)
.chain(rows.map(LinePosition::Row))
.collect();
jobs.sort_unstable_by_key(|&line_addr| {
let middle = match line_addr.direction() {
LineDirection::Row => height / 2,
LineDirection::Column => width / 2,
};
abs_sub(line_addr.index(), middle)
});
Self {
vec: jobs,
visited: HashSet::new(),
}
}
}
impl<T> JobQueue<T> for LongJobQueue<T>
where
T: Eq + Hash + Copy + Debug,
{
fn push(&mut self, job: T) {
let _ = self.visited.remove(&job);
self.vec.push(job);
}
fn pop(&mut self) -> Option<T> {
let top_job = loop {
let top_job = self.vec.pop()?;
if !self.visited.contains(&top_job) {
break top_job;
}
};
let _ = self.visited.insert(top_job);
debug!("Solving {:?}", top_job);
Some(top_job)
}
}
#[derive(Debug, PartialEq, Eq, Hash)]
struct CacheKey<B>
where
B: Block,
{
line_index: usize,
source: Line<B::Color>,
}
type CacheValue<B> = Result<Line<<B as Block>::Color>, UnsolvableLine>;
type LineSolverCache<B> = GrowableCache<CacheKey<B>, CacheValue<B>>;
const MAX_CACHE_ENTRIES_PER_LINE: usize = 2000;
fn new_cache<B>(capacity: usize) -> LineSolverCache<B>
where
B: Block,
{
GrowableCache::with_capacity(capacity)
}
impl<B> Solver<B>
where
B: Block,
B::Color: Debug,
{
pub fn new(board: MutRc<Board<B>>) -> Self {
Self {
board,
cache_rows: None,
cache_cols: None,
}
}
pub fn with_cache(board: MutRc<Board<B>>) -> Self {
let mut self_ = Self::new(board);
self_.init_cache();
self_
}
fn board(&self) -> ReadRef<'_, Board<B>> {
self.board.read()
}
fn init_cache(&mut self) {
let width = self.board().width();
let height = self.board().height();
self.cache_rows = Some(new_cache(MAX_CACHE_ENTRIES_PER_LINE * height));
self.cache_cols = Some(new_cache(MAX_CACHE_ENTRIES_PER_LINE * width));
}
fn cached_solution(
&mut self,
direction: LineDirection,
key: &CacheKey<B>,
) -> Option<CacheValue<B>> {
let cache = match direction {
LineDirection::Row => self.cache_rows.as_mut(),
LineDirection::Column => self.cache_cols.as_mut(),
};
cache.and_then(|cache| cache.cache_get(key).cloned())
}
fn set_cached_solution(
&mut self,
direction: LineDirection,
key: CacheKey<B>,
solved: CacheValue<B>,
) {
let cache = match direction {
LineDirection::Row => self.cache_rows.as_mut(),
LineDirection::Column => self.cache_cols.as_mut(),
};
if let Some(cache) = cache {
cache.cache_set(key, solved);
}
}
fn print_cache_info(&self) {
if let Some(cache) = &self.cache_cols {
let (s, h, r) = cache_info(cache);
warn!("Cache columns: Size={}, hits={}, hit rate={}.", s, h, r);
}
if let Some(cache) = &self.cache_rows {
let (s, h, r) = cache_info(cache);
warn!("Cache rows: Size={}, hits={}, hit rate={}.", s, h, r);
}
}
pub fn run<S>(&mut self, point: Option<Point>) -> Result<Vec<Point>, UnsolvableLine>
where
S: LineSolver<BlockType = B>,
{
if let Some(point) = point {
debug!("Solving {:?}", point);
let queue = SmallJobQueue::with_point(point);
self.run_jobs::<S, _>(queue)
} else {
let queue = {
let board = self.board();
LongJobQueue::with_height_and_width(board.height(), board.width())
};
self.run_jobs::<S, _>(queue)
}
}
fn run_jobs<S, Q>(&mut self, mut queue: Q) -> Result<Vec<Point>, UnsolvableLine>
where
S: LineSolver<BlockType = B>,
Q: JobQueue<LinePosition>,
{
let mut lines_solved = 0_u32;
let mut solved_cells = vec![];
while let Some(line_pos) = queue.pop() {
if let Some(updated_indexes) = self.update_line::<S>(line_pos)? {
let solved_points = updated_indexes
.iter()
.map(|&updated_index| Point::with_line_and_offset(line_pos, updated_index));
solved_cells.extend(solved_points);
let orthogonal_direction = !line_pos.direction();
queue.extend(updated_indexes.into_iter().rev().map(|new_index| {
LinePosition::with_direction_and_index(orthogonal_direction, new_index)
}));
}
lines_solved += 1;
}
debug!("Lines solved: {}", lines_solved);
Ok(solved_cells)
}
fn update_line<S>(
&mut self,
position: LinePosition,
) -> Result<Option<Vec<usize>>, UnsolvableLine>
where
S: LineSolver<BlockType = B>,
{
let (cache_key, line) = {
let board = self.board();
let line = board.get_line(position);
let cache_index = board.cache_index(position);
let key = CacheKey {
line_index: cache_index,
source: ReadRc::clone(&line),
};
(key, line)
};
let cached = self.cached_solution(position.direction(), &cache_key);
let solution = cached.unwrap_or_else(|| {
let line_desc = self.board().description(position);
debug!(
"Solving {:?}: {:?}. Partial: {:?}",
position, line_desc, line
);
let value = line::solve::<S, _>(line_desc, ReadRc::clone(&line));
self.set_cached_solution(position.direction(), cache_key, value.clone());
value
})?;
let indexes = self.update_solved(position, &line, &solution);
if let Some(indexes) = &indexes {
if !indexes.is_empty() {
debug!("New info on {:?}: {:?}", position, indexes);
}
}
Ok(indexes)
}
fn update_solved(
&self,
position: LinePosition,
old: &[B::Color],
new: &[B::Color],
) -> Option<Vec<usize>> {
if old == new {
return None;
}
let board = &self.board;
match position {
LinePosition::Row(index) => Board::set_row_with_callback(board, index, new),
LinePosition::Column(index) => Board::set_column_with_callback(board, index, new),
}
debug!("Original: {:?}", old);
debug!("Updated: {:?}", new);
#[allow(clippy::if_not_else)]
Some(
old.iter()
.zip(new)
.enumerate()
.filter_map(|(i, (pre, post))| {
if pre != post {
debug!(
"Diff on index={}: original={:?}, updated={:?}",
i, pre, post
);
Some(i)
} else {
None
}
})
.collect(),
)
}
}
impl<B> Drop for Solver<B>
where
B: Block,
{
fn drop(&mut self) {
self.print_cache_info();
}
}