# 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=0for 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 = 1crt_x = 0for 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 = 1crt_x = 0for 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 = 1crt_x = 0for 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 = 1crt_x = 0for 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 = 1crt_x = 0for 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 = 1crt_x = 0for 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 = 1crt_x = 0for 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 = 1crt_x = 0for 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 = 1crt_x = 0for 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 = 1crt_x = 0for 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 = 1crt_x = 0for 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 = 1crt_x = 0for 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 = 1crt_x = 0for 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 = 1c = 0for 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 = 1c = 0for 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=1c=0for 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=0for 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=0for 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 😅)