Advent of Code 2019 - Day 21

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.

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

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. advent-of-code-2019/test/solutions/21_test.exs at master · sb8244/advent-of-code-2019 · GitHub

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. advent-of-code-2019/test/solutions/21_test.exs at master · sb8244/advent-of-code-2019 · GitHub

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!

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”.

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.

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):

Source at: day21.erl · GitHub

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

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):