aoc/year2020/
day23.rs

1//! # Crab Cups
2//!
3//! The cups form a [singly linked list](https://en.wikipedia.org/wiki/Linked_list).
4//!
5//! For performance instead of using pointers, we store the cups in a `vec` where an element
6//! at index `i` stores the index of the next cup. For example `cup[1]` points to the first cup
7//! after cup one and `cup[cup[1]]` points to the second cup after cup one.
8//!
9//! Notes:
10//! * One million is approximately 2²⁰ so the closest integer size that fits is `u32`.
11//!   Using `u32` instead of `usize` increases speed due to better cache locality.
12//! * Cups use one-based indexing so the vec is one longer than the number of cups and the zeroth
13//!   index is unused.
14use crate::util::parse::*;
15
16pub fn parse(input: &str) -> Vec<u32> {
17    input.trim().bytes().map(|b| b.to_decimal() as u32).collect()
18}
19
20pub fn part1(input: &[u32]) -> u32 {
21    let start = input[0] as usize;
22    let mut cups = vec![0; 10];
23
24    // Link the 9 input cups, wrapping around to the start.
25    for w in input.windows(2) {
26        cups[w[0] as usize] = w[1];
27    }
28    cups[*input.last().unwrap() as usize] = start as u32;
29
30    play(&mut cups, start, 100);
31
32    (0..8).fold((0, 1), |(acc, i), _| (10 * acc + cups[i], cups[i] as usize)).0
33}
34
35pub fn part2(input: &[u32]) -> usize {
36    let start = input[0] as usize;
37    let mut cups: Vec<_> = (1..1_000_002).collect();
38
39    // Link the 9 input cups, continuing to the extra elements.
40    for w in input.windows(2) {
41        cups[w[0] as usize] = w[1];
42    }
43    cups[*input.last().unwrap() as usize] = 10;
44
45    // Wrap around to the start.
46    cups[1_000_000] = start as u32;
47
48    play(&mut cups, start, 10_000_000);
49
50    let first = cups[1] as usize;
51    let second = cups[first] as usize;
52    first * second
53}
54
55fn play(cups: &mut [u32], mut current: usize, rounds: usize) {
56    let end = cups.len() - 1;
57    let wrap = |n| if n > 1 { n - 1 } else { end };
58
59    for _ in 0..rounds {
60        // Pick up three cups (a, b, c).
61        let a = cups[current] as usize;
62        let b = cups[a] as usize;
63        let c = cups[b] as usize;
64
65        // Calculate destination.
66        let mut dest = wrap(current);
67        while dest == a || dest == b || dest == c {
68            dest = wrap(dest);
69        }
70
71        // Link current cup to the fourth cup after the three cups that have just been picked up.
72        cups[current] = cups[c];
73        current = cups[c] as usize;
74
75        // Insert the three picked up cups into their new location.
76        cups[c] = cups[dest];
77        cups[dest] = a as u32;
78    }
79}
aoc/year2020/day23.rs

aoc/year2020/
day23.rs
