DEV Community

Discussion on: Advent of Code 2020 Solution Megathread - Day 23: Crab Cups

Collapse
 
neilgall profile image
Neil Gall

This was an amazing problem. A naive approach gives absolutely terrible performance and memory characteristics in any language, and the best approach is amazingly fast. I landed somewhere in the middle.

I started in Rust of course, with a naive approach of building new vectors for each move:

use std::iter::once;

// -- model

type Cup = u32;

#[derive(Debug)]
struct Cups {
    cups: Vec<Cup>,
    offset: usize
}

#[derive(Debug)]
struct Move {
    removed: Vec<Cup>,
    destination: Cup
}

fn prev(cup: Cup) -> Cup {
    if cup == 1 { 9 } else { cup - 1 }
}

impl Cups {
    fn new(input: &str, current_cup: Cup) -> Self {
        let cups: Vec<Cup> = input.chars().map(|c| (c as Cup) - 48).collect();
        let offset = cups.iter().position(|c| *c == current_cup).unwrap();
        Cups {
            cups,
            offset
        }
    }

    fn current_cup(&self) -> Cup {
        self.cups[self.offset]
    }

    fn index_of_cup(&self, cup: Cup) -> usize {
        self.cups.iter().position(|c| *c == cup).unwrap()
    }

    fn iter(&self) -> impl Iterator<Item = Cup> + '_ {
        self.cups.iter().cycle().skip(self.offset).copied()
    }

    fn labels(&self) -> Vec<Cup> {
        let start = (self.index_of_cup(1) + 1) % 9;
        self.cups.iter().cycle().skip(start).take(8).copied().collect()
    }

    fn labels_as_str(&self) -> String {
        self.labels().iter().map(|n| n.to_string()).collect::<Vec<String>>().join("")
    }

    fn create_move(&self) -> Move {
        let removed: Vec<Cup> = self.iter().skip(1).take(3).collect();
        let mut destination = prev(self.current_cup());
        while removed.contains(&destination) {
            destination = prev(destination);
        }
        Move {
            removed,
            destination
        }
    }

    fn apply(&mut self, m: Move) {
        let dest_index = self.index_of_cup(m.destination);


        let remaining_cups = self.cups.iter()
            .cycle()
            .skip(dest_index+1)
            .filter(|c| !m.removed.contains(c))
            .take(5)
            .copied();

        let new_cups: Vec<Cup> = once(m.destination)
            .chain(m.removed.iter().copied())
            .chain(remaining_cups)
            .collect();

        self.cups = new_cups;

        let diff = (dest_index + 9 - self.offset) % 9;

        let new_offset = match diff {
            4 => 0,
            5 => 8,
            6 => 7,
            7 => 6,
            8 => 5,
            _ => panic!(format!("unexpected diff {}", diff))
        };

        println!("offset={} dest={} diff={} cups={:?} new_offset={}", self.offset, dest_index, diff, self.cups, new_offset);
        self.offset = new_offset;
    }

    fn apply_n_moves(&mut self, count: usize) {
        for _ in 0..count {
            self.apply(self.create_move());
        }
    }
}

// -- problems

fn part1(input: &str, start_cup: Cup) -> String {
    let mut cups = Cups::new(input, start_cup);
    cups.apply_n_moves(100);
    cups.labels_as_str()
}

fn main() {
    let input = "523764819";
    println!("part 1 {}", part1(input, 5));
}
Enter fullscreen mode Exit fullscreen mode

My estimate is this was going to take 20-24h to run part 2 however. So I switched to linked lists. In Rust's strict ownership model this is pretty tricky and an exercise for another day so I switched to C:

#include <assert.h>
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef unsigned long cup_id;

struct cup {
    cup_id id;
    struct cup *next;
};

struct cups {
    struct cup *current;
    struct cup *by_id;
    size_t length;
};

void print_cups(const struct cups *cups) {
    const struct cup *cup = &cups->by_id[1];
    do {
        if (cup == cups->current)
            printf("(%lu) ", cup->id);
        else 
            printf("%lu ", cup->id);
        cup = cup->next;
    } while (cup != &cups->by_id[1]);
    printf("\n");
}

