Source: Memory Reallocation
Part 1: Start with
nstacks of different sizes. Take the largest block and distribute its items starting withn+1and looping around. How many iterations of this does it take before you see a state you’ve seen before?
Part 1: Start with
nstacks of different sizes. Take the largest block and distribute its items starting withn+1and looping around. How many iterations of this does it take before you see a state you’ve seen before?
Part 1: Interpret a program made entirely of jump instructions: each instruction is how many steps to jump. Any time you use an instruction to jump, increase the value of that jump by 1 for next time. How many total steps does it take to escape (jump out of bounds)?
Part 1: Given a list of passphrases, count how many contain no duplicate words.
Part 1: Create a grid in a spiral pattern like so:
17 16 15 14 13 18 5 4 3 12 19 6 1 2 11 20 7 8 9 10 21 22 23—> …
> Given a specific index, what is the [[wiki:Manhattan Distance]]() from that point to the origin (`1`)?
This same sort of structure comes up from time to time in [Project Euler](/programming/sources/project-euler/) as well. I'm going to guess we'll see this again. Seems like a fine contender for a [library function](https://blog.jverkamp.com/2017/12/01/aoc-2017-library-functions/).
Specifically, we'll create a `SpiralGrid` class that can be used to automatically generate as large of a grid as we want lazily (it won't generate more of the grid until we need it).
```python
class SpiralGrid():
'''
Generate a spiral grid that looks like this:
17 16 15 14 13
18 5 4 3 12
19 6 1 2 11
20 7 8 9 10
21 22 23---> ...
The point (0, 0) is 1. x runs left to right, y from top to bottom. So the
point 12 is at (2, -1).
'''
def __init__(self):
self._indexes = {}
self._points = {}
def make_spiral():
index = 1
(x, y) = (0, 0)
yield index, (x, y)
# Build the layers outwards
for layer in itertools.count(1):
# Each layer starts by going right and down one (we'll go back up before yielding)
x += 1
y += 1
# Go through the four sides, up then left then down then right
# Repeat 2*layer times per side
for xd, yd in [(0, -1), (-1, 0), (0, 1), (1, 0)]:
for step in range(2 * layer):
index += 1
x += xd
y += yd
yield index, (x, y)
self._generator = make_spiral()
def __getitem__(self, key):
'''
Given an index or point return the other.
If we're given an integer, it's an index, return the point.
If we're given a tuple, it's a point, return the index.
Either way, generate as much data as we need and don't have.
'''
if isinstance(key, int):
field = self._indexes
elif isinstance(key, str):
key = int(key)
field = self._indexes
elif isinstance(key, tuple) and len(key) == 2:
field = self._points
else:
raise ValueError
while key not in field:
index, point = next(self._generator)
self._indexes[index] = point
self._points[point] = index
return field[key]
The neat part here is using a generator
to generate the coordinates of points. That way, we can run the generator until we find the point we’re looking for and cache any results for later.
Part 1: The checksum of a list of numbers is the difference between the largest and smallest number in the row. What is the sum of checksums of a file containing many such lists?
Part 1: Given a number, what is the sum of pairs of digits that match (wrapping the last digit around to the first)?
As mentioned in the main post, I’m structuring my solutions a bit differently this year. Rather than repeating the same relatively lengthy header in each function, we’re going to have a few shared files that can be imported or used for every problem.