Python code golf for Advent of Code 2022, Day 10

This December, I’m participating in Advent of Code, which is a daily coding puzzle from December 1 through December 25.

Today’s puzzle (December 10) was a lot of fun. I had so much fun with it, that I decided to try my hand at golfing my Python solution, whittling it down to as few characters as possible.

Here’s the tiniest solution I could come up with:

x=1;c=0
for l in open(0).read().replace('a','\na').splitlines():a=int(l[4:]or 0);p='.#'[abs(x-c)<=1];c=(c+1)%40;print(p,end='\n'[c:]);x+=a

In this article, I’ll explain step-by-step how that abomination came to be. It was quite a journey, and I’m hoping that you’ll learn a thing or two from it, even if you aren’t interested in code golf or Advent of Code. I learned some new things about Python even as I was writing out this article!

This article contains spoilers, so don’t read it if you want to try the problem yourself and haven’t gotten a chance yet!

Today’s problem (if you haven’t seen it and don’t plan on solving it) is the following:

As output, the program writes a series of “pixels” to a “CRT display:”

• Every “CPU cycle,” the program prints either # (a bright “pixel”) or . (a dark “pixel”).
• Every 40 pixels, it prints a newline character (\n) to begin the next row of “pixels.”
• Before each cycle, to decide whether to print a bright or dark pixel, the program reads from a CPU register called X. If the current value of X is within one pixel of the CRT’s current position, then it prints a bright pixel; otherwise it prints a dark pixel.

As input, the program reads a series of “instructions” that determine what pixel should be drawn at the current CRT position:

• The program input file contains a list of CPU instructions, one per line.
• The CPU instructions determine what the value of X will be during each CPU cycle. The value X starts at one.
• Each CPU instruction is either the string noop or addx N, where N is an integer (like -1 or 15)
• noop instructions have no effect, and require 1 CPU cycle to execute.
• addx N instructions have the effect of adding N to the CPU register X, and require 2 CPU cycles to execute. The register is not updated until after the 2 required CPU cycles.

The solution to the program is found by looking at the pixels drawn to the display.

For example, the program output for the input that I was assigned looks like this:

####..##....##..##..###....##.###..####.
#....#..#....#.#..#.#..#....#.#..#.#....
###..#.......#.#..#.#..#....#.#..#.###..
#....#.......#.####.###.....#.###..#....
#....#..#.#..#.#..#.#....#..#.#.#..#....
#.....##...##..#..#.#.....##..#..#.####.

Interpreting this image (a bit of a challenge on its own!) leads us to a solution of FCJAPJRE.

So, with all that said, here was my original solution to this problem:

lines = open('input.txt').read().splitlines()
# Initialize the X register and CRT_X position.
x = 1
crt_x = 0
for line in lines:
    # If the line has a noop instruction, we'll spend
    # 1 CPU cycle and leave X unchanged.
    cycle_duration = 1
    addx = 0
    # Otherwise if the line has an addx N instruction,
    # we'll spend 2 CPU cycles and add N to x afterwards.
    if line.startswith('addx '):
        cycle_duration = 2
        addx = int(line.split()[1])
    # For each cycle, if CRT_X is within 1 pixel of X,
    # print '#', otherwise print '.'
    for _ in range(cycle_duration):
        if x in (crt_x - 1, crt_x, crt_x + 1):
            print('#', end='')
        else:
            print('.', end='')
        crt_x += 1
        # Once we reach the end of the row, wrap CRT_X
        # back around to 0, printing a blank line.
        if crt_x == 40:
            print()
            crt_x = 0
    # Note, addx instructions only apply *after* the
    # CPU cycles have elapsed for the instruction.
    x += addx

Golfing strategy

In order to golf this code, my overall strategy was to try to rewrite the main for loop as a single Compound statement, like this:

for line in lines:statement_1;statement_2; # more statements...

The benefit of doing it this way is that we save one byte per statement. With a compound for loop, we only need a single character ; as a separator, which requires only one byte. For a “normal” for loop, the best we can do is a newline character followed by a tab character (\n\t), which requires two bytes (twice as many per statement!).

The challenge is that Python only allows certain types of compound statements. For example, the following is invalid syntax:

for line in lines: if some_condition: do_something()

To get a valid compound statement, all of the statements in the loop body need to be either variable assignments like x=1, or simple function calls like print(x).

Removing block statements in the main loop