const struct cup *first_after_1(const struct cups *cups) {
    return cups->by_id[1].next;
}

cup_id prev(cup_id id, size_t length) {
    return id == 1 ? length : id - 1;
}

void apply_move(struct cups *cups) {
    struct cup *curr = cups->current;
    struct cup *next1 = curr->next;
    struct cup *next2 = next1->next;
    struct cup *next3 = next2->next;
    struct cup *next4 = next3->next;

    cup_id dest_id = prev(cups->current->id, cups->length);
    struct cup *dest;
    do {
        dest = &cups->by_id[dest_id];
        dest_id = prev(dest_id, cups->length);
    }
    while (dest == next1 || dest == next2 || dest == next3);

    struct cup *dest_next1 = dest->next;
    struct cup *dest_next2 = dest_next1->next;
    struct cup *dest_next3 = dest_next2->next;

    // remove next1..next3 from ring
    curr->next = next4;

    // reinsert after dest
    dest->next = next1;
    next3->next = dest_next1;

    cups->current = cups->current->next;
}

void apply_n_moves(struct cups *cups, size_t count) {
    for (size_t i = 0; i < count; ++i) {
        apply_move(cups);
    }
}

struct cups *make_cups(const char *init, size_t length, cup_id current) {
    struct cups *cups = (struct cups *)malloc(sizeof(struct cups));
    cups->current = NULL;
    cups->length = length;
    cups->by_id = (struct cup *)calloc(length + 1, sizeof(struct cup));

    struct cup *first = NULL;
    struct cup **next_p = &first;
    size_t count = 0;

    while (*init) {
        cup_id id = (*init++) - '0';
        struct cup *cup = &cups->by_id[id];
        cup->id = id;
        *next_p = cup;
        next_p = &cup->next;
        count++;
    }

    while (++count <= length) {
        struct cup *cup = &cups->by_id[count];
        cup->id = count;
        *next_p = cup;
        next_p = &cup->next;
    }

    *next_p = first;
    cups->current = &cups->by_id[current];

    return cups;
}

void free_cups(struct cups *cups) {
    free(cups->by_id);
    free(cups);
}

void assert_cups(const char *tag, const struct cups *cups, const char *expect) {
    for (const struct cup *cup = first_after_1(cups); *expect; cup = cup->next, expect++) {
        cup_id expected_cup = *expect - '0';
        if (cup->id != expected_cup) {
            printf("%s: expected %u got %u\n", tag, expected_cup, cup->id);
        }
    }
}

void test_10_moves() {
    struct cups *cups = make_cups("389125467", 9, 3);
    apply_n_moves(cups, 10);
    assert_cups("test 10 moves", cups, "92658374");
    free_cups(cups);
}


void test_100_moves() {
    struct cups *cups = make_cups("389125467", 9, 3);
    apply_n_moves(cups, 100);
    assert_cups("test 100 moves", cups, "67384529");
    free_cups(cups);
}

void test_10_million_moves() {
    struct cups *cups = make_cups("389125467", 1000000, 3);
    apply_n_moves(cups, 10000000);
    const struct cup *cup = first_after_1(cups);
    cup_id prod = cup->id * cup->next->id;
    if (prod != 149245887792) {
        printf("test 10 million moves: expected 149245887792 got %lu * %lu = %lu\n", cup->id, cup->next->id, prod);
    }
    free_cups(cups);
}

void run_tests() {
    test_10_moves();
    test_100_moves();
    test_10_million_moves();
}

cup_id part2(struct cups *cups) {
    return 0;
}

int main(int argc, char **argv) {
    if (argc > 1 && strcmp(argv[1], "test") == 0) {
        run_tests();
    } else {
        struct cups* cups = make_cups("523764819", 1000000, 5);
        apply_n_moves(cups, 10000000);
        const struct cup *cup = first_after_1(cups);
        printf("part 2: %lu\n", cup->id * cup->next->id);
        free_cups(cups);
    }
}
Enter fullscreen mode Exit fullscreen mode

There is an even simpler approach however which I didn't realise until later. Each cup can be modelled by simply the index to the next cup. So you just need one huge vector of indices - each cup can be found by id by looking up a position in the vector, and the ordering can be adjusted by reassigning next indices just like how the linked list works. I'll aim to do that in Rust.

