use std::collections::HashMap;

#[path = "../lib.rs"]
mod lib;

fn str2int(s: &str) -> u32 {
    return s
        .bytes()
        .enumerate()
        .map(|(i, b)| (b as u32) << (i * 8))
        .sum();
}

fn parse() -> (Vec<bool>, HashMap<u32, (u32, u32)>) {
    let mut state = 0;
    let mut dirs = vec![];
    let mut nodes = HashMap::new();

    for line in lib::iter_input() {
        match state {
            0 => {
                dirs = line.chars().map(|c| c == 'R').collect();
                state = 1;
            }
            1 => {
                state = 2;
            }
            2 => {
                let name = str2int(&line[0..3]);
                let left = str2int(&line[7..10]);
                let right = str2int(&line[12..15]);
                nodes.insert(name, (left, right));
            }
            _ => unreachable!(),
        }
    }

    return (dirs, nodes);
}

fn lcm(offset1: usize, period1: usize, offset2: usize, period2: usize) -> Option<(usize, usize)> {
    // https://neddit.ce9e.org/r/learnprogramming/comments/7bcw31/least_common_multiple_with_an_offset/dphce2j/
    //
    // The actual input data always has offset = period.
    // But I have spent far too much time on this to throw it away.

    let mut steps = vec![period1.min(period2), period1.max(period2)];
    while steps[0] != 0 {
        steps.insert(0, steps[1] % steps[0]);
    }

    let period = period1 * period2 / steps[1];

    let gcd = steps[1] as i64;
    let d_offset = offset2 as i64 - offset1 as i64;
    let p1 = period1 as i64;
    let p2 = period2 as i64;

    if d_offset % gcd == 0 {
        // a * steps[i + 1] - b * steps[i] = d_offset
        let mut a = d_offset / gcd;
        let mut b = 0;

        for i in 0..(steps.len() - 2) {
            // steps[i] = steps[i + 2] - x * steps[i + 1]
            let x = (steps[i + 2] / steps[i + 1]) as i64;
            (a, b) = (-b, -(a + b * x));
        }

        if period1 < period2 {
            (a, b) = (-b, -a);
        }

        let af = lib::div_floor(a, p2 / gcd);
        let bf = lib::div_floor(b, p1 / gcd);
        a -= af.min(bf) * (p2 / gcd);

        let offset = offset1 + (a as usize) * period1;

        return Some((offset, period));
    } else {
        return None;
    }
}

fn walk_one<F: Fn(u32) -> bool>(
    start: u32,
    is_end: F,
    dirs: &Vec<bool>,
    nodes: &HashMap<u32, (u32, u32)>,
) -> (Vec<usize>, usize) {
    let mut pos = start;
    let mut steps = 0;
    let mut offsets = vec![];
    let mut first = (0, 0);
    loop {
        let rel = steps % dirs.len();

        if is_end(pos) {
            if first == (0, 0) {
                first = (pos, rel);
            } else if first == (pos, rel) {
                let period = steps - offsets[0];
                return (offsets, period);
            }
            offsets.push(steps);
        }

        let (left, right) = nodes.get(&pos).unwrap();
        pos = if dirs[rel] { *right } else { *left };
        steps += 1;
    }
}

fn walk<F: Fn(u32) -> bool>(
    starts: &Vec<u32>,
    is_end: F,
    dirs: &Vec<bool>,
    nodes: &HashMap<u32, (u32, u32)>,
) -> usize {
    let mut first = true;
    let mut candidates = vec![];

    for start in starts.iter() {
        let (offsets, period) = walk_one(*start, &is_end, dirs, nodes);

        if first {
            for offset in offsets.iter() {
                candidates.push((*offset, period));
            }
            first = false;
        } else {
            let mut new = vec![];
            for offset in offsets.iter() {
                for (offset2, period2) in candidates.iter() {
                    match lcm(*offset, period, *offset2, *period2) {
                        Some(x) => {
                            new.push(x);
                        }
                        None => {}
                    }
                }
            }

            candidates = new;
        }
    }

    return candidates
        .iter()
        .map(|(offset, _period)| *offset)
        .min()
        .unwrap();
}

fn main() {
    let (dirs, nodes) = parse();

    let starts1 = vec![str2int("AAA")];
    let is_end1 = |pos| pos == str2int("ZZZ");
    let steps1 = walk(&starts1, is_end1, &dirs, &nodes);
    println!("part1: {}", steps1);

    let starts2 = nodes
        .keys()
        .map(|x| *x)
        .filter(|&pos| (pos >> 16) as u8 == b'A')
        .collect();
    let is_end2 = |pos| (pos >> 16) as u8 == b'Z';
    let steps2 = walk(&starts2, is_end2, &dirs, &nodes);
    println!("part2: {}", steps2);
}