🌟 Advent of Code (AoC) 2020 🌟

use std::{collections::hash_map, ops::Not};
use std::{
    collections::HashSet,
    hash::{Hash, Hasher},
};
use std::{collections::VecDeque, io};

pub fn run<R>(mut input: R)
where
    R: io::BufRead,
{
    let mut data = vec![];
    let mut buf = String::new();
    loop {
        if input.read_line(&mut buf).unwrap() == 0 {
            break;
        }
        {
            let buf = buf.trim();
            if buf.starts_with("Player ") {
                data.push(VecDeque::new());
            } else if buf.is_empty().not() {
                if let Some(deq) = data.last_mut() {
                    deq.push_back(buf.parse::<u32>().unwrap())
                }
            }
        }
        buf.clear();
    }

    println!("Svar 1: {:?}", solve1(data.clone())); // Svar 1: (0, 32629)
    println!("Svar 2: {:?}", solve2(data.clone())); // Svar 2: (0, 32519)
}

fn solve1(mut data: Vec<VecDeque<u32>>) -> (usize, u32) {
    let vinnare = loop {
        // Samla ihop alla dragna kort
        let round = data
            .iter_mut()
            .enumerate()
            .filter_map(|(no, dec)| {
                if let Some(value) = dec.pop_front() {
                    return Some((no, value));
                }
                None
            })
            .collect::<Vec<_>>();

        // Tilldela högsta kortets ägare alla kort dragna
        if let Some((a, _)) = round.iter().max_by_key(|(_, v)| v) {
            let mut win_round = round.iter().map(|v| v.1).collect::<VecDeque<_>>();
            win_round.rotate_left(*a);
            data[*a].append(&mut win_round);
        }

        // Kontrollera om någon part har slut kort och returnera vinnarens kort.
        if data.iter().any(|v| v.is_empty()) {
            break data
                .iter()
                .enumerate()
                .max_by_key(|(_, v)| v.len())
                .unwrap();
        }
    };

    // Returnera vinnande spelare och summa
    (vinnare.0, summera(vinnare.1))
}

fn solve2(mut data: Vec<VecDeque<u32>>) -> (usize, u32) {
    let mut seen = HashSet::new();
    let vinnare = loop {
        if !seen.insert(hash(data.as_slice())) {
            break (0usize, &data[0]);
        }

        // Samla ihop alla dragna kort
        let round = data
            .iter_mut()
            .enumerate()
            .filter_map(|(no, dec)| {
                if let Some(value) = dec.pop_front() {
                    return Some((no, value));
                }
                None
            })
            .collect::<Vec<_>>();

        // Tilldela högsta kortets ägare eller subgame alla kort dragna
        let index = if round
            .iter()
            .all(|(index, value)| *value as usize <= data[*index].len())
        {
            // Kör subgame endast på urval av korten
            let subgame_data = data
                .iter()
                .enumerate()
                .map(|(a, b)| {
                    b.iter()
                        .take(round[a].1 as usize)
                        .cloned()
                        .collect::<VecDeque<_>>()
                })
                .collect::<Vec<_>>();

            solve2(subgame_data).0
        } else {
            round.iter().max_by_key(|(_, v)| v).unwrap().0
        };

        let mut win_round = round.iter().map(|v| v.1).collect::<VecDeque<_>>();
        win_round.rotate_left(index);
        data[index].append(&mut win_round);

        // Kontrollera om någon part har slut kort och returnera vinnarens kort.
        if data.iter().any(|v| v.is_empty()) {
            break data
                .iter()
                .enumerate()
                .max_by_key(|(_, v)| v.len())
                .unwrap();
        }
    };

    // Returnera vinnande spelare och summa
    (vinnare.0, summera(vinnare.1))
}

fn summera(data: &VecDeque<u32>) -> u32 {
    data.iter()
        .rev()
        .enumerate()
        .fold(0, |acc, (no, val)| acc + (no as u32 + 1) * val)
}

fn hash(vec: &[VecDeque<u32>]) -> u64 {
    let mut hasher = hash_map::DefaultHasher::new();
    for v in vec {
        v.hash(&mut hasher)
    }
    hasher.finish()
}

use std::io;

const INPUT: &[u8] = b"872495136";

pub fn run<R>(_input: R)
where
    R: io::BufRead,
{
    let data = INPUT.iter().map(|&u| (u - b'0') as u64).collect::<Vec<_>>();
    println!("Svar 1: {}", solve1(data.clone()).unwrap()); // 27865934
    println!("Svar 2: {}", solve2(data.clone()).unwrap()); // 170836011000
}

fn solve1(mut data: Vec<u64>) -> Option<String> {
    crab_cups(data.as_mut_slice(), 100)?;
    let index = hamta_index(&data, 1)?;
    data.rotate_left(index);
    Some(
        data.iter()
            .skip(1)
            .map(|v| v.to_string())
            .collect::<String>(),
    )
}

