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: 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: Given a list of integer ranges (a la
5-8), what is the first value not in any given range?
Part 1: Input will be a list of the following form:
- The first floor contains a hydrogen-compatible microchip and a lithium-compatible microchip.
- The second floor contains a hydrogen generator.
- The third floor contains a lithium generator.
- The fourth floor contains nothing relevant.
You have an elevator that can move exactly 1 or 2 items. You can only leave a microchip on a floor with a non-matching generator if a matching generator is also present.
Move all items to the top (4th) floor.
So far we’ve read backup files, parsed contacts, and parsed messages. Today we’re going to dig a little deeper and start parsing apps specifically.
So far we’ve laid the groundwork, loading local iOS backups and parsed out contacts. Today let’s take another step down the rabbit hole and figure out how messages are stored.
After yesterday’s post laying the groundwork for looking into iOS Backups, today why don’t we actually start digging into one of the more interesting files: your list of contacts.
For the last little while, I’ve been spending my spare programming time working on a slightly larger project than I normally do: a Racket library for reading iOS backups.
Basically, I want to take the mess that is an iOS backup (not particularly designed to be easy to read by other programs) and extract some information from it, backing it up in a more easily readable format.
Specifically, I would like to be able to backup:
Another five minute challenge1, this time from /r/dailyprogrammer: given any positive integer, create and render a factor tree.
About two weeks ago, I came across a post via /r/programming: Quadtree Art(src). In a sentence, the goal is to recursively divide an image into a quadtree, at each step expanding the current node with the largest internal variance.