use std::{fmt, iter::once, ops::Not};
use hashbrown::{HashMap, HashSet};
use log::{debug, info, warn};
use smallvec::SmallVec;
use crate::{
block::{
base::{
clues_from_solution,
color::{ColorDesc, ColorId, ColorPalette},
},
Block, Color, Description, Line,
},
utils::{
dedup,
rc::{mutate_ref, InteriorMutableRef, MutRc, ReadRc},
},
};
use self::callbacks::{ChangeColorCallback, RestoreCallback, SetLineCallback};
#[derive(Debug, PartialEq, Eq, Hash, Copy, Clone, PartialOrd, Ord)]
pub struct Point {
pub x: usize,
pub y: usize,
}
impl Point {
pub const fn new(x: usize, y: usize) -> Self {
Self { x, y }
}
#[allow(clippy::missing_const_for_fn)]
pub fn with_line_and_offset(position: LinePosition, offset: usize) -> Self {
let (x, y) = match position {
LinePosition::Row(line_index) => (offset, line_index),
LinePosition::Column(line_index) => (line_index, offset),
};
Self::new(x, y)
}
}
#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
pub enum LinePosition {
Row(usize),
Column(usize),
}
#[allow(clippy::missing_const_for_fn)]
impl LinePosition {
pub fn direction(self) -> LineDirection {
match self {
Self::Row(_) => LineDirection::Row,
Self::Column(_) => LineDirection::Column,
}
}
pub fn index(self) -> usize {
match self {
Self::Row(index) | Self::Column(index) => index,
}
}
pub fn with_direction_and_index(direction: LineDirection, index: usize) -> Self {
match direction {
LineDirection::Row => Self::Row(index),
LineDirection::Column => Self::Column(index),
}
}
}
#[derive(Debug, Copy, Clone)]
pub enum LineDirection {
Row,
Column,
}
impl Not for LineDirection {
type Output = Self;
fn not(self) -> Self::Output {
match self {
Self::Row => Self::Column,
Self::Column => Self::Row,
}
}
}
#[cfg(not(feature = "threaded"))]
mod callbacks {
use super::Point;
pub trait SetLineCallback: Fn(bool, usize) {}
impl<F> SetLineCallback for F where F: Fn(bool, usize) {}
pub trait RestoreCallback: Fn() {}
impl<F> RestoreCallback for F where F: Fn() {}
pub trait ChangeColorCallback: Fn(Point) {}
impl<F> ChangeColorCallback for F where F: Fn(Point) {}
}
#[cfg(feature = "threaded")]
mod callbacks {
use super::Point;
pub trait SetLineCallback: Fn(bool, usize) + Send + Sync {}
impl<F> SetLineCallback for F where F: Fn(bool, usize) + Send + Sync {}
pub trait RestoreCallback: Fn() + Send + Sync {}
impl<F> RestoreCallback for F where F: Fn() + Send + Sync {}
pub trait ChangeColorCallback: Fn(Point) + Send + Sync {}
impl<F> ChangeColorCallback for F where F: Fn(Point) + Send + Sync {}
}
pub struct Board<B>
where
B: Block,
{
cells: Vec<B::Color>,
desc_rows: Vec<ReadRc<Description<B>>>,
desc_cols: Vec<ReadRc<Description<B>>>,
palette: Option<ColorPalette>,
all_colors: Vec<ColorId>,
rows_cache_indexes: Vec<usize>,
cols_cache_indexes: Vec<usize>,
cell_rate_memo: InteriorMutableRef<HashMap<B::Color, f64>>,
on_set_line: Option<Box<dyn SetLineCallback>>,
on_restore: Option<Box<dyn RestoreCallback>>,
on_change_color: Option<Box<dyn ChangeColorCallback>>,
}
impl<B> fmt::Debug for Board<B>
where
B: Block,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(
f,
"Board(height={}, width={}, colors={:?})",
self.height(),
self.width(),
self.all_colors
)
}
}
impl<B> Board<B>
where
B: Block,
B::Color: Copy,
{
#[cfg(test)]
fn with_descriptions(rows: Vec<Description<B>>, columns: Vec<Description<B>>) -> Self {
Self::with_descriptions_and_palette(rows, columns, None)
}
pub fn with_descriptions_and_palette(
rows: Vec<Description<B>>,
columns: Vec<Description<B>>,
palette: Option<ColorPalette>,
) -> Self {
let height = rows.len();
let width = columns.len();
let all_colors = Self::all_colors(&rows);
let init = B::Color::from_color_ids(&all_colors);
warn!("Initializing board: height={}, width={}", height, width);
let cells = vec![init; width * height];
let uniq_indexes = |lines: &[Description<B>]| {
let uniq_lines: Vec<&Vec<B>> = dedup(lines.iter().map(|desc| &desc.vec));
if uniq_lines.len() < lines.len() {
warn!(
"Reducing number of clues: {} --> {}",
lines.len(),
uniq_lines.len()
);
}
lines
.iter()
.map(|desc| {
uniq_lines
.iter()
.position(|&uniq_line| uniq_line == &desc.vec)
.expect("Every line should be present in unique lines")
})
.collect()
};
let rows_cache_indexes = uniq_indexes(&rows);
let cols_cache_indexes = uniq_indexes(&columns);
let desc_rows = rows.into_iter().map(ReadRc::new).collect();
let desc_cols = columns.into_iter().map(ReadRc::new).collect();
Self {
cells,
desc_rows,
desc_cols,
palette,
all_colors,
rows_cache_indexes,
cols_cache_indexes,
cell_rate_memo: InteriorMutableRef::new(HashMap::new()),
on_set_line: None,
on_restore: None,
on_change_color: None,
}
}
fn all_colors(descriptions: &[Description<B>]) -> Vec<ColorId> {
let colors = descriptions
.iter()
.flat_map(Description::colors)
.chain(once(ColorPalette::WHITE_ID));
dedup(colors)
}
pub fn desc_by_id(&self, id: ColorId) -> Option<ColorDesc> {
self.palette
.as_ref()
.and_then(|palette| palette.desc_by_id(id))
}
pub fn iter_rows(&self) -> impl Iterator<Item = &[B::Color]> {
self.cells.chunks(self.width())
}
pub fn descriptions(&self, direction: LineDirection) -> &[ReadRc<Description<B>>] {
match direction {
LineDirection::Row => &self.desc_rows,
LineDirection::Column => &self.desc_cols,
}
}
pub fn description(&self, line_pos: LinePosition) -> ReadRc<Description<B>> {
ReadRc::clone(&self.descriptions(line_pos.direction())[line_pos.index()])
}
pub fn height(&self) -> usize {
self.desc_rows.len()
}
pub fn width(&self) -> usize {
self.desc_cols.len()
}
pub fn is_solved_full(&self) -> bool {
self.cells.iter().copied().all(Color::is_solved)
}
fn get_row_slice(&self, index: usize) -> &[B::Color] {
self.iter_rows().nth(index).expect("Invalid row index")
}
fn get_row(&self, index: usize) -> Line<B::Color> {
self.get_row_slice(index).into()
}
fn get_column_iter(&self, index: usize) -> impl Iterator<Item = &B::Color> {
self.cells.iter().skip(index).step_by(self.width())
}
pub fn get_column(&self, index: usize) -> Line<B::Color> {
self.get_column_iter(index).copied().collect()
}
pub fn get_line(&self, line_pos: LinePosition) -> Line<B::Color> {
match line_pos {
LinePosition::Row(index) => self.get_row(index),
LinePosition::Column(index) => self.get_column(index),
}
}
fn linear_index(&self, row_index: usize, column_index: usize) -> usize {
let width = self.width();
row_index * width + column_index
}
fn set_row(&mut self, index: usize, new: &[B::Color]) {
let row_start = self.linear_index(index, 0);
self.cells[row_start..row_start + new.len()].copy_from_slice(new);
}
fn set_column(&mut self, index: usize, new: &[B::Color]) {
let width = self.width();
let column_indexes = (index..).step_by(width);
for (linear_index, &new_cell) in column_indexes.zip(new) {
if let Some(cell) = self.cells.get_mut(linear_index) {
*cell = new_cell;
}
}
}
fn line_solution_rate<'a>(&self, line: impl Iterator<Item = &'a B::Color>, size: usize) -> f64
where
B::Color: 'a,
{
#![allow(clippy::cast_precision_loss)]
let solved: f64 = line.map(|cell| self.cell_solution_rate(cell)).sum();
solved / size as f64
}
fn cell_solution_rate(&self, cell: &B::Color) -> f64 {
let colors = &self.all_colors;
if !B::Color::memoize_rate() {
return cell.solution_rate(colors);
}
*mutate_ref(&self.cell_rate_memo)
.entry(*cell)
.or_insert_with(|| cell.solution_rate(colors))
}
pub fn row_solution_rate(&self, index: usize) -> f64 {
self.line_solution_rate(self.get_row_slice(index).iter(), self.width())
}
pub fn column_solution_rate(&self, index: usize) -> f64 {
self.line_solution_rate(self.get_column_iter(index), self.height())
}
pub fn solution_rate(&self) -> f64 {
self.line_solution_rate(self.cells.iter(), self.height() * self.width())
}
pub fn unsolved_cells(&self) -> impl Iterator<Item = Point> + '_ {
self.iter_rows().enumerate().flat_map(|(y, row)| {
row.iter().enumerate().filter_map(move |(x, cell)| {
if cell.is_solved() {
None
} else {
Some(Point::new(x, y))
}
})
})
}
pub fn cell(&self, point: &Point) -> B::Color {
let Point { x, y } = *point;
self.cells[self.linear_index(y, x)]
}
fn neighbours(&self, point: &Point) -> SmallVec<[Point; 4]> {
let Point { x, y } = *point;
let mut res = SmallVec::with_capacity(4);
if x > 0 {
res.push(Point::new(x - 1, y));
}
if x < self.width() - 1 {
res.push(Point::new(x + 1, y));
}
if y > 0 {
res.push(Point::new(x, y - 1));
}
if y < self.height() - 1 {
res.push(Point::new(x, y + 1));
}
res
}
pub fn unsolved_neighbours(&self, point: &Point) -> impl Iterator<Item = Point> + '_ {
self.neighbours(point)
.into_iter()
.filter(move |n| !self.cell(n).is_solved())
}
pub fn cache_index(&self, line_pos: LinePosition) -> usize {
match line_pos {
LinePosition::Row(index) => self.rows_cache_indexes[index],
LinePosition::Column(index) => self.cols_cache_indexes[index],
}
}
}
impl<B> Board<B>
where
B: Block,
{
#[allow(dead_code)]
pub fn differs(&self, other: &[B::Color]) -> bool {
self.cells.as_slice() != other
}
pub fn make_snapshot(&self) -> Vec<B::Color> {
self.cells.clone()
}
fn restore(&mut self, cells: Vec<B::Color>) {
self.cells = cells;
if self.is_solved_full() {
let white = 0;
let black = 1;
let solution_matrix: Vec<_> = self
.iter_rows()
.map(|row| {
row.iter()
.map(|&cell| {
if cell == B::Color::blank() {
white
} else {
cell.as_color_id().unwrap_or(black)
}
})
.collect()
})
.collect();
let (columns, rows) = clues_from_solution(&solution_matrix, white);
let columns: Vec<_> = columns.into_iter().map(ReadRc::new).collect();
let rows: Vec<_> = rows.into_iter().map(ReadRc::new).collect();
assert_eq!(self.desc_cols, columns);
assert_eq!(self.desc_rows, rows);
}
}
pub fn diff(&self, other: &[B::Color]) -> Vec<Point> {
let width = self.width();
self.cells
.iter()
.zip(other)
.enumerate()
.filter_map(|(i, (current, other))| {
if current == other {
None
} else {
let x = i % width;
let y = i / width;
Some(Point::new(x, y))
}
})
.collect()
}
}
impl<B> Board<B>
where
B: Block,
B::Color: Copy + fmt::Debug,
{
fn set_color(&mut self, point: &Point, color: &B::Color) {
let old_value = self.cell(point);
let Point { x, y } = *point;
let index = self.linear_index(y, x);
if let Some(cell) = self.cells.get_mut(index) {
*cell = old_value + *color;
}
}
fn unset_color(&mut self, point: &Point, color: &B::Color) -> Result<(), String> {
let old_value = self.cell(point);
let Point { x, y } = *point;
let index = self.linear_index(y, x);
if let Some(cell) = self.cells.get_mut(index) {
*cell = (old_value - *color)?;
}
Ok(())
}
pub fn reduce_colors(&mut self) {
if self.all_colors.len() <= 2 {
return;
}
let width = self.width();
let rows_ranges: Vec<_> = self
.desc_rows
.iter()
.enumerate()
.map(|(row_idx, desc)| {
let color_ranges: HashMap<_, _> = desc.color_ranges(width);
info!(
"First and last block indexes for every color in {}-th row: {:?}",
row_idx, color_ranges
);
color_ranges
})
.collect();
let height = self.height();
let columns_ranges: Vec<_> = self
.desc_cols
.iter()
.enumerate()
.map(|(col_idx, desc)| {
let color_ranges: HashMap<_, _> = desc.color_ranges(height);
info!(
"First and last block indexes for every color in {}-th column: {:?}",
col_idx, color_ranges
);
color_ranges
})
.collect();
let updated_cells: Vec<Vec<_>> = rows_ranges
.iter()
.enumerate()
.map(|(y, row_colors)| {
columns_ranges
.iter()
.enumerate()
.map(|(x, col_colors)| {
let point = Point::new(x, y);
debug!("Checking cell at {:?}", point);
let new_cell_colors: HashSet<_> = self
.all_colors
.iter()
.filter_map(|&color| {
let row_range = row_colors.get(&color);
let col_range = col_colors.get(&color);
if let (Some(row_range), Some(col_range)) = (row_range, col_range) {
debug!(
"Checking color {} in ranges {:?} and {:?}",
color, row_range, col_range
);
if row_range.contains(&x) && col_range.contains(&y) {
return Some(color);
}
}
None
})
.chain(once(ColorPalette::WHITE_ID))
.collect();
let new_cell_colors: Vec<_> = new_cell_colors.into_iter().collect();
B::Color::from_color_ids(&new_cell_colors)
})
.collect()
})
.collect();
for (y, new_row) in updated_cells.iter().enumerate() {
for (x, &new_color) in new_row.iter().enumerate() {
let point = Point::new(x, y);
let current_color = self.cell(&point);
if new_color != current_color {
info!(
"Update cell at {:?}: {:?} --> {:?}",
point, current_color, new_color
);
self.set_color(&point, &new_color);
}
}
}
}
}
#[allow(dead_code)]
impl<B> Board<B>
where
B: Block,
{
pub fn set_callback_on_set_line<CB: SetLineCallback + 'static>(&mut self, f: CB) {
self.on_set_line = Some(Box::new(f));
}
pub fn set_callback_on_restore<CB: RestoreCallback + 'static>(&mut self, f: CB) {
self.on_restore = Some(Box::new(f));
}
pub fn set_callback_on_change_color<CB: ChangeColorCallback + 'static>(&mut self, f: CB) {
self.on_change_color = Some(Box::new(f));
}
}
impl<B> Board<B>
where
B: Block,
{
pub fn set_row_with_callback(self_: &MutRc<Self>, index: usize, new: &[B::Color]) {
self_.write().set_row(index, new);
if let Some(f) = &self_.read().on_set_line {
f(false, index);
}
}
pub fn set_column_with_callback(self_: &MutRc<Self>, index: usize, new: &[B::Color]) {
self_.write().set_column(index, new);
if let Some(f) = &self_.read().on_set_line {
f(true, index);
}
}
pub fn restore_with_callback(self_: &MutRc<Self>, cells: Vec<B::Color>) {
self_.write().restore(cells);
if let Some(f) = &self_.read().on_restore {
f();
}
}
pub fn set_color_with_callback(self_: &MutRc<Self>, point: &Point, color: &B::Color) {
self_.write().set_color(point, color);
if let Some(f) = &self_.read().on_change_color {
f(*point);
}
}
pub fn unset_color_with_callback(
self_: &MutRc<Self>,
point: &Point,
color: &B::Color,
) -> Result<(), String> {
self_.write().unset_color(point, color)?;
if let Some(f) = &self_.read().on_change_color {
f(*point);
}
Ok(())
}
}
impl<B> Clone for Board<B>
where
B: Block,
{
fn clone(&self) -> Self {
Self {
cells: self.make_snapshot(),
desc_rows: self.desc_rows.clone(),
desc_cols: self.desc_cols.clone(),
palette: self.palette.clone(),
all_colors: self.all_colors.clone(),
rows_cache_indexes: self.rows_cache_indexes.clone(),
cols_cache_indexes: self.cols_cache_indexes.clone(),
cell_rate_memo: InteriorMutableRef::new(HashMap::new()),
on_set_line: None,
on_restore: None,
on_change_color: None,
}
}
}
#[cfg(test)]
mod tests {
use crate::block::{
binary::{BinaryBlock, BinaryColor::Undefined},
Description,
};
use super::Board;
#[test]
fn u_letter() {
let rows = vec![
Description::new(vec![BinaryBlock(1), BinaryBlock(1)]),
Description::new(vec![BinaryBlock(1), BinaryBlock(1)]),
Description::new(vec![BinaryBlock(3)]),
];
let columns = vec![
Description::new(vec![BinaryBlock(3)]),
Description::new(vec![BinaryBlock(1)]),
Description::new(vec![BinaryBlock(3)]),
];
let board = Board::with_descriptions(rows, columns);
assert_eq!(board.cells.len(), 9);
assert_eq!(board.get_row(0), vec![Undefined; 3].into());
}
#[test]
fn i_letter() {
let rows = vec![
Description::new(vec![BinaryBlock(1)]),
Description::new(vec![BinaryBlock(0)]),
Description::new(vec![BinaryBlock(1)]),
Description::new(vec![BinaryBlock(1)]),
Description::new(vec![BinaryBlock(1)]),
];
let columns = vec![Description::new(vec![BinaryBlock(1), BinaryBlock(3)])];
let board = Board::with_descriptions(rows, columns);
assert_eq!(board.cells.len(), 5);
assert_eq!(board.get_row(0), vec![Undefined].into());
assert_eq!(board.desc_rows[0].vec, vec![BinaryBlock(1)]);
assert_eq!(board.desc_rows[1].vec, vec![]);
assert_eq!(board.desc_rows[2].vec, vec![BinaryBlock(1)]);
}
}