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

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)

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());
}

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)

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));
}

#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);
    }
}

#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;
}