day14.rs

//
//  Part 2 is pure brute force. Compiled in release mode it still takes
//  about 1 hour or so to get to the answer. There is of course a better way
//  to do it which could be looked at later, time permitting.
//

use std::collections::HashMap;

fn main() {
    let prod =
        r#"1 HKCVW, 2 DFCT => 5 ZJZRN
        8 TCPN, 7 XHTJF, 3 DFCT => 8 ZKCXK
        1 ZJZRN, 4 NZVL, 1 NJFXK, 7 RHJCQ, 32 MCQS, 1 XFNPT => 5 ZWQX
        10 DRWB, 16 JBHKV => 6 TCPN
        3 MBFK => 7 DRWB
        9 RHJCQ => 6 MBMKZ
        1 BVFPF => 2 KRTGD
        1 QNXC, 7 BKNQT, 1 XFNPT => 4 VNFJQ
        2 TCPN, 1 WFSV => 2 TGJP
        35 DFCT => 2 RHJCQ
        1 SKBV, 7 CTRH => 8 QGDSV
        8 VSRMJ, 1 BVFPF => 4 CTRH
        1 WMCD => 3 FPZLF
        13 CVJQG, 8 DXBZJ => 9 QBDQ
        1 XSRWM => 5 GDJGV
        132 ORE => 3 MBFK
        2 BQGP => 9 LZKJZ
        5 GZLHP => 7 WFSV
        2 RXSZS, 10 MBFK, 1 BPNVK => 2 GZLHP
        13 BZFH => 8 XSRWM
        3 QLSVN => 3 SKBV
        8 QBDQ => 4 VSRMJ
        1 RXSZS => 9 CVJQG
        3 MBFK => 3 BVFPF
        7 GZLHP, 4 MBFK, 5 CVJQG => 8 XHTJF
        1 GZLHP => 2 DFCT
        4 SZDWB, 4 RHJCQ, 1 WMCD => 3 RGZDK
        2 BRXLV => 8 DXBZJ
        192 ORE => 7 RXSZS
        1 PRMR, 6 DFCT => 5 SZDWB
        104 ORE => 9 BPNVK
        6 VLJWQ, 8 ZKCXK, 6 BKNQT, 26 JRXQ, 7 FPZLF, 6 HKCVW, 18 KRTGD => 4 RBFX
        7 XFNPT, 1 GDJGV => 2 HJDB
        15 SKBV, 8 DRWB, 12 RXSZS => 3 GHQPH
        1 BZFH => 5 GCBR
        1 TGJP, 6 SKBV => 1 BZFH
        4 KRTGD, 1 ZJHKP, 1 LZKJZ, 1 VNFJQ, 6 QBDQ, 1 PRMR, 1 NJFXK, 1 HJDB => 8 TFQH
        10 BVFPF, 1 RGZDK => 8 QNXC
        1 XHTJF => 5 JRXQ
        3 XKTMK, 4 QGDSV => 3 ZJHKP
        2 BZFH => 7 PRMR
        1 BPNVK, 1 RXSZS => 5 JBHKV
        10 XHTJF => 9 BKNQT
        1 JBHKV, 2 XHTJF => 8 QLSVN
        24 VNFJQ, 42 TFQH, 39 RBFX, 1 ZWQX, 7 VBHVQ, 26 DRWB, 21 NJFXK => 1 FUEL
        26 WBKQ, 14 XHTJF => 5 BQGP
        5 WBKQ, 7 MBMKZ => 3 LQGC
        6 LQGC => 5 NZVL
        13 KRTGD, 5 GHQPH => 9 VLJWQ
        117 ORE => 4 BRXLV
        3 XKTMK, 1 PRMR => 2 MCQS
        3 DRWB, 7 BVFPF, 4 TCPN => 7 NJFXK
        10 VHFCR, 13 JZQJ => 5 XKTMK
        17 CVJQG, 4 GCBR => 9 HKCVW
        22 DFCT, 17 TGJP => 2 WBKQ
        2 JZQJ, 12 XFNPT, 1 BQGP => 2 VBHVQ
        12 HKCVW => 1 JZQJ
        1 XSRWM => 3 WMCD
        12 BZFH, 14 SKBV, 1 CTRH => 4 XFNPT
        7 ZKCXK => 6 VHFCR"#;

    let producers = parse_producers(prod);

    let mut spare_units: HashMap<String, i64> = HashMap::new();
    let mut remaining_ore: i64 = 1000000000000;
    let mut n_produced_fuel = 0;

    // Correct answer for production run is : 2876992

    loop {
        let cost = produce(0, &String::from("FUEL"), 1, &producers, &mut spare_units);
        if cost > remaining_ore {
            break
        } else {
            remaining_ore -= cost;
            n_produced_fuel += 1
        }
        println!("{}", remaining_ore);
    }

    println!("Produced fuel: {}", n_produced_fuel);
}

fn produce(indent: usize, required_material: &String, required_amount: i64, producers: &Vec<Producer>, spare_units: &mut HashMap<String, i64>) -> i64 {
    let mut remaining_needed_amount = required_amount;
    if let Some(v) = spare_units.get(required_material) {
        if *v > 0  {
            let remaining_v = 0.max(*v - required_amount);
            remaining_needed_amount = 0.max(required_amount - *v);

            spare_units.insert(required_material.clone(), remaining_v);
        }
    }
    let cost = if remaining_needed_amount == 0 {
        0
    } else {
        if required_material == "ORE" {
            remaining_needed_amount
        }  else {
            let producer = producers.iter().find( |p| p.output.material == *required_material).unwrap();
            let mut produced_amount = 0;
            let mut cost = 0;
            while produced_amount < remaining_needed_amount {
                produced_amount += producer.output.amount;
                cost += producer.inputs.iter().fold(0, |acc, inp| acc + produce(indent + 2, &inp.material, inp.amount, producers, spare_units))
            }
            let spare_amount = produced_amount - remaining_needed_amount;
            if let Some(v) = spare_units.get(required_material) {
                spare_units.insert(required_material.clone(), v + spare_amount);
            } else {
                spare_units.insert(required_material.clone(), spare_amount);
            }
            cost
        }
    };
    cost
}

fn parse_producers(defs: &str) -> Vec<Producer> {
    let mut producers: Vec<Producer> = vec!();
    defs.trim().split('\n').for_each(
        |l| {
            let mut split_iter = l.split("=>");
            let inp = split_iter.next().unwrap();
            let res = split_iter.next().unwrap();
            let output = parse_material_amount(res);
            let mut inputs: Vec<MaterialAmount> = vec!();
            inp.split(',').for_each(
                |i| inputs.push(parse_material_amount(i.trim()))
            );
            producers.push(
                Producer {
                    inputs: inputs,
                    output: output
                }
            )
        }
    );
    producers
}

fn parse_material_amount(d: &str) -> MaterialAmount {
    let mut splitter = d.trim().split_whitespace();
    let amount: i64 = splitter.next().unwrap().parse().unwrap();
    let material: String = String::from(splitter.next().unwrap());

    MaterialAmount {
        amount: amount,
        material: material
    }
}

struct Producer {
    inputs: Vec<MaterialAmount>,
    output: MaterialAmount
}

struct MaterialAmount {
    amount: i64,
    material: String
}