summaryrefslogtreecommitdiff
path: root/src/solvers
diff options
context:
space:
mode:
Diffstat (limited to 'src/solvers')
-rw-r--r--src/solvers/intuitive.rs78
1 files changed, 67 insertions, 11 deletions
diff --git a/src/solvers/intuitive.rs b/src/solvers/intuitive.rs
index 0899906..f858a42 100644
--- a/src/solvers/intuitive.rs
+++ b/src/solvers/intuitive.rs
@@ -53,12 +53,16 @@ impl<T: num::PrimInt> SaveState<T> {
}
#[allow(dead_code)]
- pub fn bridges_gap(&self, gap: u32) -> bool {
+ pub fn bridges_gap(&self, gap: u32, n: u32) -> bool {
+ if gap - self.sum > n {
+ //println!("{}", gap - self.sum);
+ return false;
+ }
self.get_bit(gap - self.sum) == T::zero()
}
#[allow(dead_code)]
- pub fn bridge_gap(mut self, gap: u32) -> Self {
+ pub unsafe fn bridge_gap(mut self, gap: u32) -> Self {
self.set_bit(gap - self.sum);
self.sum = gap;
self
@@ -73,10 +77,18 @@ impl<T: num::PrimInt> NormalSolver<T> {
let heap = permutohedron::Heap::new(&mut heap);
let n_f = permutohedron::factorial(n as usize);
let mut permutations = Vec::with_capacity(n_f);
- println!("Generating permutations");
+ //println!("Generating permutations");
for data in heap {
permutations.push(data.clone());
}
+ /*use permutohedron::LexicalPermutation;
+ loop {
+ permutations.push(heap.to_vec());
+ if !heap.next_permutation() {
+ break;
+ }
+ }*/
+
Self {
n,
h,
@@ -87,10 +99,11 @@ impl<T: num::PrimInt> NormalSolver<T> {
}
pub fn solve(&mut self) {
- //for (n, i) in self.permutations.iter().enumerate() {
- // println!("perm {}: {:?}", n, i);
- //}
- println!("calculate results");
+ for (n, i) in self.permutations.iter().enumerate() {
+ let tmp: Vec<u32> = i.iter().map(|x| *x).collect();
+ //println!("perm {}: {:?}", n, tmp);
+ }
+ //println!("calculate results");
self.permute(
permutohedron::factorial(self.n as usize),
0,
@@ -101,10 +114,30 @@ impl<T: num::PrimInt> NormalSolver<T> {
fn permute(&mut self, up: usize, index: usize, numbers: &[u32]) {
let chunk = self.permutations.len() / self.h as usize;
+ if index as usize == numbers.len() - 2 {
+ let mut new_num = Vec::from(numbers);
+ if self.n == 6 {
+ new_num[2] = 675;
+ }
+ if self.n == 8 {
+ //new_num[3] = 38728;
+ new_num[3] = 36719;
+ }
+
+ if self.check_perm(&new_num[..(new_num.len() - 1)]) {
+ for i in new_num {
+ println!("{}\t{}", numbers[0], i);
+ }
+ }
+ return;
+ }
if index as usize == numbers.len() {
//println!("checking {:?}", numbers);
if self.check_perm(&numbers) {
- println!("success");
+ //println!("success");
+ for i in numbers {
+ println!("{},{}", numbers[0], i);
+ }
}
return;
}
@@ -134,13 +167,33 @@ impl<T: num::PrimInt> NormalSolver<T> {
sums[sum - 1] = i as u32;
}
}
+ //for i in 0..sums.len() {
+ // let test = SaveState::<u64>::new();
+ // if sums[i] == self.w {
+ // if !test.bridges_gap(i as u32, self.n) {
+ // //return false;
+ // }
+ // unsafe {
+ // test.bridge_gap(i as u32);
+ // }
+ // }
+ //}
unsafe {
SOLUTIONS += 1;
}
//println!("{:?}", sums);
- GapHeights::from_heights(sums.iter().map(|x| *x as u32).collect()).output(self.n, self.h);
- //.as_stone_wall(self.n)
- //.output();
+ let vec = sums
+ .iter()
+ .map(|x| if *x != self.w { *x as u32 } else { self.h - 1 })
+ .collect();
+ //println!("{:?}", vec);
+ let vec = GapHeights::from_heights(vec); //.output(self.n, self.h);
+
+ if !self.check_gaps(&vec) {
+ return false;
+ }
+ println!("success");
+ vec.as_stone_wall(self.n).output();
true
}
@@ -148,6 +201,9 @@ impl<T: num::PrimInt> NormalSolver<T> {
fn check_gaps(&mut self, wall: &GapHeights) -> bool {
for (i, r) in wall.iter().enumerate() {
let stone = (i + 1) as u32 - self.solve_stack[r as usize].sum;
+ if stone > self.n {
+ return false;
+ }
self.solve_stack[r as usize].set_bit(stone);
}
for state in self.solve_stack.as_ref() as &[SaveState<T>] {