use std::collections::BTreeMap;
use pathfinding::prelude::Matrix;
use crate::cats::Colour::*;
use crate::cats::Direction::*;
use crate::cats::Transformation::*;
use crate::cats::Transformation;
use crate::cats::{Colour, Direction};
use crate::cell::*;
use crate::shape::*;
#[derive(Debug, Hash, Clone, PartialEq, Eq)]
pub struct Grid {
pub colour: Colour,
pub cells: Matrix<Cell>,
}
impl Grid {
pub fn new(rows: usize, cols: usize, colour: Colour) -> Self {
if cols > 100 || rows > 100 {
return Self::trivial();
}
let cells: Matrix<Cell> = Matrix::from_fn(rows, cols, |(x, y)| Cell::new_colour(x, y, colour));
Self { colour, cells }
}
pub fn trivial() -> Self {
Grid::new(0, 0, Black)
}
pub fn dummy() -> Self {
Grid::new(2, 2, Black)
}
pub fn is_trivial(&self) -> bool {
self.cells.rows == 0 && self.cells.columns == 0 && self.colour == Black
}
pub fn is_dummy(&self) -> bool {
self.cells.rows == 2 && self.cells.columns == 2 && self.colour == Black
}
pub fn new_from_matrix(cells: &Matrix<Cell>) -> Self {
let mut colour = NoColour;
for c in cells.values() {
if c.colour != Black {
if colour == NoColour {
colour = c.colour;
} else if colour != c.colour {
colour = Mixed;
break;
}
}
}
Self { colour, cells: cells.clone() }
}
pub fn duplicate(grid: &[Vec<usize>]) -> Self {
let x: usize = grid.len();
let y: usize = grid[0].len();
let mut colour = NoColour;
let cells: Matrix<Cell> = Matrix::from_fn(x, y, |(x, y)| Cell::new(x, y, grid[x][y]));
for c in cells.values() {
if c.colour != Black {
if colour == NoColour {
colour = c.colour;
} else if colour != c.colour {
colour = Mixed;
break;
}
}
}
Self { colour, cells }
}
pub fn is_empty(&self) -> bool {
for c in self.cells.values() {
if c.colour != Black {
return false
}
}
true
}
pub fn find_colour(&self, colour: Colour) -> Vec<Cell> {
self.cells.values().filter(|c| c.colour == colour).cloned().collect()
}
pub fn in_to_squared_out(&self) -> Self {
let rows = self.cells.rows;
let cols = self.cells.columns;
if rows != cols {
return Grid::trivial();
}
let mut g = Self::new(rows * rows, cols * cols, Black);
for r in (0 .. rows * rows).step_by(rows) {
for c in (0 .. cols * cols).step_by(cols) {
g.copy_to_position_mut(self, r, c);
}
}
g
}
pub fn find_colours(&self) -> BTreeMap<Colour, usize> {
let mut c: BTreeMap<Colour, usize> = BTreeMap::new();
for cell in self.cells.values() {
*c.entry(cell.colour).or_insert(0) += 1;
}
c
}
pub fn find_min_colour(&self) -> Colour {
let cols = self.find_colours();
let col = cols.iter()
.filter(|(&col, _)| col != Black)
.min_by(|col, c| col.1.cmp(c.1))
.map(|(col, _)| col);
if let Some(col) = col {
*col
} else {
NoColour
}
}
pub fn find_max_colour(&self) -> Colour {
let cols = self.find_colours();
let col = cols.iter()
.filter(|(&col, _)| col != Black)
.max_by(|col, c| col.1.cmp(c.1))
.map(|(col, _)| col);
if let Some(col) = col {
*col
} else {
NoColour
}
}
pub fn stretch_down(&self) -> Grid {
let mut m = Matrix::new(self.cells.rows, self.cells.columns, Cell::new(0, 0, 0));
for y in 0 .. self.cells.columns {
let mut colour = NoColour;
for x in 1 .. self.cells.rows {
if self.cells[(x - 1,y)].colour != Black {
if colour == NoColour {
colour = self.cells[(x - 1,y)].colour;
m[(x - 1,y)].colour = colour;
} else {
continue;
}
}
m[(x,y)].row = x;
m[(x,y)].col = y;
m[(x,y)].colour = if colour == NoColour {
self.cells[(x,y)].colour
} else {
colour
};
}
}
Grid::new_from_matrix(&m)
}
pub fn is_diag_origin(&self) -> bool {
if !self.is_square() || self.colour == Mixed {
return false;
}
for ((r, c), cell) in self.cells.items() {
if r != c && cell.colour != Black {
return false;
}
}
true
}
pub fn is_diag_not_origin(&self) -> bool {
self.rot_90().is_diag_origin()
}
pub fn gravity_down(&self) -> Grid {
let mut values: Vec<Colour> = vec![Black;self.cells.columns];
let mut counts: Vec<usize> = vec![0;self.cells.columns];
for ((r, c), cell) in self.cells.items() {
if self.cells[(r,c)].colour != Black {
if values[c] == Black {
values[c] = cell.colour;
}
counts[c] += 1;
}
}
let mut m = self.cells.clone();
for (r, c) in self.cells.keys() {
if self.cells[(r,c)].colour == Black {
m[(r,c)].colour = values[c];
}
if self.cells.rows - r > counts[c] {
m[(r,c)].colour = Black;
}
}
Grid::new_from_matrix(&m)
}
pub fn gravity_up(&self) -> Grid {
self.mirrored_rows().gravity_down().mirrored_rows()
}
pub fn move_down(&self) -> Grid {
let mut m = Matrix::new(self.cells.rows, self.cells.columns, Cell::new(0, 0, 0));
for r in 1 .. self.cells.rows {
for c in 0 .. self.cells.columns {
m[(r,c)].row = r;
m[(r,c)].col = c;
m[(r,c)].colour = self.cells[(r - 1,c)].colour;
}
}
Grid::new_from_matrix(&m)
}
pub fn move_up(&self) -> Grid {
let mut m = Matrix::new(self.cells.rows, self.cells.columns, Cell::new(0, 0, 0));
for r in 1 .. self.cells.rows {
for c in 0 .. self.cells.columns {
m[(r,c)].row = r;
m[(r,c)].col = c;
m[(r - 1,c)].colour = self.cells[(r,c)].colour;
}
}
Grid::new_from_matrix(&m)
}
pub fn move_right(&self) -> Grid {
let mut m = Matrix::new(self.cells.rows, self.cells.columns, Cell::new(0, 0, 0));
for r in 0 .. self.cells.rows {
for c in 1 .. self.cells.columns {
m[(r,c)].row = r;
m[(r,c)].col = c;
m[(r,c)].colour = self.cells[(r,c - 1)].colour;
}
}
Grid::new_from_matrix(&m)
}
pub fn move_left(&self) -> Grid {
let mut m = Matrix::new(self.cells.rows, self.cells.columns, Cell::new(0, 0, 0));
for r in 0 .. self.cells.rows {
for c in 1 .. self.cells.columns {
m[(r,c)].row = r;
m[(r,c)].col = c;
m[(r,c - 1)].colour = self.cells[(r,c)].colour;
}
}
Grid::new_from_matrix(&m)
}
pub fn trim(&self, r: usize, c: usize) -> Self {
if self.cells.rows <= r && self.cells.columns <= c {
return self.clone();
}
let mut grid = Grid::new(r, c, Black);
for ((r, c), cell) in self.cells.items() {
if r < grid.cells.rows && c < grid.cells.columns {
grid.cells[(r,c)].row = cell.row;
grid.cells[(r,c)].col = cell.col;
grid.cells[(r,c)].colour = cell.colour;
}
}
grid
}
pub fn free_border(&self, dir: Direction) -> bool {
match dir {
Up => {
for i in 0 .. self.cells.columns {
if self.cells[(0, i)].colour != Black {
return false;
}
}
true
},
Down => {
for i in 0 .. self.cells.columns {
if self.cells[(self.cells.rows - 1, i)].colour != Black {
return false;
}
}
true
},
Left => {
for i in 0 .. self.cells.rows {
if self.cells[(i, 0)].colour != Black {
return false;
}
}
true
},
Right => {
for i in 0 .. self.cells.rows {
if self.cells[(i, self.cells.columns - 1)].colour != Black {
return false;
}
}
true
},
_ => false
}
}
pub fn recolour(&self, from: Colour, to: Colour) -> Self {
let mut grid = self.clone();
grid.recolour_mut(from, to);
grid
}
pub fn recolour_mut(&mut self, from: Colour, to: Colour) {
for c in self.cells.values_mut() {
if c.colour == from || from == NoColour {
c.colour = to;
}
}
}
pub fn force_recolour(&self, to: Colour) -> Self {
let mut grid = self.clone();
grid.colour = to;
for c in grid.cells.values_mut() {
c.colour = to;
}
grid
}
pub fn copy_to_position(&self, grid: &Self, r: usize, c: usize) -> Self {
let mut i = self.clone();
i.copy_to_position_mut(grid, r, c);
i
}
pub fn copy_to_position_mut(&mut self, grid: &Self, rp: usize, cp: usize) {
if rp + grid.cells.rows > self.cells.rows || cp + grid.cells.columns > self.cells.columns {
return;
}
for ((r, c), cell) in grid.cells.items() {
self.cells[(rp + r, cp + c)] = cell.clone();
}
}
pub fn copy_shape_to_grid_mut(&mut self, shape: &Shape) {
self.copy_shape_to_grid_position_mut(shape, shape.orow, shape.ocol)
}
pub fn copy_shape_to_grid_position_mut(&mut self, shape: &Shape, row: usize, col: usize) {
for (r, c) in shape.cells.keys() {
if row+r >= self.cells.rows || col+c >= self.cells.columns {
continue;
}
self.cells[(row+r, col+c)].colour = shape.cells[(r,c)].colour;
}
}
pub fn draw_lines(&mut self, shapes: &[&Shape], overwrite: bool, hv: bool) {
for (j, s) in shapes.iter().enumerate() {
for shape in shapes.iter().skip(j) {
if hv {
self.draw_line_row(s, shape, s.colour, false, false);
} else {
self.draw_line_col(s, shape, s.colour, false, false);
}
}
}
for (j, s) in shapes.iter().enumerate() {
for shape in shapes.iter().skip(j) {
if hv {
self.draw_line_col(s, shape, s.colour, overwrite, false);
} else {
self.draw_line_row(s, shape, s.colour, overwrite, false);
}
}
}
}
pub fn draw_mut(&mut self, dir: Direction, r: usize, c: usize, colour: Colour) {
self.draw_bg_mut(dir, r, c, colour, Black);
}
pub fn draw_bg_mut(&mut self, dir: Direction, r: usize, c: usize, colour: Colour, bg: Colour) {
fn change_colour(cell_colour: &mut Colour, colour: Colour, bg: Colour) {
if *cell_colour == bg || *cell_colour == colour {
*cell_colour = colour;
}
}
match dir {
Up => {
for r in 0 ..= r {
change_colour(&mut self.cells[(r,c)].colour, colour, bg);
}
},
Down => {
for r in r .. self.cells.rows {
change_colour(&mut self.cells[(r,c)].colour, colour, bg);
}
},
Left => {
for c in 0 ..= c {
change_colour(&mut self.cells[(r,c)].colour, colour, bg);
}
},
Right => {
for c in c .. self.cells.columns {
change_colour(&mut self.cells[(r,c)].colour, colour, bg);
}
},
UpRight => {
for (r, c) in ((0 ..= r).rev()).zip(0 ..= self.cells.columns) {
if r < self.cells.rows && c < self.cells.columns {
change_colour(&mut self.cells[(r,c)].colour, colour, bg);
}
}
},
UpLeft => {
for (r, c) in ((0 ..= r).rev()).zip((0 ..= c).rev()) {
if r < self.cells.rows && c < self.cells.columns {
change_colour(&mut self.cells[(r,c)].colour, colour, bg);
}
}
},
DownRight => {
for (r, c) in (r .. self.cells.rows).zip(c .. self.cells.columns) {
if r < self.cells.rows && c < self.cells.columns {
change_colour(&mut self.cells[(r,c)].colour, colour, bg);
}
}
},
DownLeft => {
for (r, c) in (r .. self.cells.rows).zip((0 ..= c).rev()) {
if r < self.cells.rows && c < self.cells.columns {
change_colour(&mut self.cells[(r,c)].colour, colour, bg);
}
}
},
FromUpRight => {
for (r, c) in (0 ..= r).rev().zip(c-1 .. self.cells.columns) {
change_colour(&mut self.cells[(r,c)].colour, colour, bg);
}
},
FromUpLeft => {
for (r, c) in (0 ..= r).zip(0 ..= c) {
change_colour(&mut self.cells[(r,c)].colour, colour, bg);
}
},
FromDownRight => {
for (r, c) in (r .. self.cells.rows).zip(c .. self.cells.columns) {
change_colour(&mut self.cells[(r,c)].colour, colour, bg);
}
},
FromDownLeft => {
for (r, c) in (r-1 .. self.cells.rows).zip((0 ..= c).rev()) {
change_colour(&mut self.cells[(r,c)].colour, colour, bg);
}
},
_ => {},
}
}
pub fn draw_line_row(&mut self, s1: &Shape, s2: &Shape, colour: Colour, overwrite: bool, fill: bool) {
let r1 = s1.orow;
let c1 = s1.ocol;
let r2 = s2.orow;
let c2 = s2.ocol;
self.draw_line_row_coords(r1, c1, r2, c2, colour, overwrite, fill, s1.cells.columns);
}
#[allow(clippy::too_many_arguments)]
pub fn draw_line_row_coords(&mut self, r1: usize, c1: usize, r2: usize, c2: usize, colour: Colour, overwrite: bool, fill: bool, thick: usize) {
if r1 == r2 && c1 != c2 {
for y in c1.min(c2)+1 .. c1.max(c2) {
for t in 0 .. thick {
if self.cells.rows <= r1+t || self.cells.columns <= y {
break;
}
if overwrite || self.cells[(r1+t,y)].colour == Black {
if overwrite && fill && self.cells[(r1+t,y)].colour != Black {
self.flood_fill_bg_mut(r1+t, y, self.cells[(r1+t,y)].colour, NoColour, colour);
} else {
if overwrite && fill && self.cells[(r1+t-1,y)].colour != Black {
self.flood_fill_bg_mut(r1+t-1, y, self.cells[(r1+t-1,y)].colour, NoColour, colour);
}
self.cells[(r1+t,y)].colour = colour;
if overwrite && fill && self.cells[(r1+t+1,y)].colour != Black {
self.flood_fill_bg_mut(r1+t+1, y, self.cells[(r1+t+1,y)].colour, NoColour, colour);
}
}
}
}
}
}
}
pub fn draw_line_col(&mut self, s1: &Shape, s2: &Shape, colour: Colour, overwrite: bool, fill: bool) {
let r1 = s1.orow;
let c1 = s1.ocol;
let r2 = s2.orow;
let c2 = s2.ocol;
self.draw_line_col_coords(r1, c1, r2, c2, colour, overwrite, fill, s1.cells.rows);
}
#[allow(clippy::too_many_arguments)]
pub fn draw_line_col_coords(&mut self, r1: usize, c1: usize, r2: usize, c2: usize, colour: Colour, overwrite: bool, fill: bool, thick: usize) {
if c1 == c2 && r1 != r2 {
for x in r1.min(r2)+1 .. r1.max(r2) {
for t in 0 .. thick {
if self.cells.rows <= x || self.cells.columns <= c1+t {
break;
}
if overwrite || self.cells[(x,c1+t)].colour == Black {
if overwrite && fill && self.cells[(x,c1+t)].colour != Black {
self.flood_fill_bg_mut(x, c1+t, self.cells[(x,c1+t)].colour, NoColour, colour);
} else {
if overwrite && fill && self.cells[(x,c1+t-1)].colour != Black {
self.flood_fill_bg_mut(x, c1+t-1, self.cells[(x,c1+t-1)].colour, NoColour, colour);
}
self.cells[(x,c1+t)].colour = colour;
if overwrite && fill && self.cells[(x,c1+t+1)].colour != Black {
self.flood_fill_bg_mut(x, c1+t+1, self.cells[(x,c1+t+1)].colour, NoColour, colour);
}
}
}
}
}
}
}
fn extend(&self, lr: bool) -> Self {
self.extend_by(lr, 2)
}
fn extend_by(&self, lr: bool, amount: usize) -> Self {
let rows = self.cells.rows;
let cols = self.cells.columns;
let mut grid = if lr {
Grid::new(rows, cols * amount, Black)
} else {
Grid::new(rows * amount, cols, Black)
};
for ((r, c), cell) in self.cells.items() {
grid.cells[(r,c)].row = r;
grid.cells[(r,c)].col = c;
grid.cells[(r,c)].colour = cell.colour;
}
grid.colour = self.colour;
grid
}
pub fn extend_right(&self) -> Self {
self.extend(true)
}
pub fn extend_left(&self) -> Self {
self.mirrored_cols().extend(true).mirrored_cols()
}
pub fn extend_down(&self) -> Self {
self.extend(false)
}
pub fn extend_up(&self) -> Self {
self.mirrored_rows().extend(false).mirrored_rows()
}
pub fn extend_right_by(&self, amount: usize) -> Self {
self.extend_by(true, amount)
}
pub fn extend_left_by(&self, amount: usize) -> Self {
self.mirrored_cols().extend_by(true, amount).mirrored_cols()
}
pub fn extend_down_by(&self, amount: usize) -> Self {
self.extend_by(false, amount)
}
pub fn extend_up_by(&self, amount: usize) -> Self {
self.mirrored_rows().extend_by(false, amount).mirrored_rows()
}
pub fn dup_func(&self, lr: bool, func: &dyn Fn(&Self) -> Self) -> Self {
let rows = self.cells.rows;
let cols = self.cells.columns;
let mut grid = if lr {
let temp = self.mirrored_cols().extend_right();
let temp = &func(&temp);
temp.mirrored_cols()
} else {
let temp = self.mirrored_rows().extend_down();
let temp = &func(&temp);
temp.mirrored_rows()
};
for r in 0 .. rows {
for c in 0 .. cols {
grid.cells[(r,c)].row = r;
grid.cells[(r,c)].col = c + cols;
grid.cells[(r,c)].colour = self.cells[(r,c)].colour;
}
}
grid.colour = self.colour;
grid
}
fn dup(&self, lr: bool) -> Self {
self.dup_func(lr, &|g| g.clone())
}
pub fn dup_right(&self) -> Self {
self.dup(true)
}
pub fn dup_left(&self) -> Self {
self.mirrored_cols().dup(true).mirrored_cols()
}
pub fn dup_down(&self) -> Self {
self.dup(false)
}
pub fn dup_up(&self) -> Self {
self.mirrored_rows().dup(false).mirrored_rows()
}
pub fn dup_right_func(&self, func: &dyn Fn(&Self) -> Self) -> Self {
self.dup_func(true, &func)
}
pub fn dup_left_func(&self, func: &dyn Fn(&Self) -> Self) -> Self {
self.mirrored_cols().dup_func(true, &func).mirrored_cols()
}
pub fn dup_down_func(&self, func: &dyn Fn(&Self) -> Self) -> Self {
self.dup_func(false, &func)
}
pub fn dup_up_func(&self, func: &dyn Fn(&Self) -> Self) -> Self {
self.mirrored_rows().dup_func(false, &func).mirrored_rows()
}
pub fn mirror_dir_func(&self, lr: bool, func: &dyn Fn(&Self) -> Self) -> Self {
let rows = self.cells.rows;
let cols = self.cells.columns;
let mut grid = if lr {
let temp = self.extend_right();
let temp = &func(&temp);
temp.mirrored_cols()
} else {
let temp = self.extend_down();
let temp = &func(&temp);
temp.mirrored_rows()
};
for r in 0 .. rows {
for c in 0 .. cols {
grid.cells[(r,c)].row = r;
grid.cells[(r,c)].col = c;
grid.cells[(r,c)].colour = self.cells[(r,c)].colour;
}
}
grid.colour = self.colour;
grid
}
pub fn mirror_dir(&self, lr: bool) -> Self {
self.mirror_dir_func(lr, &|g| g.clone())
}
pub fn mirror_right(&self) -> Self {
self.mirror_dir(true)
}
pub fn mirror_left(&self) -> Self {
self.mirrored_cols().mirror_dir(true).mirrored_cols()
}
pub fn mirror_down(&self) -> Self {
self.mirror_dir(false)
}
pub fn mirror_up(&self) -> Self {
self.mirrored_rows().mirror_dir(false).mirrored_rows()
}
pub fn mirror_right_func(&self, func: &dyn Fn(&Self) -> Self) -> Self {
self.mirror_dir_func(true, &func)
}
pub fn mirror_left_func(&self, func: &dyn Fn(&Self) -> Self) -> Self {
self.mirrored_cols().mirror_dir_func(true, &func).mirrored_cols()
}
pub fn mirror_down_func(&self, func: &dyn Fn(&Self) -> Self) -> Self {
self.mirror_dir_func(false, &func)
}
pub fn mirror_up_func(&self, func: &dyn Fn(&Self) -> Self) -> Self {
self.mirrored_rows().mirror_dir_func(false, &func).mirrored_rows()
}
pub fn pixels(&self) -> usize {
self.cells.values()
.filter(|c| c.colour != Black).
count()
}
pub fn transform(&self, trans: Transformation) -> Self {
match trans {
NoTrans => self.clone(),
MirrorX => self.mirrored_rows(),
MirrorY => self.mirrored_cols(),
Trans => self.transposed(),
Rotate90 => self.rot_rect_90(),
Rotate180 => self.rot_rect_180(),
Rotate270 => self.rot_rect_270(),
Rotate90MirrorX => self.rot_rect_90().mirrored_rows(),
Rotate180MirrorX => self.rot_rect_180().mirrored_rows(),
Rotate270MirrorX => self.rot_rect_270().mirrored_rows(),
Rotate90MirrorY => self.rot_rect_90().mirrored_cols(),
Rotate180MirrorY => self.rot_rect_180().mirrored_cols(),
Rotate270MirrorY => self.rot_rect_270().mirrored_cols(),
MirrorXRotate90 => self.mirrored_rows().rot_rect_90(),
MirrorXRotate180 => self.mirrored_rows().rot_rect_180(),
MirrorXRotate270 => self.mirrored_rows().rot_rect_270(),
MirrorYRotate90 => self.mirrored_cols().rot_rect_90(),
MirrorYRotate180 => self.mirrored_cols().rot_rect_180(),
MirrorYRotate270 => self.mirrored_cols().rot_rect_270(),
}
}
pub fn inverse_transform(&self, trans: Transformation) -> Self {
let trans = Transformation::inverse(&trans);
self.transform(trans)
}
pub fn size(&self) -> usize {
self.cells.columns * self.cells.rows
}
pub fn same_size(&self, other: &Self) -> bool {
self.size() == other.size()
}
pub fn same_shape(&self, other: &Self) -> bool {
self.cells.rows == other.cells.rows && self.cells.columns == other.cells.columns
}
pub fn dimensions(&self) -> (usize, usize) {
(self.cells.columns, self.cells.rows)
}
pub fn add_border(&self, n: usize) -> Self {
self.add_border_colour(n, Black)
}
pub fn add_border_colour(&self, n: usize, colour: Colour) -> Self {
let mut g = Self::new(self.cells.rows + n * 2, self.cells.columns + n * 2, colour);
g.copy_to_position_mut(self, n, n);
g
}
pub fn remove_border(&self, n: usize) -> Self {
if self.cells.rows < n * 2 || self.cells.columns < n * 2 {
return self.clone();
}
self.subgrid(n, self.cells.rows - n * 2, n, self.cells.columns - n * 2)
}
pub fn max_dim(&self) -> usize {
self.cells.rows.max(self.cells.columns)
}
pub fn derive_missing_rule(&self, other: &Self) -> Self {
if self.cells.rows == 1 || self.cells.columns == 0 ||other.cells.rows % self.cells.rows != 0 || other.cells.columns % self.cells.columns != 0 {
return Self::trivial();
}
let sg = other.subgrid(0, self.cells.rows, 0, self.cells.columns);
match self.diff(&sg) {
Some(diff) => diff,
None => Self::trivial(),
}
}
pub fn apply_missing_rule(&self, other: &Self) -> Self {
let mut grid = self.clone();
for ((r, c), cell) in self.cells.items() {
if cell.colour != Black {
grid.copy_centre(r, c, other);
}
}
grid
}
pub fn copy_centre(&mut self, cr: usize, cc: usize, other: &Self) {
if other == &Grid::trivial() {
return;
}
let centre_r = (other.cells.rows / 2) as isize;
let centre_c = (other.cells.columns / 2) as isize;
let or = centre_r - cr as isize;
let oc = centre_c - cc as isize;
let rs = if or < 0 { 0 } else { or as usize };
let re = if or < 0 {
let incdec = if or < -1 { 1 } else { -1 };
(other.cells.rows as isize + or + incdec) as usize
} else {
other.cells.rows
};
let cs = if oc < 0 { 0 } else { oc as usize };
let ce = if oc < 0 {
let incdec = if oc < -1 { 1 } else { -1 };
(other.cells.columns as isize + oc + incdec) as usize
} else {
other.cells.columns
};
for r in rs .. re {
for c in cs .. ce {
let colour = other.cells[(r, c)].colour;
let sr = (r as isize - or) as usize;
let sc = (c as isize - oc) as usize;
if sr >= self.cells.rows || sc >= self.cells.columns {
continue;
}
if !colour.is_same() && colour != Black && self.cells[(sr, sc)].colour == Black {
self.cells[(sr, sc)].colour = colour.to_base();
}
}
}
}
pub fn fill_border(&mut self) {
let hr = self.cells.rows / 2;
let hc = self.cells.columns / 2;
for layer in 0 .. hr.min(hc) {
let mut cc = NoColour;
for i in layer .. self.cells.rows - layer {
let c = self.cells[(i,layer)].colour;
if c != Black && cc == NoColour {
cc = c;
} else if c != Black && c != cc {
return;
}
}
for i in layer .. self.cells.columns - layer {
let c = self.cells[(layer,i)].colour;
if c != Black && cc == NoColour {
cc = c;
} else if c != Black && c != cc {
return;
}
}
for i in layer .. self.cells.rows - layer {
let c = self.cells[(i,layer)].colour;
if c == Black {
self.cells[(i,layer)].colour = cc;
}
}
for i in layer .. self.cells.columns - layer {
let c = self.cells[(layer, i)].colour;
if c == Black {
self.cells[(layer,i)].colour = cc;
}
}
}
}
pub fn has_colour(&self, tlr: usize, tlc: usize, rlen: usize, clen: usize, colour: Colour) -> bool {
for r in tlr .. rlen {
for c in tlc .. clen {
if self.cells[(r,c)].colour == colour {
return true;
}
}
}
false
}
pub fn find_row_seq(&self, sr: usize, sc: usize, seq: &[Colour], width: usize) -> (usize, usize) {
let mut cnt = 0;
let mut xp = 0;
let mut rs = usize::MAX;
let mut cs = usize::MAX;
'outer:
for r in 0 .. self.cells.columns - width {
for c in 0 .. self.cells.rows - seq.len() {
if c == sr+1 && r <= sc { continue 'outer};
let cell = self.cells[(c,r)].clone();
if xp != r {
xp = r;
cnt = 0;
rs = usize::MAX;
cs = usize::MAX;
}
if seq[cnt] == cell.colour {
if !self.has_colour(c, r, seq.len(), width, Black) {
if cnt == 0 {
rs = c;
cs = r;
}
if cnt == seq.len() - 1 {
break 'outer;
}
cnt += 1;
}
} else if cnt > 0 {
cnt = 0;
rs = usize::MAX;
cs = usize::MAX;
}
}
}
(rs, cs)
}
pub fn find_col_seq(&self, sr: usize, sc: usize, seq: &[Colour], length: usize) -> (usize, usize) {
let mut cnt = 0;
let mut rp = 0;
let mut rs = usize::MAX;
let mut cs = usize::MAX;
'outer:
for r in 0 .. self.cells.rows - length {
for c in 0 .. self.cells.columns - seq.len() {
if c == sc+1 && r <= sr { continue 'outer};
let cell = self.cells[(r,c)].clone();
if rp != r {
rp = r;
cnt = 0;
rs = usize::MAX;
cs = usize::MAX;
}
if seq[cnt] == cell.colour {
if !self.has_colour(r, c, length, seq.len(), Black) {
if cnt == 0 {
rs = r;
cs = c;
}
cnt += 1;
if cnt == seq.len() {
break 'outer;
}
}
} else if cnt > 0 {
cnt = 0;
rs = usize::MAX;
cs = usize::MAX;
}
}
}
(rs, cs)
}
pub fn colour_every_nxn_for_m(colour: Colour, side: usize, n: usize, m: usize) -> Grid {
if m == 0 || n == 0 {
return Grid::trivial();
}
let mut grid = Grid::new(side, side, Black);
let mut count = 0;
'outer:
for r in 0 .. side {
for c in 0 .. side {
if (r + grid.cells.rows * c) % n == 0 {
grid.cells[(r, c)].colour = colour;
count += 1;
}
if count == m {
break 'outer;
}
}
}
grid
}
pub fn colour_dimensions(&self, colour: Colour) -> (usize, usize) {
let mut min_r: usize = usize::MAX;
let mut max_r: usize = 0;
let mut min_c: usize = usize::MAX;
let mut max_c: usize = 0;
for ((x, y), c) in self.cells.items() {
if c.colour == colour {
min_r = x.min(min_r);
max_r = x.max(max_r);
min_c = y.min(min_c);
max_c = y.max(max_c);
}
}
(max_r - min_r + 1, max_c - min_c + 1)
}
pub fn bigger(&self, other: &Self) -> bool {
self.size() > other.size()
}
pub fn smaller(&self, other: &Self) -> bool {
self.size() < other.size()
}
pub fn cell_count(&self) -> usize {
self.cell_count_colour(Black)
}
pub fn cell_count_colour(&self, colour: Colour) -> usize {
self.cells.values().filter(|c| c.colour != colour).count()
}
pub fn flood_fill(&self, x: usize, y: usize, ignore_colour: Colour, new_colour: Colour) -> Self {
self.flood_fill_bg(x, y, ignore_colour, Black, new_colour)
}
pub fn flood_fill_bg(&self, r: usize, c: usize, ignore_colour: Colour, bg: Colour, new_colour: Colour) -> Self {
let mut grid = self.clone();
grid.flood_fill_bg_mut(r, c, ignore_colour, bg, new_colour);
grid
}
pub fn flood_fill_mut(&mut self, r: usize, c: usize, ignore_colour: Colour, new_colour: Colour) {
self.flood_fill_bg_mut(r, c, ignore_colour, Black, new_colour)
}
pub fn flood_fill_bg_mut(&mut self, r: usize, c: usize, ignore_colour: Colour, bg: Colour, new_colour: Colour) {
let reachable = self.cells.bfs_reachable((r, c), false, |i| self.cells[i].colour == bg || self.cells[i].colour == ignore_colour);
reachable.iter().for_each(|&i| self.cells[i].colour = new_colour);
}
pub fn flood_fill_from_seeds(&self, ignore_colour: Colour, new_colour: Colour) -> Self {
let mut grid = self.clone();
let coloured: Vec<(usize, usize)> = grid.cells.items()
.filter(|(_, cell)| cell.colour == ignore_colour)
.map(|(i, _)| i)
.collect();
coloured.iter()
.for_each(|(r, c)| grid.flood_fill_mut(*r, *c, ignore_colour, new_colour));
grid
}
pub fn subgrid(&self, tlr: usize, sr: usize, tlc: usize, sc: usize) -> Self {
let mut m = Matrix::new(sr, sc, Cell::new(0, 0, 0));
for r in 0 .. sr {
for c in 0 .. sc {
m[(r,c)].row = self.cells[(r + tlr,c + tlc)].row;
m[(r,c)].col = self.cells[(r + tlr,c + tlc)].col;
m[(r,c)].colour = self.cells[(r + tlr,c + tlc)].colour;
}
}
Self::new_from_matrix(&m)
}
pub fn cell_colour_cnt_map(&self) -> BTreeMap<Colour, usize> {
let mut h: BTreeMap<Colour, usize> = BTreeMap::new();
for c in self.cells.values() {
if c.colour != Black {
*h.entry(c.colour).or_insert(0) += 1;
}
}
h
}
pub fn get_diff_colour(&self, other: &Self) -> Colour {
let mut in_colour = Black;
if let Some(diff) = self.diff(other) {
let colour = diff.cell_colour_cnt_map_diff();
if colour.len() != 1 {
return in_colour;
}
if let Some((colour, _)) = colour.first_key_value() {
in_colour = colour.to_base()
}
}
in_colour
}
pub fn cell_colour_cnt_map_diff(&self) -> BTreeMap<Colour, usize> {
let mut h: BTreeMap<Colour, usize> = BTreeMap::new();
for c in self.cells.values() {
if c.colour >= DiffBlack && c.colour <= DiffBrown {
*h.entry(c.colour).or_insert(0) += 1;
}
}
h
}
pub fn even_rows(&self) -> bool {
self.cells.rows % 2 == 0
}
pub fn even_columns(&self) -> bool {
self.cells.columns % 2 == 0
}
pub fn border_top(&self) -> bool {
self.cells.items()
.filter(|((r, _), cell)| *r == 0 && cell.colour != Black)
.count() == self.cells.columns - 1
}
pub fn border_bottom(&self) -> bool {
self.cells.items()
.filter(|((r, _), cell)| *r == self.cells.columns - 1 && cell.colour != Black)
.count() == self.cells.columns - 1
}
pub fn border_left(&self) -> bool {
self.cells.items()
.filter(|((_, c), cell)| *c == 0 && cell.colour != Black)
.count() == self.cells.rows - 1
}
pub fn border_right(&self) -> bool {
self.cells.items()
.filter(|((_, c), cell)| *c == self.cells.rows - 1 && cell.colour != Black)
.count() == self.cells.rows - 1
}
pub fn mirrored_rows(&self) -> Self {
let mut m = self.cells.flipped_ud();
for (r, c) in self.cells.keys() {
m[(r, c)].row = r;
m[(r, c)].col = c;
}
Self::new_from_matrix(&m)
}
pub fn mirrored_cols(&self) -> Self {
let mut m = self.cells.flipped_lr();
for (x, y) in self.cells.keys() {
m[(x, y)].row = x;
m[(x, y)].col = y;
}
Self::new_from_matrix(&m)
}
fn compare_colour(this: &Matrix<Cell>, other: &Matrix<Cell>) -> bool {
if this.columns == 1 || this.rows == 1 || this.columns != other.columns || this.rows != other.rows {
return false;
}
for x in 0 .. this.rows {
for y in 0 .. this.columns {
if this[(x, y)].colour != other[(x, y)].colour {
return false
}
}
}
true
}
pub fn is_mirror_rows(&self) -> bool {
if self.cells.len() <= 4 {
return false
}
let copy = self.cells.flipped_ud();
Self::compare_colour(&self.cells, ©)
}
pub fn is_mirror_cols(&self) -> bool {
if self.cells.len() <= 4 {
return false
}
let copy = self.cells.flipped_lr();
Self::compare_colour(&self.cells, ©)
}
pub fn is_symmetric(&self) -> bool {
self.is_mirror_rows() && self.is_mirror_cols()
}
pub fn is_mirror_offset_rows(&self, skew: i32) -> bool {
let copy = if skew < 0 {
self.cells.slice(0 .. (self.cells.rows as i32 + skew) as usize, 0 .. self.cells.columns)
} else {
self.cells.slice((skew as usize) .. self.cells.rows, 0 .. self.cells.columns)
};
if copy.is_err() { return false; };
let this = copy.unwrap();
let flipped_copy = this.flipped_ud();
Self::compare_colour(&this, &flipped_copy)
}
pub fn is_mirror_offset_cols(&self, skew: i32) -> bool {
let copy = if skew < 0 {
self.cells.slice(0 .. self.cells.rows, 0 .. (self.cells.columns - skew.unsigned_abs() as usize))
} else {
self.cells.slice(0 .. self.cells.rows, (skew as usize) .. self.cells.columns)
};
if copy.is_err() { return false; };
let this = copy.unwrap();
let flipped_copy = this.flipped_lr();
Self::compare_colour(&this, &flipped_copy)
}
pub fn is_panelled_rows(&self) -> bool {
let len: usize = self.cells.rows;
let half: usize = len / 2;
if len < 4 || half == 0 { return false }
let offset: usize = if len % 2 == 0 { 0 } else { 1 };
for c in 0 .. self.cells.columns {
for r in 0 .. half {
if self.cells[(r, c)].colour != self.cells[(half + offset + r, c)].colour {
return false;
}
}
}
true
}
pub fn is_panelled_cols(&self) -> bool {
let len: usize = self.cells.columns;
let half: usize = len / 2;
if len < 4 || half == 0 { return false }
let offset: usize = if len % 2 == 0 { 0 } else { 1 };
for r in 0 .. self.cells.rows {
for c in 0 .. half {
if self.cells[(r, c)].colour != self.cells[(r, half + offset + c)].colour {
return false;
}
}
}
true
}
pub fn transpose(&mut self) {
if self.cells.rows != self.cells.columns {
return;
}
self.cells.transpose();
}
pub fn transposed(&self) -> Self {
if self.cells.rows != self.cells.columns {
return self.clone();
}
let mut m: Matrix<Cell> = self.cells.clone();
m.transpose();
for (r, c) in self.cells.keys() {
m[(r, c)].row = r;
m[(r, c)].col = c;
}
Self::new_from_matrix(&m)
}
pub fn inv_transposed(&self) -> Self {
Self::new_from_matrix(&self.cells.rotated_cw(2).transposed())
}
pub fn rotated_90(&self, times: usize) -> Self {
if self.cells.rows != self.cells.columns {
return self.clone();
}
let mut m: Matrix<Cell> = self.cells.clone();
m.rotate_cw(times);
for (r, c) in self.cells.keys() {
m[(r, c)].row = r;
m[(r, c)].col = c;
}
Self::new_from_matrix(&m)
}
pub fn rotated_270(&self, times: usize) -> Self {
if self.cells.rows != self.cells.columns {
return self.clone();
}
let mut m: Matrix<Cell> = self.cells.clone();
m.rotate_ccw(times);
for (r, c) in self.cells.keys() {
m[(r, c)].row = r;
m[(r, c)].col = c;
}
Self::new_from_matrix(&m)
}
pub fn rotate_90(&self, times: usize) -> Self {
if times == 1 {
self.rot_rect_90()
} else if times == 2 {
self.rot_rect_90().rot_rect_90()
} else if times == 3 {
self.rot_rect_90().rot_rect_90().rot_rect_90()
} else {
self.clone()
}
}
pub fn rot_00(&self) -> Self { self.clone()
}
pub fn rot_90(&self) -> Self {
self.rotated_90(1)
}
pub fn rot_180(&self) -> Self {
self.rotated_90(2)
}
pub fn rot_270(&self) -> Self {
self.rotated_270(1)
}
pub fn rot_rect_90(&self) -> Self {
if self.cells.rows == self.cells.columns {
self.rotated_90(1)
} else {
let mut rot = Grid::new(self.cells.columns, self.cells.rows, Black);
let n = self.cells.rows;
for ((r, c), cell) in self.cells.items() {
rot.cells[(c, n - r - 1)].row = r;
rot.cells[(c, n - r - 1)].col = c;
rot.cells[(c, n - r - 1)].colour = cell.colour;
}
rot
}
}
pub fn rot_rect_180(&self) -> Self {
if self.cells.rows == self.cells.columns {
self.rotated_90(2)
} else {
self.rot_rect_90().rot_rect_90()
}
}
pub fn rot_rect_270(&self) -> Self {
if self.cells.rows == self.cells.columns {
self.rotated_270(1)
} else {
self.rot_rect_90().rot_rect_90().rot_rect_90()
}
}
pub fn colours(&self) -> BTreeMap<Colour, usize> {
let mut h: BTreeMap<Colour, usize> = BTreeMap::new();
for cell in self.cells.values() {
if cell.colour != Black {
*h.entry(cell.colour).or_insert(0) += 1;
}
}
h
}
pub fn min_colour(&self) -> Colour {
let h = self.colours();
match h.iter().min_by(|col, c| col.1.cmp(c.1)) {
None => NoColour,
Some((colour,_)) => *colour
}
}
pub fn max_colour(&self) -> Colour {
let h = self.colours();
match h.iter().max_by(|col, c| col.1.cmp(c.1)) {
None => NoColour,
Some((colour,_)) => *colour
}
}
pub fn no_colours(&self) -> usize {
self.colours().len()
}
pub fn single_colour(&self) -> Colour {
let h = self.colours();
if h.is_empty() {
NoColour
} else if h.len() == 1 {
*h.keys().max().unwrap()
} else {
Mixed
}
}
fn draw_row(&mut self, from_c: usize, to_c: usize, x: usize, colour: Colour) -> usize {
for c in from_c .. to_c {
self.cells[(x, c)].colour = colour;
}
if to_c > 0 { to_c - 1 } else { 0 }
}
fn draw_col(&mut self, from_r: usize, to_r: usize, y: usize, colour: Colour) -> usize {
for r in from_r .. to_r {
self.cells[(r, y)].colour = colour;
}
if to_r > 0 { to_r - 1 } else { 0 }
}
pub fn do_circle(&self, colour: Colour, spiral: bool) -> Self {
let inc = if spiral { 2 } else { 0 };
let mut copy = self.clone();
let mut cinc = 0;
let mut sr = 0;
let mut sc = 1;
let mut rows = self.cells.rows;
let mut cols = self.cells.columns;
let mut cc = copy.draw_row(sr, cols, 0, colour);
let mut cr = copy.draw_col(sc, rows, cc, colour);
cc = copy.draw_row(sr, cols - 1, cr, colour);
if spiral { sc += 1};
copy.draw_col(sc, rows - 1, 0, colour);
if spiral {
while sr + 1 < cc {
sr += 1;
sc += 1;
rows -= inc;
cols -= inc;
cinc += inc;
cc = copy.draw_row(sr, cols, cinc, colour);
cr = copy.draw_col(sc, rows, cc, colour);
sr += 1;
cc = copy.draw_row(sr, cols - 1, cr, colour);
sc += 1;
copy.draw_col(sc, rows - 1, cinc, colour);
}
}
Self::new_from_matrix(©.cells)
}
pub fn circle(&self, colour: Colour) -> Self {
self.do_circle(colour, false)
}
pub fn spiral(&self, colour: Colour) -> Self {
self.do_circle(colour, true)
}
pub fn show_matrix(m: &Matrix<Cell>, diff: bool, io: bool) {
let mut px = 0;
for ((r, c), cell) in m.items() {
if r != px {
println!();
px = r;
} else if c != 0 {
print!(" ");
}
let colour = cell.colour.to_usize();
if colour == 100 {
print!("{}", if !diff && io { "##" } else { "#" });
} else if colour == 101 {
print!("{}", if !diff && io { "**" } else { "*" });
} else if diff && !io {
if colour >= 10 { print!("#", ) } else { print!("{colour}") };
} else if !diff && io {
print!("{colour:0>2}");
} else if !diff && !io {
if colour >= 20 { print!("#") } else { print!("{}", colour % 10) };
} else {
print!("{}", colour % 10);
}
}
}
fn show_any(&self, diff: bool, io: bool) {
println!("--------Grid--------");
Grid::show_matrix(&self.cells, diff, io);
println!();
}
pub fn show_summary(&self) {
println!("0/0: {}/{} {:?}", self.cells.rows, self.cells.columns, self.colour);
}
pub fn show(&self) {
self.show_any(true, false);
}
pub fn show_full(&self) {
self.show_any(false, true);
}
pub fn show_out(&self) {
self.show_any(false, false);
}
pub fn show_io(&self) {
self.show_any(true, true);
}
pub fn has_bg_grid(&self) -> Colour {
self.has_bg_grid_impl(true, true)
}
pub fn has_bg_grid_coloured(&self) -> Colour {
self.has_bg_grid_impl(false, true)
}
pub fn has_bg_grid_not_sq(&self) -> Colour {
self.has_bg_grid_impl(true, false)
}
pub fn has_bg_grid_coloured_not_sq(&self) -> Colour {
self.has_bg_grid_impl(false, false)
}
fn has_bg_grid_impl(&self, can_be_black: bool, square: bool) -> Colour {
let mut colour = NoColour;
if self.cells.len() <= 9 || (square && self.cells.rows != self.cells.columns) {
return colour;
}
let mut nox = false;
'outerr:
for x in 0 .. self.cells.rows {
if can_be_black || self.cells[(x, 0)].colour != Black {
colour = self.cells[(x, 0)].colour;
} else {
continue;
}
if colour == self.cells[(x, 0)].colour {
for c in 0 .. self.cells.columns {
if colour != self.cells[(x, c)].colour {
continue 'outerr;
}
nox = true;
}
break; }
}
'outerc:
for y in 0 .. self.cells.columns {
if nox {
if can_be_black || self.cells[(0, y)].colour != Black {
colour = self.cells[(0, y)].colour;
} else {
continue;
}
}
if colour == self.cells[(0, y)].colour {
for r in 0 .. self.cells.rows {
if colour != self.cells[(r, y)].colour {
continue 'outerc;
}
}
if !can_be_black && colour == Black {
break;
}
return colour; }
}
NoColour
}
pub fn ray(&self, _direction: (i8, i8)) -> Shape {
Shape::new_empty()
}
pub fn r#move(&self, _direction: (i8, i8)) -> Shape {
Shape::new_empty()
}
pub fn template_shapes(&self, template: &Self) -> Shapes {
let mut shapes = Shapes::new_sized(self.height(), self.width());
if self.height() % template.height() != 0 || self.width() % template.width() != 0 {
return shapes;
}
let rr = self.height() / template.height();
let cr = self.width() / template.width();
for (tr, r) in (0 .. self.height()).step_by(rr).enumerate() {
for (tc, c) in (0 .. self.width()).step_by(cr).enumerate() {
if template.cells[(tr,tc)].colour != Black {
let sg = self.subgrid(r, rr, c, cr);
shapes.shapes.push(sg.as_shape());
}
}
}
shapes
}
pub fn fill_template(&self, filler: &Shape) -> Grid {
let mut shapes = Shapes::new_sized(self.height() * filler.height(), self.width() * filler.width());
let rr = filler.height();
let cr = filler.width();
for r in 0 .. self.height() {
for c in 0 .. self.width() {
if self.cells[(r,c)].colour != Black {
let s = filler.to_position(r * rr, c * cr);
shapes.shapes.push(s);
}
}
}
shapes.to_grid()
}
pub fn scale_up(&self, factor: usize) -> Self {
let mut cells = Matrix::new(self.cells.rows * factor, self.cells.columns * factor, Cell::new(0, 0, 0));
for r in 0 .. cells.rows {
for c in 0 .. cells.columns {
let rf = r / factor;
let cf = c / factor;
cells[(r, c)].row = r;
cells[(r, c)].col = c;
cells[(r, c)].colour = self.cells[(rf, cf)].colour;
}
}
Self::new_from_matrix(&cells)
}
pub fn scale_down(&self, factor: usize) -> Self {
let mut cells = Matrix::new(self.cells.rows / factor, self.cells.columns / factor, Cell::new(0, 0, 0));
for r in 0 .. cells.rows {
for c in 0 .. cells.columns {
let rf = r * factor;
let cf = c * factor;
cells[(r, c)].row = r;
cells[(r, c)].col = c;
cells[(r, c)].colour = self.cells[(rf, cf)].colour;
}
}
Self::new_from_matrix(&cells)
}
pub fn resize(&self, factor: usize) -> Self {
let mut cells = Matrix::new(self.cells.rows * factor, self.cells.columns * factor, Cell::new(0, 0, 0));
for ((r, c), cell) in self.cells.items() {
let rf = r + factor;
let cf = c + factor;
cells[(rf, cf)].row = r;
cells[(rf, cf)].col = c;
cells[(rf, cf)].colour = cell.colour;
}
Self::new_from_matrix(&cells)
}
pub fn resize_inc(&self, factor: usize) -> Self {
let mut cells = Matrix::new(self.cells.rows + factor * 2, self.cells.columns + factor * 2, Cell::new(0, 0, 0));
for ((r, c), cell) in self.cells.items() {
let rf = r + factor;
let cf = c + factor;
cells[(rf, cf)].row = r;
cells[(rf, cf)].col = c;
cells[(rf, cf)].colour = cell.colour;
}
Self::new_from_matrix(&cells)
}
pub fn find_patch(&self, patch: &Shape) -> (usize, usize) {
if patch.size() < 4 {
return (0, 0);
}
let colour00 = patch.cells[(0,0)].colour;
let colour01 = patch.cells[(0,1)].colour;
let colour10 = patch.cells[(1,0)].colour;
let colour11 = patch.cells[(1,1)].colour;
for ((rw, cl), cell) in self.cells.items() {
if rw > patch.cells.rows || cl > patch.cells.columns {
if cell.colour == colour00 && rw + patch.cells.rows < self.cells.rows && cl + patch.cells.columns < self.cells.columns && self.cells[(rw+1,cl)].colour == colour10 && self.cells[(rw,cl+1)].colour == colour01 && self.cells[(rw+1,cl+1)].colour == colour11 {
let s = self.subgrid(rw, patch.cells.rows, cl, patch.cells.columns);
if s.equals(&patch.to_grid()) == Same {
return (rw, cl);
}
}
}
}
(0, 0)
}
pub fn find_colour_patches(&self, colour: Colour) -> Shapes {
fn mshape(cells: &mut Matrix<Cell>, colour: Colour) -> Option<(usize, usize, Matrix<Cell>)> {
let rc = cells.items().filter(|(_, cell)| cell.colour == colour).map(|(pos, _)| pos).min();
if let Some((r, c)) = rc {
let reachable = cells.bfs_reachable((r, c), false, |i| cells[i].colour == colour);
let tlr = *reachable.iter().map(|(r, _)| r).min().unwrap();
let tlc = *reachable.iter().map(|(_, c)| c).min().unwrap();
let brr = *reachable.iter().map(|(r, _)| r).max().unwrap();
let brc = *reachable.iter().map(|(_, c)| c).max().unwrap();
let mut m = Matrix::new(brr - tlr + 1, brc - tlc + 1, Cell::new(0, 0, 0));
for r in tlr ..= brr {
for c in tlc ..= brc {
let cell = &mut m[(r - tlr, c - tlc)];
cell.row = r;
cell.col = c;
}
}
reachable.iter().for_each(|(r, c)| {
cells[(*r, *c)].colour = NoColour;
});
Some((tlr, tlc, m))
} else {
None
}
}
let mut shapes = Shapes::new_sized(self.cells.rows, self.cells.columns);
let mut cells = self.cells.clone();
while let Some((or, oc, m)) = mshape(&mut cells, colour) {
let s = Shape::new(or, oc, &m);
shapes.add(&s);
}
shapes
}
pub fn find_black_patches(&self) -> Shapes {
self.find_black_patches_limit(12)
}
pub fn find_black_patches_limit(&self, limit: usize) -> Shapes {
if self.cells.rows < limit && self.cells.columns < limit {
return Shapes::new_sized(0, 0);
}
self.find_colour_patches(Black)
}
fn find_gaps(&self, bg: Colour) -> (Vec<usize>, Vec<usize>) {
let mut rs: Vec<usize> = Vec::new();
let mut cs: Vec<usize> = Vec::new();
rs.push(0);
cs.push(0);
let mut lastr: isize = -1;
let mut lastc: isize = -1;
for ((r, c), cell) in self.cells.items() {
if cell.colour == bg {
if c == 0 {
if (lastr + 1) as usize != r {
rs.push(r);
}
lastr = r as isize;
}
if r == 0 {
if (lastc + 1) as usize != c {
cs.push(c);
}
lastc = c as isize;
}
}
}
(rs, cs)
}
pub fn toddle_colour(&self, bg: Colour, fg: Colour) -> Self {
let s = self.recolour(bg, ToBlack + bg).recolour(fg, bg);
s.recolour(ToBlack + bg, fg)
}
pub fn to_shapes_base_bg(&self, bg: Colour) -> Shapes {
let mut shapes: Vec<Shape> = Vec::new();
let (mut rs, mut cs) = self.find_gaps(bg);
if rs.len() >= 2 && rs[0] == rs[1] || cs.len() > 4 && cs[0] == cs[1] {
return Shapes::new(); }
if self.cells[(self.cells.rows - 1, 0)].colour != bg {
rs.push(self.cells.rows);
}
if self.cells[(0, self.cells.columns - 1)].colour != bg {
cs.push(self.cells.columns);
}
for i in 0 .. rs.len() - 1 {
let mut sr = rs[i];
if i > 0 {
sr += 1;
for x in sr .. rs[i + 1] {
if self.cells[(x, 0)].colour != bg {
break;
}
}
}
for j in 0 .. cs.len() - 1 {
let mut sc = cs[j];
if j > 0 {
sc += 1;
for y in sc .. cs[j + 1] {
if self.cells[(0, y)].colour != bg {
break;
}
}
}
let xsize = rs[i + 1] - sr;
let ysize = cs[j + 1] - sc;
let mut m = Matrix::from_fn(xsize, ysize, |(_, _)| Cell::new_empty());
for r in sr .. rs[i + 1] {
for c in sc .. cs[j + 1] {
m[(r - sr, c - sc)].row = r;
m[(r - sr, c - sc)].col = c;
m[(r - sr, c - sc)].colour = self.cells[(r, c)].colour;
}
}
shapes.push(Shape::new_cells(&m));
}
}
Shapes::new_shapes(&shapes)
}
pub fn has_shapes_base_bg(&self) -> bool {
match self.has_bg_grid() {
NoColour => false,
colour => {
let shapes = self.to_shapes_base_bg(colour);
shapes.len() >= 4
}
}
}
pub fn copy_part_matrix(rs: usize, cs: usize, rows: usize, cols: usize, cells: &Matrix<Cell>) -> Matrix<Cell> {
let mut m = Matrix::new(rows, cols, Cell::new(0, 0, 0));
for r in 0 .. rows {
for c in 0 .. cols {
m[(r, c)].row = cells[(rs + r, cs + c)].row;
m[(r, c)].col = cells[(rs + r, cs + c)].col;
m[(r, c)].colour = cells[(rs + r, cs + c)].colour;
}
}
m
}
fn de_diag(or: usize, oc: usize, s: &Shape, shapes: &mut Shapes) {
if s.cells.rows >= 4 && s.cells.rows % 2 == 0 && s.cells.rows == s.cells.columns {
let hrow = s.cells.rows / 2;
let hcol = s.cells.columns / 2;
if s.cells[(hrow - 1, hcol - 1)].colour == Black && s.cells[(hrow, hcol)].colour == Black && s.cells[(hrow - 1, hcol)].colour != Black && s.cells[(hrow, hcol - 1)].colour != Black {
let m = Self::copy_part_matrix(hrow, 0, hrow, hcol, &s.cells);
shapes.add(&Shape::new(or + hrow, oc, &m));
let m = Self::copy_part_matrix(0, hcol, hrow, hcol, &s.cells);
shapes.add(&Shape::new(or, oc + hcol, &m));
} else if s.cells[(hrow - 1, hcol - 1)].colour != Black && s.cells[(hrow, hcol)].colour != Black && s.cells[(hrow - 1, hcol)].colour == Black && s.cells[(hrow, hcol - 1)].colour == Black {
let m = Self::copy_part_matrix(0, 0, hrow, hcol, &s.cells);
shapes.add(&Shape::new(or, oc, &m));
let m = Self::copy_part_matrix(hrow, hcol, hrow, hcol, &s.cells);
shapes.add(&Shape::new(or + hrow, oc + hcol, &m));
} else { shapes.add(s);
}
} else {
shapes.add(s);
}
}
fn to_shapes_base(&self, same_colour: bool, diag: bool, cons: bool, bg: Colour) -> Shapes {
fn mshape(same_colour: bool, bgc: Colour, bg: Colour, cells: &mut Matrix<Cell>, diag: bool) -> Option<(usize, usize, Matrix<Cell>)> {
let rc = cells.items().filter(|(_, c)| c.colour != bgc && c.colour != bg).map(|(xy, _)| xy).min();
if let Some((r, c)) = rc {
let start_colour = cells[(r, c)].colour;
let reachable = cells.bfs_reachable((r, c), diag, |i| cells[i].colour != bgc && cells[i].colour != bg && (!same_colour || cells[i].colour == start_colour));
let tlr = *reachable.iter().map(|(r, _)| r).min().unwrap();
let tlc = *reachable.iter().map(|(_, c)| c).min().unwrap();
let brr = *reachable.iter().map(|(r, _)| r).max().unwrap();
let brc = *reachable.iter().map(|(_, c)| c).max().unwrap();
let mut m = Matrix::new(brr - tlr + 1, brc - tlc + 1, Cell::new(0, 0, 0));
for r in tlr ..= brr {
for c in tlc ..= brc {
let cell = &mut m[(r - tlr, c - tlc)];
cell.row = r;
cell.col = c;
}
}
reachable.iter().for_each(|(r, c)| {
m[(r - tlr, c - tlc)].colour = cells[(*r, *c)].colour;
cells[(*r, *c)].colour = bgc;
});
Some((tlr, tlc, m))
} else {
None
}
}
let mut shapes = Shapes::new_sized(self.cells.rows, self.cells.columns);
let mut cells = self.cells.clone();
let bg = if bg == NoColour {
match self.has_bg_grid_not_sq() {
NoColour => bg,
colour => colour
}
} else {
bg
};
if bg == NoColour || bg == Black {
let bgc = Black;
while let Some((or, oc, m)) = mshape(same_colour, bgc, bg, &mut cells, diag) {
let s = Shape::new(or, oc, &m);
Self::de_diag(or, oc, &s, &mut shapes);
}
} else {
shapes = self.to_shapes_base_bg(bg);
if shapes.is_empty() {
while let Some((or, oc, m)) = mshape(same_colour, Black, bg, &mut cells, diag) {
let s = Shape::new(or, oc, &m);
Self::de_diag(or, oc, &s, &mut shapes);
}
}
}
if cons {
shapes = shapes.consolidate_shapes();
}
shapes.shapes.sort();
shapes
}
pub fn to_shapes_coloured(&self) -> Shapes {
self.to_shapes_base(false, true, false, Black)
}
pub fn to_shapes(&self) -> Shapes {
self.to_shapes_base(true, true, false, Black)
}
pub fn to_shapes_cons(&self) -> Shapes {
self.to_shapes_base(true, true, true, Black)
}
pub fn to_shapes_coloured_bg(&self, bg: Colour) -> Shapes {
self.to_shapes_base(false, true, false, bg)
}
pub fn to_shapes_bg(&self, bg: Colour) -> Shapes {
self.to_shapes_base(true, true, false, bg)
}
pub fn to_shapes_bg_cons(&self, bg: Colour) -> Shapes {
self.to_shapes_base(true, true, true, bg)
}
pub fn to_shapes_coloured_cbg(&self) -> Shapes {
self.to_shapes_base(false, true, false, NoColour)
}
pub fn to_shapes_cbg(&self) -> Shapes {
self.to_shapes_base(true, true, false, NoColour)
}
pub fn to_shapes_coloured_sq(&self) -> Shapes {
self.to_shapes_base(false, false, false, Black)
}
pub fn to_shapes_sq(&self) -> Shapes {
self.to_shapes_base(true, false, false, Black)
}
pub fn to_shapes_coloured_bg_sq(&self, bg: Colour) -> Shapes {
self.to_shapes_base(false, false, false, bg)
}
pub fn to_shapes_bg_sq(&self, bg: Colour) -> Shapes {
self.to_shapes_base(true, false, false, bg)
}
pub fn to_shapes_coloured_cbg_sq(&self) -> Shapes {
self.to_shapes_base(false, false, false, NoColour)
}
pub fn to_shapes_cbg_sq(&self) -> Shapes {
self.to_shapes_base(true, false, false, NoColour)
}
pub fn as_shape(&self) -> Shape {
if self.size() == 0 {
return Shape::trivial();
}
Shape::new_cells(&self.cells)
}
pub fn as_shape_position(&self, r: usize, c: usize) -> Shape {
if self.size() == 0 {
return Shape::trivial();
}
Shape::new(r, c, &self.cells)
}
pub fn as_shapes(&self) -> Shapes {
if self.size() == 0 {
return Shapes::new();
}
Shapes::new_from_shape(&Shape::new_cells(&self.cells))
}
pub fn as_shapes_position(&self, r: usize, c: usize) -> Shapes {
if self.size() == 0 {
return Shapes::new();
}
Shapes::new_from_shape(&Shape::new(r, c, &self.cells))
}
pub fn as_pixel_shapes(&self) -> Shapes {
if self.size() == 0 {
return Shapes::new();
}
let mut shapes = Shapes::new_sized(self.cells.rows, self.cells.columns);
for ((r, c), cell) in self.cells.items() {
if cell.colour != Black {
let s = Shape::new_sized_coloured_position(r, c, 1, 1, cell.colour);
shapes.shapes.push(s);
}
}
shapes
}
pub fn is_square(&self) -> bool {
self.cells.rows > 1 && self.cells.rows == self.cells.columns
}
pub fn square(&self) -> usize {
self.cells.rows * self.cells.columns
}
pub fn height(&self) -> usize {
self.cells.rows
}
pub fn width(&self) -> usize {
self.cells.columns
}
pub fn row_colour(&self, r: usize) -> Colour {
let colour = self.cells[(r,0)].colour;
Self::row_colour_matrix(&self.cells, r, colour)
}
pub fn row_colour_matrix(m: &Matrix<Cell>, r: usize, colour: Colour) -> Colour {
for y in 1 .. m.columns {
if m[(r,y)].colour != colour {
return Mixed;
}
}
colour
}
pub fn find_pixel(&self, colour: Colour) -> (usize, usize) {
for ((r, c), cell) in self.cells.items() {
if cell.colour == colour {
return (r, c);
}
}
(0, 0)
}
pub fn invert_colour(&self) -> Self {
self.invert_colour_new(self.colour)
}
pub fn invert_colour_new(&self, colour: Colour) -> Self {
if self.colour == Mixed {
return Self::trivial();
}
let mut grid = self.clone();
for cell in grid.cells.values_mut() {
cell.colour = if cell.colour == Black {
colour
} else {
Black
};
}
grid
}
pub fn blank(&self) -> Self {
let mut shape = self.clone();
for cell in shape.cells.values_mut() {
cell.colour = Black;
}
shape
}
pub fn col_colour(&self, c: usize) -> Colour {
let colour = self.cells[(0,c)].colour;
Self::col_colour_matrix(&self.cells, c, colour)
}
pub fn col_colour_matrix(m: &Matrix<Cell>, c: usize, colour: Colour) -> Colour {
for x in 1 .. m.rows {
if m[(x,c)].colour != colour {
return Mixed;
}
}
colour
}
pub fn div9(&self) -> bool {
self.cells.rows == 3 && self.cells.columns == 3
}
pub fn is_3x3(&self) -> bool {
self.cells.rows % 3 == 0 && self.cells.columns % 3 == 0
}
pub fn is_full(&self) -> bool {
for (r, c) in self.cells.keys() {
if self.cells[(r, c)].colour == Black {
return false;
}
}
true
}
pub fn has_marker(&self, shape: &Shape) -> bool {
self.has_marker_colour(shape, Black)
}
pub fn has_marker_colour(&self, s: &Shape, colour: Colour) -> bool {
for (r, c) in s.cells.keys() {
if r == 0 && s.orow >= 3 &&
self.cells[(s.orow - 1, s.ocol + c)].colour != colour &&
self.cells[(s.orow - 2, s.ocol + c)].colour != colour &&
self.cells[(s.orow - 3, s.ocol + c)].colour != colour ||
c == 0 && s.ocol >= 3 &&
self.cells[(s.orow + r, s.ocol - 1)].colour != colour &&
self.cells[(s.orow + r, s.ocol - 2)].colour != colour &&
self.cells[(s.orow + r, s.ocol - 3)].colour != colour ||
r == s.cells.rows - 1 &&
s.orow + s.cells.rows < self.cells.rows - 3 &&
self.cells[(s.orow + 1, s.ocol + c)].colour != colour &&
self.cells[(s.orow + 2, s.ocol + c)].colour != colour &&
self.cells[(s.orow + 3, s.ocol + c)].colour != colour ||
c == s.cells.columns - 1 &&
s.ocol + s.cells.columns < self.cells.columns - 3 &&
self.cells[(s.orow + r, s.ocol + c + 1)].colour != colour &&
self.cells[(s.orow + r, s.ocol + c + 2)].colour != colour &&
self.cells[(s.orow + r, s.ocol + c + 3)].colour != colour {
return true;
}
}
false
}
pub fn find_rectangles(&self) -> Shapes {
let grid = self.recolour(Black, NoColour);
let shapes = grid.to_shapes();
let mut new_shapes = shapes.clone();
new_shapes.shapes = Vec::new();
for s in shapes.shapes.iter() {
if s.is_full() && grid.has_marker_colour(s, NoColour) {
let s = s.recolour(NoColour, Black);
new_shapes.shapes.push(s.clone());
}
}
new_shapes
}
pub fn has_gravity(&self, orientation: usize) -> bool {
if self.cells.rows != self.cells.columns {
return false;
}
let mut grid = self.clone();
grid = grid.rotate_90(orientation);
let mut has_black = false;
for r in 0 .. grid.cells.rows {
let mut prev = grid.cells[(r, 0)].colour;
if !has_black {
has_black = prev == Black;
}
for c in 1 .. grid.cells.columns {
let next = grid.cells[(r, c)].colour;
if prev != next && next == Black {
return false;
}
prev = next;
}
}
has_black
}
pub fn has_gravity_down(&self) -> bool {
self.has_gravity(3)
}
pub fn has_gravity_up(&self) -> bool {
self.has_gravity(1)
}
pub fn has_gravity_left(&self) -> bool {
self.has_gravity(0)
}
pub fn has_gravity_right(&self) -> bool {
self.has_gravity(0)
}
pub fn equals(&self, other: &Self) -> Colour {
if self.size() == 0 || other.size() == 0 || self.cells.columns != other.cells.columns || self.cells.rows != other.cells.rows {
return DiffShape;
}
for (c1, c2) in self.cells.values().zip(other.cells.values()) {
if c1.colour.to_base() != c2.colour.to_base() {
return DiffBlack + c2.colour;
}
}
Same
}
pub fn bleach(&self) -> Grid {
let mut shape = self.clone();
if self.size() == 0 {
return shape;
}
shape.colour = NoColour;
for cell in shape.cells.values_mut() {
if cell.colour != Black {
cell.colour = NoColour;
}
}
shape
}
pub fn equal_footprint(&self, other: &Self) -> bool {
self.cells.columns == other.cells.columns && self.cells.rows == other.cells.rows
}
pub fn equal_shape(&self, other: &Self) -> bool {
if !self.equal_footprint(other) {
return false;
}
for ((sr, sc), (or, oc)) in self.cells.keys().zip(other.cells.keys()) {
if sr != or || sc != oc {
return false;
}
}
true
}
pub fn diff_only_diff(&self) -> Self {
let mut g = self.clone();
for c in g.cells.values_mut() {
if Colour::to_usize(c.colour) / 40 < 10 {
c.colour = Colour::from_usize(Colour::to_usize(c.colour) / 40);
} else {
c.colour = Black;
}
}
g
}
pub fn diff_only_and(&self, colour: Colour) -> Self {
let mut g = self.clone();
for c in g.cells.values_mut() {
if c.colour.is_same() {
c.colour = colour;
} else {
c.colour = Black;
}
}
g
}
pub fn diff_only_or(&self, colour: Colour) -> Self {
let mut g = self.clone();
for c in g.cells.values_mut() {
if Colour::to_usize(c.colour) > 0 {
c.colour = colour;
} else {
c.colour = Black;
}
}
g
}
pub fn diff_only_xor(&self, colour: Colour) -> Self {
let mut g = self.clone();
for c in g.cells.values_mut() {
if c.colour == Black || Colour::to_usize(c.colour) > 30 {
c.colour = Black;
} else {
c.colour = colour;
}
}
g
}
pub fn diff_only_not(&self, colour: Colour) -> Self {
let mut g = self.clone();
for c in g.cells.values_mut() {
if c.colour == Black {
c.colour = colour;
} else {
c.colour = Black;
}
}
g
}
pub fn diff_only_same(&self) -> Self {
let mut g = self.clone();
for c in g.cells.values_mut() {
if c.colour.is_same() {
c.colour = c.colour.to_base();
} else {
c.colour = Black;
}
}
g
}
pub fn diff_black_same(&self, colour: Colour) -> Self {
let mut g = self.clone();
for c in g.cells.values_mut() {
if Colour::to_usize(c.colour) == 30 {
c.colour = colour;
} else {
c.colour = Black;
}
}
g
}
pub fn diff_other_same(&self, colour: Colour) -> Self {
let mut g = self.clone();
for c in g.cells.values_mut() {
if Colour::to_usize(c.colour) > 30 && Colour::to_usize(c.colour) < 40 {
c.colour = colour;
} else {
c.colour = Black;
}
}
g
}
pub fn find_unique_colours(&self) -> Vec<Colour> {
let mut unique_colours = Vec::new();
for row in 0..self.cells.rows {
for col in 0..self.cells.columns {
let colour = self.cells[(row, col)].colour;
if !unique_colours.contains(&colour) {
unique_colours.push(colour);
}
}
}
unique_colours
}
pub fn find_colour_row_order(&self) -> BTreeMap<usize, Colour> {
let mut colours: BTreeMap<usize, Colour> = BTreeMap::new();
let mut col_set: Vec<Colour> = Vec::new();
for row in 0 .. self.cells.rows {
let colour = self.cells[(row, 0)].colour;
if colour != Black && !col_set.contains(&colour){
colours.insert(row, colour);
col_set.push(colour);
}
let colour = self.cells[(row, self.cells.columns - 1)].colour;
if colour != Black && !col_set.contains(&colour){
colours.insert(row, colour);
col_set.push(colour);
}
}
colours
}
pub fn diff_only_transparent(&self) -> Self {
let mut g = self.clone();
for c in g.cells.values_mut() {
if c.colour != Black {
c.colour = Colour::to_base(c.colour);
}
}
g
}
pub fn diff(&self, other: &Self) -> Option<Self> {
self.diff_impl(other, true)
}
pub fn diff_orig(&self, other: &Self) -> Option<Self> {
self.diff_impl(other, false)
}
pub fn diff_impl(&self, other: &Self, diff: bool) -> Option<Self> {
if self.cells.columns != other.cells.columns || self.cells.rows != other.cells.rows {
return None;
}
let mut newg = other.clone();
for (((r, c), c1), ((_, _), c2)) in self.cells.items().zip(other.cells.items()) {
if c1.colour != c2.colour {
newg.cells[(r, c)].colour = if c1.colour == Black {
c2.colour + ToBlack
} else if c2.colour == Black {
c1.colour + FromBlack
} else if diff {
c2.colour + DiffBlack
} else {
c1.colour + OrigBlack
};
} else if c1.colour != Black && c1.colour == c2.colour {
newg.cells[(r, c)].colour = c1.colour + SameBlack;
}
}
Some(newg)
}
pub fn distance(&self, other: &Self) -> f64 {
let diff = self.diff_impl(other, true);
if diff.is_none() {
return -1.0;
}
let diff = diff.unwrap();
let mut cnt = 0;
for cell in diff.cells.values() {
if cell.colour == Black || cell.colour.is_same() {
cnt += 1;
}
}
cnt as f64 / diff.size() as f64
}
pub fn centre_of(&self) -> (usize, usize) {
(self.cells.rows / 2, self.cells.columns / 2)
}
pub fn count_diff(&self) -> (usize, usize) {
let mut total = 0;
let mut count = 0;
for c in self.cells.values() {
if c.colour == NoColour {
count += 1;
}
total += 1;
}
(count, total)
}
pub fn tile_mut(&mut self, tile: &Self) {
for r in (0 .. self.height()).step_by(tile.height()) {
for c in (0 .. self.width()).step_by(tile.width()) {
for ((tr, tc), cell) in tile.cells.items() {
if r + tr < self.height() && c + tc < self.width() {
self.cells[(r + tr, c + tc)].colour = cell.colour;
}
}
}
}
}
pub fn roll_right(&self) -> Self {
let mut grid = self.clone();
let rows = self.cells.rows;
let cols = self.cells.columns;
let first = self.cells.slice(0 .. rows, 0 .. 1);
if let Ok(first) = first {
for r in 0 .. rows {
for c in 1 .. cols {
grid.cells[(r,c-1)].colour = self.cells[(r,c)].colour;
}
}
for r in 0 .. rows {
grid.cells[(r,cols-1)].colour = first[(r,0)].colour;
}
}
grid
}
pub fn roll_left(&self) -> Self {
self.rotate_90(2).roll_right().rotate_90(2)
}
pub fn roll_up(&self) -> Self {
self.rotate_90(3).roll_right().rotate_90(1)
}
pub fn roll_down(&self) -> Self {
self.rotate_90(3).roll_right().rotate_90(3)
}
pub fn to_json(&self) -> String {
let mut grid: Vec<Vec<usize>> = vec![vec![0; self.cells.columns]; self.cells.rows];
for r in 0 .. self.cells.rows {
for c in 0 .. self.cells.columns {
let colour: usize = self.cells[(r, c)].colour.to_usize();
grid[r][c] = colour;
}
}
serde_json::to_string(&grid).unwrap()
}
pub fn to_vec(&self) -> Vec<Vec<usize>> {
let mut grid: Vec<Vec<usize>> = vec![vec![0; self.cells.columns]; self.cells.rows];
for r in 0 .. self.cells.rows {
for c in 0 .. self.cells.columns {
let colour: usize = self.cells[(r, c)].colour.to_usize();
grid[r][c] = colour;
}
}
grid
}
pub fn corner_idx(&self) -> (Self, Direction) {
let g = self.subgrid(0, 2, 0, 2);
if g.no_colours() == 4 {
return (g, FromUpLeft);
}
let g = self.subgrid(self.cells.rows - 2, 2, self.cells.columns - 2, 2);
if g.no_colours() == 4 {
return (g, FromDownRight);
}
let g = self.subgrid(self.cells.rows - 2, 2, 0, 2);
if g.no_colours() == 4 {
return (g, FromDownLeft);
}
let g = self.subgrid(0, 2, self.cells.columns - 2, 2);
if g.no_colours() == 4 {
return (g, FromUpRight);
}
(self.clone(), Other)
}
pub fn corner_body(&self, dir: Direction) -> Self {
let hx = self.cells.rows - 2;
let hy = self.cells.columns - 2;
match dir {
FromUpLeft => self.subgrid(0, hx, 0, hy),
FromDownRight => self.subgrid(self.cells.rows - hx, hx, self.cells.columns - hy, hy),
FromDownLeft => self.subgrid(self.cells.rows - hx, hx, 0, hy),
FromUpRight => self.subgrid(0, hx, self.cells.columns - hy, hy),
_ => self.clone(),
}
}
pub fn split_4(&self) -> Vec<Self> {
let hr = self.cells.rows / 2;
let hc = self.cells.columns / 2;
if hr == 0 || hc == 0 || self.cells.rows % 2 != 0 || self.cells.columns % 2 != 0 {
return Vec::new();
}
let s1 = self.subgrid(0, hr, 0, hc);
let s2 = self.subgrid(0, hr, self.cells.columns - hc, hc);
let s3 = self.subgrid(self.cells.rows - hr, hr, 0, hc);
let s4 = self.subgrid(self.cells.rows - hr, hr, self.cells.columns - hc, hc);
vec![s1, s2, s3, s4]
}
pub fn split_4_inline(&self, delimiter: bool) -> Shapes {
let rows = self.cells.rows;
let cols = self.cells.columns;
let mut dr = if delimiter { 1 } else { 0 };
let mut dc = if delimiter { 1 } else { 0 };
let mut shapes = Shapes::new_sized(rows, cols);
if rows % 4 != 0 && cols % 4 != 0 || rows < dr * 3 || cols < dc * 3 {
return shapes;
}
if ((rows - dr * 3) % 4 != 0 || cols % 4 != 0) &&
(rows % 4 != 0 || (cols - dc * 3) % 4 != 0) {
dr = 0;
dc = 0;
}
let (s1, s2, s3, s4) = if rows > cols {
let qx = rows / 4;
if qx * 4 >= rows {
dr = 0;
}
(self.subgrid(0, qx, 0, cols),
self.subgrid(qx + dr, qx, 0, cols),
self.subgrid((qx + dr) * 2, qx, 0, cols),
self.subgrid((qx + dr) * 3, qx, 0, cols))
} else {
let qy = cols / 4;
if qy * 4 >= cols {
dc = 0;
}
(self.subgrid(0, rows, 0, qy),
self.subgrid(0, rows, qy + dc, qy),
self.subgrid(0, rows, (qy + dc) * 2, qy),
self.subgrid(0, rows, (qy + dc) * 3, qy))
};
shapes.shapes = vec![s1.as_shape(), s2.as_shape(), s3.as_shape(), s4.as_shape()];
shapes
}
pub fn full_row(&self, shape: &Shape) -> bool {
shape.orow == 0 && shape.cells.rows == self.cells.rows
}
pub fn full_col(&self, shape: &Shape) -> bool {
shape.ocol == 0 && shape.cells.columns == self.cells.columns
}
pub fn full_dim_split(&self, shapes: &Shapes) -> (Colour, Shapes) {
let mut div_colour = NoColour;
let mut horizontal = false;
let mut shapes = shapes.clone();
for s in shapes.shapes.iter_mut() {
if self.full_row(s) {
horizontal = true;
s.to_position_mut(s.orow, s.ocol * 2 + 1);
div_colour = s.colour;
} else if self.full_col(s) {
horizontal = false;
s.to_position_mut(s.orow * 2 + 1, s.ocol);
div_colour = s.colour;
}
}
if horizontal {
shapes.shapes.sort_by(|a,b| (a.ocol,a.orow).cmp(&(b.ocol,b.orow)));
} else {
shapes.shapes.sort_by(|a,b| (a.orow,a.ocol).cmp(&(b.orow,b.ocol)));
}
(div_colour, shapes)
}
pub fn split_2(&self) -> Shapes {
if self.cells.rows % 2 != 0 && self.cells.columns % 2 != 0 {
return Shapes::new();
}
let mut shapes = Shapes::new_sized(self.cells.rows, self.cells.columns);
let hr = self.cells.rows / 2;
let hc = self.cells.columns / 2;
let s1 = if self.cells.rows > self.cells.columns {
self.subgrid(0, hr, 0, self.cells.columns)
} else {
self.subgrid(0, self.cells.rows, 0, hc)
};
let s2 = if self.cells.rows > self.cells.columns {
self.subgrid(hr, self.cells.rows - hr, 0, self.cells.columns)
} else {
self.subgrid(0, self.cells.rows, hc, self.cells.columns - hc)
};
shapes.shapes = vec![s1.as_shape(), s2.as_shape()];
shapes
}
pub fn full(&self) -> bool {
if self.cells.rows == 0 {
return false;
}
for cell in self.cells.values() {
if cell.colour == Black {
return false;
}
}
true
}
pub fn get_patch(&self, r: usize, c: usize, rows: usize, cols: usize) -> Shape {
match self.cells.slice(r .. r + rows, c .. c + cols) {
Ok(m) => Shape::new(r, c, &m),
Err(_e) => {
Shape::trivial()
}
}
}
pub fn fill_patch_mut(&mut self, other: &Shape, or: usize, oc: usize) {
if self.size() <= other.size() {
return;
}
for (r, c) in other.cells.keys() {
if self.cells[(or + r, oc + c)].colour == Black {
self.cells[(or + r, oc + c)].colour = other.cells[(r, c)].colour;
}
}
}
}
#[derive(Debug, Clone, PartialEq)]
pub struct QualifiedGrid {
pub grid: Grid,
pub bg: Colour,
pub shapes: Shapes,
pub coloured_shapes: Shapes,
pub black: Shapes,
}
impl QualifiedGrid {
pub fn new(data: &[Vec<usize>]) -> Self {
let grid = Grid::duplicate(data);
let bg = grid.has_bg_grid();
let shapes = if bg == NoColour {
grid.to_shapes()
} else {
grid.to_shapes_bg(bg)
};
let coloured_shapes = if bg == NoColour {
grid.to_shapes_coloured()
} else {
grid.to_shapes_coloured_bg(bg)
};
let black = grid.find_black_patches();
Self { grid: grid.clone(), bg, shapes, coloured_shapes, black }
}
pub fn new_cons(data: &[Vec<usize>]) -> Self {
let grid = Grid::duplicate(data);
let bg = grid.has_bg_grid();
let shapes = if bg == NoColour {
grid.to_shapes_cons()
} else {
grid.to_shapes_bg_cons(bg)
};
let coloured_shapes = if bg == NoColour {
grid.to_shapes_coloured()
} else {
grid.to_shapes_coloured_bg(bg)
};
let black = grid.find_black_patches();
Self { grid: grid.clone(), bg, shapes, coloured_shapes, black }
}
pub fn trivial() -> Self {
Self { grid: Grid::trivial(), bg: NoColour, shapes: Shapes::new(), coloured_shapes: Shapes::new(), black: Shapes::new() }
}
pub fn single_shape_count(&self) -> usize {
self.shapes.len()
}
pub fn colour_shape_count(&self) -> usize {
self.coloured_shapes.len()
}
pub fn has_bg_shape(&self) -> bool {
for s in self.shapes.shapes.iter() {
if s.orow == 0 && s.ocol == 0 && s.cells.rows == self.grid.cells.rows && s.cells.columns == self.grid.cells.columns {
return true;
}
}
false
}
pub fn has_bg_coloured_shape(&self) -> bool {
for s in self.shapes.coloured_shapes.iter() {
if s.orow == 0 && s.ocol == 0 && s.cells.rows == self.grid.cells.rows && s.cells.columns == self.grid.cells.columns {
return true;
}
}
false
}
}