DEV Community

loading...
Cover image for Advent of Code 2020 Solution Megathread - Day 23: Crab Cups

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

rpalo profile image Ryan Palo ・1 min read

Sorry, a bit late today. Had my last day of work before the Christmas weekend, and I was on the road for a lot of the day. Christmas Eve Eve! So excited!

The Puzzle

In today’s puzzle, that crab that we taught how to play cards has decided to teach us a game involving cups. It's apparently a very clever crab. Given cups labeled in a specific order, they are shuffled around based on an algorithm. Our job is to keep track of them and not to let the crab hustle us.

The Leaderboards

As always, this is the spot where I’ll plug any leaderboard codes shared from the community.

Ryan's Leaderboard: 224198-25048a19
Enter fullscreen mode Exit fullscreen mode

If you want to generate your own leaderboard and signal boost it a little bit, send it to me either in a DEV message or in a comment on one of these posts and I'll add it to the list above.

Yesterday’s Languages

Updated 08:54PM 12/23/2020 PST.

Language Count
Python 2
Haskell 1
Rust 1
JavaScript 1
TypeScript 1

Merry Coding!

Discussion (6)

pic
Editor guide
Collapse
bgaster profile image
Benedict Gaster • Edited

Ok so I'll be the first to emit that while my part one was fine in Haskell it was never going to scale to part 2! I really hate mutable arrays in Haskell, I mean what's the point, and as such I wrote the 2nd part in rust.

Here's Haskell for part 1:

input :: [Int]
input = [2,1,9,7,4,8,3,6,5]

