From 53184c5377320b96455614e2010089a27ae3aba4 Mon Sep 17 00:00:00 2001
From: Gard Spreemann <gspr@nonempty.org>
Date: Thu, 9 Dec 2021 17:25:04 +0100
Subject: Day 7

---
 07/src/part-2.rs | 80 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 80 insertions(+)
 create mode 100644 07/src/part-2.rs

(limited to '07/src/part-2.rs')

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);
+
+}
-- 
cgit v1.2.3