Day 23: Crab Cups

#!/usr/bin/env python3

import re

def print_cups(cups, current_index):
    r = ''
    for i, c in enumerate(cups):
        if i == 0:
            if current_index == 0:
                r += f'({c})'
            else:
                r += f'{c}'
        elif i == current_index:
            r += f' ({c})'
        else:
            r += f' {c}'
    return r

cups = [int(c) for c in open('./input', 'r').read().strip()]
#cups = open('./example_input', 'r').read()

current_index = 0
for move in range(1, 101):
    print(f'-- move {move:03d} --')
    print(f'cups: {print_cups(cups, current_index)}')
    cur_label = cups[current_index]

    # pick up three cups clockwise of the current cup
    pickup = []

    popindex = (current_index + 1) % len(cups)
    pickup.append(cups.pop(popindex))
    if popindex != 0:
        popindex = (current_index + 1) % len(cups)
    pickup.append(cups.pop(popindex))
    if popindex != 0:
        popindex = (current_index + 1) % len(cups)
    pickup.append(cups.pop(popindex))
    print(f'pick up: {pickup}')

    # select destination cup:
    dest_label = cur_label - 1
    if dest_label < min(cups):
        dest_label = max(cups)
    while dest_label in pickup:
        dest_label -= 1
        if dest_label < min(cups):
            dest_label = max(cups)
    print(f'destination: {dest_label}')

    # place cups immediately to the right of destination cup
    dest_index = cups.index(dest_label)
    cups.insert(dest_index + 1, pickup.pop(-1))
    cups.insert(dest_index + 1, pickup.pop(-1))
    cups.insert(dest_index + 1, pickup.pop(-1))

    # choose new cup
    current_index = (cups.index(cur_label) + 1) % len(cups)
    print()

start = cups.index(1)
cups = cups[start + 1:] + cups[:start]
print('-- final --')
print(f'cups! {"".join([str(c) for c in cups])}')

The problem for today wasn't too bad... but it still took me a while because I had to implement a circularly linked list in Python, which I've never done before (I have in C/C++, but never in Python). Once I had the data structure working though, it was pretty straightforward to implement the rules of the game.

# Classes

class Cup:
    def __init__(self, label, right=None):
        self.label = int(label)
        self.right = right


    def push(self, label):
        self.right = Cup(label, self.right if self.right else self)
        return self.right

    def pop(self):
        right      = self.right
        self.right = self.right.right
        return right.label

    def __str__(self):
        return f'{self.label}'

# Functions

def link_cups(labels):
    head    = Cup(labels.pop(0))
    current = head
    for label in labels:
        current = current.push(label)
    return head
   
def dump_cups(head):
    cups    = [f'({head})']
    current = head.right

    while current != head:
        cups.append(f'{current.label}')
        current = current.right

    return ' '.join(cups)

def find_cup(head, target):
    while head.label != target:
        head = head.right
    return head

def find_max(head):
    maximum = head.label
    current = head.right

    while current != head:
        if current.label > maximum:
            maximum = current.label
        current = current.right

    return maximum

def play_game(cups, moves=100):
    current = cups

    for move in range(1, moves + 1):
        print(f'\n-- move {move} --')
        print(f'cups:', dump_cups(current))

        # Pick up three cups immediately clockwise of current cup
        three_cups = [current.pop(), current.pop(), current.pop()]
        print(f'pick up:', ' '.join(map(str, three_cups)))
        
        # Select destination cup, where label is equal to current cup's label - 1
        destination_label = current.label - 1

        # Make sure destination isn't in one of three cups
        while destination_label in three_cups:
            destination_label -= 1

        # If destnation is below lowest value (1), then wrap to highest in remaining cups
        if destination_label == 0:
            destination_label = find_max(current)

        # Place cups after destination
        destination = find_cup(current, destination_label)
        
        print(f'destination: {destination}')

        for label in three_cups:
            destination = destination.push(label)
        
        # Advance to next cup
        current = current.right

    return current

def order_cups(cups):
    first = find_cup(cups, 1)
    return ''.join(dump_cups(first).split()[1:])

# Main Execution

def main():
    #cups = link_cups(list('389125467'))
    cups = link_cups(list('193467258'))
    cups = play_game(cups)

    print(order_cups(cups))

