You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

217 lines
6.0 KiB

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>());
}