Advent of code 2020 day 23 part 2

adventofcode2020_day23_part_2.rs

/*
    solution to the second part of https://adventofcode.com/2020/day/23

    it executes in less than a minute in release mode, but it ain't pretty

    main points:
    - double linked list to easily insert/split/remove
    - the nodes are not individual values, but ranges instead
    - because looking up a value in a linked list takes so long, there is a hashmap pointing to the
      slices for each value. everytime a slice is added or changed, all the values of the slice
      are reindexed
    - at the beginning of the game there are huge slices ( one slice contains 10-1000000 values ),
      so reindexing is very expensive. thus before 250000 iterations, there is just a stack of slice
      to which added or modified slices are pushed, when looking up a value the stack is looked
      up in reverse direction until one matches - we don't bother cleaning up
 */

use std::fmt::{Display, Formatter};
use std::fmt;
use itertools::Itertools;
use std::collections::HashMap;
use std::rc::Rc;
use std::cell::RefCell;

#[derive(Clone)]
struct Slice {
    start: usize,
    end: usize,
    next: Option<Rc<RefCell<Slice>>>,
    prev: Option<Rc<RefCell<Slice>>>,
}

impl PartialEq for Slice {
    fn eq(&self, other: &Self) -> bool {
        self.start == other.start && self.end == other.end
    }
}

impl Eq for Slice {}


impl Slice {
    fn new(start: usize, end: usize) -> Rc<RefCell<Self>> {
        let s = Slice {
            start,
            end,
            next: None,
            prev: None,
        };
        let s = Rc::new(RefCell::new(s));
        let to_link = s.clone();

        s.as_ref().borrow_mut().next = Some(to_link.clone());
        s.as_ref().borrow_mut().prev = Some(to_link.clone());

        s
    }

    fn contains_value(&self, value: usize) -> bool {
        value >= self.start && value <= self.end
    }

    fn relative_position(&self, value: usize) -> Option<usize> {
        if value >= self.start && value <= self.end {
            Some((value - self.start) as usize)
        } else {
            None
        }
    }

    fn len(&self) -> usize {
        (self.end - self.start + 1) as usize
    }

    fn highlight_string(&self, position: usize) -> String {
        (self.start..=self.end).enumerate().map(|(p, x)| {
            if p == position {
                format!("({})", x)
            } else {
                x.to_string()
            }
        }).join(" ").to_string()
    }
}

#[derive(Clone)]
struct Cursor {
    slice: Rc<RefCell<Slice>>,
    position: usize,
}

impl PartialEq for Cursor {
    fn eq(&self, other: &Self) -> bool {
        let self_ref = self.slice.as_ref().borrow();
        let other_ref = other.slice.as_ref().borrow();

        self_ref.end == other_ref.end && self_ref.start == other_ref.start && self.position == other.position
    }
}

impl Eq for Cursor {}

impl Cursor {
    fn next(&mut self) {
        let slice_ref = self.slice.as_ref().borrow();
        self.position = self.position + 1;
        if self.position == slice_ref.len() {
            let next = slice_ref.next.clone().unwrap();
            drop(slice_ref);
            self.position = 0;
            self.slice = next;
        }
    }

    fn value(&self) -> usize {
        self.slice.as_ref().borrow().start + self.position
    }