Here’s our original code again, this time with comments removed:

lines = open('input.txt').read().splitlines()
x = 1
crt_x = 0
for line in lines:
    cycle_duration = 1
    addx = 0
    if line.startswith('addx '):
        cycle_duration = 2
        addx = int(line.split()[1])
    for _ in range(cycle_duration):
        if x in (crt_x - 1, crt_x, crt_x + 1):
            print('#', end='')
        else:
            print('.', end='')
        crt_x += 1
        if crt_x == 40:
            print()
            crt_x = 0
    x += addx

As the first major simplification, let’s try to get rid of the inner nested for loop.

The reason we had the nested for loop in the original implementation is that we have to deal with the differing CPU cycle requirements for each instruction: noop instructions take 1 cycle, and addx instructions take 2 cycles. The inner loop would execute once for each cycle, printing one pixel each time.

The key observation is that if we artificially insert a noop instruction before each addx instruction, then we can pretend that addx instructions only take 1 CPU cycle, and our program should behave exactly the same without needing the inner loop!

lines = (open('input.txt').read()
         # Artificially insert a
         # noop line before each addx:
         .replace('addx', 'noop\naddx')
         .splitlines())
x = 1
crt_x = 0
for line in lines:
    addx = 0
    if line.startswith('addx '):
        addx = int(line.split()[1])
    if x in (crt_x - 1, crt_x, crt_x + 1):
        print('#', end='')
    else:
        print('.', end='')
    crt_x += 1
    if crt_x == 40:
        print()
        crt_x = 0
    x += addx

Now that we’re treating all instructions as taking only 1 cycle, we can simplify even further by replacing all noop lines with addx 0, which are now equivalent. The benefit of doing that is that it lets us parse all lines as addx instructions, rather than needing a conditional to deal with the possibility of noop instructions:

lines = (open('input.txt').read()
         .replace('addx', 'noop\naddx')
         # Make all noops look like adds:
         .replace('noop', 'addx 0')
         .splitlines())
x = 1
crt_x = 0
for line in lines:
    # All instructions are now "addx n",
    # so we can trim to get just " n".
    # Note that int() strips whitespace.
    addx = int(line[4:])
    if x in (crt_x - 1, crt_x, crt_x + 1):
        print('#', end='')
    else:
        print('.', end='')
    crt_x += 1
    if crt_x == 40:
        print()
        crt_x = 0
    x += addx

Now, we also want to get rid of those if-else statements, since they are not allowed in compound for-loops.

For the first one, let’s make a variable p for the text we want to print, then print it once:

lines = (open('input.txt').read()
         .replace('addx', 'noop\naddx')
         .replace('noop', 'addx 0')
         .splitlines())
x = 1
crt_x = 0
for line in lines:
    addx = int(line[4:])
    # Using an "if ... else" expression here:
    p = '#' if x in (crt_x - 1, crt_x, crt_x + 1) else '.'
    print(p, end='')
    crt_x += 1
    if crt_x == 40:
        print()
        crt_x = 0
    x += addx

Note, in this new code, we’re still using if and else, but now we're using an if-else expression, not an if-else statement.

Next, there’s still another if statement we need to get rid of. Let's use the % operator to implement the wrap-around logic, and append '\n' to the printed text only when p wraps around to 0:

lines = (open('input.txt').read()
         .replace('addx', 'noop\naddx')
         .replace('noop', 'addx 0')
         .splitlines())
x = 1
crt_x = 0
for line in lines:
    addx = int(line[4:])
    p = '#' if x in (crt_x - 1, crt_x, crt_x + 1) else '.'
    print(p, end='')
    # Using % here:
    crt_x = (crt_x + 1) % 40
    # Using "if ... else" here:
    print('\n' if crt_x == 0 else '', end='')
    x += addx

OK! Now, we can condense our code into a single compound statement, since each line is either an assignment or a single function call.

That will make the code super hard to read, though, so let’s do a few more optimizations while our loop body is still nice and indented.

The lowest hanging fruit is to replace the crt_x computation with a shorter expression. Instead of explicitly checking each possible x position, we can check whether the CRT's x position is within distance 1 of the sprite's x position:

lines = (open('input.txt').read()
         .replace('addx', 'noop\naddx')
         .replace('noop', 'addx 0')
         .splitlines())
