1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101

use std::cell::RefCell;
use std::path::Path;
use std::fmt::Display;
use std::sync::atomic::{AtomicI32, Ordering};

pub use rayon;
pub use itertools;

pub mod input;
pub mod grid;

pub mod prelude {
    pub use std::collections::VecDeque;
    pub use std::collections::hash_map::Entry;
    pub use std::iter::once;

    pub use hashbrown::{HashMap, HashSet};
    pub use itertools::{Itertools, iproduct};
    pub use regex::{Regex, Captures};
    pub use odds::slice::rotate_left;
    pub use arrayvec::ArrayVec;

    pub fn rotate_right<T>(t: &mut [T], n: usize) {
        let m = t.len() - n;
        odds::slice::rotate_left(t, m);
    }

    pub struct Uids<T> {
        map: hashbrown::HashMap<T, usize>
    }

    impl<T: std::hash::Hash + Eq> Uids<T> {
        pub fn new() -> Uids<T> {
            Uids { map: Default::default() }
        }

        pub fn get_id(&mut self, k: T) -> usize {
            let n = self.map.len();
            *self.map.entry(k).or_insert(n)
        }
    }

    impl<T, Q> std::ops::Index<&Q> for Uids<T>
    where T: std::hash::Hash + Eq + std::borrow::Borrow<Q>, Q: std::hash::Hash + Eq + ?Sized
    {
        type Output = usize;
        fn index(&self, q: &Q) -> &usize {
            &self.map[&q]
        }
    }

    /// Perform a binary search
    pub fn binary_search<I, F>(mut low: I, mut high: I, mut test: F) -> I
    where I: num::Integer + Copy + From<u8>, F: FnMut(I) -> bool
    {
        loop {
            if low + I::one() == high {
                return high;
            }
            let guess = (low + high) / I::from(2);
            if test(guess) {
                high = guess;
            } else {
                low = guess;
            }
        }
    }
}

thread_local! {
    static INPUT: RefCell<Option<&'static str>> = Default::default();
}

static OUT_CONTROL: AtomicI32 = AtomicI32::new(1);

pub fn bench_mode(path: impl AsRef<Path>) {
    OUT_CONTROL.store(0, Ordering::SeqCst);
    INPUT.with(|k| *k.borrow_mut() = Some(
        Box::leak(
            std::fs::read_to_string(path.as_ref()).unwrap_or_else(
                |e| panic!("could not read input file: {}", e)).into()
        )
    ));
}

pub fn print(part: &str, value: impl Display) {
    if OUT_CONTROL.load(Ordering::SeqCst) > 0 {
        let n = OUT_CONTROL.fetch_add(1, Ordering::SeqCst);
        println!("{}. {}: {}", n, part, value);
    }
}

pub fn verify(part: &str, value: impl Display, check: impl Display) {
    let value_str = format!("{}", value);
    let check_str = format!("{}", check);
    assert_eq!(value_str, check_str);
    if OUT_CONTROL.load(Ordering::SeqCst) > 0 {
        let n = OUT_CONTROL.fetch_add(1, Ordering::SeqCst);
        println!("{}. {}: {}", n, part, value_str);
    }
}