From edaccaaf15a526714f3de4e9e044341abd037885 Mon Sep 17 00:00:00 2001 From: natrixaeria Date: Thu, 2 Jan 2020 15:34:07 +0100 Subject: Start to implement incremental block solver --- src/main.rs | 6 +- src/row.rs | 27 ++++++++ src/solver.rs | 8 +++ src/solvers/incremental_block.rs | 133 +++++++++++++++++++++++++++++++++++++++ src/solvers/mod.rs | 1 + src/solvers/solver1.rs | 51 +++++++++++++++ src/structs.rs | 2 +- 7 files changed, 225 insertions(+), 3 deletions(-) create mode 100644 src/row.rs create mode 100644 src/solvers/incremental_block.rs create mode 100644 src/solvers/solver1.rs (limited to 'src') diff --git a/src/main.rs b/src/main.rs index 32143d5..95a05eb 100644 --- a/src/main.rs +++ b/src/main.rs @@ -2,9 +2,11 @@ mod solver; mod solvers; mod structs; +use solver::Solver; + fn main() { - let mut solver = solvers::intuitive::NormalSolver::::new(8); + let mut solver = solvers::incremental_block::IncrementalBlockSover::new(4); - solver.solve(); + solver.solve().output(); //wall.output(solver.n, solver.h); } diff --git a/src/row.rs b/src/row.rs new file mode 100644 index 0000000..fc0633b --- /dev/null +++ b/src/row.rs @@ -0,0 +1,27 @@ +pub fn encode_row(n: u32, mut x: u64) -> Vec { + let mut row = Vec::with_capacity(n as usize); + let mut pieces: Vec = (0..n).collect(); + for i in (1..=n.into()).rev() { + let p = (x % i) as u32; + let piece = pieces[p as usize]; + row.push(piece + 1); + pieces.swap_remove(p as usize); + x /= i; + } + row +} + +pub fn colliding(w1: &[u32], w2: &[u32]) -> bool { + let n = w1.len() - 1; + let (mut v1, mut v2) = (w1.iter().take(n), w2.iter().take(n)); + let (mut i, mut j) = (*v1.next().unwrap(), *v2.next().unwrap()); + loop { + if i < j { + i += if let Some(&k) = v1.next() { k } else { return false; }; + } else if i > j { + j += if let Some(&k) = v2.next() { k } else { return false; }; + } else { + return true; + } + } +} diff --git a/src/solver.rs b/src/solver.rs index c289cd6..809ddb4 100644 --- a/src/solver.rs +++ b/src/solver.rs @@ -1,9 +1,17 @@ use crate::structs::StoneWall; +/// calculate h and w +pub fn wall_stats(n: u32) -> (u32, u32) { + let h = (n >> 1) + 1; + (h, (n - 1) * h) +} + pub trait Solver { fn new(n: u32) -> Self; fn solve(&mut self) -> StoneWall; fn n(&self) -> u32; + fn h(&self) -> u32; + fn w(&self) -> u32; } diff --git a/src/solvers/incremental_block.rs b/src/solvers/incremental_block.rs new file mode 100644 index 0000000..d4ebb81 --- /dev/null +++ b/src/solvers/incremental_block.rs @@ -0,0 +1,133 @@ +use std::iter::repeat; +use crate::solver::{Solver, wall_stats}; +use crate::structs::StoneWall; + +pub struct IncrementalBlockSover { + n: u32, h: u32, w: u32, + rows: Vec>, +} + +struct SubSolver<'s> { + solver: &'s mut IncrementalBlockSover, + start: u32, + count: u32, + heights: Vec, + // for all gaps the possible rows + gap_possibilities: Vec>, + pos: Vec, +} + +impl<'s> SubSolver<'s> { + fn from_index(solver: &'s mut IncrementalBlockSover, index: u32) -> Option { + let gap_possibilities = vec![vec![]; index as usize]; + let row_existence = vec![false; index as usize]; + let start = solver.rows[0][index as usize].0 + 1; + for row in 1..solver.h { + let min_sz = start - solver.row_size(row); + for gap in 0..index { + if !solver.visited(row, min_sz + gap) { + gap_possibilities[gap as usize].push(row); + row_existence[row as usize] = true; + } + } + } + if row_existence.iter().all(|&x| x) { + Some(Self { + count: index, + start, solver, + heights: Vec::with_capacity(index as usize), + pos: vec![0; gap_possibilities.len()], + gap_possibilities, + }) + } else { None } + } + + fn increment_at(&mut self, n: u32) -> bool { + if self.pos[n as usize] as usize + 1 == self.gap_possibilities[n as usize].len() { + if n as usize + 1 == self.pos.len() { + false + } else { + self.increment_at(n + 1) + } + } else { + self.pos[n as usize] += 1; + true + } + } +} + +impl<'s> Iterator for SubSolver<'s> { + type Item = (); + + fn next(&mut self) -> Option { + for (i, p) in self.pos.iter().enumerate().rev() { + t + } + None + } +} + +impl IncrementalBlockSover { + fn generate_first_row(&mut self) { + let mut sum = 0; + self.rows[0] = (1..=self.n) + .map(|n| { + sum += n; + (sum - n, n) + }) + .collect(); + } + + fn get_wall(&self) -> StoneWall { + let mut wall = StoneWall::create_empty(self.n); + for (h, row) in self.rows.iter().enumerate() { + for (n, &(_, stone)) in row.iter().enumerate() { + wall.set_stone(h as u32, n as u32, stone).unwrap() + } + } + wall + } + + fn visited(&self, row: u32, stone: u32) -> bool { + self.rows[row as usize].iter() + .position(|&(_, s)| s == stone) + .is_some() + } + + fn row_size(&self, row: u32) -> u32 { + self.rows[row as usize] + .last() + .map_or(0, |&(i, s)| i + s) + } +} + +impl Solver for IncrementalBlockSover { + fn new(n: u32) -> Self { + let (h, w) = wall_stats(n); + Self { + n, h, w, + rows: repeat(Vec::with_capacity(h as usize)) + .take(h as usize) + .collect() + } + } + + fn solve(&mut self) -> StoneWall { + self.generate_first_row(); + println!("{:?}", self.rows); + self.get_wall() + } + + fn n(&self) -> u32 { + self.n + } + + fn h(&self) -> u32 { + self.h + } + + fn w(&self) -> u32 { + self.w + } +} + diff --git a/src/solvers/mod.rs b/src/solvers/mod.rs index 0b1d716..4fc1330 100644 --- a/src/solvers/mod.rs +++ b/src/solvers/mod.rs @@ -1 +1,2 @@ pub mod intuitive; +pub mod incremental_block; diff --git a/src/solvers/solver1.rs b/src/solvers/solver1.rs new file mode 100644 index 0000000..ab1fbd1 --- /dev/null +++ b/src/solvers/solver1.rs @@ -0,0 +1,51 @@ +use crate::structs::{StoneWall, GapHeights}; + +#[derive(Clone)] +struct State { + stones_used: Vec, + gaps: GapHeights, +} + +impl State { + fn from_gaps(gaps: GapHeights, n: u32) -> Self { + let h = n/2 + 1; + Self { + stones_used: vec![false; n * h], + gaps + } + } + + fn stone_used(&self, n: u32, h: u32) -> bool { + self.stones_used.get() + } + + fn as_wall(&self, n: u32) -> StoneWall { + self.gaps.as_stone_wall(n) + } +} + +struct RecursiveSolver { + n: u32, + states: Vec +} + +impl Sover for RecursiveSolver { + fn new(n: u32) -> Self { + let w = (n/2 + 1) * (n - 1); + let gaps = GapHeights::create_empty(w); + Self { + n, + states: vec![State::from_gaps(gaps)] + } + } + + fn solve(&mut self) -> Option { + let w = self.w(); + if let Some(state) = self.states.last() { + } + } + + fn n(&self) -> u32 { + self.n + } +} diff --git a/src/structs.rs b/src/structs.rs index aa70680..1d33215 100644 --- a/src/structs.rs +++ b/src/structs.rs @@ -21,7 +21,7 @@ impl StoneWall { pub fn output(&mut self) { let colors = [[31, 32], [33, 35]]; - self.rows.sort_by_key(|x| x[0]); + //self.rows.sort_by_key(|x| x[0]); for (i, row) in self.rows.iter().enumerate() { for (j, &stone) in row.iter().enumerate() { -- cgit v1.2.3-54-g00ecf