Advent of Code - 2019 - Day 5 - 6

The fifth problem marked the return of Intcode machine. Now it should be extended with immediate arguments, as well as input, output, jumps and conditionals. Not being very computationally expensive it was entirely straightforward to extend the solution from by adding plumbing for inputs and outputs and adding the new opcodes.

At the end I experimented a bit with various optimizations, and I noticed that more aggressive inlining sometimes made a difference. For example inlining all the calls to val/3 saves 6.5% of the gas. Still today’s problems would fit comfortably within a microblock with 97k/117k gas for the part 1/part 2.

My solution can be found here - good luck with your solving!

4 Likes

The sixth problem included a fairly
simple graph/tree problem. In the first part you were supposed to find the
total depth of all nodes in the tree and in the second part you had to find the
common ancestor of two nodes and calculate the distance between them (through
that common ancestor).

This problem showed a shortcoming of Sophia, we are missing some functions on
string, to handle the raw input data we would have needed String.split
which is not yet there. So
we did some preprocessing of the input data (you could do this and write it to
the state, so not to much cheating I think).

The naive implementation of part 1 became pretty expensive 3.5G gas and more
than 15 seconds runtime, but after adding some memoization (using the state!)
the solution actually fits in a block at 5.7M gas. Part 2 was a lot easier and
only require 1.6M gas.

My solution is here

1 Like

Yeah, day 5 was straight forward. Yet you seem to outperform my solution by 6x.

My solution is here

Runtime:

39771 steps / 627661 gas / 1543527 reductions / 37.41ms
Store:
  #{}
16574641
([email protected])13> aefa_sophia_test:run_file("day_05/sophia/2019_day_5.aes", "solve_part2", []).
43387 steps / 699895 gas / 1643284 reductions / 38.77ms
Store:
  #{}
15163975

My solutions are pretty slow, I didn’t optimize it yet. However, reading your notes I have the feeling I need to read up on state and stateful functions :slight_smile:

My solutions are here