if __name__ == '__main__':
    main()

The second part was also straightforward. The main changes were adding more cups to the initial list and using a hash table / map to keep track of where the cups are. The reason for this is that you need to locate the destination cup in order to insert the three cups you extracted. In Part 1, I used a simple linear search that scanned the whole list to find this cup. With one million cups, however, a linear search is really slow, so I used a dictionary to map the cup's label to its actual object. With this dictionary in place, I could find the destination cup in constant time.

I could have also optimized find_max, which is still linear, but since it wasn't called often, I decided to leave it be. In the end, my second part took about one minute to run (after I removed all print statements).

--- day23-A.py	2020-12-23 10:35:12.511615829 -0500
+++ day23-B.py	2020-12-23 10:48:37.059680740 -0500
@@ -29,6 +29,10 @@
     current = head
     for label in labels:
         current = current.push(label)
+
+    for label in range(10, 1000000 + 1):
+        current = current.push(label)
+
     return head
    
 def dump_cups(head):
@@ -57,16 +61,23 @@
 
     return maximum
 
-def play_game(cups, moves=100):
+def make_map(head):
+    mapping = {head.label: head}
+    current = head.right
+
+    while current != head:
+        mapping[current.label] = current
+        current = current.right
+
+    return mapping
+
+def play_game(cups, moves=10000000):
     current = cups
+    mapping = make_map(cups)
 
     for move in range(1, moves + 1):
-        print(f'\n-- move {move} --')
-        print(f'cups:', dump_cups(current))
-
         # Pick up three cups immediately clockwise of current cup
         three_cups = [current.pop(), current.pop(), current.pop()]
-        print(f'pick up:', ' '.join(map(str, three_cups)))
         
         # Select destination cup, where label is equal to current cup's label - 1
         destination_label = current.label - 1
@@ -80,21 +91,20 @@
             destination_label = find_max(current)
 
         # Place cups after destination
-        destination = find_cup(current, destination_label)
+        destination = mapping[destination_label]
         
-        print(f'destination: {destination}')
-
         for label in three_cups:
-            destination = destination.push(label)
+            destination    = destination.push(label)
+            mapping[label] = destination
         
         # Advance to next cup
         current = current.right
 
     return current
 
-def order_cups(cups):
+def two_cups(cups):
     first = find_cup(cups, 1)
-    return ''.join(dump_cups(first).split()[1:])
+    return first.right.label * first.right.right.label
 
 # Main Execution
 
@@ -103,7 +113,7 @@
     cups = link_cups(list('193467258'))
     cups = play_game(cups)
 
-    print(order_cups(cups))
+    print(two_cups(cups))
 
 if __name__ == '__main__':
     main()

use std::env;
use std::io::{self};

const NUM_CUPS_P1: usize = 9;
const NUM_CUPS_P2: usize = 1_000_000;

#[derive(Debug,Clone)]
struct Cup {
    cw: usize,
    ccw: usize,
}

fn part1(input: &str) -> io::Result<()> {
    let cups_order = std::fs::read_to_string(input)
        .expect("Input file not found.")
        .chars()
        .map(|c| c.to_digit(10).unwrap() as usize)
        .collect::<Vec<_>>();

    let mut cups = vec![Cup {cw: 0, ccw: 0}; NUM_CUPS_P1+1];
    
    // Initialize cups
    // cups[0] is dead
    for ix in 0..NUM_CUPS_P1 {
        let label = cups_order[ix];
        let ixp1 = if ix+1 == NUM_CUPS_P1 { 0 } else { ix + 1 };
        let ixm1 = if ix   == 0 { NUM_CUPS_P1-1 } else { ix - 1};
        cups[label].cw  = cups_order[ixp1];
        cups[label].ccw = cups_order[ixm1];
    }

    let mut current = cups_order[0];
    let mut destination;
    for _ in 0..100 {
        let selected = [
            cups[current].cw,
            cups[cups[current].cw].cw,
            cups[cups[cups[current].cw].cw].cw];

        destination = current - 1;
        if destination == 0 { destination = NUM_CUPS_P1; }
        'dest_lp: loop {
            if destination != selected[0] &&
               destination != selected[1] &&
               destination != selected[2] { break 'dest_lp;
            } else {
                destination -= 1;
                if destination == 0 { destination = NUM_CUPS_P1; }
            }
        }

        // Split 3 cups out of chain
        let chain_cw_save = cups[selected[2]].cw; // clockwise end of 3 cup chain
        cups[chain_cw_save].ccw = current;
        cups[current].cw = chain_cw_save;

        // Insert 3 cups
        let dest_cw_save = cups[destination].cw;
        cups[destination].cw = selected[0];
        cups[selected[0]].ccw = destination;
        cups[selected[2]].cw = dest_cw_save;
        cups[dest_cw_save].ccw = selected[2];

        current = cups[current].cw;
    }

    // Build answer string
    let mut ans: Vec<usize> = Vec::new();
    let mut next = cups[1].cw;
    for _ in 0..NUM_CUPS_P1-1 {
        ans.push(next);
        next = cups[next].cw;
    }
    let ans = ans.iter().map(|x| format!("{}",x)).collect::<String>();

    println!("Part 1: {}", ans); // 26354798
    
    Ok(())
}

