- commit
- df2f786f3fe1f9a876a988ffc74e03554d533983
- parent
- 5b610ea9470197e4aefa6c18b9984f143f9a2e53
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2022-12-17 12:54
2022-12-17 part2
Diffstat
| M | 2022/17/solution.rs | 110 | +++++++++++++++++++++++++++++++++++++++++-------------------- |
1 files changed, 75 insertions, 35 deletions
diff --git a/2022/17/solution.rs b/2022/17/solution.rs
@@ -1,21 +1,33 @@ 1 1 use std::collections::HashSet; -1 2 use std::collections::HashMap; -1 3 use std::convert::TryInto; 2 4 3 5 #[path = "../lib.rs"] mod lib; 4 6 -1 7 const WIDTH: usize = 7; -1 8 5 9 struct Shape {6 -1 blocks: HashSet<(i64, i64)>,7 -1 bottom: HashSet<(i64, i64)>,8 -1 left: HashSet<(i64, i64)>,9 -1 right: HashSet<(i64, i64)>,10 -1 width: i64,11 -1 height: i64,-1 10 blocks: HashSet<(usize, usize)>, -1 11 bottom: HashSet<(usize, usize)>, -1 12 left: HashSet<(usize, usize)>, -1 13 right: HashSet<(usize, usize)>, -1 14 width: usize, -1 15 height: usize, -1 16 } -1 17 -1 18 #[derive(Hash, PartialEq, Eq)] -1 19 struct CacheKey { -1 20 move_i: usize, -1 21 shape_i: usize, -1 22 // not sure if 4 rows are enough to capture this, but hope it works, but at least its very probable -1 23 top_rows: [[bool; WIDTH]; 4], 12 24 } 13 2514 -1 fn make_shape(blocks: Vec<(i64, i64)>) -> Shape {-1 26 fn make_shape(blocks: Vec<(usize, usize)>) -> Shape { 15 27 return Shape { 16 28 blocks: blocks.iter().map(|(x, y)| (*x, *y)).collect(),17 -1 bottom: blocks.iter().filter(|(x, y)| !blocks.contains(&(*x, *y - 1))).map(|(x, y)| (*x, *y)).collect(),18 -1 left: blocks.iter().filter(|(x, y)| !blocks.contains(&(*x - 1, *y))).map(|(x, y)| (*x, *y)).collect(),-1 29 bottom: blocks.iter().filter(|(x, y)| *y == 0 || !blocks.contains(&(*x, *y - 1))).map(|(x, y)| (*x, *y)).collect(), -1 30 left: blocks.iter().filter(|(x, y)| *x == 0 || !blocks.contains(&(*x - 1, *y))).map(|(x, y)| (*x, *y)).collect(), 19 31 right: blocks.iter().filter(|(x, y)| !blocks.contains(&(*x + 1, *y))).map(|(x, y)| (*x, *y)).collect(), 20 32 width: blocks.iter().map(|(x, _)| *x).max().unwrap() + 1, 21 33 height: blocks.iter().map(|(_, y)| *y).max().unwrap() + 1, @@ -36,13 +48,12 @@ fn get_input() -> Vec<bool> { 36 48 return moves; 37 49 } 38 5039 -1 fn render(covered: &HashSet<(i64, i64)>) {40 -1 // let width = covered.iter().map(|(x, _)| *x).max().unwrap() + 1;41 -1 let width = 7;-1 51 #[allow(dead_code)] -1 52 fn render(covered: &HashSet<(usize, usize)>) { 42 53 let height = covered.iter().map(|(_, y)| *y).max().unwrap() + 1; 43 54 44 55 for y in (0..height + 3).rev() {45 -1 for x in 0..width {-1 56 for x in 0..WIDTH { 46 57 if covered.contains(&(x, y)) { 47 58 print!("#"); 48 59 } else { @@ -54,33 +65,38 @@ fn render(covered: &HashSet<(i64, i64)>) { 54 65 print!("\n"); 55 66 } 56 6757 -1 fn part1(moves: &Vec<bool>, shapes: &[Shape; 5], width: i64, n: usize) -> i64 {-1 68 fn part1(moves: &Vec<bool>, shapes: &[Shape; 5], n: usize) -> usize { 58 69 let mut height = 0; 59 70 let mut move_i = 0;60 -1 let mut covered: HashSet<(i64, i64)> = HashSet::new();-1 71 let mut i = 0; -1 72 let mut covered: HashSet<(usize, usize)> = HashSet::new(); 61 7362 -1 for i in 0..n {-1 74 let mut cache = HashMap::new(); -1 75 let mut jump_height = 0; -1 76 -1 77 while i < n { 63 78 let shape = &shapes[i % shapes.len()]; 64 79 let mut x = 2;65 -1 let mut y = height + 3;66 -167 -1 // for _ in 0..3 {68 -1 // if moves[move_i] {69 -1 // if x + shape.width + 1 < width {70 -1 // x += 1;71 -1 // }72 -1 // } else {73 -1 // if x > 0 {74 -1 // x -= 1;75 -1 // }76 -1 // }77 -1 // move_i = (move_i + 1) % moves.len();78 -1 // }-1 80 let mut y = height; -1 81 -1 82 // PERF: for the first three steps there can bo no collisions -1 83 for _ in 0..3 { -1 84 if moves[move_i] { -1 85 if x + shape.width < WIDTH { -1 86 x += 1; -1 87 } -1 88 } else { -1 89 if x > 0 { -1 90 x -= 1; -1 91 } -1 92 } -1 93 move_i = (move_i + 1) % moves.len(); -1 94 } 79 95 80 96 loop { 81 97 let move_right = moves[move_i]; 82 98 if move_right {83 -1 if x + shape.width < width && shape.right.iter().all(|(xs, ys)| !covered.contains(&((x + *xs + 1, y + *ys)))) {-1 99 if x + shape.width < WIDTH && shape.right.iter().all(|(xs, ys)| !covered.contains(&((x + *xs + 1, y + *ys)))) { 84 100 x += 1; 85 101 } 86 102 } else { @@ -100,11 +116,35 @@ fn part1(moves: &Vec<bool>, shapes: &[Shape; 5], width: i64, n: usize) -> i64 { 100 116 covered.extend(shape.blocks.iter().map(|(xs, ys)| (x + xs, y + ys))); 101 117 height = (y + shape.height).max(height); 102 118 -1 119 if jump_height == 0 { -1 120 let cache_key = CacheKey { -1 121 move_i: move_i, -1 122 shape_i: i % shapes.len(), -1 123 top_rows: (0..4).map(|x| { -1 124 return (0..WIDTH).map(|dy| { -1 125 return dy < height && covered.contains(&(x, height - 1 - dy)); -1 126 }).collect::<Vec<bool>>().try_into().unwrap(); -1 127 }).collect::<Vec<[bool; WIDTH]>>().try_into().unwrap(), -1 128 }; -1 129 -1 130 if let Some((prior_i, prior_height)) = cache.get(&cache_key) { -1 131 let di = i - prior_i; -1 132 let dh = height - prior_height; -1 133 let count = (n - i) / di; -1 134 println!("jumped from {} to {} ({}x{})", i, i + di * count, di, count); -1 135 i += di * count; -1 136 jump_height = dh * count; -1 137 } else { -1 138 cache.insert(cache_key, (i, height)); -1 139 } -1 140 } -1 141 103 142 // render(&covered); -1 143 -1 144 i += 1; 104 145 }105 -1 // render(&covered);106 146107 -1 return height;-1 147 return height + jump_height; 108 148 } 109 149 110 150 fn main() { @@ -144,6 +184,6 @@ fn main() { 144 184 ]), 145 185 ]; 146 186147 -1 println!("part1: {}", part1(&moves, &shapes, 7, 2022));148 -1 // println!("part2: {}", part2(&optimized, 26));-1 187 println!("part1: {}", part1(&moves, &shapes, 2022)); -1 188 println!("part2: {}", part1(&moves, &shapes, 1000000000000)); 149 189 }