Day 7

5 files changed, 125 insertions, 0 deletions

diff --git a/07/Cargo.toml b/07/Cargo.toml
new file mode 100644
index 0000000..2a881ac
--- /dev/null
+++ b/07/Cargo.toml
@@ -0,0 +1,15 @@
+[package]
+name = "day-07"
+version = "0.1.0"
+authors = ["Gard Spreemann <gspr@nonempty.org>"]
+edition = "2021"
+
+[[bin]]
+name = "part-1"
+path = "src/part-1.rs"
+
+[[bin]]
+name = "part-2"
+path = "src/part-2.rs"
+
+[dependencies]
diff --git a/07/input.txt b/07/input.txt
new file mode 100644
index 0000000..0ef389c
--- /dev/null
+++ b/07/input.txt
@@ -0,0 +1 @@
+1101,1,29,67,1102,0,1,65,1008,65,35,66,1005,66,28,1,67,65,20,4,0,1001,65,1,65,1106,0,8,99,35,67,101,99,105,32,110,39,101,115,116,32,112,97,115,32,117,110,101,32,105,110,116,99,111,100,101,32,112,114,111,103,114,97,109,10,27,591,29,1713,943,341,593,941,152,142,746,674,269,241,20,8,991,662,34,24,669,34,233,137,576,215,957,570,553,111,205,210,27,1397,941,31,246,1064,83,53,285,517,972,29,742,34,260,185,1582,1273,248,1132,346,1208,146,171,220,1769,47,735,719,12,39,517,694,253,293,244,31,133,163,22,47,20,166,190,1072,24,17,445,250,6,139,134,361,304,812,201,825,87,118,1213,710,132,261,184,37,512,90,1276,1007,83,132,874,0,109,1005,513,1544,1759,1447,351,1172,1087,1392,643,872,3,882,805,547,1360,20,33,5,844,411,121,167,586,5,39,230,1321,1058,197,244,178,12,900,257,21,346,280,225,571,717,62,55,368,120,254,695,766,55,534,266,9,273,1,466,203,870,1188,623,15,135,538,779,698,83,850,1244,63,562,19,1050,6,495,243,1388,293,38,80,265,261,1392,351,505,922,434,644,721,97,227,635,753,467,6,1649,945,1405,492,332,789,414,440,791,105,778,1851,959,80,291,1077,434,928,272,156,72,321,180,1281,78,15,603,1243,306,533,1024,637,719,62,378,3,339,1805,1236,647,92,574,63,418,1342,226,85,532,9,19,893,155,1686,350,54,161,51,437,1096,508,137,920,20,146,824,142,233,328,286,289,229,90,89,760,1005,557,7,510,1572,64,1378,0,624,15,476,368,885,1264,260,312,141,799,1303,1136,706,54,1612,395,84,508,201,213,241,293,74,132,350,652,291,239,119,184,840,594,310,588,129,330,311,8,177,366,379,522,527,1332,857,853,621,560,464,339,2,839,582,23,466,1415,325,971,582,118,391,1098,640,1351,201,800,1579,332,100,196,1,238,1078,157,599,378,392,1433,34,366,473,193,90,106,245,393,164,1751,1054,697,749,389,1060,66,604,190,444,54,1273,175,65,1188,1977,829,744,918,66,1023,404,1436,1392,26,366,98,1038,254,304,723,21,606,349,5,645,610,1626,287,523,411,826,155,457,230,1124,648,271,567,671,71,918,20,16,787,975,785,133,132,330,278,2,1460,493,696,1264,40,319,691,332,1258,26,213,1024,389,688,183,162,604,993,539,75,998,362,466,1033,647,78,103,666,1338,1158,1397,319,1073,416,1274,9,52,302,83,427,546,132,228,499,7,829,77,76,271,68,1,1388,874,521,530,594,531,710,7,1104,85,832,30,7,285,40,1414,140,243,141,1613,575,805,709,627,310,97,1093,377,364,876,283,176,545,57,300,3,1255,360,1100,90,87,1017,28,9,1094,112,1339,20,713,134,345,559,138,1078,116,874,334,485,756,585,872,846,1072,262,11,1285,95,1658,36,79,308,13,221,364,264,571,110,605,102,465,3,194,619,310,890,880,724,26,330,378,44,1430,642,328,89,527,111,420,1239,93,46,267,379,18,238,1373,303,833,521,761,30,748,343,630,289,84,1160,789,45,100,734,204,275,1543,1072,1787,105,87,0,164,719,354,284,309,1743,1608,41,259,343,76,515,310,661,986,114,203,711,73,297,98,1346,372,166,1073,111,910,679,289,56,46,114,430,411,326,48,1117,10,330,666,107,389,68,995,171,1690,161,1051,1362,741,361,418,702,956,1311,621,277,816,604,160,19,1298,25,585,189,1259,697,89,128,543,1148,27,270,165,1005,1022,400,38,423,467,43,967,1242,133,719,7,1,348,597,79,122,126,168,312,898,158,1,162,133,455,366,62,6,1159,346,529,505,29,503,177,749,190,910,386,274,1284,525,520,981,743,603,17,597,330,183,276,445,380,360,936,1562,1007,35,492,129,716,374,412,518,117,4,1469,713,356,92,7,372,113,128,164,359,1409,1147,543,8,179,232,1356,1131,168,579,133,174,1357,1601,21,104,365,7,32,1052,1656,1313,396,171,688,840,115,370,766,309,1477,38,556,5,1696,284,310,217,158,127,208,75,443,241,120,76,13,948,227,855,29,362,362,535,313,882,233,514,152,380,630,63,29,233,1623,862,139,21,828,119,154,130,1057,542,226,868,89,160,1267,346,209,1067,1001,92,170,104,557,634,161,1825,717,622,51,190,600,22,114,902,11,3,388,1773,523,224,1455,773,283,56,102,207,23,840,67,743,407,1017,957,94,33,38,710,176,115,926,537,338,606,257,957,1573,1270,222,591,714,1430,209,250,17,69,917,1270,81,648,96,74,232,426,299,598,41,1125,1108,50,521,209,327,452,281,609,124,1124,606,1395,554,754,15,559,174,786,1325,634,133,93,398
diff --git a/07/src/part-1.rs b/07/src/part-1.rs
new file mode 100644
index 0000000..db20c41
--- /dev/null
+++ b/07/src/part-1.rs
@@ -0,0 +1,27 @@
+use std::io::{BufRead};
+
+fn cost(positions: & [i64], dest: i64) -> i64 {
+    positions.into_iter().map(|x| (x - dest).abs()).sum()
+}
+
+fn median<T: Copy + Ord>(mut x: Vec<T>) -> T {
+    let n = x.len();
+    *x.select_nth_unstable(n/2).1
+}
+
+pub fn main() {
+    let mut stdin = std::io::stdin();
+    let mut handle = stdin.lock();
+
+    let input: String = {
+        let mut buf = String::new();
+        handle.read_line(&mut buf).unwrap();
+        String::from(buf.trim_end())
+    };
+
+    let positions: Vec<i64> = input.split(',').map(|w| w.parse().expect("Malformed input")).collect();
+    let median = median(positions.clone());
+    let cost = cost(& positions, median);
+    
+    println!("Align at {} for a cost of {}.", median, cost);
+}
diff --git a/07/src/part-2.rs b/07/src/part-2.rs
new file mode 100644
index 0000000..926b9a1
--- /dev/null
+++ b/07/src/part-2.rs
@@ -0,0 +1,80 @@
+use std::io::{BufRead};
+
+/*
+ *  The corresponding real-relaxed problem attains its cost minimum at
+ *  position x when
+ * 
+ *   x + L(x)/(2N)
+ *
+ *  is as close to the average of all the initial positions as
+ *  possible. Here L is the function defined by
+ * 
+ *   L(x) = (num of initials < x) - (num of initials > x).
+ *
+ *  We compute L and the average in linear time, and then the best
+ *  *integer* approximation of x in linear time. In order to not have
+ *  to thoroughly fuss about the error in the real-relaxed problem, we
+ *  then check the two integer neighbors of that integer
+ *  approximation.
+ * 
+ *  Equivalently, to avoid floating point computations, we look at
+ *  when 2Nx + L(x) is as close as possible to 2S, where S is the sum
+ *  of all initial positions.
+ *
+ */
+
+fn cost(positions: & [i64], dest: i64) -> i64 {
+    positions.into_iter().map(|x| ((x-dest).pow(2) + (x-dest).abs())/2).sum()
+}
+
+pub fn main() {
+    let mut stdin = std::io::stdin();
+    let mut handle = stdin.lock();
+
+    let input: String = {
+        let mut buf = String::new();
+        handle.read_line(&mut buf).unwrap();
+        String::from(buf.trim_end())
+    };
+
+    let positions: Vec<i64> = {
+        let mut tmp: Vec<i64> = input.split(',').map(|w| w.parse().expect("Malformed input")).collect();
+        (&mut tmp).sort();
+        tmp
+    };
+    let n: usize = positions.len();
+    let s: i64 = (& positions).into_iter().sum();
+
+    // FIXME: Should build this backwards instead, but whatever.
+    let l: Vec<i64> = {
+        let mut ret: Vec<i64> = Vec::with_capacity(n);
+        let mut pos: i64 = positions[0];
+        let mut dups: usize = (& positions[0..]).into_iter().take_while(|p| **p == pos).count();
+        ret.extend(std::iter::repeat(-(n as i64) + (dups as i64)).take(dups));
+        let mut i: usize = dups;
+        while i < (n as usize) {
+            pos = positions[i];
+            dups = (& positions[i..]).into_iter().take_while(|p| **p == pos).count();
+            ret.extend(std::iter::repeat((dups as i64) + ret[i-1]).take(dups));
+            i += dups;
+        }
+        ret
+    };
+    
+    let best_relaxed_position: i64 = {
+        let mut ret = positions[0];
+        let mut best = i64::MAX;
+        for i in 0..n {
+            let err = (2*(n as i64)*positions[i] + l[i] - 2*s).abs();
+            if err < best {
+                ret = positions[i];
+                best = err;
+            }
+        }
+        ret
+    };
+    println!("Best relaxed position: {} (will therefore check {}, {}, {}).", best_relaxed_position, best_relaxed_position-1, best_relaxed_position, best_relaxed_position+1);
+    let best_cost = [-1, 0, 1].into_iter().map(|offset| cost(& positions, best_relaxed_position + offset)).min().unwrap();
+    println!("Minimal fuel cost: {}", best_cost);
+
+}
diff --git a/07/test.txt b/07/test.txt
new file mode 100644
index 0000000..27e8c4e
--- /dev/null
+++ b/07/test.txt
@@ -0,0 +1,2 @@
+16,1,2,0,4,2,7,1,2,14
+