DEV Community

loading...

Advent of Code 2020: Python Solution Day 23

qviper profile image Viper ・2 min read

Today's challenge was flashback from Data Structure and Algorithms class during BSC. The first part was not that harder and again I took help from some people's code, specially here. I have updated my repository here.

Please share your solution too.

Part 1

from collections import deque

class LinkedListNode:
    def __init__(self, item):
        self.item = item
        self.left = None
        self.right = None

my_input = [int(i) for i in "459672813"]

def part1():
    my_cups = deque(my_input)
    for _ in range(100):
        orig = my_cups[0]
        dest = my_cups[0]-1

        if dest < 1:
            dest = 9
        my_cups.rotate(-1)

        cup1 = my_cups.popleft()
        cup2 = my_cups.popleft()
        cup3 = my_cups.popleft()

        while dest in (cup1, cup2, cup3):
            dest = dest - 1 if dest > 1 else dest + 8

        while my_cups[0] != dest:
            my_cups.rotate(-1)
        my_cups.rotate(-1)

        my_cups.append(cup1)
        my_cups.append(cup2)
        my_cups.append(cup3)

        while my_cups[0] != orig:
            my_cups.rotate(-1)
        my_cups.rotate(-1)

    while my_cups[0] != 1:
        my_cups.rotate(-1)
    my_cups.popleft()

    return ''.join([str(i) for i in my_cups])
print(f"Part 1 solution: {part1()}")
Enter fullscreen mode Exit fullscreen mode

Part 2

def part2():
    my_nodes = {}

    last_node = None
    for i in my_input:
        curr_node = LinkedListNode(i)
        my_nodes[i] = curr_node

        if last_node is not None:
            last_node.right = curr_node
            curr_node.left = last_node

        last_node = curr_node
    for i in range(len(my_input)+1, 1_000_001):
        curr_node = LinkedListNode(i)
        my_nodes[i] = curr_node
        if last_node is not None:
            last_node.right = curr_node
            curr_node.left = last_node
        last_node = curr_node

    # Complete the circle
    ptr = my_nodes[my_input[0]]
    last_node.right = ptr
    ptr.left = last_node

    ptr = my_nodes[my_input[0]]
    for i in range(10000000):
        p_val = ptr.item

        cup1 = ptr.right
        cup2 = cup1.right
        cup3 = cup2.right

        ptr.right = cup3.right
        ptr.right.left = ptr

        d_val = p_val - 1 or 1000000
        while d_val in (cup1.item, cup2.item, cup3.item):
            d_val = d_val - 1 or 1000000

        d_node = my_nodes[d_val]

        cup3.right = d_node.right
        cup3.right.left = cup3
        d_node.right = cup1
        cup1.left = d_node

        ptr = ptr.right

    while ptr.item != 1:
        ptr = ptr.right

    return ptr.right.item * ptr.right.right.item
print(f"Part 2 solution: {part2()}")
Enter fullscreen mode Exit fullscreen mode

Discussion (0)

pic
Editor guide