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 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 current = start;
23    let mut cups = vec![0; 10];
24
25    // Link the 9 input cups, wrappping around to the start.
26    for &next in &input[1..] {
27        cups[current] = next;
28        current = next as usize;
29    }
30    cups[current] = start as u32;
31
32    play(&mut cups, start, 100);
33
34    (0..8).fold((0, 1), |(acc, i), _| (10 * acc + cups[i], cups[i] as usize)).0
35}
36
37pub fn part2(input: &[u32]) -> usize {
38    let start = input[0] as usize;
39    let mut current = start;
40    let mut cups: Vec<_> = (1..1_000_002).collect();
41
42    // Link the 9 input cups, continuing to the extra elements.
43    for &next in &input[1..] {
44        cups[current] = next;
45        current = next as usize;
46    }
47    cups[current] = 10;
48
49    // Wrap around to the start
50    cups[1_000_000] = start as u32;
51
52    play(&mut cups, start, 10_000_000);
53
54    let first = cups[1] as usize;
55    let second = cups[first] as usize;
56    first * second
57}
58
59fn play(cups: &mut [u32], mut current: usize, rounds: usize) {
60    for _ in 0..rounds {
61        // Pickup three cups (a, b, c)
62        let a = cups[current] as usize;
63        let b = cups[a] as usize;
64        let c = cups[b] as usize;
65
66        // Calculate destination
67        let mut dest = if current > 1 { current - 1 } else { cups.len() - 1 };
68        while dest == a || dest == b || dest == c {
69            dest = if dest > 1 { dest - 1 } else { cups.len() - 1 };
70        }
71
72        // Link current cup to the fourth cup after the three cups that have just been picked up.
73        cups[current] = cups[c];
74        current = cups[c] as usize;
75
76        // Insert the three picked up cups into their new location
77        cups[c] = cups[dest];
78        cups[dest] = a as u32;
79    }
80}
aoc/year2020/day23.rs

aoc/year2020/
day23.rs
