- commit
- acb2230241fdf96bab3e3e953eee39563de62612
- parent
- 6af372228cc5f33a27d4867774f288dcde5b873f
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2022-12-15 08:51
2022-12-15 (slow)
Diffstat
| A | 2022/15/input.txt | 33 | +++++++++++++++++++++++++++++++++ |
| A | 2022/15/solution.rs | 121 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2022/15/test.txt | 14 | ++++++++++++++ |
3 files changed, 168 insertions, 0 deletions
diff --git a/2022/15/input.txt b/2022/15/input.txt
@@ -0,0 +1,33 @@ -1 1 Sensor at x=2716507, y=2935757: closest beacon is at x=2710394, y=2763439 -1 2 Sensor at x=3999794, y=3723425: closest beacon is at x=3369445, y=3597264 -1 3 Sensor at x=3657442, y=1764502: closest beacon is at x=3049587, y=2338806 -1 4 Sensor at x=3164509, y=3196584: closest beacon is at x=3369445, y=3597264 -1 5 Sensor at x=2809936, y=2799950: closest beacon is at x=2710394, y=2763439 -1 6 Sensor at x=2694454, y=2773569: closest beacon is at x=2710394, y=2763439 -1 7 Sensor at x=10878, y=1715223: closest beacon is at x=325433, y=2000000 -1 8 Sensor at x=803461, y=2606485: closest beacon is at x=325433, y=2000000 -1 9 Sensor at x=675548, y=1606326: closest beacon is at x=325433, y=2000000 -1 10 Sensor at x=2679411, y=2786440: closest beacon is at x=2710394, y=2763439 -1 11 Sensor at x=2154234, y=2343200: closest beacon is at x=3049587, y=2338806 -1 12 Sensor at x=2110512, y=354398: closest beacon is at x=1675167, y=-146032 -1 13 Sensor at x=2791638, y=1261304: closest beacon is at x=3049587, y=2338806 -1 14 Sensor at x=1312875, y=239990: closest beacon is at x=1675167, y=-146032 -1 15 Sensor at x=3942335, y=797194: closest beacon is at x=3809420, y=402553 -1 16 Sensor at x=2701618, y=2767691: closest beacon is at x=2710394, y=2763439 -1 17 Sensor at x=3984844, y=228193: closest beacon is at x=3809420, y=402553 -1 18 Sensor at x=2860718, y=2887510: closest beacon is at x=2710394, y=2763439 -1 19 Sensor at x=3621521, y=3823030: closest beacon is at x=3369445, y=3597264 -1 20 Sensor at x=3750994, y=3221696: closest beacon is at x=4361396, y=3105847 -1 21 Sensor at x=182700, y=100955: closest beacon is at x=1675167, y=-146032 -1 22 Sensor at x=2647016, y=2816460: closest beacon is at x=2710394, y=2763439 -1 23 Sensor at x=3190979, y=2626436: closest beacon is at x=3049587, y=2338806 -1 24 Sensor at x=2772574, y=2692795: closest beacon is at x=2710394, y=2763439 -1 25 Sensor at x=3538486, y=282: closest beacon is at x=3809420, y=402553 -1 26 Sensor at x=3688953, y=378293: closest beacon is at x=3809420, y=402553 -1 27 Sensor at x=2698132, y=2757338: closest beacon is at x=2710394, y=2763439 -1 28 Sensor at x=305105, y=3671091: closest beacon is at x=325433, y=2000000 -1 29 Sensor at x=2715037, y=2453: closest beacon is at x=1675167, y=-146032 -1 30 Sensor at x=3740685, y=2657814: closest beacon is at x=4174142, y=2733685 -1 31 Sensor at x=3911207, y=340249: closest beacon is at x=3809420, y=402553 -1 32 Sensor at x=1554097, y=1471192: closest beacon is at x=1675167, y=-146032 -1 33 Sensor at x=1891025, y=3796582: closest beacon is at x=3369445, y=3597264
diff --git a/2022/15/solution.rs b/2022/15/solution.rs
@@ -0,0 +1,121 @@
-1 1 // use std::collections::HashSet;
-1 2
-1 3 #[path = "../lib.rs"] mod lib;
-1 4
-1 5 fn get_input() -> Vec<(i64, i64, i64, i64)> {
-1 6 return lib::iter_input().map(|line| {
-1 7 let parts: Vec<&str> = line.split("=").collect();
-1 8 return (
-1 9 lib::split_once(parts[1], ',').unwrap().0.parse().unwrap(),
-1 10 lib::split_once(parts[2], ':').unwrap().0.parse().unwrap(),
-1 11 lib::split_once(parts[3], ',').unwrap().0.parse().unwrap(),
-1 12 parts[4].parse().unwrap(),
-1 13 );
-1 14 }).collect();
-1 15 }
-1 16
-1 17 fn get_ranges(positions: &Vec<(i64, i64, i64, i64)>, y: i64) -> Vec<(i64, i64)> {
-1 18 let mut ranges = vec![];
-1 19
-1 20 for (xs, ys, xb, yb) in positions.iter() {
-1 21 let d = (xs - xb).abs() + (ys - yb).abs();
-1 22 let x1 = xs - d + (y - ys).abs();
-1 23 let x2 = xs + d - (y - ys).abs();
-1 24 ranges = merge(ranges, x1, x2);
-1 25 }
-1 26
-1 27 return ranges;
-1 28 }
-1 29
-1 30 fn render(v: &Vec<(i64, i64)>) {
-1 31 for (x1, x2) in v.iter() {
-1 32 print!("{}-{}, ", x1, x2);
-1 33 }
-1 34 print!("\n");
-1 35 }
-1 36
-1 37 fn merge(v: Vec<(i64, i64)>, b1: i64, b2: i64) -> Vec<(i64, i64)> {
-1 38 if b1 > b2 {
-1 39 return v;
-1 40 }
-1 41
-1 42 let mut result = vec![];
-1 43 let mut new1 = b1;
-1 44 let mut new2 = b2;
-1 45 for (a1, a2) in v.into_iter() {
-1 46 if a1 <= new2 && new1 <= a2 {
-1 47 new1 = new1.min(a1);
-1 48 new2 = new2.max(a2);
-1 49 } else {
-1 50 result.push((a1, a2));
-1 51 }
-1 52 }
-1 53 result.push((new1, new2));
-1 54 return result;
-1 55 }
-1 56
-1 57 fn remove(v: Vec<(i64, i64)>, b1: i64, b2: i64) -> Vec<(i64, i64)> {
-1 58 let mut result = vec![];
-1 59 for (a1, a2) in v.into_iter() {
-1 60 if a1 <= b2 && b1 <= a2 {
-1 61 if a1 < b1 {
-1 62 result.push((a1, b1 - 1));
-1 63 }
-1 64 if b2 < a2 {
-1 65 result.push((b2 + 1, a2));
-1 66 }
-1 67 } else {
-1 68 result.push((a1, a2));
-1 69 }
-1 70 }
-1 71 return result;
-1 72 }
-1 73
-1 74 fn count(v: Vec<(i64, i64)>) -> i64 {
-1 75 return v.iter().map(|(x1, x2)| x2 - x1 + 1).sum();
-1 76 }
-1 77
-1 78 fn part1(positions: &Vec<(i64, i64, i64, i64)>) -> i64 {
-1 79 // different value for test and real input
-1 80 let y = if positions.len() == 14 { 10 } else { 2000000 };
-1 81
-1 82 let mut ranges = get_ranges(positions, y);
-1 83
-1 84 for (xs, ys, xb, yb) in positions.iter() {
-1 85 if *ys == y {
-1 86 ranges = remove(ranges, *xs, *xs);
-1 87 }
-1 88 if *yb == y {
-1 89 ranges = remove(ranges, *xb, *xb);
-1 90 }
-1 91 }
-1 92
-1 93 return count(ranges);
-1 94 }
-1 95
-1 96 fn part2(positions: &Vec<(i64, i64, i64, i64)>) -> i64 {
-1 97 // different value for test and real input
-1 98 let n = if positions.len() == 14 { 20 } else { 4000000 };
-1 99
-1 100 for y in 0..=n {
-1 101 let ranges = get_ranges(positions, y);
-1 102 let mut foo = vec![(0, n)];
-1 103 for (x1, x2) in ranges.iter() {
-1 104 foo = remove(foo, *x1, *x2);
-1 105 }
-1 106 if !foo.is_empty() {
-1 107 assert_eq!(foo.len(), 1);
-1 108 assert_eq!(foo[0].0, foo[0].1);
-1 109 let x = foo[0].0;
-1 110 return x * 4000000 + y;
-1 111 }
-1 112 }
-1 113
-1 114 return 0;
-1 115 }
-1 116
-1 117 fn main() {
-1 118 let positions = get_input();
-1 119 println!("part1: {}", part1(&positions));
-1 120 println!("part2: {}", part2(&positions));
-1 121 }
diff --git a/2022/15/test.txt b/2022/15/test.txt
@@ -0,0 +1,14 @@ -1 1 Sensor at x=2, y=18: closest beacon is at x=-2, y=15 -1 2 Sensor at x=9, y=16: closest beacon is at x=10, y=16 -1 3 Sensor at x=13, y=2: closest beacon is at x=15, y=3 -1 4 Sensor at x=12, y=14: closest beacon is at x=10, y=16 -1 5 Sensor at x=10, y=20: closest beacon is at x=10, y=16 -1 6 Sensor at x=14, y=17: closest beacon is at x=10, y=16 -1 7 Sensor at x=8, y=7: closest beacon is at x=2, y=10 -1 8 Sensor at x=2, y=0: closest beacon is at x=2, y=10 -1 9 Sensor at x=0, y=11: closest beacon is at x=2, y=10 -1 10 Sensor at x=20, y=14: closest beacon is at x=25, y=17 -1 11 Sensor at x=17, y=20: closest beacon is at x=21, y=22 -1 12 Sensor at x=16, y=7: closest beacon is at x=15, y=3 -1 13 Sensor at x=14, y=3: closest beacon is at x=15, y=3 -1 14 Sensor at x=20, y=1: closest beacon is at x=15, y=3