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):
- make sure we can make the next two jumps
- make sure we can make this jump
- if we’re ok to jump, but there is no hole… don’t
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: https://gist.github.com/ferd/a5a830d2ca58b10013cf1abe8271137f
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.
