advent2021-07.rs

use std::cmp;
use std::fs;

fn calc_gas(subs: &Vec<i32>, position: i32) -> i32 {
    subs.iter().fold(0, |acc, sub| acc + (sub - position).abs())
}

// 1+2+3+4..n == (n * (n+1)) / 2
fn calc_gas_exp(subs: &Vec<i32>, position: i32) -> i32 {
    subs.iter().fold(0, |acc, sub| {
        let n = (sub - position).abs();
        acc + (n * (n + 1)) / 2
    })
}

/**
 * Part 1. The cheapest position in terms of gas is the median position.
 * I don't have a proof for why that's true. I reason it out as follows:
 *      Outliers don't matter, take an example of [10000, 1, 0].
 *      position 1 is best at 10000
 *      Moving closer to the outlier reduces the cost for the outlier,
 *      but makes it more expensive for the other 2 at a tradeoff of 2 to 1.
 */ 
pub fn linear_gas(subs: &Vec<i32>) -> i32 {
    let mut sorted_subs = subs.clone();
    sorted_subs.sort();
    let median = sorted_subs.len() / 2;
    return cmp::min(calc_gas(&sorted_subs, sorted_subs[median]), calc_gas(&sorted_subs, sorted_subs[median + 1]));
}

/**
 * Prt 2. The cheapest position in terms of gas is the average position.
 * I don't have a proof for why that's true. I reason it out as follows:
 *      Outliers now matter, because moving 1 additional space costs more for the outliers
 *      The average balances out the large cost of moving outliers with
 *      additional (less expensive) movement from the values close to median
 */ 
pub fn exponential_gas(subs: &Vec<i32>) -> i32 {
    let mut sorted_subs = subs.clone();
    sorted_subs.sort();
    let average = sorted_subs.iter().sum::<i32>() / sorted_subs.len() as i32;
    return cmp::min(calc_gas_exp(&sorted_subs, average), calc_gas_exp(&sorted_subs, average + 1));
}