- commit
- 150ed5b49297d8847c67da395af813b348ce750d
- parent
- 12b4e6a0627989ce75715061947c61b04bf34b6f
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2022-12-15 10:51
refactor
Diffstat
| M | 2022/15/solution.rs | 37 | +++++++++++++++++++++++-------------- |
1 files changed, 23 insertions, 14 deletions
diff --git a/2022/15/solution.rs b/2022/15/solution.rs
@@ -14,7 +14,7 @@ fn get_input() -> Vec<(i64, i64, i64, i64)> {
14 14 }).collect();
15 15 }
16 16
17 -1 fn merge(v: Vec<(i64, i64)>, b1: i64, b2: i64) -> Vec<(i64, i64)> {
-1 17 fn range_merge(v: Vec<(i64, i64)>, b1: i64, b2: i64) -> Vec<(i64, i64)> {
18 18 if b1 > b2 {
19 19 return v;
20 20 }
@@ -34,7 +34,7 @@ fn merge(v: Vec<(i64, i64)>, b1: i64, b2: i64) -> Vec<(i64, i64)> {
34 34 return result;
35 35 }
36 36
37 -1 fn remove(v: Vec<(i64, i64)>, b1: i64, b2: i64) -> Vec<(i64, i64)> {
-1 37 fn range_remove(v: Vec<(i64, i64)>, b1: i64, b2: i64) -> Vec<(i64, i64)> {
38 38 let mut result = vec![];
39 39 for (a1, a2) in v.into_iter() {
40 40 if a1 <= b2 && b1 <= a2 {
@@ -51,10 +51,6 @@ fn remove(v: Vec<(i64, i64)>, b1: i64, b2: i64) -> Vec<(i64, i64)> {
51 51 return result;
52 52 }
53 53
54 -1 fn count(v: Vec<(i64, i64)>) -> i64 {
55 -1 return v.iter().map(|(x1, x2)| x2 - x1 + 1).sum();
56 -1 }
57 -1
58 54 fn part1(positions: &Vec<(i64, i64, i64, i64)>) -> i64 {
59 55 // different value for test and real input
60 56 let y = if positions.len() == 14 { 10 } else { 2000000 };
@@ -65,19 +61,19 @@ fn part1(positions: &Vec<(i64, i64, i64, i64)>) -> i64 {
65 61 let d = (xs - xb).abs() + (ys - yb).abs();
66 62 let x1 = xs - d + (y - ys).abs();
67 63 let x2 = xs + d - (y - ys).abs();
68 -1 ranges = merge(ranges, x1, x2);
-1 64 ranges = range_merge(ranges, x1, x2);
69 65 }
70 66
71 67 for (xs, ys, xb, yb) in positions.iter() {
72 68 if *ys == y {
73 -1 ranges = remove(ranges, *xs, *xs);
-1 69 ranges = range_remove(ranges, *xs, *xs);
74 70 }
75 71 if *yb == y {
76 -1 ranges = remove(ranges, *xb, *xb);
-1 72 ranges = range_remove(ranges, *xb, *xb);
77 73 }
78 74 }
79 75
80 -1 return count(ranges);
-1 76 return ranges.iter().map(|(x1, x2)| x2 - x1 + 1).sum();
81 77 }
82 78
83 79 fn slant(x: i64, y: i64) -> (i64, i64) {
@@ -99,7 +95,7 @@ fn part2(positions: &Vec<(i64, i64, i64, i64)>) -> i64 {
99 95 for (xs, ys, xb, yb) in positions.iter() {
100 96 let d = (xs - xb).abs() + (ys - yb).abs();
101 97
102 -1 // turn by 45deg so we can work with rectangular areas
-1 98 // turn by 45deg so we can work with rectangles areas
103 99 let (x, y) = slant(*xs, *ys);
104 100
105 101 let bx1 = x - d;
@@ -112,6 +108,19 @@ fn part2(positions: &Vec<(i64, i64, i64, i64)>) -> i64 {
112 108 if ax2 < bx1 || ax1 > bx2 || ay2 < by1 || ay1 > by2 {
113 109 tmp.push((ax1, ay1, ax2, ay2));
114 110 } else {
-1 111 // remove one rectangle from another, splitting it into up
-1 112 // to 4 smaller ones.
-1 113 //
-1 114 // ax1 ax2
-1 115 // ay1 +---+-------+---+
-1 116 // | | 3 | |
-1 117 // | +-------+ | by1
-1 118 // | 1 | | 2 |
-1 119 // | +-------+ | by2
-1 120 // | | 4 | |
-1 121 // ay2 +---+-------+---+
-1 122 // bx1 bx2
-1 123
115 124 if ax1 < bx1 {
116 125 tmp.push((ax1, ay1, bx1 - 1, ay2));
117 126 }
@@ -131,7 +140,7 @@ fn part2(positions: &Vec<(i64, i64, i64, i64)>) -> i64 {
131 140 areas = tmp;
132 141 }
133 142
134 -1 let foo = areas.iter().map(|(ax1, ay1, ax2, ay2)| {
-1 143 let filtered = areas.iter().map(|(ax1, ay1, ax2, ay2)| {
135 144 let (x1, y1) = unslant(*ax1, *ay1);
136 145 let (x2, y2) = unslant(*ax2, *ay2);
137 146 return (x1, y1, x2, y2);
@@ -143,8 +152,8 @@ fn part2(positions: &Vec<(i64, i64, i64, i64)>) -> i64 {
143 152 || (*y1 > n && *y2 > n)
144 153 )).collect::<Vec<(i64, i64, i64, i64)>>();
145 154
146 -1 assert_eq!(foo.len(), 1);
147 -1 let (x1, y1, x2, y2) = foo[0];
-1 155 assert_eq!(filtered.len(), 1);
-1 156 let (x1, y1, x2, y2) = filtered[0];
148 157 assert_eq!(x1, x2);
149 158 assert_eq!(y1, y2);
150 159 return x1 * 4000000 + y1;