fn part2(input: &str) -> io::Result<()> {
    let cups_order = std::fs::read_to_string(input)
        .expect("Input file not found.")
        .chars()
        .map(|c| c.to_digit(10).unwrap() as usize)
        .collect::<Vec<_>>();

    let mut cups = vec![Cup {cw: 0, ccw: 0}; NUM_CUPS_P2+1];
    
    // Initialize cups
    // cups[0] is dead
    for ix in 0..NUM_CUPS_P1 {
        let label = cups_order[ix];
        let ixp1 = if ix+1 == NUM_CUPS_P1 { NUM_CUPS_P1+1 } else { cups_order[ix+1] };
        let ixm1 = if ix   == 0 { NUM_CUPS_P2 } else { cups_order[ix-1] };
        cups[label].cw  = ixp1;
        cups[label].ccw = ixm1;
    }
    for ix in NUM_CUPS_P1+1..=NUM_CUPS_P2 {
        let label = ix;
        let ixp1 = if ix+1 == NUM_CUPS_P2+1 { cups_order[0] } else { ix + 1 };
        let ixm1 = if ix-1 == NUM_CUPS_P1 { cups_order[NUM_CUPS_P1-1] } else { ix - 1 };
        cups[label].cw  = ixp1;
        cups[label].ccw = ixm1;
    }

    let mut current = cups_order[0];
    let mut destination;
    for _ in 0..10_000_000 {
        let selected = [
            cups[current].cw,
            cups[cups[current].cw].cw,
            cups[cups[cups[current].cw].cw].cw];

        destination = current - 1;
        if destination == 0 { destination = NUM_CUPS_P2; }
        'dest_lp: loop {
            if destination != selected[0] &&
               destination != selected[1] &&
               destination != selected[2] { break 'dest_lp;
            } else {
                destination -= 1;
                if destination == 0 { destination = NUM_CUPS_P2; }
            }
        }

        // Split 3 cups out of chain
        let chain_cw_save = cups[selected[2]].cw; // clockwise end of 3 cup chain
        cups[chain_cw_save].ccw = current;
        cups[current].cw = chain_cw_save;

        // Insert 3 cups
        let dest_cw_save = cups[destination].cw;
        cups[destination].cw = selected[0];
        cups[selected[0]].ccw = destination;
        cups[selected[2]].cw = dest_cw_save;
        cups[dest_cw_save].ccw = selected[2];

        current = cups[current].cw;
    }

    let cup1 = cups[1].cw;
    let cup2 = cups[cups[1].cw].cw;
    let part2 = cup1 * cup2;

    println!("Part 2: {}", part2); // 166298218695
    
    Ok(())
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    part1(&filename).unwrap();
    part2(&filename).unwrap();
}

public override string SolvePart1()
{
	var input = "198753462";
	var cups = input.Select(c => c - '0').ToList();
	var currIdx = 0;
	var temp = new int[3];

	for (int i = 0; i < 100; i++)
	{
		var curr = cups[currIdx];
		temp[0] = cups[(currIdx + 1) % 9];
		temp[1] = cups[(currIdx + 2) % 9];
		temp[2] = cups[(currIdx + 3) % 9];
		cups.Remove(temp[0]);
		cups.Remove(temp[1]);
		cups.Remove(temp[2]);

		var target = curr == 1 ? 9 : curr - 1;
		while (temp.Contains(target))
		{
			target = target == 1 ? 9 : target - 1;
		}

		cups.InsertRange(cups.IndexOf(target) + 1, temp);
		currIdx = (cups.IndexOf(curr) + 1) % 9;
	}

	return $"Final order: {new string(cups.Select(i => (char)(i + '0')).ToArray())}";
}

