- commit
- 12b4e6a0627989ce75715061947c61b04bf34b6f
- parent
- acb2230241fdf96bab3e3e953eee39563de62612
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2022-12-15 10:40
faster solution
Diffstat
| M | 2022/15/solution.rs | 102 | +++++++++++++++++++++++++++++++++++++++++-------------------- |
1 files changed, 69 insertions, 33 deletions
diff --git a/2022/15/solution.rs b/2022/15/solution.rs
@@ -14,26 +14,6 @@ fn get_input() -> Vec<(i64, i64, i64, i64)> {
14 14 }).collect();
15 15 }
16 16
17 -1 fn get_ranges(positions: &Vec<(i64, i64, i64, i64)>, y: i64) -> Vec<(i64, i64)> {
18 -1 let mut ranges = vec![];
19 -1
20 -1 for (xs, ys, xb, yb) in positions.iter() {
21 -1 let d = (xs - xb).abs() + (ys - yb).abs();
22 -1 let x1 = xs - d + (y - ys).abs();
23 -1 let x2 = xs + d - (y - ys).abs();
24 -1 ranges = merge(ranges, x1, x2);
25 -1 }
26 -1
27 -1 return ranges;
28 -1 }
29 -1
30 -1 fn render(v: &Vec<(i64, i64)>) {
31 -1 for (x1, x2) in v.iter() {
32 -1 print!("{}-{}, ", x1, x2);
33 -1 }
34 -1 print!("\n");
35 -1 }
36 -1
37 17 fn merge(v: Vec<(i64, i64)>, b1: i64, b2: i64) -> Vec<(i64, i64)> {
38 18 if b1 > b2 {
39 19 return v;
@@ -79,7 +59,14 @@ fn part1(positions: &Vec<(i64, i64, i64, i64)>) -> i64 {
79 59 // different value for test and real input
80 60 let y = if positions.len() == 14 { 10 } else { 2000000 };
81 61
82 -1 let mut ranges = get_ranges(positions, y);
-1 62 let mut ranges = vec![];
-1 63
-1 64 for (xs, ys, xb, yb) in positions.iter() {
-1 65 let d = (xs - xb).abs() + (ys - yb).abs();
-1 66 let x1 = xs - d + (y - ys).abs();
-1 67 let x2 = xs + d - (y - ys).abs();
-1 68 ranges = merge(ranges, x1, x2);
-1 69 }
83 70
84 71 for (xs, ys, xb, yb) in positions.iter() {
85 72 if *ys == y {
@@ -93,25 +80,74 @@ fn part1(positions: &Vec<(i64, i64, i64, i64)>) -> i64 {
93 80 return count(ranges);
94 81 }
95 82
-1 83 fn slant(x: i64, y: i64) -> (i64, i64) {
-1 84 return (x + y, x - y);
-1 85 }
-1 86
-1 87 fn unslant(x: i64, y: i64) -> (i64, i64) {
-1 88 return ((x + y) / 2, (x - y) / 2);
-1 89 }
-1 90
96 91 fn part2(positions: &Vec<(i64, i64, i64, i64)>) -> i64 {
97 92 // different value for test and real input
98 93 let n = if positions.len() == 14 { 20 } else { 4000000 };
99 94
100 -1 for y in 0..=n {
101 -1 let ranges = get_ranges(positions, y);
102 -1 let mut foo = vec![(0, n)];
103 -1 for (x1, x2) in ranges.iter() {
104 -1 foo = remove(foo, *x1, *x2);
105 -1 }
106 -1 if !foo.is_empty() {
107 -1 assert_eq!(foo.len(), 1);
108 -1 assert_eq!(foo[0].0, foo[0].1);
109 -1 let x = foo[0].0;
110 -1 return x * 4000000 + y;
-1 95 let p1 = slant(n / 2 - n, n / 2);
-1 96 let p2 = slant(n / 2 + n, n / 2);
-1 97 let mut areas = vec![(p1.0, p1.1, p2.0, p2.1)];
-1 98
-1 99 for (xs, ys, xb, yb) in positions.iter() {
-1 100 let d = (xs - xb).abs() + (ys - yb).abs();
-1 101
-1 102 // turn by 45deg so we can work with rectangular areas
-1 103 let (x, y) = slant(*xs, *ys);
-1 104
-1 105 let bx1 = x - d;
-1 106 let by1 = y - d;
-1 107 let bx2 = x + d;
-1 108 let by2 = y + d;
-1 109
-1 110 let mut tmp = vec![];
-1 111 for (ax1, ay1, ax2, ay2) in areas.into_iter() {
-1 112 if ax2 < bx1 || ax1 > bx2 || ay2 < by1 || ay1 > by2 {
-1 113 tmp.push((ax1, ay1, ax2, ay2));
-1 114 } else {
-1 115 if ax1 < bx1 {
-1 116 tmp.push((ax1, ay1, bx1 - 1, ay2));
-1 117 }
-1 118 if ax2 > bx2 {
-1 119 tmp.push((bx2 + 1, ay1, ax2, ay2));
-1 120 }
-1 121 let x1 = ax1.max(bx1);
-1 122 let x2 = ax2.min(bx2);
-1 123 if ay1 < by1 {
-1 124 tmp.push((x1, ay1, x2, by1 - 1));
-1 125 }
-1 126 if ay2 > by2 {
-1 127 tmp.push((x1, by2 + 1, x2, ay2));
-1 128 }
-1 129 }
111 130 }
-1 131 areas = tmp;
112 132 }
113 133
114 -1 return 0;
-1 134 let foo = areas.iter().map(|(ax1, ay1, ax2, ay2)| {
-1 135 let (x1, y1) = unslant(*ax1, *ay1);
-1 136 let (x2, y2) = unslant(*ax2, *ay2);
-1 137 return (x1, y1, x2, y2);
-1 138 }).filter(|(x1, y1, x2, y2)| !(
-1 139 // this filter is not sufficient in the general case, but worked with my data
-1 140 (*x1 < 0 && *x2 < 0)
-1 141 || (*y1 < 0 && *y2 < 0)
-1 142 || (*x1 > n && *x2 > n)
-1 143 || (*y1 > n && *y2 > n)
-1 144 )).collect::<Vec<(i64, i64, i64, i64)>>();
-1 145
-1 146 assert_eq!(foo.len(), 1);
-1 147 let (x1, y1, x2, y2) = foo[0];
-1 148 assert_eq!(x1, x2);
-1 149 assert_eq!(y1, y2);
-1 150 return x1 * 4000000 + y1;
115 151 }
116 152
117 153 fn main() {