m (x:xs) = let (three, xs') = splitAt 3 xs
               d            = dest' (x-1) xs'
               (ab, aa)     = span (/= d) xs'
           in ab ++ h aa ++ three ++ t aa ++ [x]
    where
        h []     = []
        h (x:_)  = [x]
        t []     = []
        t (x:xs) = xs

dest' 0 xs = maximum xs
dest' c xs | c `elem` xs = c
           | otherwise = dest' (c-1) xs

task1 0 xs = xs
task1 n xs = task1 (n-1) (m xs) 

main = do
    print (task1 100 input)
Enter fullscreen mode Exit fullscreen mode

and here's Rust for part 2:

const N: usize = 1000000;
const M: usize = 10000000;

fn in_holding(x: usize, holding: &[usize;3]) -> bool {
    for i in 0..3 {
        if x == holding[i] {
            return true;
        }
    }
    false
}

fn task2() -> usize {
    let mut v : Vec<usize> = Vec::with_capacity(N);
    for i in 0..N {
        v.push(i+1);
    }

    // build the beginning of our "linked" list with my input: 219748365
    v[0] = 2;
    v[2] = 1;
    v[1] = 9;
    v[9] = 7;
    v[7] = 4; 
    v[4] = 8;
    v[8] = 3;
    v[3] = 6;
    v[6] = 5;
    v[5] = 10;
    v[N - 1] = 0;

    let mut curr = v[0];
    let mut holding: [usize;3] = [0;3];

    for _ in 0..M {
        // "copy" 3 holding
        holding[0] = v[curr];
        holding[1] = v[holding[0]];
        holding[2] = v[holding[1]];

        // find destination
        let mut dest = if curr == 0 { N-1 } else { curr - 1 };
        while in_holding(dest, &holding) {
            dest = dest - 1;
        }

        // update
        let tmp = v[dest];
        v[dest] = holding[0];
        v[curr] = v[holding[2]];
        v[holding[2]] = tmp;

        curr = v[curr];
    }

    v[1] * v[v[1]]
}

fn main() {

    println!("{}", task2());
}
Enter fullscreen mode Exit fullscreen mode
Collapse
meseta profile image
Yuan Gao • Edited

A bit of linked list action in python. This can be optimized further because the dict only contains continuous numbers (other than 0) so we shouldn't need: a dict whose key is the cup value, and where each entry is a node containing the next cup. Instead we can have a list whose index is the cup value and where each entry contains the next cup. The two are basically equivalent, but the list is faster.

from functools import reduce

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

    def gen(self, count):
        cur = self
        for _ in range(count):
            yield cur
            cur = cur.next

class CupsGame:
    def __init__(self, data):
        self.min_cup = min(data)
        self.max_cup = max(data)
        self.cups = {value: Node(value) for value in data}

        def link(prev, cup):
            prev.next = cup
            return cup

        last_cup = reduce(link, self.cups.values())
        self.current = last_cup.next = self.cups[data[0]]

    def run(self, count):
        for _ in range(count):
            *pickup, self.current.next = self.current.gen(5)

            try_value = self.current.value
            while self.cups[try_value] in pickup:
                try_value -= 1
                if try_value < self.min_cup:
                    try_value = self.max_cup

            destination = self.cups[try_value]
            pickup[-1].next = destination.next
            destination.next = pickup[1]

            self.current = self.current.next

    def output(self, value, count):
        return (cup.value for cup in self.cups[value].next.gen(count))

raw = "872495136"
data = list(map(int, raw))

game = CupsGame(data)
game.run(100)
print("output", "".join(map(str, game.output(1, 8))))

data = list(map(int, raw)) + list(range(10, 1000001))
game = CupsGame(data)
game.run(10000000)
cup_a, cup_b = game.output(1, 2)
print("prod", cup_a*cup_b)
Enter fullscreen mode Exit fullscreen mode
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
Collapse
rpalo profile image
Ryan Palo Author

Little late to finish this one, but I did it and I'm happy with it even if the memory usage might be atrocious.

#include "Day23.h"

#include <stdio.h>

#define PART1_MAX_CUPS 9
#define PART1_ITERATIONS 100
#define PART2_MAX_CUPS 1000000
#define PART2_ITERATIONS 10000000

/// A Cup is a node in a cyclic linked list consisting of a number
/// and a pointer to the next node.
typedef struct Cup {
  int value;
  struct Cup* next;
} Cup;

/// Part one parses the digits in the input into 9 distinct cups
/// and links tail to head to form a cycle.  Returning the head
/// of the cycle is sufficient.
Cup* parse(const char* filename) {
  FILE* fp;
  fp = fopen(filename, "r");
  if (fp == NULL) {
    printf("Couldn't open file.\n");
    exit(EXIT_FAILURE);
  }
  Cup* head = (Cup*)malloc(sizeof(Cup));
  head->value = getc(fp) - '0';

  Cup* current = head;
  char c;
  while ((c = getc(fp)) != EOF) {
    current->next = (Cup*)malloc(sizeof(Cup));
    current = current->next;
    current->value = c - '0';
  }
  current->next = head;
  fclose(fp);
  return head;
}

/// Part one runs 100 iterations of the following algorithm:
///
/// 1. Detatch the three cups immediately clockwise (next) of the
///    current cup.
/// 2. Select a target number that is 1 less than the current cup's.
///    If that target number is one of the selected cups's numbers,
///    subtract 1 again.  If we go to 0, start over at the top end
///    of the set of cups.
/// 3. Insert the detatched 3 cups immediately after the cup with its
///    value equal to the target number.
/// 4. Increment the current cup to the next clockwise cup.
///
/// Finally, returns the digits in-order starting with the one immediately
/// clockwise from 1 and stopping just before 1 at the end.
int part1(const char* filename) {
  Cup* current = parse(filename);

  for (int i = 0; i < PART1_ITERATIONS; i++) {
    Cup* removed_head = current->next;
    Cup* removed_tail = removed_head->next->next;
    current->next = removed_tail->next;
    int dest = current->value - 1;
    while (dest == removed_head->value || dest == removed_head->next->value || dest == removed_tail->value || dest == 0) {
      dest -= 1;
      if (dest <= 0) dest = PART1_MAX_CUPS;
    }
    Cup* dest_cup = current;
    // Linear search for the destination cup.
    for (int count = 0; count < PART1_MAX_CUPS + 1; count++, dest_cup = dest_cup->next) {
      if (dest_cup->value == dest) {
        removed_tail->next = dest_cup->next;
        dest_cup->next = removed_head;
        break;
      }
      if (count == PART1_MAX_CUPS) {
        printf("Didn't find the dest cup.  Dest: %d\n", dest);
        exit(EXIT_FAILURE);
      }
    }
    current = current->next;
  }
  // Linear search for 1.
  while (current->value != 1) current = current->next;

  // Create a number that is the next 8 digits following 1.
  current = current->next;
  int result = 0;
  while (current->value != 1) {
    result *= 10;
    result += current->value;
    current = current->next;
  }

  return result;
}

/// The second part parsing function does much the same thing as part 1,
/// but, additionally, we store an array of cups, with each cup stored
/// at the index of its value.  That way, lookup cost is O(1) instead
/// of O(n).
Cup** parse2(const char* filename, int* start_index) {
  FILE* fp;
  fp = fopen(filename, "r");
  if (fp == NULL) {
    printf("Couldn't open file.\n");
    exit(EXIT_FAILURE);
  }

  // Store the cups *at* their index, which means the 0th spot is
  // empty for ergonomic reasons.
  Cup** cups = (Cup**)malloc(sizeof(Cup*)*(PART2_MAX_CUPS + 1));
  if (cups == NULL) {
    printf("Couldn't malloc the cups array.\n");
    exit(EXIT_FAILURE);
  }
  Cup* head = (Cup*)malloc(sizeof(Cup));
  head->value = getc(fp) - '0';
  cups[head->value] = head;

  // We still have to know which cup is our starting cup, so save that
  *start_index = head->value;

  // Add the rest of the cups in the order specified in the input file.
  Cup* current = head;
  char c;
  while ((c = getc(fp)) != EOF) {
    current->next = (Cup*)malloc(sizeof(Cup));
    current = current->next;
    current->value = c - '0';
    cups[current->value] = current;
  }

  // Add the remaining cups from 10 to 
  for (int i = PART1_MAX_CUPS + 1; i <= PART2_MAX_CUPS; i++) {
    current->next = (Cup*)malloc(sizeof(Cup));
    current = current->next;
    current->value = i;
    cups[i] = current;
  }
  current->next = head;
  fclose(fp);
  return cups;
}

/// Free the cups
static void free_cups(Cup** cups) {
  for (int i = 1; i <= PART2_MAX_CUPS; i++) {
    free(cups[i]);
  }
  free(cups);
}

/// Part two upgrades to 1,000,000 cups and 10,000,000 iterations.
/// Returns the product of the two cups immediately following 1 afterwards.
int64_t part2(const char* filename) {
  int start_index;
  Cup** cups = parse2(filename, &start_index);
  Cup* current = cups[start_index];

  for (int i = 0; i < PART2_ITERATIONS; i++) {
    Cup* removed_head = current->next;
    Cup* removed_tail = removed_head->next->next;
    current->next = removed_tail->next;
    int dest = current->value - 1;
    while (dest == removed_head->value || dest == removed_head->next->value || dest == removed_tail->value || dest == 0) {
      dest -= 1;
      if (dest <= 0) dest = PART2_MAX_CUPS;
    }
    Cup* dest_cup = cups[dest];
    removed_tail->next = dest_cup->next;
    dest_cup->next = removed_head;
    current = current->next;
  }
  int64_t result = (int64_t)cups[1]->next->value * (int64_t)cups[1]->next->next->value;
  free_cups(cups);
  return result;
}

/// Run both parts.
int day23() {
  printf("====== Day 23 ======\n");
  printf("Part 1: %d\n", part1("data/day23.txt"));
  printf("Part 2: %lld\n", part2("data/day23.txt"));
  return EXIT_SUCCESS;
}
Enter fullscreen mode Exit fullscreen mode
Collapse
thibpat profile image
Thibaut Patel

My JavaScript video walkthrough: