This is a pure datastructure puzzle. If you have a large ordered sequence of values, and you need to insert or delete values at arbitrary points in that sequence, then the obvious choice is to use a linked list. Since we want to shift values forward and backward, you'd want it to be doubly linked. In a regular Python list, moving a value around would require shifting all the values following after it up and down, or you'd have to manually swap out values between the source and target indices, and that either gets very unwieldy or very inefficient. But in a linked list, you'd simply unlink the item that's being moved and re-link it in the new position.
The Python standard library does have collections.deque
, but because we have to track which values have moved already and which ones still to process, we'd still have to scan through the values each time or do complicated bookkeeping, killing the efficiency of having a double-linked datastructure in the first place.
The option I'm picking here is to implement the doubly-linked list directly. That's not complicated, but it's not something most Python developers have to think about.
from __future__ import annotations
from typing import Iterable, Iterator, Self
class EncryptedNumber:
__slots__ = "value", "next", "prev"
value: int
next: "EncryptedNumber"
prev: "EncryptedNumber"
def __init__(
self,
value: int,
prev: "EncryptedNumber" | None = None,
next: "EncryptedNumber" | None = None,
):
self.value = value
self.next = self if next is None else next
self.prev = self if prev is None else prev
def append(self, value: int):
new = EncryptedNumber(value, next=self.next, prev=self)
self.next.prev = new
self.next = new
return new
def remove(self):
"""Remove this node from the sequence
**Does not** clear the prev / next pointers on this node.
"""
self.prev.next, self.next.prev = self.next, self.prev
def insert(self, other: Self):
"""Insert other in between this node and and the next"""
other.next, self.next.prev = self.next, other
self.next, other.prev = other, self
def mix(self, length: int):
# locate the new prev and next nodes based on the value
# The value is adjusted to avoid circling the list multiple times, with
# the length *minus 1* because the current node is not included.
target, value = self, self.value % (length - 1)
if not value:
return
self.remove()
# value is positive, always, thanks to the modulo operation above. That
# may not be the most efficient direction however, so test if we can't
# reduce the rotation steps by going the other way.
if value > (length - 1) // 2:
# go the other way, it's shorter.
value = -length + value
while value:
target = target.prev
value += 1
else:
while value:
target = target.next
value -= 1
target.insert(self)
class EncryptedFile:
head: EncryptedNumber
order: list[EncryptedNumber]
length: int
def __init__(self, values: Iterable[int]):
it = iter(values)
self.head = tail = EncryptedNumber(next(it))
self.order = [self.head]
add = self.order.append
for value in it:
tail = tail.append(value)
add(tail)
if value == 0:
self.head = tail
self.length = len(self.order)
def __str__(self):
values = []
node = self.head
while True:
values.append(str(node.value))
node = node.next
if node is self.head:
break
return f"[{', '.join(values)}]"
def __len__(self):
return self.length
def __iter__(self) -> Iterator[EncryptedNumber]:
node = self.head
while True:
yield node
node = node.next
if node is self.head:
break
def mix(self):
for node in self.order:
node.mix(self.length)
@property
def coordinates(self) -> tuple[int, int, int]:
"""Return the 1000th, 2000th and 3000th values after 0"""
coords, node = [], self.head
for _ in range(3):
for _ in range(1000 % self.length):
node = node.next
coords.append(node.value)
return tuple(coords)
example = "1 2 -3 3 -2 0 4".split()
example_file = EncryptedFile(map(int, example))
example_file.mix()
assert example_file.coordinates == (4, -3, 2)
import aocd
file_data = [int(v) for v in aocd.get_data(day=20, year=2022).splitlines()]
file = EncryptedFile(file_data)
file.mix()
print("Part 1:", sum(file.coordinates))
Part 1: 6387
Because we have an efficient structure, implementing part two is trivial. We can take the description on face value and just mix ten times after updating the values with the key.
from typing import Final
KEY: Final[int] = 811589153
def decrypt(file: EncryptedFile, key: int) -> tuple[int, int, int]:
for number in file:
number.value *= key
for _ in range(10):
file.mix()
return file.coordinates
example_file = EncryptedFile(map(int, example))
assert decrypt(example_file, KEY) == (811589153, 2434767459, -1623178306)
file = EncryptedFile(file_data)
print("Part 2:", sum(decrypt(file, KEY)))
Part 2: 2455057187825