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. That’s about where I am today!

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

AoC 2021 Day 5: Linear Avoidinator

Source: Hydrothermal Venture

Part 1: Given a list of lines, find the number of integer points which are covered by more than one line (ignore non-vertical and non-horizontal lines).

Okay. Start with the data structures:

@dataclass(frozen=True)
class Point:
    x: int
    y: int


@dataclass(frozen=True)
class Line:
    p1: Point
    p2: Point

    def is_vertical(self):
        return self.p1.x == self.p2.x

    def is_horizontal(self):
        return self.p1.y == self.p2.y

    def is_orthagonal(self):
        return self.is_vertical() or self.is_horizontal()

    def points(self):
        # TODO: handle lines that aren't vertical, horizontal, or diagonal

        xd = 0 if self.p1.x == self.p2.x else (1 if self.p1.x < self.p2.x else -1)
        yd = 0 if self.p1.y == self.p2.y else (1 if self.p1.y < self.p2.y else -1)

        p = self.p1
        while p != self.p2:
            yield p
            p = Point(p.x + xd, p.y + yd)

        yield p

Dataclasses are great. They give you constructors and a bunch of other things for free. On top of that, if you specify frozen=True, making them immutable, you also get hashable types for free (which I’ll use in the problem).

Perhaps the most interesting bit here is the function that will iterate through the points in a List. Specifically, it will figure out the x and y delta (xd and yd) and repeatedly add that until you hit the end point.

Note: this only works for lines that are vertical, horizontal, or diagonal (at 45 degrees). Anything else needs a better line drawing algorithm (of which there are a few). If we need it, I’ll implement it.

Next, use that to parse:

def parse(file: TextIO) -> List[Line]:
    result = []

    for line in file:
        x1, y1, x2, y2 = [int(v) for v in line.replace(' -> ', ',').split(',')]
        result.append(Line(Point(x1, y1), Point(x2, y2)))

    return result

The input format is x1,y1 -> x2,y2, but it’s easier to split and convert if we do it all directly. There are a few other ways we could have done this: splitting on anything non-numeric or using a regular expression / something else for parsing directly. But I think this is clear enough.

And with all that, the problem is actually pretty short:

def part1(file: typer.FileText):

    lines = parse(file)
    counter: MutableMapping[Point, int] = collections.Counter()

    for line in lines:
        if not line.is_orthagonal():
            continue

        for point in line.points():
            counter[point] += 1

    print(sum(1 if count > 1 else 0 for point, count in counter.items()))

We’ll use the built in collections.Counter datatype, since that’s exactly what we’re doing: counting things. Then just iterate over every line, skip the non-orthagonal ones, iterate over every point, and count them up. At the end, print the number that we saw more than once. Et voila.

$ python3 linear-avoidinator.py part1 input.txt
5632

read more...


AoC 2021 Day 2: Submarine Simulator

Source: Dive!

Part 1: Simulate a submarine with 3 commands: forward N, down N, and up N that move forward, increase depth, and decrease depth in that order. Calculate the product of the final position and depth.

read more...


Advent of Code 2021

Been a while since I’ve done an advent of code! I’ll probably backfill a few years eventually, but for now, let’s just write some code!

As always, these problems are wonderful to try to solve yourself. If you agree, stop reading now. This post isn’t going anywhere.

If you’d like to see the full form of any particular solution, you can do so on GitHub (including previous years and possibly some I haven’t written up yet): jpverkamp/advent-of-code

read more...


Neural Network Cellular Automata

Okay. A random post on the /r/cellular_automata subreddit inspired me.

Let’s generate a cellular automata where each pixel updates based on a neural network given as input:

  • The x/y coordinates (scaled to the range 0-1)
  • An optional random value (to make it more dynamic)
  • A variety of neighboring data, such as:
    • The number of neighbors that are ‘active’ (> 50% white), ranges 0-8 scaled to 0-1. This should allow Conway's Game of Life
    • The RGB values of all neighbors (allows a superset of the above)
    • Gradients, subtract color value of the left from the right so that you get edges and side to side movement

Let’s do it!

read more...


Solving Snakebird

Snakebird!

A cute little puzzle game, where you move around snake(birds). Move any number of snakes around the level, eating fruit, and getting to the exit. The main gotchas are that you have gravity to content with–your snake will easily fall off the edge of the world–and each time you eat a fruit, your snake gets bigger. This can help get longer to get into hard to reach places or it can cause trouble when you trap yourself in corners.

Let’s use the new immutable.js solver to solve these problems!

read more...


Immutable.js Solvers

A bit ago I wrote about writing a generic brute force solver (wow, was that really two months ago?). It got … complicate. Mostly, because every time I wrote a step function, I had to be careful to undo the same. Wouldn’t it be nice if we could just write a step function and get backtracking for ‘free’?

Well, with immutability you can!

read more...