x = 1
crt_x = 0
for line in lines:
    addx = int(line[4:])
    # Using a distance formula here:
    p = '#' if abs(x - crt_x) <= 1 else '.'
    print(p, end='')
    crt_x = (crt_x + 1) % 40
    print('\n' if crt_x == 0 else '', end='')
    x += addx

Another low-hanging fruit is to combine the two print statements:

lines = (open('input.txt').read()
         .replace('addx', 'noop\naddx')
         .replace('noop', 'addx 0')
         .splitlines())
x = 1
crt_x = 0
for line in lines:
    addx = int(line[4:])
    p = '#' if abs(x - crt_x) <= 1 else '.'
    crt_x = (crt_x + 1) % 40
    # Combining both print() statements:
    print(p + ('\n' if crt_x == 0 else ''), end='')
    x += addx

Golfing the if-else expressions

We’ve simplified quite a bit so far, but one thing to notice is that the if-else expressions require quite a lot of bytes to represent.

A neat way to get rid of if-else expressions is to group the two possible outcomes into an array, where the first array element contains the False branch's expression, and the second array element contains the True branch's expression. Then, you can index into that array using the conditional bool result, since array[False] works the same as array[0] and array[True] works the same as array[1] due to type conversion.

So, if we have some code that looks like this:

true_branch if condition else false_branch

We can rewrite it like this:

[false_branch,true_branch][condition]

But wait — there’s more! If false_branch and true_branch are both single-character strings, we can write a compact string literal containing the two characters, instead of an array with two separate strings. So instead of writing ['A','B'][condition] we can write 'AB'[condition].

In our case, the optimization looks like this:

'#'if abs(x-crt_x)<=1 else'.'
'.#'[abs(x-crt_x)<=1]######## 8 bytes saved!

Note, we even applied a trick here in the first line: the '#'if and else'.' in the first line are omitting an optional space. But we still save 8 bytes by rewriting using array indexing.

So, let’s apply that trick to our code so far:

lines = (open('input.txt').read()
         .replace('addx', 'noop\naddx')
         .replace('noop', 'addx 0')
         .splitlines())
x = 1
crt_x = 0
for line in lines:
    addx = int(line[4:])
    # Condensing "if ... else":
    p = '.#'[abs(x-crt_x)<=1]
    crt_x = (crt_x + 1) % 40
    print(p + ('\n' if crt_x == 0 else ''), end='')
    x += addx

So, can we apply this to the second if-else as well?

Turns out, we can’t, because we’re dealing with an empty string in the else case 😕 So we’d be stuck using a list like ['','\n'] instead of just '\n' .

But we can apply an even more interesting trick here: we can take a slice into the string.

The idea is that if the crt_x value is zero, then we want to take a slice starting with index 0, like '\n[0:], which is just '\n'. Otherwise, we know that crt_x is greater than or equal to 1 (since it can't be negative). In that case, taking a slice starting anywhere greater than or equal to 1 will yield an empty string. So the pattern is that \n[0:] evaluates to '\n', but then '\n'[1:] and '\n'[2:] (and so on) evaluate to ''.

Check out the byte savings:

''if crt_x else'\n'
'\n'[crt_x:]####### 7 bytes saved!

Here’s the whole program again so far:

lines = (open('input.txt').read()
         .replace('addx', 'noop\naddx')
         .replace('noop', 'addx 0')
         .splitlines())
x = 1
crt_x = 0
for line in lines:
    addx = int(line[4:])
    p = '.#'[abs(x-crt_x)<=1]
    crt_x = (crt_x + 1) % 40
    # Condensing "if ... else":
    print(p + '\n'[crt_x:], end='')
    x += addx

OK, now before we start making the code even harder to read, lets zoom out a bit and look for some bigger-picture optimizations we can make.

More input transformations

Recall that earlier, we transformed the input so that it consists of only addx instructions. But that came at a cost of some verbose replace() calls. Can we shorten those?

Well, one observation is that the letter ‘a’ only appears in ‘addx’, so the following are equivalent:

replace('addx', 'noop\naddx')
replace('a', 'noop\na')###### 6 bytes saved!

Another observation is that our code right now only works if all of the instructions look like 'addx N' where N is a number. But we're spending quite a bit of code on making sure all lines adhere to that pattern.

To reduce the amount of code here, we need an important insight: if a number appears in the current line, it will always appear after index 4. This is because the strings “addx” and “noop” both have lengths of at most 4.

