- commit
- fa87a81b2c714d0d9eb99132531cacc174815c74
- parent
- f80c19893b91751bcf41bc558da0f9a8bd9f6814
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2021-12-22 08:17
refactor and optimize
Diffstat
| M | 2021/22/part2.rs | 165 | +++++++++++++++++++++++++++++++++---------------------------- |
1 files changed, 89 insertions, 76 deletions
diff --git a/2021/22/part2.rs b/2021/22/part2.rs
@@ -3,7 +3,6 @@ use std::fs::File; 3 3 use std::io::BufRead; 4 4 use std::io::BufReader; 5 56 -1 #[derive(Copy, Clone)]7 6 struct Area { 8 7 x1: i64, 9 8 x2: i64, @@ -13,64 +12,79 @@ struct Area { 13 12 z2: i64, 14 13 } 15 1416 -1 fn get_ranges(s: &str) -> Area {17 -1 let parsed = s18 -1 .split(",")19 -1 .map(|r| match r[2..]20 -1 .split("..")21 -1 .collect::<Vec<&str>>()[..] {22 -1 [left, right] => (23 -1 left.parse::<i64>().unwrap(),24 -1 right.parse::<i64>().unwrap(),25 -1 ),26 -1 _ => unreachable!(),27 -1 }28 -1 )29 -1 .collect::<Vec<(i64, i64)>>();30 -131 -1 return match parsed[..] {32 -1 [x, y, z] => Area {33 -1 x1: x.0,34 -1 x2: x.1,35 -1 y1: y.0,36 -1 y2: y.1,37 -1 z1: z.0,38 -1 z2: z.1,39 -1 },40 -1 _ => unreachable!(),41 -1 };42 -1 }-1 15 impl Area { -1 16 fn parse(s: &str) -> Self { -1 17 let parsed = s -1 18 .split(",") -1 19 .map(|r| match r[2..] -1 20 .split("..") -1 21 .collect::<Vec<&str>>()[..] { -1 22 [left, right] => ( -1 23 left.parse::<i64>().unwrap(), -1 24 right.parse::<i64>().unwrap(), -1 25 ), -1 26 _ => unreachable!(), -1 27 } -1 28 ) -1 29 .collect::<Vec<(i64, i64)>>(); 43 3044 -1 fn area_difference(a: Area, b: Area) -> Vec<Area> {45 -1 let mut shards = vec![];-1 31 return match parsed[..] { -1 32 [x, y, z] => Self { -1 33 x1: x.0, -1 34 x2: x.1, -1 35 y1: y.0, -1 36 y2: y.1, -1 37 z1: z.0, -1 38 z2: z.1, -1 39 }, -1 40 _ => unreachable!(), -1 41 }; -1 42 } 46 4347 -1 let x1 = if a.x1 > b.x1 {a.x1} else {b.x1};48 -1 let x2 = if a.x2 < b.x2 {a.x2} else {b.x2};49 -1 let y1 = if a.y1 > b.y1 {a.y1} else {b.y1};50 -1 let y2 = if a.y2 < b.y2 {a.y2} else {b.y2};51 -1 let z1 = if a.z1 > b.z1 {a.z1} else {b.z1};52 -1 let z2 = if a.z2 < b.z2 {a.z2} else {b.z2};-1 44 fn diff(&self, other: &Self) -> Vec<Self> { -1 45 // break down self into shards that do not overlap with other -1 46 let mut shards = vec![]; 53 4754 -1 if a.x1 <= x1 - 1 {55 -1 shards.push(Area { x1: a.x1, x2: x1 - 1, y1: a.y1, y2: a.y2, z1: a.z1, z2: a.z2 });56 -1 }57 -1 if a.y1 <= y1 - 1 {58 -1 shards.push(Area { x1: x1, x2: x2, y1: a.y1, y2: y1 - 1, z1: a.z1, z2: a.z2 });59 -1 }60 -1 if a.z1 <= z1 - 1 {61 -1 shards.push(Area { x1: x1, x2: x2, y1: y1, y2: y2, z1: a.z1, z2: z1 - 1 });62 -1 }63 -1 if z2 + 1 <= a.z2 {64 -1 shards.push(Area { x1: x1, x2: x2, y1: y1, y2: y2, z1: z2 + 1, z2: a.z2 });65 -1 }66 -1 if y2 + 1 <= a.y2 {67 -1 shards.push(Area { x1: x1, x2: x2, y1: y2 + 1, y2: a.y2, z1: a.z1, z2: a.z2 });-1 48 let x1 = if self.x1 > other.x1 {self.x1} else {other.x1}; -1 49 let x2 = if self.x2 < other.x2 {self.x2} else {other.x2}; -1 50 let y1 = if self.y1 > other.y1 {self.y1} else {other.y1}; -1 51 let y2 = if self.y2 < other.y2 {self.y2} else {other.y2}; -1 52 let z1 = if self.z1 > other.z1 {self.z1} else {other.z1}; -1 53 let z2 = if self.z2 < other.z2 {self.z2} else {other.z2}; -1 54 -1 55 if self.x1 < x1 { -1 56 shards.push(Area { x1: self.x1, x2: x1 - 1, y1: self.y1, y2: self.y2, z1: self.z1, z2: self.z2 }); -1 57 } -1 58 if self.y1 < y1 { -1 59 shards.push(Area { x1, x2, y1: self.y1, y2: y1 - 1, z1: self.z1, z2: self.z2 }); -1 60 } -1 61 if self.z1 < z1 { -1 62 shards.push(Area { x1, x2, y1, y2, z1: self.z1, z2: z1 - 1 }); -1 63 } -1 64 if z2 < self.z2 { -1 65 shards.push(Area { x1, x2, y1, y2, z1: z2 + 1, z2: self.z2 }); -1 66 } -1 67 if y2 < self.y2 { -1 68 shards.push(Area { x1, x2, y1: y2 + 1, y2: self.y2, z1: self.z1, z2: self.z2 }); -1 69 } -1 70 if x2 < self.x2 { -1 71 shards.push(Area { x1: x2 + 1, x2: self.x2, y1: self.y1, y2: self.y2, z1: self.z1, z2: self.z2 }); -1 72 } -1 73 -1 74 return shards; 68 75 }69 -1 if x2 + 1 <= a.x2 {70 -1 shards.push(Area { x1: x2 + 1, x2: a.x2, y1: a.y1, y2: a.y2, z1: a.z1, z2: a.z2 });-1 76 -1 77 fn overlap(&self, other: &Self) -> bool { -1 78 return self.x1 <= other.x2 && other.x1 <= self.x2 -1 79 && self.y1 <= other.y2 && other.y1 <= self.y2 -1 80 && self.z1 <= other.z2 && other.z1 <= self.z2; 71 81 } 72 8273 -1 return shards;-1 83 fn count(&self) -> i64 { -1 84 return (self.x2 - self.x1 + 1) -1 85 * (self.y2 - self.y1 + 1) -1 86 * (self.z2 - self.z1 + 1); -1 87 } 74 88 } 75 89 76 90 fn add_area(area: Area, mut areas: &mut Vec<Area>) { @@ -80,16 +94,25 @@ fn add_area(area: Area, mut areas: &mut Vec<Area>) { 80 94 81 95 let mut i = 0; 82 96 while i < areas.len() {83 -1 let other = areas[i];84 -1 if area.x1 <= other.x2 && other.x1 <= area.x285 -1 && area.y1 <= other.y2 && other.y1 <= area.y286 -1 && area.z1 <= other.z2 && other.z1 <= area.z2 {87 -1 for shard in area_difference(area, other) {88 -1 add_area(shard, &mut areas);-1 97 let other = &areas[i]; -1 98 if area.overlap(other) { -1 99 let shards1 = area.diff(other); -1 100 let shards2 = other.diff(&area); -1 101 // PERF: optimize for a smaller areas.len() -1 102 if shards1.len() < shards2.len() { -1 103 for shard in shards1 { -1 104 add_area(shard, &mut areas); -1 105 } -1 106 return; -1 107 } else { -1 108 areas.remove(i); -1 109 for shard in shards2 { -1 110 areas.push(shard); -1 111 } 89 112 }90 -1 return;-1 113 } else { -1 114 i += 1; 91 115 }92 -1 i += 1;93 116 } 94 117 areas.push(area); 95 118 } @@ -97,12 +120,9 @@ fn add_area(area: Area, mut areas: &mut Vec<Area>) { 97 120 fn remove_area(area: Area, areas: &mut Vec<Area>) { 98 121 let mut i = 0; 99 122 while i < areas.len() {100 -1 let other = areas[i];101 -1 if area.x1 <= other.x2 && other.x1 <= area.x2102 -1 && area.y1 <= other.y2 && other.y1 <= area.y2103 -1 && area.z1 <= other.z2 && other.z1 <= area.z2 {104 -1 areas.remove(i);105 -1 for shard in area_difference(other, area) {-1 123 if area.overlap(&areas[i]) { -1 124 let other = areas.remove(i); -1 125 for shard in other.diff(&area) { 106 126 areas.push(shard); 107 127 } 108 128 } else { @@ -111,13 +131,6 @@ fn remove_area(area: Area, areas: &mut Vec<Area>) { 111 131 } 112 132 } 113 133114 -1 fn count(areas: &Vec<Area>) -> i64 {115 -1 return areas116 -1 .iter()117 -1 .map(|area| (area.x2 - area.x1 + 1) * (area.y2 - area.y1 + 1) * (area.z2 - area.z1 + 1))118 -1 .sum();119 -1 }120 -1121 134 fn main() { 122 135 let path = args().nth(1).unwrap(); 123 136 let file = File::open(path).unwrap(); @@ -128,7 +141,7 @@ fn main() { 128 141 match line.unwrap().split(" ").collect::<Vec<&str>>()[..] { 129 142 [a, b] => { 130 143 let on = a == "on";131 -1 let area = get_ranges(b);-1 144 let area = Area::parse(b); 132 145 if on { 133 146 add_area(area, &mut areas); 134 147 } else { @@ -139,5 +152,5 @@ fn main() { 139 152 } 140 153 } 141 154142 -1 println!("{}", count(&areas));-1 155 println!("{}", areas.iter().map(|area| area.count()).sum::<i64>()); 143 156 }