Advent of Code 2019 - Day 9

Note: This topic is to talk about Day 9 of the Advent of Code 2019.

There is a private leaderboard for elixirforum members. You can join it by following this link and entering the following code:

39276-eeb74f9a

1 Like

Here is my solution.

5 Likes

Nothing too exciting in my code here. My intcode computer has overall been a bit of a mess due to not going back and cleaning it up.

This problem really showed some issues in how I had implicit rules baked into my code. I was not putting arg 3 through any type of mode checking, because it was always itself previously. That bit me hard today, and I had to spend a ton of time debugging why my stuff wasn’t working.

4 Likes

I got top 80-90! Here is the meat of my solution.

I specifically designed my intcode interpreter to allow rapid extension of it, I even spent an hour cleaning it up the other day, seems like that paid off.

It’s pretty cool to see how well a recursive interpreter of a self-modifying memory/code VM actually ends up working with immutable memory. Very fun.

I would also be curious about the timings people got on the second part. Mine was 3.860 seconds (timed from the shell).

5 Likes

Wow!!! Great work. That’s super speedy.

I’m honestly surprised here. I feel like I didn’t do anything special to make mine fast, but it is significantly faster than 3s.

➜  advent_2019 git:(master) mix test test/solutions/9_test.exs
...

Finished in 0.6 seconds
3 tests, 0 failures

Do you use lists in your solution?

edit: I see that you use :array. I believe that switching over to an index based map would speed yours up significantly. I’ve learned to very rarely use [] or :array, from last year’s AoC.

2 Likes

To be clear I have used elixir less than a week and know nearly nothing about optimizing it (or erlang), I use advents of code to learn new languages.

I was worried a list would be too slow because of the O(n) access and couldn’t find good information on optimization. I figured the erlang :array would probably be better than that.

Could you point me to the documentation for what you are describing?

Edit: Is it simply just using integers in a map?

Both parts finish in 0.1 seconds:

$ mix test
...

Finished in 0.1 seconds
3 tests, 0 failures
1 Like

Looking at your code I feel like an idiot for missing that I can use the function pattern matching as a sort of multi-method. I may need to do some additional refactoring.

I’ll still have to always write a forwarding method, but it might make it a cleaner copy paste in the end rather than doing what I am now with the explicit forwarding.

Hm, I’m wrong here. I tried to do a benchmark with :array.get and :array.set vs Map functions and they were about the same. I’m not sure why it would be so much slower without digging in more.

1 Like

I suspect my use of .exs and dynamically loading my libraries with Code.require_file("../day07/el.ex", __DIR__) might have something to do with it.

I haven’t learned mix yet…

Anyway thanks for the feed back! It was very useful.

Edit: some other possible reasons:

  • Pattern matches (wide ones too) in my main loop?
  • Probably not the right way of pattern/matching forwarding?

I’ll have to play around with it.

This is my solution. So far I strived to keep the code clean, and this payed off, b/c the changes to the machine code were minimal. I finally extracted Intcode interpreter into a separate module, but I still keep that module code in the same file as the solution, so others can easily read the entire solution from a single file. As for the perf, the 2nd part takes about 500ms on my machine.

3 Likes

So, uh, what’s the catch with part 2? I just used my part 1 solution, and it worked.

Eric Wastl (the creator of AOC) doesn’t want to reveal that yet:

https://www.reddit.com/r/adventofcode/comments/e85b6d/2019_day_9_solutions/fa9e8av/?context=3

Here’s my solution powered by the revised homemade intcode computer. :joy:

It took 570ms to finish part2.

It cost me ten minutes or so to debug. What surprised me was that it was a REAL diagnose program, pointing out that I had something wrong with executing opcode 3. It was true, I did not support mode 2 for reading at that moment. :cold_sweat: What an ingenious puzzle!

1 Like

Interestingly, my solution is using :array and runs relatively quickly.

$ mix test test/day9_test.exs
..

Finished in 0.4 seconds
2 doctests, 0 failures

It’s working but it’s really slow : https://github.com/cblavier/advent/blob/master/lib/2019/day5/day5.ex

Any idea of what I should improve in my code?
(my guess is that I’m using a lot of binaries instead of integers)

I had a glance, it seems that List.replace_at/3 is used in write_memory. This is quite slow. If a list is under random access and update frequently, Map is preferred.

1 Like

Just finished mine. As you guys said, the refactoring made to the VM in day5/7 definitively paid off!

Follow the @qhwa suggestion. Use a Map to represent the memory of the VM. Keys are addresses and values are intcodes.
After seeing the code of the people here, I’ve decided to just use a struct with memory, ip, relative_base, input, output, etc. keys. In this way each function just takes a vm (with some other arguments) and returns the updated VM. This makes easier to use pipes in the code.

1 Like

Is there a benchmarking tool that benchmarks the code speed giving a score that’s independent from the machine’s speed?

Not that I’m aware of. You’d need to run both versions on the same machine.

As an aside, I suspect that the slowness of my solution is due to the usage of streams. Moving to plain recursion might help, but I don’t even want to bother to check this because the execution time is ATM good enough. If at some later challenge it starts causing problems, I’ll see about optimizing it :slight_smile:

2 Likes