    fn take_right(&mut self, game: &mut Game) -> Rc<RefCell<Slice>> {
        let mut self_ref = self.slice.as_ref().borrow_mut();

        if self.position + 1 == self_ref.len() {
            let next_rc = self_ref.next.clone().unwrap();
            let mut next_ref = next_rc.as_ref().borrow_mut();

            let result = Slice::new(next_ref.start, next_ref.start);

            if next_ref.len() == 1 {
                let next_next_rc = next_ref.next.clone().unwrap();
                let next_next_ref = next_next_rc.as_ref().borrow_mut();

                if next_next_ref.start == self_ref.end + 1 {
                    let next_next_next_rc = next_next_ref.next.clone().unwrap();
                    self_ref.end = next_next_ref.end;
                    drop(self_ref);
                    game.link(self.slice.clone(), next_next_next_rc);
                } else {
                    drop(next_next_ref);
                    drop(self_ref);
                    game.link(self.slice.clone(), next_next_rc.clone())
                }
            } else {
                next_ref.start = next_ref.start + 1;
                drop(next_ref);
                game.reindex(&next_rc);
            }
            result
        } else {
            let value = self_ref.start + self.position + 1;
            let result = Slice::new(value, value);

            if self.position + 1 == self_ref.len() - 1 {
                self_ref.end -= 1;
            } else {
                let end = self_ref.end;
                self_ref.end = value - 1;

                let new_slice = Slice::new(value + 1, end);

                let right = self_ref.next.clone().unwrap();
                drop(self_ref);

                game.link(new_slice.clone(), right);
                game.link(self.slice.clone(), new_slice);
            }
            result
        }
    }
}

impl Display for Slice {
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        (self.start..=self.end).map(|x| x.to_string()).join(" ").fmt(f)
    }
}

impl Display for Game {
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        self.string_highlight().fmt(f)
    }
}

enum IndexMode {
    Vec,
    Hash,
}

struct Game {
    highlight: Cursor,
    shortcuts_vec: Vec<Rc<RefCell<Slice>>>,
    shortcuts_map: HashMap<usize, (Rc<RefCell<Slice>>, usize)>,
    index_mode: IndexMode,
}

impl Game {
    fn push_right(&mut self, left_rc: Rc<RefCell<Slice>>, position: usize, right_rc: Rc<RefCell<Slice>>) -> Rc<RefCell<Slice>> {
        let mut left_ref = left_rc.as_ref().borrow_mut();
        let right_ref = right_rc.as_ref().borrow_mut();
        let next_rc = left_ref.next.clone().unwrap();

        if position == left_ref.len() - 1 {
            if left_ref.end + 1 == right_ref.start {
                left_ref.end = right_ref.end;
                drop(left_ref);
                self.link(left_rc.clone(), next_rc);
                left_rc.clone()
            } else {
                drop(right_ref);
                drop(left_ref);
                self.link(right_rc.clone(), next_rc);
                self.link(left_rc.clone(), right_rc.clone());
                right_rc.clone()
            }
        } else {
            let split_slice = Slice::new(left_ref.start + position + 1, left_ref.end);
            left_ref.end = left_ref.start + position;
            drop(left_ref);
            drop(right_ref);
            self.link(left_rc.clone(), right_rc.clone());
            self.link(right_rc.clone(), split_slice.clone());
            self.link(split_slice.clone(), next_rc.clone());
            right_rc.clone()
        }
    }

    fn reindex(&mut self, slice: &Rc<RefCell<Slice>>) {
        match self.index_mode {
            IndexMode::Vec => self.shortcuts_vec.push(slice.clone()),
            IndexMode::Hash => {
                let slice_ref = slice.as_ref().borrow();

                for (position, value) in (slice_ref.start..=slice_ref.end).enumerate() {
                    self.shortcuts_map.insert(value, (slice.clone(), position));
                }
            }
        };
    }

    fn link(&mut self, left: Rc<RefCell<Slice>>, right: Rc<RefCell<Slice>>) {
        {
            let mut left_ref = left.as_ref().borrow_mut();
            left_ref.next = Some(right.clone());
            drop(left_ref);
            self.reindex(&left);
        }
        {
            let mut right_ref = right.as_ref().borrow_mut();
            right_ref.prev = Some(left.clone());

            drop(right_ref);
            self.reindex(&right);
        }
    }

    fn next_highlight(&mut self) {
        self.highlight.next()
    }

    fn string_highlight(&self) -> String {
        let mut result = Vec::<String>::new();

        result.push(self.highlight.slice.as_ref().borrow().highlight_string(self.highlight.position));
        let mut self_ref = self.highlight.slice.clone().as_ref().borrow().next.clone().unwrap();

        while self_ref.clone() != self.highlight.slice {
            result.push(self_ref.as_ref().borrow().to_string());
            let next = self_ref.as_ref().borrow().next.clone().unwrap();
            self_ref = next;
        }
        result.join("; ")
    }

