Advent of Code 2019 - Day 17

Learning Questions & Discussions Coding Challenges
,
1

Note: This topic is to talk about Day 17 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

2

Hardcoded part 2 solution, oh well. It’s much easier to solve this manually than to write code that does it.

3

Can’t figure out why my part1 output is wrong :exploding_head:

Can you tell me what is your part1 result for my puzzle input? https://gist.github.com/cblavier/b92d4bedf0bf12268ee9e25fef694cd5

I suspect a bug in my intcode VM … :frowning_face:

4

Giving a hint, just in case you have the same bug as I had in my interpreter (and took a while to figure out). Specifically I constructed the output by doing [x | xs]. This however meant the output was reversed, but as it happens, this wasn’t really an issue until Day 17 part 1 (seriously, I only realized the issue now, as it happens, no previous tasks cared about whether the output was reversed or not).

If you have two newlines at the start of an output, that’s the issue. Those should be at end, not at the start.

2 Likes
5

:sob:

(thanks, it was indeed the issue !!!)

6

My solution for day 17.

When I did part 1, I expected to have to move the robot from start to finish for part 2, but the question was not what I expected. I calculated the movements by hand and pushed the data manually.

7

Thank you so much, I couldn’t figure out why the tests were working but the puzzle input was not!

8

Here is my solution.

For part 2 I wrote a path finder function. (It would probably been faster to read out the path manually from printout in part 1, but what’s the fun in that?) My first attempt produced a too long path that I could not fit in the robot’s limited program space. I had to adjust the path finder to always going straight if possible so to avoid unnecessary turns. That shortened the path so I that could fit in the robot’s program memory.

If I hadn’t already been spending so much time on this puzzle, it would have been function to try to automatically split the path into the different parts of the robot’s program memory. I decided to split the path manually.

9

I couldn’t resist the temptation to add an automatic splitter of the robot program.

Here is the updated code and here is the splitting code.

10

That’s impressive! Great work on doing the actual automated solution here.

I don’t think I did anything special—it’s a pretty standard solution. I was a bit frustrated because I knew the right path to do when only 25 people had solved both parts. But I had flipped my graph around (r, c iteration instead of c, r) and it completely changed my result. So I spent about 3 hours on it in the end. Once I realized the inversion mistake, I had the answer in about 10 minutes :frowning:

1 Like
11

My solution

I also created an automated solution after first doing it manually. Manually was definitely faster :stuck_out_tongue:

12

Wow, this was very finicky!

I refused to solve the problem manually. It was clear to me in the morning that it’s not tricky in the algorithmical sense, but that there will be many fine-print details to pay attention to.

I ultimately solved it in a brute-force fashion. I did a depth-first search to find complete paths, then on each path I look for a valid program. This boils down to trying all possible triplets of main routines until I’m able to encode the entire thing into three routines, none of which exceeds the desired length.

The code is available here. It could use a bit more of a cleanup, can’t say it’s my finest hour :slight_smile:

2 Likes
13

I’m stuck on part 2.

I want to find the solution with program. So I made a path finding function. It outputs all (in my mind) possible routes, in which another function searches for the ABC pattens.

It works on the small examples provided, but sadly not with my puzzle input. I think there might be some issues with my path finding algorithm. However I couldn’t figure it out in hours.

The code looks ugly at this moment. :joy:

rewriting it.

14

Did the entire thing fully automated using some brute-force probabilistic searches to break down the full path into subroutines and then re-combine the valid subroutines into a sequence of calls that re-create the original program.

One of my biggest struggles there was just remembering the limitations of my intcode computer in that it only handles integers and not strings!

15

Turns out my pattern searching approach was not working correctly. Finally get it perfectly working! Tired but really happy!