Collapse
 
neilgall profile image
Neil Gall

And here we are. Setting up the initial array was the hardest bit. And it's faster than the C pointer version.

$ time ./target/release/day23
part 1 49576328
part 2 511780369955

real    0m0.475s
user    0m0.464s
sys 0m0.010s
Enter fullscreen mode Exit fullscreen mode

// -- model

type Cup = usize;

#[derive(Debug)]
struct Cups {
    length: usize,
    cups: Vec<Cup>,
    current: Cup
}

fn str_as_cup_ids(s: &str) -> impl Iterator<Item = Cup> + '_ {
    s.chars().map(|c| (c as Cup) - 48)
}

impl Cups {
    fn new<I>(input: I, current: Cup) -> Self where I: Iterator<Item = Cup> {
        let ids: Vec<Cup> = input.collect();
        let last = ids.len()-1;
        let mut cups: Vec<Cup> = (2..=ids.len()+1).collect();
        cups[last] = 1;

        for i in 1..ids.len() {
            cups[ids[i-1]-1] = ids[i];
        }
        cups[ids[last]-1] = ids[0];

        Cups {
            length: cups.len(),
            cups,
            current
        }
    }

    fn from_str(input: &str, current_cup: Cup) -> Self {
        Cups::new(str_as_cup_ids(input), current_cup)
    }

    fn next(&self, id: Cup) -> Cup {
        self.cups[id-1]
    }

    fn set(&mut self, from: Cup, to: Cup) {
        self.cups[from-1] = to;
    }

    fn prev_id(&self, cup: Cup) -> Cup {
        if cup == 1 { self.length as Cup } else { cup - 1 }
    }

    fn labels(&self) -> Vec<Cup> {
        let mut labels = vec![];
        let mut cup = self.next(1);
        for _ in 1..self.length {
            labels.push(cup);
            cup = self.next(cup);
        }
        labels
    }

    fn labels_as_str(&self) -> String {
        self.labels().iter().map(|n| n.to_string()).collect::<Vec<String>>().join("")
    }

    fn apply_move(&mut self) {
        let curr = self.current;
        let next1 = self.next(curr);
        let next2 = self.next(next1);
        let next3 = self.next(next2);
        let next4 = self.next(next3);

        let mut dest = self.prev_id(curr);
        while dest == next1 || dest == next2 || dest == next3 {
            dest = self.prev_id(dest);
        }

        let dest_next1 = self.next(dest);

        // remove next1..next3 from ring
        self.set(curr, next4);

        // reinsert after dest
        self.set(dest, next1);
        self.set(next3, dest_next1);

        self.current = self.next(curr);
   }

    fn apply_n_moves(&mut self, count: usize) {
        for _ in 0..count {
            self.apply_move();
        }
    }
}

// -- problems

fn part1(input: &str, start_cup: Cup) -> String {
    let mut cups = Cups::from_str(input, start_cup);
    cups.apply_n_moves(100);
    cups.labels_as_str()
}

fn part2(input: &str, start_cup: Cup) -> Cup {
    let mut cups = Cups::new(str_as_cup_ids(input).chain(10..=1_000_000), start_cup);
    cups.apply_n_moves(10_000_000);

    let first_2: Vec<Cup> = cups.labels().iter().take(2).copied().collect();
    first_2[0] * first_2[1]
}

fn main() {
    let input = "523764819";
    println!("part 1 {}", part1(input, 5));
    println!("part 2 {}", part2(input, 5));
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_10_moves() {
        let mut cups = Cups::from_str("389125467", 3);
        println!("{:?}", cups.labels());
        cups.apply_n_moves(10);
        assert_eq!(cups.labels(), vec![9, 2, 6, 5, 8, 3, 7, 4]);
    }

    #[test]
    fn test_100_moves() {
        let mut cups = Cups::from_str("389125467", 3);
        cups.apply_n_moves(100);
        assert_eq!(cups.labels(), vec![6, 7, 3, 8, 4, 5, 2, 9]);        
    }
}
Enter fullscreen mode Exit fullscreen mode