diff options
author | Dennis Kobert <dennis@kobert.dev> | 2020-01-12 03:47:14 +0100 |
---|---|---|
committer | Dennis Kobert <dennis@kobert.dev> | 2020-01-12 03:47:14 +0100 |
commit | 1650906f010574e8810c8b0b98334e22fac5894d (patch) | |
tree | fe27a9d727e143353c1fcf0286890d549c443303 /src/solvers/single.rs | |
parent | 6b6f830f8e6d4c0b0d1328b7b22f810ad039d038 (diff) |
Restructuring
Diffstat (limited to 'src/solvers/single.rs')
-rw-r--r-- | src/solvers/single.rs | 136 |
1 files changed, 136 insertions, 0 deletions
diff --git a/src/solvers/single.rs b/src/solvers/single.rs new file mode 100644 index 0000000..ad3e5b7 --- /dev/null +++ b/src/solvers/single.rs @@ -0,0 +1,136 @@ +use rayon::prelude::*; + +/// Solve for a given N and return the resulting wall +#[derive(Clone)] +pub struct NormalSolver { + pub n: u32, + /// calculated height [might not be correct!] + pub h: u32, + /// width + pub w: u32, + pub chunk: u32, + pub mask: u64, + /// Use to store already used blocks as a bitmask + permutations: Vec<Vec<u32>>, + masks: Vec<u64>, + senders: Vec<std::sync::mpsc::Sender<super::opencl::Job>>, +} + +static mut TRIES: u32 = 0; +static mut SOLUTIONS: u32 = 0; + +impl NormalSolver { + pub fn new(n: u32) -> Self { + let h = n / 2 + 1; + let w = h * (n - 1); + 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; + let mut permutations = Vec::with_capacity(n_f); + let mut masks: Vec<u64> = vec![0; n_f]; + println!("Generating permutations"); + for (j, data) in heap.enumerate() { + permutations.push(data.clone()); + let mut sum = 0; + for stone in permutations[j].iter().take(n as usize - 1) { + //.take(n as usize - 1) { + sum += stone; + masks[j] |= 1 << sum; + } + } + + let src = + std::fs::read_to_string("src/solvers/check.cl").expect("failed to open kernel file"); + + let senders = + super::opencl::GpuSolver::launch_sevice(&masks, n, h, w, 0, src.as_ref()).unwrap(); + Self { + n, + h, + w, + chunk, + mask: (1 << w) - 2, + permutations, + masks, + senders, + } + } + + pub fn solve(&mut self) { + for (n, i) in self.permutations.iter().enumerate() { + let tmp: Vec<u32> = i.iter().map(|x| *x).collect(); + //println!("perm {}: {:?}", n, tmp); + //println!("perm {}: {:b}", n, self.masks[n]); + } + println!("calculate results"); + self.permute( + permutohedron::factorial(self.n as usize), + 0, + 0, + ((0..(self.h - 1)) + .map(|x| x * self.chunk) + .collect::<Vec<u32>>()) + .as_ref(), + ); + unsafe { println!("tries: {}\nsolutions: {}", TRIES, SOLUTIONS) } + loop { + std::thread::sleep(std::time::Duration::from_secs(5)); + } + } + + fn permute(&self, up: usize, index: usize, curr_mask: u64, numbers: &[u32]) { + if curr_mask.count_ones() < index as u32 * (self.n - 1) { + return; + } + let mut new_num = Vec::from(numbers); + let start = numbers[index as usize] / self.chunk; + if index as usize == numbers.len() - 1 { + //#[cfg(feature = "gpu")] + //{ + let mut info = sys_info::mem_info().unwrap(); + while info.avail < info.total / 8 { + std::thread::sleep_ms(50); + info = sys_info::mem_info().unwrap(); + println!("mem wait {:?}", info); + } + let i = self.n - 2 - numbers[index] / self.chunk; + self.senders[i as usize] + .send(super::opencl::Job::new(new_num, curr_mask)) + .unwrap(); + return; + //} + } + for i in start..self.n - (self.h - 1 - index as u32) { + for n in 1..(numbers.len() - index) { + new_num[n + index] = (n as u32 + i) * self.chunk; + } + /*if index == 0 { + (0..self.chunk).into_par_iter().for_each(|j| { + let mut new_num = new_num.clone(); + let tmp = i * self.chunk + j; + new_num[index] = tmp; + self.permute( + up, + index + 1, + curr_mask | self.masks[tmp as usize], + &new_num, + ); + }); + } else {*/ + for j in 0..self.chunk { + new_num[index] = i * self.chunk + j; + if index == 0 { + println!("progress: {}%", j as f64 / self.chunk as f64); + } + self.permute( + up, + index + 1, + curr_mask | self.masks[new_num[index] as usize], + &new_num, + ); + } + //} + } + } +} |