So, this means we can delete the call to replace('noop', 'addx 0') entirely! We just need to handle the possibility of the number being an empty string (''), so our conversion int(line[4:]) now becomes int(line[4:] or 0). So we’ve added some code, but it’s a net win overall:

# Removing "replace('noop', 'addx 0')":
lines = open('input.txt').read().replace('a', 'noop\na').splitlines()
x = 1
crt_x = 0
for line in lines:
    # Adding "or 0" to allow noops:
    addx = int(line[4:] or 0)
    p = '.#'[abs(x-crt_x)<=1]
    crt_x = (crt_x + 1) % 40
    print(p + '\n'[crt_x:], end='')
    x += addx

One thing to note is that Python allows referencing out-of-bounds indexes when taking a slice and it will return an empty string. This means that line[4:] will return an empty string whether the line is "noop" or if the line is blank. So we actually don't even need to replace 'a' with 'noop\na'. We can just replace it with '\na':

# Removing "noop" here:
lines = open('input.txt').read().replace('a', '\na').splitlines()
x = 1
crt_x = 0
for line in lines:
    addx = int(line[4:] or 0)
    p = '.#'[abs(x-crt_x)<=1]
    crt_x = (crt_x + 1) % 40
    print(p + '\n'[crt_x:], end='')
    x += addx

The last interesting observation is that we can remove the + in the print() statement by taking advantage of the fact that the print() statement already concatenates the end argument onto the first argument that we're printing:

lines = open('input.txt').read().replace('a', '\na').splitlines()
x = 1
crt_x = 0
for line in lines:
    addx = int(line[4:] or 0)
    p = '.#'[abs(x-crt_x)<=1]
    crt_x = (crt_x + 1) % 40
    # Letting print() concatenate
    # via the "end" arg:
    print(p, end='\n'[crt_x:])
    x += addx

Now the remaining optimizations are all pretty mechanical.

Minifying the result

Next up, we’ll do a speed round of easy minifications, which are all very mechanical and could probably be done using some sort of minification tool.

Our solution so far is 234 bytes.

Shortening variable names to onecharacter brings this to 194 bytes (-40):

s = open('input.txt').read().replace('a', '\na').splitlines()
x = 1
c = 0
for l in s:
    a = int(l[4:] or 0)
    p = '.#'[abs(x-c)<=1]
    c = (c + 1) % 40
    print(p, end='\n'[c:])
    x += a

Inlining s reduces this further to 188 bytes (-6):

x = 1
c = 0
for l in open('input.txt').read().replace('a', '\na').splitlines():
    a = int(l[4:] or 0)
    p = '.#'[abs(x-c)<=1]
    c = (c + 1) % 40
    print(p, end='\n'[c:])
    x += a

Trimming whitespace within each line brings us down to 159 bytes (-29):

x=1
c=0
for l in open('input.txt').read().replace('a','\na').splitlines():
  a=int(l[4:]or 0)
  p='.#'[abs(x-c)<=1]
  c=(c+1)%40
  print(p,end='\n'[c:])
  x+=a

Converting to compound statements gets us to 148 bytes (-11):

x=1;c=0
for l in open('input.txt').read().replace('a','\na').splitlines():a=int(l[4:]or 0);p='.#'[abs(x-c)<=1];c=(c+1)%40;print(p,end='\n'[c:]);x+=a

Cheating a bit!

As a finishing touch, we can shorten open('input.txt') by changing how we read the input. Instead of reading from the input.txt file, we can read the file contents from stdin, which on Unix-like systems is file descriptor 0. Python's open() API treats integer values as file descriptor numbers, so we can write open(0) here:

x=1;c=0
for l in open(0).read().replace('a','\na').splitlines():a=int(l[4:]or 0);p='.#'[abs(x-c)<=1];c=(c+1)%40;print(p,end='\n'[c:]);x+=a

(This one was arguably cheating, since it’s sort of an OS-specific trick 😅)

Drum roll please…

The final program is only 138 bytes in length! 🎉

There are probably even more optimizations that can be made, maybe even using a totally different high-level approach. But this is what I came up with, and I hope you learned something from this example!

I also recommend checking out the Reddit thread for Day 10, which has lots of other cool solutions. I wouldn’t be surprised if there are Python solutions in that thread that are even shorter than mine.

My favorite from the thread is the Python solution here which implements OCR on the output so that it prints the letters in plain text rather than ASCII art. Super cool!