1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
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>,
}
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 = (1..=n).collect::<Vec<u32>>();
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;
}
}
Self {
n,
h,
w,
chunk,
mask: (1 << w) - 2,
permutations,
masks,
}
}
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 {}: {:?}", 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) }
}
fn permute(&self, up: usize, index: usize, curr_mask: u64, numbers: &[u32]) {
if index as usize == numbers.len() {
//println!("checking {:?}", numbers);
unsafe {
TRIES += 1;
}
let mut tmask: u64 = 0;
let mut sum = 0;
let mut stones = 0;
for i in 1..=(self.w + 1) {
if curr_mask & (1 << i) == 0 {
stones += 1;
tmask |= 1 << (i - sum);
sum = i;
}
}
if tmask == (1 << (self.n + 1)) - 2 && stones == self.n {
println!("tmask: {:b}", tmask);
println!("curr: {:b}", curr_mask);
//println!("success");
unsafe {
SOLUTIONS += 1;
}
for i in numbers {
println!("{}\t{}", numbers[0], i);
}
}
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")]
{
crate::solvers::opencl::check(
self.masks.as_ref(),
self.w,
self.n,
curr_mask,
(start * self.chunk) as usize,
)
.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 && false {
(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;
self.permute(
up,
index + 1,
curr_mask | self.masks[new_num[index] as usize],
&new_num,
);
}
}
}
}
}
|
