diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/lib.rs | 2 | ||||
-rwxr-xr-x | src/main.rs | 14 | ||||
-rw-r--r-- | src/permutations.rs | 45 | ||||
-rwxr-xr-x | src/solver.rs | 12 | ||||
-rw-r--r-- | src/solvers/gpusolver.rs | 65 | ||||
-rwxr-xr-x | src/solvers/intuitive.rs | 2 | ||||
-rwxr-xr-x | src/solvers/mod.rs | 1 | ||||
-rw-r--r-- | src/solvers/opencl.rs | 3 | ||||
-rwxr-xr-x | src/structs.rs | 1 |
9 files changed, 134 insertions, 11 deletions
@@ -1,7 +1,7 @@ +mod permutations; pub mod solver; pub mod solvers; pub mod structs; -#[macro_use] pub static N: u32 = 10; pub fn solve(n: u32) { diff --git a/src/main.rs b/src/main.rs index 95e3746..fdf3fcd 100755 --- a/src/main.rs +++ b/src/main.rs @@ -1,10 +1,16 @@ +mod permutations; mod solver; mod solvers; mod structs; -#[macro_use] +use crate::solver::{IteratorSolver, Solver}; -pub static N: u32 = 10; +pub static N: u32 = 8; fn main() { - let mut solver = solvers::intuitive::NormalSolver::new(N); - solver.solve(); + //let mut solver = solvers::intuitive::NormalSolver::new(N); + //solver.solve(); + let solver = solvers::gpusolver::GpuSolver::new(N); + println!("solver: {:?}", solver); + for (i, solution) in solver.solve().enumerate() { + println!("{}: {:?}", i, solution); + } } diff --git a/src/permutations.rs b/src/permutations.rs new file mode 100644 index 0000000..7b8e4d3 --- /dev/null +++ b/src/permutations.rs @@ -0,0 +1,45 @@ +use permutohedron::{Heap, LexicalPermutation}; + +pub trait PermutationGenerator { + fn permutations(n: u32) -> Vec<Vec<u32>>; +} + +pub struct HeapsPermutations; + +impl PermutationGenerator for HeapsPermutations { + fn permutations(n: u32) -> Vec<Vec<u32>> { + Heap::<'_, Vec<u32>, _>::new(&mut (1..=n).collect()).collect() + } +} + +pub struct LexicalPermutations { + state: Vec<u32>, + is_ended: bool, +} + +impl Iterator for LexicalPermutations { + type Item = Vec<u32>; + fn next(&mut self) -> Option<Self::Item> { + if self.is_ended { + None + } else { + self.is_ended = self.state.next_permutation(); + Some(self.state.clone()) + } + } +} + +impl LexicalPermutations { + fn new(n: u32) -> Self { + Self { + state: (1..=n).collect(), + is_ended: false + } + } +} + +impl PermutationGenerator for LexicalPermutations { + fn permutations(n: u32) -> Vec<Vec<u32>> { + Self::new(n).collect() + } +} diff --git a/src/solver.rs b/src/solver.rs index 809ddb4..db4e732 100755 --- a/src/solver.rs +++ b/src/solver.rs @@ -8,10 +8,16 @@ pub fn wall_stats(n: u32) -> (u32, u32) { 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; } + +pub trait FirstSolver { + fn solve(self) -> StoneWall; +} + +pub trait IteratorSolver: Solver { + type IntoIter: Iterator<Item=StoneWall>; + fn solve(self) -> Self::IntoIter; +} diff --git a/src/solvers/gpusolver.rs b/src/solvers/gpusolver.rs new file mode 100644 index 0000000..2b9eb4a --- /dev/null +++ b/src/solvers/gpusolver.rs @@ -0,0 +1,65 @@ +use crate::solver::{wall_stats, Solver, IteratorSolver}; +use crate::structs::StoneWall; +use crate::permutations::PermutationGenerator; + +#[derive(Debug)] +pub struct GpuSolver { + n: u32, h: u32, w: u32, + permutations: Vec<Vec<u32>>, + masks: Vec<u64>, +} + +impl GpuSolver { + fn solve_to_vec(&mut self) -> Vec<StoneWall> { + vec![] + } +} + +fn generate_permutations(n: u32) -> Vec<Vec<u32>> { + crate::permutations::HeapsPermutations::permutations(n) +} + +fn generate_masks(permutations: &[Vec<u32>]) -> Vec<u64> { + let mut masks = Vec::with_capacity(permutations.len()); + for p in permutations { + let mut v = 0; + let mut x = 0u64; + for i in p.iter().take(p.len() - 1).map(|i| { + v += i; + v + }) { + x |= 1 << i + } + masks.push(x) + } + masks +} + +impl Solver for GpuSolver { + fn new(n: u32) -> Self { + let (h, w) = wall_stats(n); + let permutations = generate_permutations(n); + let masks = generate_masks(&permutations); + Self { + n, h, w, + permutations, + masks, + } + } + fn n(&self) -> u32 { + self.n + } + fn h(&self) -> u32 { + self.h + } + fn w(&self) -> u32 { + self.w + } +} + +impl IteratorSolver for GpuSolver { + type IntoIter = std::vec::IntoIter<StoneWall>; + fn solve(mut self) -> Self::IntoIter { + self.solve_to_vec().into_iter() + } +} diff --git a/src/solvers/intuitive.rs b/src/solvers/intuitive.rs index a5ff935..3db1d33 100755 --- a/src/solvers/intuitive.rs +++ b/src/solvers/intuitive.rs @@ -22,7 +22,7 @@ impl NormalSolver { pub fn new(n: u32) -> Self { let h = n / 2 + 1; let w = h * (n - 1); - let mut heap = (1..=n).collect::<Vec<u32>>(); + let mut heap: Vec<_> = (1..=n).collect(); let heap = permutohedron::Heap::new(&mut heap); let n_f = permutohedron::factorial(n as usize); let chunk = n_f as u32 / n; diff --git a/src/solvers/mod.rs b/src/solvers/mod.rs index 6eb2ec4..1bdc228 100755 --- a/src/solvers/mod.rs +++ b/src/solvers/mod.rs @@ -1,4 +1,5 @@ //pub mod incremental_block; pub mod intuitive; //#[cfg(feature = "gpu")] +pub mod gpusolver; pub mod opencl; diff --git a/src/solvers/opencl.rs b/src/solvers/opencl.rs index ae5bfa3..676c5cc 100644 --- a/src/solvers/opencl.rs +++ b/src/solvers/opencl.rs @@ -1,5 +1,4 @@ -#[macro_use] -use ocl::{Buffer, Context, Device, Platform, Program, Queue}; +use ocl::{Buffer, Context, Device, Platform, Queue}; use std::sync::mpsc::{Receiver, Sender}; pub struct Job { diff --git a/src/structs.rs b/src/structs.rs index 1d33215..55cff29 100755 --- a/src/structs.rs +++ b/src/structs.rs @@ -1,3 +1,4 @@ +#[derive(Clone, Debug)] pub struct StoneWall { rows: Vec<Vec<u32>>, } |