Programming

The earliest memory I have of ‘programming’ is in the early/mid 90s when my father brought home a computer from work. We could play games on it … so of course I took the spreadsheet program he used (LOTUS 123, did I date myself with that?) and tried to modify it to print out a helpful message for him. It … halfway worked? At least I could undo it so he could get back to work…

After that, I picked up programming for real in QBASIC (I still have a few of those programs lying around), got my own (junky) Linux desktop from my cousin, tried to learn VBasic (without a Windows machine), and eventually made it to high school… In college, I studied computer science and mathematics, mostly programming in Java/.NET, although with a bit of everything in the mix. A few of my oldest programming posts on this blog are from that time.

After that, on to grad school! Originally, I was going to study computational linguistics, but that fell through. Then programming languages (the school’s specialty). And finally I ended up studying censorship and computer security… before taking a hard turn into the private sector to follow my PhD advisor.

Since then, I’ve worked in the computer security space at a couple of different companies. Some don’t exist any more, some you’ve probably heard of. I still program for fun too, and not just in security.

But really, I still have a habit of doing a little bit of everything. Whatever seems interesting at the time!

All posts

Recent posts

AoC 2017 Day 3: Spiraly

2017-12-03

Source: Spiral Memory

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.

read more...

AoC 2017: Library Functions

2017-12-01

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.

read more...

Clock drift in Docker containers

2017-11-15

I was working on a docker container which uses the aws cli to mess around with some autoscaling groups when I got a somewhat strange error:

A client error (SignatureDoesNotMatch) occurred when calling the DescribeAutoScalingGroups operation: Signature not yet current: 20171115T012426Z is still later than 20171115T012420Z (20171115T011920Z + 5 min.)

Hmm.

Are the clocks off?

read more...

AoC 2016 Day 24: Venti

2016-12-24

Source: Air Duct Spelunking

Part 1: Given a map of the form:

########### #0.1…..2# #.#######.# #4…….3# ###########


> Find the shortest route to visit each of the points, starting at `0`.





First, we want to take the map that we were given and simplify it. We know that we want to visit all of the points, so lets take the original map and turn it just into a map of distances between any two named points.

```python
walls = set()
name_to_point = {}
point_to_name = {}

# Load the input file into a set of walls and the location of points of interest
for y, line in enumerate(fileinput.input(args.files)):
    for x, c in enumerate(line.strip()):
        if c.isdigit():
            name_to_point[int(c)] = (x, y)
            point_to_name[(x, y)] = int(c)

        elif c == '#':
            walls.add((x, y))

# Dynamically fill a distance map to a given point
def distances_to(name):
    to_scan = queue.Queue()
    to_scan.put((name_to_point[name], 0))

    scanned = set()

    result = {}

    while not to_scan.empty():
        point, distance = to_scan.get()

        if point in point_to_name:
            name = point_to_name[point]
            if name not in result:
                result[name] = distance

        if point in scanned:
            continue
        else:
            scanned.add(point)

        x, y = point
        for xd, yd in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            neighbor = (x + xd, y + yd)
            if neighbor not in walls:
                to_scan.put((neighbor, distance + 1))

    return result

distances = {
    name: distances_to(name)
    for name in name_to_point
}
names = list(sorted(name_to_point.keys()))

The first part loads the map and the second part will flood fill out from each point. This will find the minimum distance from each named point to the given one, somewhat simplifying the problem.

read more...

AoC 2016 Day 23: Assembunny2

2016-12-23

Source: Safe Cracking

Part 1: Take the assembunny interpreter from day 12 and add an instruction (tgl X) that modifies the code at an offset of X instructions.

  • inc becomes dec; any other one argument instruction (including tgl) becomes inc
  • jnz becomes cpy; any other two argument instructions become jnz
  • Toggling an instruction outside of the program does nothing (it does not halt execution)
  • If toggling produces an invalid instruction, ignore it

Run the given program with the initial register of a = 7. What is the final value in register a?

read more...