use std::mem::replace;

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

type Item = usize;

const MARK_MISSING: usize = !0;

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
struct OptionItem(Item);

impl OptionItem {
    pub const NONE: Self = Self(MARK_MISSING);

    fn item(self) -> Option<Item> {
        if self.0 == MARK_MISSING {
            None
        } else {
            Some(self.0)
        }
    }
}

impl From<Item> for OptionItem {
    fn from(i: Item) -> Self {
        assert_ne!(i, MARK_MISSING);
        Self(i)
    }
}

impl From<Option<Item>> for OptionItem {
    fn from(i: Option<Item>) -> Self {
        match i {
            None => Self(MARK_MISSING),
            Some(i) => Self::from(i),
        }
    }
}

#[derive(Clone, PartialEq, Eq, Debug)]
struct Cups {
    current: OptionItem,
    last: OptionItem,
    next_cup: Vec<OptionItem>,
}

impl Default for Cups {
    fn default() -> Self {
        Self {
            current: OptionItem::NONE,
            last: OptionItem::NONE,
            next_cup: Vec::new(),
        }
    }
}

impl Cups {
    fn last(&self) -> Option<Item> {
        self.last.item()
    }

    fn insert_after(&mut self, prev: Item, value: Item) {
        let next = replace(&mut self.next_cup[prev], value.into()).item().unwrap();
        if value >= self.next_cup.len() {
            self.next_cup.resize(value, OptionItem::NONE);
            self.next_cup.push(next.into());
            assert_eq!(self.next_cup[value], next.into());
        } else {
            assert_eq!(self.next_cup[value], OptionItem::NONE);
            self.next_cup[value] = next.into();
        }
        if self.last.item().unwrap() == prev {
            self.last = value.into();
        }
    }

    fn extend_after<I>(&mut self, mut after: Item, iter: I)
    where
        I: IntoIterator<Item=Item>,
    {
        for item in iter {
            self.insert_after(after, item);
            after = item;
        }
    }

    fn extend<I>(&mut self, iter: I)
    where
        I: IntoIterator<Item=Item>,
    {
        let mut iter = iter.into_iter();
        if let Some(first) = iter.next() {
            if let Some(prev) = self.last() {
                self.insert_after(prev, first);
            } else {
                assert!(self.next_cup.is_empty());
                self.next_cup.resize(first, OptionItem::NONE);
                self.next_cup.push(first.into());
                self.current = first.into();
                self.last = first.into();
            }
            self.extend_after(first, iter);
        }
    }

    fn iter_from(&self, start: Item) -> impl Iterator<Item=Item> + '_ {
        let mut current = start;
        let mut first = true;
        std::iter::from_fn(move || {
            if !first && current == start {
                return None;
            }
            first = false;
            let item = current;
            current = self.next_cup[item].item().unwrap();
            Some(item)
        })
    }

    fn iter(&self) -> impl Iterator<Item=Item> + '_ {
        self.iter_from(self.current.item().unwrap())
    }

    fn remove_after(&mut self, previous: Item) -> Item {
        let item = self.next_cup[previous].item().unwrap();
        let follow = self.next_cup[item].item().unwrap();
        self.next_cup[item] = OptionItem::NONE;
        self.next_cup[previous] = follow.into();
        if item == self.current.item().unwrap() {
            if item == previous {
                // last item
                self.current = OptionItem::NONE;
                self.last = OptionItem::NONE;
                self.next_cup.clear();
            } else {
                // if we removed the "current" item: move current pointer forward
                self.current = follow.into();
            }
        } else if item == self.last.item().unwrap() {
            // just removed the last item
            self.last = previous.into();
        }
        item
    }

    fn drain_after(&mut self, previous: Item, mut len: usize) -> impl Iterator<Item=Item> + '_ {
        std::iter::from_fn(move || {
            if len == 0 {
                return None;
            }
            len -= 1;
            Some(self.remove_after(previous))
        })
    }

    fn drain(&mut self, range: std::ops::Range<usize>) -> impl Iterator<Item=Item> + '_ {
        let len = range.end - range.start;
        let after = if len == 0 {
            0 // don't care
        } else if range.start > 0 {
            self.iter().skip(range.start - 1).next().unwrap()
        } else {
            self.last().unwrap()
        };
        self.drain_after(after, len)
    }

    fn parse(cups: &str) -> Self {
        let mut result = Cups::default();
        result.extend(cups.bytes().map(|c| (c - b'0') as Item));
        result
    }

    fn rotate_left(&mut self, items: usize) {
        let next = self.iter().skip(items).next().unwrap();
        self.current = next.into();
    }

    fn mix(&mut self) {
        let max_entry = self.next_cup.len() - 1;
        let pickup = self.drain(1..4).collect::<Vec<_>>();
        let mut insert_after = self.current.item().unwrap();
        loop {
            insert_after = match insert_after.checked_sub(1) {
                Some(n) => n,
                None => max_entry,
            };
            if self.next_cup[insert_after] != OptionItem::NONE {
                break;
            }
        }
        self.extend_after(insert_after, pickup);
        self.rotate_left(1);
    }

    fn rotate_to_one(&mut self) {
        assert_ne!(self.next_cup[1], OptionItem::NONE);
        self.current = 1.into();
    }
}

fn main() {
    let mut cups = Cups::parse(INPUT.trim());
    for _ in 0..100 {
        cups.mix();
    }
    cups.rotate_to_one();
    println!("Cups: {}", cups.iter().skip(1).map(|c| format!("{}", c)).collect::<Vec<_>>().join(""));

    let mut cups = Cups::parse(INPUT.trim());
    cups.extend(10..=1000000);
    for _ in 0..10000000 {
        cups.mix()
    }
    cups.rotate_to_one();
    println!("Cup product: {}", cups.drain(1..3).map(|c| c as u64).product::<u64>());
}