# Advent of Code 2019 - Day 21

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

Today was interesting. My solution is here.

For part 1 I just started walking, and then covering one failing case at a time, minimizing the boolean expression as I went along.

For part 2 I spent some considerable time drawing Karnaugh maps, and even thinking about implementing a boolean expression reducer. Finally, I started from scratch, drawing one failing pattern at a time, and trying to optically see the smallest amounts of conditions needed to cover them all, which ultimately brought me to the solution.

3 Likes

Nice one @sasajuric !

I went the other way and tried to find a generic solution that jumps whenever possible and required. Donâ€™t know if it would cover all the possible land shapes, but it worked well for me, though a bit longer.

``````    # if A is hole set T to true
NOT A T
# set J to true if A was hole
OR T J
# same for B
NOT B T
OR T J
# same for C
NOT C T
OR T J
# Now J is true if there is a hole incoming in either A, B or C
# We will jump only if we can land on D
AND D J
# Now J is true if hole incoming and D is ground.
# We must ensure that we can also jump from D to H
#                     or move from D to E.
# First we set T to false if J is true
NOT J T
# Then we will check if H is ground or E is ground
# and set T to true in either case
OR H T
OR E T
# If J was false, and T was set to true, T is still true,
# meaning that H or E are ground, although they may not be ground.
# But still, we will only jump if a hole is comming, requiring
# that bot J and T are true, and set J to true if so.
AND T J
RUN
``````
2 Likes

I had a bit of a slow start trying to work it out. I felt pretty intimidated by it at first. Eventually, I just dug in and treated it like TDD. That was sort of cool imo, because the program was executing test cases.

I basically did what @sasajuric did for pt1. Except I started with their triple jump and then extended the other failing cases as I went. https://github.com/sb8244/advent-of-code-2019/blob/master/test/solutions/21_test.exs#L8

I was a bit scared in pt2 because I had maxed out my program length in 1. I ended up just scrapping it and starting fresh. Honestly, I feel like it was easier and the end result is actually shorter. https://github.com/sb8244/advent-of-code-2019/blob/master/test/solutions/21_test.exs#L45

Edit: I just compared @sasajuric program and mine. I think I can use the AND D at the end of the program to shorten mine a bit. Nice!

3 Likes

I solved part 1 by myself in my head while away from my computer. (My solution is not the shortest possible. See the comment in my code.)

I did not solve part 2 by myself. I spent hours looking at the droid failing and tweaking my boolean expression. When my expressions started to hit the 15 instruction limit, I gave up and tried to find a hint on reddit. Unfortunately the first post I looked into contained a direct spoiler.

Here is â€śmy solutionâ€ť.

2 Likes

Nice! I have a feeling that a generic solution could be derived automatically, rather than by hand. The idea is to generate all solvable combinations, and from that compute a table of valid jumps which would solve every possible valid combination. Once we have such table, we could build a logical table, do boolean reduction, and convert to springscript. Not sure if the idea is actually solid, but intuitively it seems possible. I might explore this later.

Yeah, `AND D` was a big breakthrough for me after banging at the solution for some time I finally figured out that doing this at the end is enough to avoid the â€śgame-over by jumpâ€ť, and that I can forget about D in all the previous clauses. As a result, I only had to somehow accommodate â€śchained jumpsâ€ť (e.g. `#..##..#`). This also made it slightly easier to seek for common patterns.

3 Likes

I donâ€™t know whether my input was easier or I stumbled upon a simple solution, but I found this one pretty easy (all the actual code was just brought in from earlier daysâ€™ work).

For Part 1, all I did was jump anytime there was a gap ahead and a safe landing spot. I ran it to see what would happen. Surprisingly, that was enough!

For Part 2, I ended up with these three steps (12 instructions):

1. make sure we can make the next two jumps
2. make sure we can make this jump
3. if weâ€™re ok to jump, but there is no holeâ€¦ donâ€™t

Day 21 solution

That one was kind of easy for me! I donâ€™t know if itâ€™s my input specifically but I found part 1 straightforward: only jump if D is free and thereâ€™s a hole in ABC.

Part 2 gave the bot more sight, but essentially I took my rules for part 1, added that you canâ€™t jump if thereâ€™s a hole in H, and after a few failures, I got output showing me that having some solid ground in E-G as well could be useful. I had all of E-H in a check for â€śI need ground there somewhereâ€ť, which failed, so I then just took out FG after successive failures (and was left with E|H) to check properly.

This is finally a short video (might still be processing when posting this):

P.S. that message passing stuff works well for the intcode computer!

1 Like

After taking another look, I noticed that part 1 can be coded using only one output register:

``````OR A J
AND C J
NOT J J
AND D J
``````

heh that would have been useful. Spent a while figuring out how to reset `T` to `false` to handle the second problem without dropping the first, though I eventually just found a way that worked for my needs (using `NOT J T` because if Iâ€™m not jumping, well Iâ€™m not jumping anyway)

Yep, this was the last thing I checked for part 2 (but in reverse, so even easier):

I used that same trick during my intermediate experiments In general I had fun playing with this limited assembly and scarce resources available.