diff options
| -rw-r--r-- | src/day7.rs | 83 |
1 files changed, 83 insertions, 0 deletions
diff --git a/src/day7.rs b/src/day7.rs index 4b0828a..9b04ead 100644 --- a/src/day7.rs +++ b/src/day7.rs @@ -62,6 +62,9 @@ pub fn solve_day7_part1_median(input : &Vec<usize>) -> usize { } //Part 2 is more "difficult". Here the fuel function is no longer linear, but rather quadratic. +//(see https://de.wikipedia.org/wiki/Gaußsche_Summenformel - no, there's no English wiki page +//on this) +// //This means all the nice properties we found in the first part are not applicable. On the plus //side, now we have quadratic behaviour around the minimum, so Newton's method is on the table //again. @@ -74,6 +77,80 @@ pub fn solve_day7_part1_median(input : &Vec<usize>) -> usize { // //Still, put in words, the global minimum is there, where the sum of all distances + half the count //is the same on both sides. +// +//Finding the exact point is not straightforward, but we can get a reasonably good estimate and +//an upper bound for the error. +// +//First, let's write the full function that has to be fulfilled: +//sum((x-pos[i]), i) + 0.5*sum(sign(x-pos[i]),i) = 0 +//sum((x-pos[i]), i) + 0.5*sum(1, i where pos[i] < x) - 0.5*sum(1, i where pos[i] > x) = 0 +//sum((x-pos[i]), i) = 0.5*(n_right - n_left) +// +//Now let's look at how those two values change when we change x by 1. +//The left hand side will change by the total number of crabs, as each term will change by 1. +//That is already the total range the right side can ever cover, as it can, at maximum change by +//the total number of crabs if all crabs were within a single unit. It is also bounded, meaning +//that it can never be larger than half the number of crabs (if all crabs are at the same side). +// +//In other words, if we find a solution to +//sum((x-pos[i]),i) = 0 +//we are already at most 1 unit away from the exact solution, and the exact solution is always in +//the direction that makes the imbalance 0.5*(n_right - n_left) smaller, or, put differently, +//towards the median. +// +//This information about the direction allows us to further reduce our error estimate. The latest +//after we have passed half the number of crabs, the sign of the imbalance 0.5*(n_right - n_left) +//must flip, meaning that the solution to sum((x-pos[i]),i) = 0 actually can never be more than 0.5 +//units away from the true solution. (Assuming otherwise would need us to correct our result in +//both directions at the same time, what is absurd -> point proven.) +// +//We could have gotten the same reduction in error by exploiting the quantization of the problem. +//With full integer steps it is not possible to move "over" a crab by moving one step, at best we +//can move "on" or "off" a crab. This already limits the maximum change of the imbalance to half +//the number of crabs. +// +//Now knowing that the maximum error from solving +//sum((x-pos[i]),i) = 0 +//is 0.5 steps, we can limit our search range to two integer position values, namely the rounded +//solution, and the rounded solution ±1 in direction towards the median. +// +//The condition that fulfills +//sum((x-pos[i]),i) = 0 +//again is a well known quantity: The arithmetic mean. +// +//So, long story short: If we test the fuel consumption at the rounded arithmetic mean of the +//crab positions, the two neighbouring positions, and then pick the result with the lowest value, +//we have a solution. + +fn compute_fuel_costs_for_position_part2(input : &Vec<usize>, position : usize) -> usize { + input.iter() + .map(|&x| if x > position { x-position } else { position - x }) + .map(|dx| dx*dx+dx).sum::<usize>() + /2 +} + +fn rounded_arithmetic_mean(v : &Vec<usize>) -> usize { + ((2*v.iter().sum::<usize>()) / v.len() + 1) / 2 +} + +#[derive(Debug)] +pub struct NoInputError; +impl std::fmt::Display for NoInputError { + fn fmt(&self, f : &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> { + write!(f, "No input from generator. Could not compute fuel consumption.") + } +} +impl std::error::Error for NoInputError {} + +#[aoc(day7,part2,Mean)] +pub fn solve_part2_mean(input :&Vec<usize>) -> Result<usize, NoInputError> { + //computing the fuel consumption a third time is probably cheaper than finding the median. + //Let's just try three values, take the best one. + let mean = rounded_arithmetic_mean(input); + (mean-1..=mean+1).map(|position| compute_fuel_costs_for_position_part2(input,position)).min() + .ok_or(NoInputError) +} + #[cfg(test)] mod tests { use super::*; @@ -91,4 +168,10 @@ mod tests { let result = solve_day7_part1_median(&input); assert_eq!(result, 37); } + #[test] + fn test_day7_part2_average() { + let input = input_generator(get_day7_test_string()).unwrap(); + let result = solve_part2_mean(&input).unwrap(); + assert_eq!(result,168) + } } |