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
|
pub struct Wall {
heights: Vec<u32>,
}
impl Wall {
pub fn from_heights(heights: Vec<u32>) -> Self {
Self { heights }
}
fn create_empty(w: u32) -> Self {
let heights = if w == 0 {
vec![]
} else if w == 1 {
vec![0]
} else {
let mut v = Vec::with_capacity(w as usize);
v.push(0);
v.push(1);
v
};
Self { heights }
}
pub fn calculate_row(&self, r: u32, stones: &mut [u32]) {
let mut len = 1;
let mut i = 0;
for &height in self.heights.iter().chain([r].iter()) {
if height == r {
stones[i] = len;
i += 1;
len = 0;
}
len += 1;
}
}
pub fn output(&self, n: u32, h: u32) {
let mut stones = vec![0; n as usize];
let mut toggle = 0;
let colors = [
"\x1b[31m", "\x1b[32m", "\x1b[33m", "\x1b[34m", "\x1b[35m", "\x1b[36m",
];
for row in 0..h {
self.calculate_row(row, &mut stones);
for &len in stones.iter() {
print!("{}", colors[toggle]);
toggle = (toggle + 1) % colors.len();
for _ in 0..len {
print!("◙");
}
}
println!("\x1b[m");
}
}
}
/// Solve for a given N and return the resulting wall
pub struct Solver<T: num::PrimInt> {
pub n: u32,
/// calculated height [might not be correct!]
pub h: u32,
/// width
pub w: u32,
/// Use to store already used blocks as a bitmask
solve_stack: Vec<SaveState<T>>,
}
#[derive(Clone)]
pub struct SaveState<T: num::PrimInt> {
pub bitmask: T,
pub index: u32,
}
impl<T: num::PrimInt> SaveState<T> {
pub fn new() -> Self {
Self {
bitmask: T::zero(),
index: 0,
}
}
pub fn set_bit(&mut self, stone: u32) {
self.bitmask =
self.bitmask | T::from(1 << stone).expect("Stone placing index out of bounds");
}
pub fn get_bit(&self, stone: u32) -> T {
self.bitmask & T::from(1 << stone).expect("Requested stone index out of bounds")
}
pub fn bridges_gap(&self, index: u32) -> bool {
self.get_bit(index - self.index) == T::zero()
}
pub fn bridge_gap(&mut self, index: u32) {
self.set_bit(index - self.index);
self.index = index
}
}
impl<T: num::PrimInt> Solver<T> {
pub fn new(n: usize) -> Self {
let h = n / 2 + 1;
let w = h * (n - 1);
Self {
n: (n as u32),
h: (h as u32),
w: (w as u32),
solve_stack: vec![SaveState::new(); h],
}
}
pub fn solve(&mut self) -> Wall {
let wall = Wall::create_empty(self.w);
wall.heights
.iter()
.take(2)
.zip(0..1)
.for_each(|(x, i)| self.solve_stack[*x as usize].set_bit(i));
wall
}
}
|
