Advent of Code 2019 - Day 2

Learning Questions & Discussions Coding Challenges
,
42

Very late myself, here’s mine: https://github.com/dimitarvp/aoc2019.ex/blob/master/lib/day2.ex

Rather naive solution using the for comprehension with a filter for part two, finishes in ~85ms (milliseconds).

Figured it was slow and added another version with binary search which finishes in ~750us (microseconds), a ~113 times improvement.

Pretty happy with the result, would welcome criticism!

EDIT: DISCLAIMER: Borrowed the pretty neat short variable names from @bjorng’s solution. I liked them a lot and used them. :slight_smile:

1 Like
43

There’s another thing, you use for... and pipe it to Enum.find while for ... with a filter is faster (on my machine and exercise implementation at least).

44

I discovered that the first element in the output memory is monotonically increasing so I cheated by introducing an alternative: a binary search. It’s crazy fast, <1ms:

  def bsearch(mem, range, expected) do
    pos = Bitwise.bsr(range.first + range.last, 1)
    {noun, verb} = {div(pos, 100), rem(pos, 100)}

    case exec(mem, noun, verb) do
      ^expected ->
        {noun, verb}

      less when less < expected ->
        bsearch(mem, (noun*100 + verb)..range.last, expected)

      greater when greater > expected ->
        bsearch(mem, range.first..(noun*100 + verb), expected)
    end
  end

  def part2_with_binary_search() do
    mem = memory()
    {noun, verb} = bsearch(mem, 0..9999, 19690720)
    noun*100 + verb
  end
3 Likes
45

In my solution that change doesn’t improve performance. In fact, the code is slower, because it always calculates all outputs, instead of stopping early when the result is found.

46

Here’s my day 2 solution: https://github.com/axelson/advent_of_code/tree/master/day2/lib

My little interpreter appears to be much more verbose than others, but I must say that I do like modeling the program state as a struct.

47

Wow, really highly efficient solution! I love it.

48

Is there syntactic sugar for List.replace_at? E.g.:

    test_program =
      @program
      |> List.replace_at(1, noun)
      |> List.replace_at(2, verb)
49

I try to keep it pure functional, and avoid the need for ‘memory’. (?) My part 2:

  @program [1,12,2,3,1,1,2,3,1,3,4,3,1,5,0,3,2,10,1,19,1,19,9,23,1,23,6,27,2,27,13,31,1,10,31,35,1,10,35,39,2,39,6,43,1,43,5,47,2,10,47,51,1,5,51,55,1,55,13,59,1,59,9,63,2,9,63,67,1,6,67,71,1,71,13,75,1,75,10,79,1,5,79,83,1,10,83,87,1,5,87,91,1,91,9,95,2,13,95,99,1,5,99,103,2,103,9,107,1,5,107,111,2,111,9,115,1,115,6,119,2,13,119,123,1,123,5,127,1,127,9,131,1,131,10,135,1,13,135,139,2,9,139,143,1,5,143,147,1,13,147,151,1,151,2,155,1,10,155,0,99,2,14,0,0]
  @desired_output 19690720
  @nouns 0..99
  @verbs 0..99

  def part2 do
    Util.cartesian_product(@nouns, @verbs)
    |> Enum.find(&is_solution?/1)
  end

  def is_solution?({noun, verb}) do
    @program
    |> List.replace_at(1, noun)
    |> List.replace_at(2, verb)
    |> execute
    |> Enum.at(0) == @desired_output
  end

  # etc.
50

My implementation of the VM is purely functional, and I doubt you’ll be able to get rid of the necessity to keep the altered memory around. Keeping it in the original link though will massively slow down your VM. You should use a datastructure with faster random access and random “write”.

1 Like
51

You can use pattern matching.

[head, _, _ | rest] = @program
test_program = [head, noun, verb | rest]
1 Like