~sgiath/aoc-2019

Advent of Code 2019
Add day 14
Add Day 10 Task 2 solution and Day 13 template
Add Day 12 task 2 solution

refs

master
browse  log 

clone

read-only
https://git.sr.ht/~sgiath/aoc-2019
read/write
git@git.sr.ht:~sgiath/aoc-2019

You can also use your local clone with git send-email.

#Advent of Code 2019

Author: Filip Vavera FilipVavera@sgiath.dev

#How to run the solution?

Run specific day:

mix day1
mix day2
...

Or you can run them all in one:

mix all

If you want to run it against different inputs you can replace input files in priv/input/ folder or change how input files or other inputs are loaded in AdventOfCode.Inputs module.

#How to test?

I am trying to use Test Driven Development approach so code also contains unittests. You can run them with:

mix test

This prooved to be quite useful right on day 5 when I extended code from day 2 and I used these tests to ensure it is still backwards compatible with day 2 task.

#Benchmark

Operating System: Linux
CPU Information: Intel(R) Core(TM) i7-6700K CPU @ 4.00GHz
Number of Available Cores: 8
Available memory: 31.33 GB
Elixir 1.9.4
Erlang 22.1.8

Name                    ips        average  deviation         median         99th %
Day 1, Task 1      254.36 K        3.93 μs   ±390.05%        3.75 μs        6.76 μs
Day 1, Task 2       34.74 K       28.78 μs    ±17.99%       27.34 μs       49.53 μs

Name                    ips        average  deviation         median         99th %
Day 2, Task 1       23.73 K      0.0421 ms    ±11.74%      0.0410 ms      0.0593 ms
Day 2, Task 2     0.00906 K      110.33 ms     ±3.04%      109.25 ms      125.61 ms

Name                    ips        average  deviation         median         99th %
Day 3, Task 1          7.88      126.94 ms     ±6.58%      126.26 ms      151.22 ms
Day 3, Task 2          4.38      228.42 ms     ±7.49%      224.92 ms      267.17 ms

Name                    ips        average  deviation         median         99th %
Day 4, Task 1         13.83       72.30 ms     ±2.06%       71.77 ms       78.73 ms
Day 4, Task 2         13.65       73.27 ms     ±2.31%       72.82 ms       83.78 ms

Name                    ips        average  deviation         median         99th %
Day 5, Task 1        9.74 K      102.69 μs     ±8.08%      100.21 μs      134.88 μs
Day 5, Task 2        5.77 K      173.18 μs     ±8.18%      167.86 μs      227.82 μs

Name                    ips        average  deviation         median         99th %
Day 6, Task 1        3.70 K        0.27 ms    ±18.25%        0.26 ms        0.52 ms
Day 6, Task 2       0.125 K        7.99 ms     ±8.43%        7.73 ms        9.97 ms

Name                    ips        average  deviation         median         99th %
Day 7, Task 1          4.18      239.33 ms    ±25.74%      232.08 ms      350.92 ms
Day 7, Task 2          1.18      847.70 ms    ±20.22%      839.78 ms     1090.36 ms

Name                    ips        average  deviation         median         99th %
Day 8, Task 1        1.98 K      504.69 μs     ±4.78%      501.22 μs      549.97 μs
Day 8, Task 2        1.51 K      664.31 μs     ±5.55%      659.70 μs      793.36 μs

Name                    ips        average  deviation         median         99th %
Day 9, Task 1        1.31 K        0.76 ms     ±7.80%        0.76 ms        0.96 ms
Day 9, Task 2     0.00112 K      896.75 ms     ±0.43%      895.46 ms      903.92 ms

Name                     ips        average  deviation         median         99th %
Day 12, Task 1        439.25        2.28 ms     ±6.24%        2.25 ms        2.66 ms
Day 12, Task 2          2.06      486.18 ms     ±0.96%      485.75 ms      493.84 ms

#Notes

#Day 2

I implemented Intcode computer inside that day module but extract it and edit later when Day 5 arrived. Original computer was much simpler. The code can be found in Git history.

I also added Flow later to speed up parameters finding. Original time was around 1s to find correct parameters. Flow changed it to cca 300ms and switching from List to :array for computer memory representation changed it to 110ms.

#Day 5

Original computer used List instead of :array for memory representation and I noticed that my solution was much slower than https://github.com/sevenseacat/advent_of_code_2019 solution despite other solutions beeing faster. I saw that this solution uses :array for memory representation so after some research I learned that :array has constant access time in contrast to List which is actually linked list. I give it try and immediatelly my solution was 3x faster.

I decided to treat input and output to the program as static parameters. If the computer will be used later with more complicated inputs I plan to rewrite it to use Process.get/1 and Process.set/2 to pass parameters between computer and main process.

#Day 6

I used Graph library for task 2 and its function Graph.dijkstra/3 and I feel like it is cheating so maybe I will rewrite it later.

#Day 7

It didn't take long before I had to rewrite the Intcode computer. My first design didn't take into account dynamic inputs - all inputs were given to the program before it started. This redesign was much larger than anticipated and I almost abandoned it. From the start I knew that Elixir process messaging is the right answer - yeah of course I could stop the program on input, remember the Instruction Poiner, get the input and resume the program from last state but I had a feeling that this design will backfire to me later and I wanted to do it righ. So Elixir process messaging. I never extensively work with it - yeah I send one or two messages here and there but I never designed actuall workflow with them so it was pain. But finally I get it working - Intcode instance is running as GenServer and you can load the instance without actually running the program. Program also expect 3 other parameters pid from the process where input is generated, pid from the process where output should be send and pid from the process where secondary output will be sent.

#Day 8

Quite easy but it took me a long time before I realized that I should actually print the final image. I was trying to decode the binary "message" of the image without realizing that it is and actuall image.

#Day 9

With my new design of the Intcode computer it was exceptionaly easy to solve this problem.