public override string SolvePart2()
{
	var input = "198753462";
	var cups = new CircularlyLinkedList(1000000);
	int populate = 0;
	foreach (var c in input)
	{
		cups._buf[populate] = new CircularlyLinkedList.ListNode(c - '0');
		populate++;
	}
	for(; populate < 1000000; populate++)
	{
		cups._buf[populate] = new CircularlyLinkedList.ListNode(populate + 1);
	}
	cups.Initialize();

	var cupsHash = new Dictionary<int, CircularlyLinkedList.ListNode>();
	foreach (var n in cups._buf)
	{
		cupsHash.Add(n.Payload, n);
	}

	var one = cupsHash[1];

	var curr = cups.Head;
	for (int i = 0; i < 10000000; i++)
	{
		var temp = cups.RemoveMultipleAfter(curr, 3);
		var targetLabel = curr.Payload == 1 ? 1000000 : curr.Payload - 1;
		while (targetLabel == temp.Payload || targetLabel == temp.Next.Payload || targetLabel == temp.Next.Next.Payload)
		{
			targetLabel = targetLabel == 1 ? 1000000 : targetLabel - 1;
		}

		var target = cupsHash[targetLabel];
		cups.InsertMultipleAfter(target, temp, temp.Next.Next);

		curr = curr.Next;
		if (i % 100000 == 0)
		{
			Console.WriteLine($"Completed {i} rounds");
		}
	}

	long star1 = one.Next.Payload;
	long star2 = one.Next.Next.Payload;

	return $"Stars are {star1} and {star2} = {star1 * star2}";
}

public class CircularlyLinkedList
{
	public class ListNode
	{
		public ListNode Next { get; set; }
		public ListNode Back { get; set; }
		public int Payload { get; }

		public ListNode(int p)
		{
			Payload = p;
		}

	}

	public ListNode[] _buf { get; }

	public ListNode Head { get; set; }

	public CircularlyLinkedList(int capacity)
	{
		_buf = new ListNode[capacity];
	}

	public void Initialize()
	{
		for(int i = 1; i < _buf.Length - 1; i++)
		{
			_buf[i].Next = _buf[i + 1];
			_buf[i].Back = _buf[i - 1];
		}
		_buf[0].Next = _buf[1];
		_buf[0].Back = _buf[^1];

		_buf[^1].Next = _buf[0];
		_buf[^1].Back = _buf[^2];

		Head = _buf[0];
	}

	public void InsertAfter(ListNode target, ListNode ins)
	{
		ins.Next = target.Next;
		ins.Back = target;
		target.Next.Back = ins;
		target.Next = ins;
	}

	public void InsertMultipleAfter(ListNode target, ListNode insFirst, ListNode insLast)
	{
		insLast.Next = target.Next;
		insFirst.Back = target;
		target.Next.Back = insLast;
		target.Next = insFirst;
	}

	public ListNode RemoveMultipleAfter(ListNode target, int count)
	{
		var ret = target.Next;
		var afterLast = target.Next;
		for (int i = 0; i < count; i++)
		{
			afterLast = afterLast.Next;
		}
		var last = afterLast.Back;

		target.Next = afterLast;
		afterLast.Back = target;

		last.Next = null;
		ret.Back = null;

		Head = target;

		return ret;
	}
}

The circularly-linked list has some horrendous software engineering in terms of defining clean API boundaries, but it allowed me to do initialization easily, so /shrug. The neat trick was realizing that while we need constant-time insert/delete and find operations, we don't actually need random-access at all - so a linked list is a perfect solution because we also know where each element will be.

I'm pretty sure you could optimize this further and remove the hashtable by just using the position in the backing array as your lookup, but it'd be an extra step to wire it up correctly to initialize

My part1 solution run against part2 would have taken ~3.5hr. The version shown here gets through it in 5.59s. Not a bad speedup.