// Extremt trött att få fram svaret. :)
fn solve2(mut data: Vec<u64>) -> Option<u64> {
    data.extend((10..=1_000_000).into_iter());
    crab_cups(data.as_mut_slice(), 10_000_000)?;
    let index = hamta_index(&data, 1)?;
    Some(data[(index + 1) % data.len()] * data[(index + 2) % data.len()])
}

fn crab_cups(data: &mut [u64], length: u64) -> Option<()> {
    let &min = data.iter().min()?;
    let &max = data.iter().max()?;

    for i in 0..length {
        data.rotate_left((i != 0) as usize);
        let mut dp = data[0] - 1;
        let index = loop {
            match dp {
                x if data[1..4].contains(&x) => dp -= 1,
                x if x < min => dp = max,
                x => break hamta_index(data, x)?,
            }
        };
        data[1..=index].rotate_left(3);
    }
    Some(())
}

fn hamta_index(data: &[u64], search: u64) -> Option<usize> {
    data.iter().position(|&b| b == search)
}

use std::io;
use std::{collections::HashSet, ops::Not};

const NARLIGGANDE: &[(i32, i32)] = &[(1, 0), (1, -1), (0, -1), (-1, 0), (-1, 1), (0, 1)];

pub fn run<R>(mut input: R)
where
    R: io::BufRead,
{
    let mut buffer = String::new();
    let mut svarta_brickor = HashSet::new();
    let mut nya_svarta_brickor = HashSet::new();

    loop {
        if input.read_line(&mut buffer).unwrap() == 0 {
            break;
        }
        let mut rad = buffer.trim();
        let mut koordinater = (0, 0);
        while rad.is_empty().not() {
            (0..3)
                .into_iter()
                .find_map(|len| match &rad[..len] {
                    "e" => Some((1, (1, 0))),
                    "se" => Some((2, (1, -1))),
                    "sw" => Some((2, (0, -1))),
                    "w" => Some((1, (-1, 0))),
                    "nw" => Some((2, (-1, 1))),
                    "ne" => Some((2, (0, 1))),
                    _ => None,
                })
                .map(|(size, pos)| {
                    koordinater = (koordinater.0 + pos.0, koordinater.1 + pos.1);
                    rad = &rad[size..];
                });
        }

        if !svarta_brickor.insert(koordinater) {
            svarta_brickor.remove(&koordinater);
        }
        buffer.clear();
    }
    println!("Svar 1: {:?}", svarta_brickor.len()); // 479

    for _ in 0..100 {
        svarta_brickor
            .iter()
            .flat_map(|&bricka| {
                narliggande(bricka)
                    .map(|b| (b, false))
                    .chain(std::iter::once((bricka, true)))
            })
            .for_each(|(bricka, svart)| {
                let antal_svarta = narliggande(bricka)
                    .filter(|pos| svarta_brickor.contains(pos))
                    .count();
                if svart && (1 == antal_svarta || antal_svarta == 2)
                    || svart.not() && 2 == antal_svarta
                {
                    nya_svarta_brickor.insert(bricka);
                }
            });
        svarta_brickor = std::mem::take(&mut nya_svarta_brickor);
    }
    println!("Svar 2: {:?}", svarta_brickor.len()); // 4135
}

fn narliggande(bricka: (i32, i32)) -> impl Iterator<Item = (i32, i32)> {
    NARLIGGANDE
        .iter()
        .map(move |b| (b.0 + bricka.0, b.1 + bricka.1))
}

use std::io;

pub fn run<R>(input: R)
where
    R: io::BufRead,
{
    let mut iter = input
        .lines()
        .filter_map(|r| r.ok())
        .filter_map(|s| s.parse::<u64>().ok());

    let pubk_card = iter.next().unwrap(); // Input: 8458505
    let pubk_room = iter.next().unwrap(); // Input: 16050997

    let find = |subject: u64, result: u64| -> u64 {
        (0..)
            .into_iter()
            .skip_while(|v| transform(subject, *v) != result)
            .next()
            .unwrap()
    };
    println!("Svar: {}", transform(pubk_room, find(7, pubk_card))); // Svar: 448851
}

fn transform(subject: u64, loop_size: u64) -> u64 {
    // (0..loop_size).fold(1, |acc, _| (acc * subject) % 20201227)
    mod_pow(subject, loop_size, 20201227)
}

fn mod_pow(base: u64, exp: u64, modulus: u64) -> u64 {
    if exp == 0 {
        1
    } else if exp % 2 == 0 {
        mod_pow(base.pow(2) % modulus, exp >> 1, modulus)
    } else {
        base * mod_pow(base, exp - 1, modulus) % modulus
    }
}