    fn cursor_for_value(&self, value: usize) -> Cursor {
        match self.index_mode {
            IndexMode::Vec => {
                for slice in self.shortcuts_vec.iter().rev() {
                    let slice_ref = slice.as_ref().borrow();
                    if slice_ref.contains_value(value) {
                        let pos = slice_ref.relative_position(value).unwrap();
                        drop(slice_ref);
                        return Cursor {
                            slice: slice.clone(),
                            position: pos,
                        };
                    }
                }
            }
            IndexMode::Hash => {
                let (slice, position) = self.shortcuts_map.get(&value).unwrap();
                return Cursor {
                    slice: slice.clone(),
                    position: *position,
                };
            }
        }

        panic!("value not found");
    }

    fn switch_indexmode(&mut self) {
        self.index_mode = IndexMode::Hash;

        let mut self_ref = self.highlight.slice.clone().as_ref().borrow().next.clone().unwrap();

        while self_ref != self.highlight.slice {
            self.reindex(&self_ref);
            let next = self_ref.as_ref().borrow().next.clone().unwrap();
            self_ref = next;
        }
    }

    fn new(slice: Rc<RefCell<Slice>>) -> Self {
        Game {
            highlight: Cursor { slice, position: 0 },
            shortcuts_vec: Vec::new(),
            shortcuts_map: HashMap::new(),
            index_mode: IndexMode::Vec,
        }
    }
}

fn main() {
    let upto = 1000000;
    let iterations: usize = 10000000;

    let input = "925176834";

    let mut iter = input.chars().map(|x| x.to_string().parse::<usize>()).flatten();
    let value = iter.next().unwrap();
    let mut game = Game::new(Slice::new(value, value));
    let mut max = value;

    let mut cursor = game.highlight.clone();

    for number in iter {
        game.push_right(cursor.slice.clone(), cursor.position, Slice::new(number, number));
        cursor.next();
        max = max.max(number);
    }

    if upto >= max + 1 {
        game.push_right(cursor.slice.clone(), cursor.position, Slice::new(max + 1, upto));
    }

    let mut cursor = game.highlight.clone();
    for _ in 1..=upto {
        game.reindex(&cursor.slice.clone());
        cursor.next();
    }

    let mut picked_values = Vec::new();

    for g in 0..iterations {
        {
            if g % 10000 == 0 {
                println!("Game {}", g + 1);
            }
            if g == 250000 {
                println!("Hash mode!");
                game.switch_indexmode();
            }
        }

        picked_values.clear();
        {
            // we clone the cursor and use it to avoid ownership problems, as we pass game again
            let mut cursor = game.highlight.clone();
            picked_values.push(cursor.take_right(&mut game).as_ref().borrow().start);
            picked_values.push(cursor.take_right(&mut game).as_ref().borrow().start);
            picked_values.push(cursor.take_right(&mut game).as_ref().borrow().start);
            game.highlight = cursor;
        }

        let mut destination_value = game.highlight.value();

        loop {
            destination_value -= 1;

            if destination_value == 0 {
                destination_value = upto;
            }
            if !picked_values.contains(&destination_value) {
                break;
            }
        }

        let mut destination_cursor = game.cursor_for_value(destination_value);

        for value in &picked_values {
            game.push_right(destination_cursor.slice.clone(), destination_cursor.position, Slice::new(*value, *value));
            destination_cursor.next();
        }

        if game.highlight.position >= game.highlight.slice.as_ref().borrow().len() {
            // in case highlighted slice was split off, find again
            let value = game.highlight.value();
            game.highlight.position = 0;
            game.highlight = game.cursor_for_value(value);
        }

        game.next_highlight();
    }

    let mut cursor = game.cursor_for_value(1);
    cursor.next();
    let value1 = cursor.value();
    cursor.next();
    let value2 = cursor.value();

    println!("{} {} {}", value1, value2, value1 * value2)
}