Advent Of Code 2018

Jan 2019
    !
  -~*~-
   /!\
  /%;@\
 o/@,%\o
 /%;`@,\
o/@'%',\o
'^^^N^^^`

Advent of Code is an annual programming competition to complete 25 challenges in December. It’s a way grow as a programmer, through solving problems and reveiwing others code. In this article I will cover two things I learned about this year and try to convince you to join next years competition.

1. Assembly Language

I have always be interested in how computers work, see building a transistor from scratch. I have never had the chance to program in assembly. That changed on Day 16, the challenge was to run a new programming language called elf code. Elf code looked almost identical to assembly.

4 0 2 0
13 2 0 2
2 2 3 2
4 3 2 3
3 3 2 2
13 2 1 2
6 2 1 1
10 1 2 3
4 2 3 0
13 1 0 1
2 1 1 1

The first number is the opcode, which could represent 1 of 16 operations, ‘add’, ‘mul’, ‘mov’. The second and third were inputs and the forth was what register to use for the output.

First, I wrote the code in python. It turned out way too slow, even with pypy and a better data structure. I got it down to 1/10th of the original but after 3 hours, I stopped it.

To solve it, you need to watch how the elf code is being executed, find the pattern and simplify the logic. I was curious if this could be completed by running right on the hardware.

Using an intermeddiate step to C, Below is a snippet of the assembly. ‘;’ is a comment. The ‘l01’, ‘l02’, ‘l03’ and ‘l07’ are labels. For example the first command is jmp l17, which is jump to label l17.

      jmp       l17           ;  L00: goto *jump_table[0+16+1]; //addi 3 16 3
l01:  mov       r11, 1        ;  L01: reg[1] = 1; //seti 1 2 1
l02:  mov       r12, 1        ;  L02: reg[2] = 1; //seti 1 1 2
l03:  mov       rax, r11      ;  L03: reg[5] = reg[1] * reg[2]; //mulr 1 2 5
      mov       rbx, r12      ;
      imul      rax, rbx      ;
      mov       r15, rax      ;
      cmp       r15, r14      ;  L04: reg[5] = reg[5] == reg[4]; //eqrr 5 4 5
      sete      al            ;  Grab the flag
      movzx     r15, al       ;  Move the flag to r15 extends with zeros
      je        l07           ;  L05: goto *jump_table[reg[5] + 5 + 1]; //addr 5 3 3
      jmp       l08           ;  L06: goto *jump_table[6 + 1 + 1]; //addi 3 1 3
l07:  add       r10, r11      ;  L07: reg[0] = reg[1] + reg[0]; //addr 1 0 0

In the end the assembly was not fast enough, even being roughly 20x faster than my original python implementation.

Along the way I learned x86-64 commands, registers, flags and jump commands. I also learned why assembly is not written. This code ran about as fast as the C code that I made but not being portable between different computers and being somewhat hard to follow. Below is the code to write a single character to the screen.

print:
      mov       [value], r10     
      mov       rax, 1           ; system call for write
      mov       rdi, 1           ; file handle 1 is stdout
      mov       rsi, value       ; address of string to output
      mov       rdx, 8           ; number of bytes
      syscall                    ; invoke operating system to do the write
      mov       rax, 60          ; system call for exit
      xor       rdi, rdi         ; exit code 0
      syscall                    ; invoke operating system to exit 

All the code can be found on my github

2. Python Imports

Most of the time I avoid python imports, I found the default data types do the job. During these challenges, I have come to love defaultdict, copy, dequeue. Also networkx for building networks and re for regular expressions

defaultdict - Having a set value for when nothing exist is a very useful feature

somedict = {}
print(somedict[3]) # KeyError

someddict = defaultdict(int)
print(someddict[3]) # print int(), thus 0

copy - Because python calls list by reference this is useful to keep things functional

import copy
copy.copy(x)
copy.deepcopy(x)

dequeue - A double-ended queue, this is useful for when rotation is needed with a rotate function

d = deque(xrange(10))
d.rotate(2)

networkx - This was useful for all types of graph equations. Shortest path was used many times

graph = networkx.Graph()
# ...adding nodes...
result = networkx.shortest_path(graph)

re - This is a very popular library I have tried to avoid it.

Some people, when confronted with a problem, think “I know, I’ll use regular expressions.” Now they have two problems.

Jamie Zawinski

Now I follow Jeff Atwoods take on them. They are amazing but only when you use them sparsely. As an example, the line below grabs the numbers from the a line of text and converts them to integers

list(map(int, re.findall(r'-?\d+', line)))

During the challenge, I read as much as I coded. Reading other peoples code was enlightening. You saw how they approached the problem and what trade-offs they chose.

Thank you Eric Wastl for creating advent of code and everybody that shared their solutions online. I learned a lot.