const INPUT: &str = include_str!("../../data/day25");

const MOD: u32 = 20201227;

// transform(subject, key) = (subject ** key) mod 20201227
//
// public_key := transform(7, private_key)
// shared_secret := transform(peer_public_key, local_private_key)

fn transform(subject: u32, key: u32) -> u32 {
    let mut value = 1u64;
    let subject = subject as u64;
    for _ in 0..key {
        value = (value * subject) % (MOD as u64);
    }
    value as u32
}

fn find_key(subject: u32, transformed: u32) -> u32 {
    let mut value = 1u64;
    let mut key = 0;
    let subject = subject as u64;
    let transformed = transformed as u64;
    while value != transformed {
        value = (value * subject) % (MOD as u64);
        key += 1;
    }
    key
}

fn main() {
    let card_pub_key;
    let door_pub_key;
    {
        let mut lines = INPUT.lines();
        card_pub_key = lines.next().unwrap().parse::<u32>().unwrap();
        door_pub_key = lines.next().unwrap().parse::<u32>().unwrap();
        assert!(lines.next().is_none());
    }
    let card_priv_key = find_key(7, card_pub_key);
    println!("Card private key: {}", card_priv_key);
    let shared_secret = transform(door_pub_key, card_priv_key);
    println!("Shared secret: {}", shared_secret);
}