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
|
mod parallel;
mod serial;
pub use parallel::{AsyncTester, ParallelProblemSolver};
pub use serial::{SerialProblemSolver, SyncTester};
pub struct ProblemSolver {
width: usize,
depth: usize,
cache: Vec<Vec<Option<bool>>>,
solution: Vec<usize>,
idx: usize,
dirty: bool,
}
impl ProblemSolver {
pub fn new(width: usize, depth: usize) -> Self {
Self {
width,
depth,
cache: vec![vec![None; depth]; width],
solution: vec![0; width],
idx: 0,
dirty: false,
}
}
}
impl ProblemSolver {
pub fn bail(&mut self) -> bool {
if self.try_advance_source() {
true
} else {
self.try_backtrack()
}
}
pub fn has_missing_cell(&self) -> Option<usize> {
for res_idx in 0..self.width {
if self.cache[res_idx].iter().all(|c| *c == Some(false)) {
return Some(res_idx);
}
}
None
}
fn is_cell_missing(&self, res_idx: usize, source_idx: usize) -> bool {
if let Some(false) = self.cache[res_idx][source_idx] {
return true;
}
false
}
fn is_current_cell_missing(&self) -> bool {
let res_idx = self.idx;
let source_idx = self.solution[res_idx];
let cell = &self.cache[res_idx][source_idx];
if let Some(false) = cell {
return true;
}
false
}
pub fn try_advance_resource(&mut self) -> bool {
if self.idx >= self.width - 1 {
false
} else {
self.idx += 1;
while self.is_current_cell_missing() {
if !self.try_advance_source() {
return false;
}
}
true
}
}
pub fn try_advance_source(&mut self) -> bool {
while self.solution[self.idx] < self.depth - 1 {
self.solution[self.idx] += 1;
if !self.is_current_cell_missing() {
return true;
}
}
false
}
pub fn try_backtrack(&mut self) -> bool {
while self.solution[self.idx] == self.depth - 1 {
if self.idx == 0 {
return false;
}
self.idx -= 1;
}
self.solution[self.idx] += 1;
self.prune()
}
pub fn prune(&mut self) -> bool {
for i in self.idx + 1..self.width {
let mut source_idx = 0;
while self.is_cell_missing(i, source_idx) {
if source_idx >= self.depth - 1 {
return false;
}
source_idx += 1;
}
self.solution[i] = source_idx;
}
true
}
pub fn is_complete(&self) -> bool {
self.idx == self.width - 1
}
}
|
