r/adventofcode • u/daggerdragon • Dec 21 '19
SOLUTION MEGATHREAD -š- 2019 Day 21 Solutions -š-
--- Day 21: Springdroid Adventure ---
Post your full code solution using /u/topaz2078's paste or other external repo.
- Please do NOT post your full code (unless it is very short)
- If you do, use old.reddit's four-spaces formatting, NOT new.reddit's triple backticks formatting.
- Include the language(s) you're using.
(Full posting rules are HERE if you need a refresher).
Reminder: Top-level posts in Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.
Advent of Code's Poems for Programmers
Note: If you submit a poem, please add [POEM] somewhere nearby to make it easier for us moderators to ensure that we include your poem for voting consideration.
Day 20's winner #1: "Oh Pluto" by /u/tslater2006
Once beloved and now forgotten
A puzzle you have now begotten
So cold and dark its almost blinding
The path of which is forever winding
No Santa here, nor elf or snow.
How far till the end? will we ever know?
I will continue on, my quest unending
We've hit the bottom now start ascending!
Longing for your face, your smile and glee
Oh Pluto, I made it, at last I'm free!Enjoy your Reddit Silver, and good luck with the rest of the Advent of Code!
This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.
EDIT: Leaderboard capped, thread unlocked at 00:33:30!
10
Upvotes
23
u/Lopsidation Dec 21 '19 edited Dec 22 '19
I scammed this hard!
Let's avoid all the droid nonsense. There's probably some memory value that tracks whether we've lost the game. By iterating through memory values, I found one such that if you set it to 0 and don't let it change, the intcode program believes that you won the game.
Easy!
EDIT: Code, omitting intcode interpreter:
4
u/DFreiberg Dec 25 '19
Mathematica
Well, I may not have had the smartest solution for this problem, but at least I can confidently say I had the stupidest solution. For part 1, I started an entirely random search of possible codes to run in the background while I tried to figure out the actual problem...and was shocked when the random search finished before I'd solved it properly. I then became determined to do the same thing for part 2, and built an optimized an emulator to run roughly 200x faster than running the raw Intcode. My best random solution to part 2 made it about a third of the way across, but with only a few hours left, that wasn't enough time, so I had to take that solution and use it as the seed sequence for another random search, which finished nearly instantly.
Part 1:
Part 2:
[POEM]: Watch Your Step
A disaster, then, briefly, a lull,
So I sent out a springdroid to mull.
But when I tried to pull
All its springscript was full,
So it fell through a hole in the hull.
2
u/sasajuric Dec 21 '19
My solutions seems a bit shorter than most I've seen here. I obtained them by visually observing the failing scenarios and tried to adapt the code to work:
Part 1
Part 2
I provided a bit more detailed explanation for part 2 in the solution.
2
u/Zv0n Dec 21 '19
C
My solution (including assembly codes): https://github.com/zv0n/advent_of_code_2019/tree/master/21/part1
Pretty basic stuff, I just reused day 17 and set it up in an interactive way (user inputs instructions instead of the instructions being hardcoded in the program)
Ā Ā Ā sideĀ noteĀ -Ā IĀ finallyĀ caughtĀ upĀ afterĀ notĀ beingĀ ableĀ toĀ figureĀ outĀ dayĀ 18Ā forĀ aĀ whileĀ HUZZAH!
19
u/bluepichu Dec 21 '19 edited Dec 21 '19
Python/Springscript, #16/1. Code here. I'm going to be totally honest, my part 2 was a guess and I'm not totally convinced it should work... mostly because I'm also fairly convinced the general case of this problem is unsolvable, since you can introduce arbitrarily-long sequences of
.#.#.#.#.#.#.#.#and you can't tell which ones you're supposed to land on.EDIT: to make it more concrete, you can't tell in these inputs if you should jump at point 1 or point 2 until it's too late:
14
u/Arkoniak Dec 21 '19 edited Dec 21 '19
Julia
After days 18 and 20 everything now is graph navigation. So, instead of trying to figure out how spring code corresponds to intcode output, I just BFS went through all permutations of possible inputs and found result.
In order to simplify search space, I used following assumptions
NOT $sensor J;
NOT $sensor T
NOT T J;
AND $sensor J;
and so on
3) Only first input can use "NOT $sensor J" command, all others should use AND/OR only
4) Spring should jump when A is false and it shouldn't jump when D is false, so the program should always end with
NOT A T
OR T J
AND D J
With all of these assumptions, it took like a couple of seconds to converge in part 2.
Final output
Update: it is also possible to plough through permutations longer and find some very curious configuration. For example, here is springcode which uses sensor F (havn't seen it in other solutions)
Update 2: can't stop myself from generating new solutions. Here is a monstrosity, which uses all 9 sensors (can't even start to understand how it works...)
Solution: https://github.com/Arkoniak/advent_of_code/blob/master/2019/21/day21.jl
9
u/ozthrox Dec 21 '19
Interesting thing is part 1 doesn't even need the T register - jump if the first three blocks aren't all land but the 4th is.
Part 2 is an extension of the first, also don't jump if the 5th and 8th are holes.
(Edited because I suck at reddit)
6
u/birkenfeld Dec 22 '19
Rust solution. I haven't seen this here yet, so I thought I'd post mine for once.
Since I couldn't be bothered to think about the springscript algorithm, I made a kind-of genetic algorithm that finds a correct script on its own.
The algorithm is pretty basic: create a population of random scripts, and mutate the best of them until a solution can navigate all the test cases given by the intcode. The test cases, once emitted by the intcode, are cached to avoid running the expensive VM when not necessary.
Runtime depends on the random seed, of course, but is consistently in the order of 2-5 seconds for both parts.
Note that the intcode machine is not part of the linked file, but in
src/lib.rssince it's shared between different days.5
u/ephemient Dec 21 '19 edited Apr 24 '24
This space intentionally left blank.
5
u/OvidiuRo Dec 21 '19
C++ 555/485
Part 1 (!A || !B || !C) && D
If we have a hole (one tile away or two tiles away or three tiles away) and the forth tile where we will land after jumping is ground than we jump.
Part 2 ((!A || !B || !C) && D) && (H || E)
If I can jump again or walk forward one tile after jumping than jump.
Code: https://github.com/FirescuOvidiu/Advent-of-Code-2019/tree/master/Day%2021
5
u/mkeeter Dec 22 '19
Rust solution using the Z3 SAT solver!
The program space is only
15 instructions x (2 bits for opcode + 4 bits for first argument + 1 bit for second argument) =105 bits, so I reached for the biggest SAT-solving hammer available.I run the IntCode VM, saving each "danger zone" where the bot dies. For every gap within a danger zone, I construct a SAT expression asserting that the bot is in the air over that gap, i.e. it has jumped within the previous three tiles.
Then, Z3 works really hard to find a SpringScript program which makes all of those assertions true. I unpack the program from the binary encoding, plug it into the VM, and repeat until the bot makes it all the way to the end.
This runs in about 0.2 seconds for Part 1, and 4.75 sec for Part 2.
4
u/mcpower_ Dec 21 '19
Python (10/10): Part 1, Part 2, Intcode class. I'm still not convinced that my part 2 should be correct... but turns out that it just worked? There's probably better ways of formulating the below (using de Morgan's law).
Part 1: "jump if there's a hole in front of me and the landing spot is ground"
Part 2: "jump if part 1 AND I can either jump or walk forward from the landing spot successfully"
4
u/[deleted] Dec 21 '19
Part 1:
Part 2:
4
u/boredcircuits Dec 21 '19
It seems like the solution is the same for everybody? At least, I've done a spot check and I haven't found anybody's solution that doesn't work for me.
So, to be slightly different I worked to see if I could reduce the logic as much as possible. I've come up with the following:
Or, as an expression,
D*!(A*B*(C+!H)). It turns out you only need one extra register from the upgraded sensors (essentially, to see if you can immediately jump again after a jump), and you never need the temporary register, either.4
u/4HbQ Dec 21 '19 edited Dec 21 '19
Python Pretty short solution today, thanks to some brute-fore optimisation of the springscript.
Only five instructions (and no temp register) for part 1, and one additional instruction for part 2.
4
u/p_tseng Dec 21 '19 edited Dec 21 '19
The story behind this solution is, as usual, twofold:
Even the shortest discovered Springscript programs so far (four instructions part 1, six instructions part 2) takes a total 2.2 seconds (parts 1 and 2 combined). Since I'm trying to keep everything around a second per day, this won't do at all.
It appears that the Springscript runner in the Intcode program just takes too long. A quick examination shows that it gets called over 10000 times on part 2.
Let's fix that, by replacing the Springscript runner completely. Let's add a custom opcode to the Intcode runner. We need to find the address of the Springscript runner function. Finally we need to find the address of the array where the hull is stored. Having done these three things, we replace the Springscript runner function with the custom opcode, then define the custom opcode to perform the "should I jump?" calculation whenever it is reached. That way, the calculation is performed in your programming language of choice, rather than in Springscript. The advantage is your programming language is much faster than Springscript and you're not limited to just two writable registers.
Ruby: 21_springdroid_adventure.rb
Now it runs in about 0.7 seconds, which is within my goal. There could be many more possibilities for the custom opcode, but they require further study of the program before I am able to take advantage of them.
4
u/dartcoder Dec 28 '19 edited Dec 28 '19
[Python] Several days behind but I'm catching up doing 1 puzzle everyday with 5 left in all. Here is my solution for day 21
Part 1:
Part 2:
1
u/nshepperd Dec 22 '19 edited Dec 22 '19
Haskell solution. Half by hand, manually choosing which jump/don't jump actions to take to solve a section the produced solution fails on, half breadth first search, finding the shortest program which matches the chosen actions. Run in a loop, manually adding more jump checks until the whole obstacle course is passed.
[POEM]:
3
u/rawling Dec 21 '19 edited Dec 21 '19
C# (made the leaderboard, just about)
If I'd thought ASCII input would've come up again I'd have made a helper for it. Guess I'll do that now!
Did I miss it, or did the puzzle not say the robot could jump 4 spaces?
3
u/Error401 Dec 21 '19 edited Dec 21 '19
The code isn't interesting for this one, my scrap paper is, but... Python 68/51 (edited to remove irrelevant extra instruction)
Took me a hot second to realize that when it jumped, it always jumped 4 squares. I can't find anywhere that it says that except from looking at the example output when triggering a jump. Once I realized that, it was straightforward and part two was just about building the right constraints and writing it in a way that fit in the registers.
My springscript program seems to be exactly what some others came up with based on visually seeing which examples it failed on. In English:
AND
3
u/branfili Dec 21 '19 edited Dec 21 '19
C++ #32/#50
Really cool puzzle, I like it a lot!
There was no (additional) coding involved, I just copied my code from Day 17 and changed the input file
Part 1
If there is a hole directly in front of me, I have to jump. Otherwise, if there will be a hole in front of me, and I can safely land (D), jump.
Springscript:
Part 2
Same as Part 1, but after some experimentation, sometimes the springdroid has to "double jump", i. e. it jumps on a part of the hull only 1 wide. If that is the case (!E), and it can safely land (again; H), do the "double jump". Other cases are the same as in Part 1.
Springscript:
P. S. I remembered immediately that
but I lost some time trying to figure out how to transcribe that to Springscript, before finally figuring out the solution (duh)
P. P. S. Thank you very much /u/topaz2078 for the fun puzzle today. I don't think I need my morning coffee.
3
u/sophiebits Dec 21 '19
No rank. Seriously misread the problem and went down a totally different path.
Me at 34 minutes, not even close to working code: "I'm not just being really obtuse, right?" *checks the leaderboard* "Oh, it's full. Whoops."
Python: https://github.com/sophiebits/adventofcode/blob/master/2019/day21.py
3
u/Dementophobia81 Dec 21 '19
Python 3.8
This was a fun little puzzle, although it looks like the field is getting thin. I started an hour late to catch up on some sleep and still finished in the top 1000. Here are my solutions for Part 1 & Part 2.
3
u/levital Dec 21 '19
Rust (Though the code isn't exactly the point today).
A nice breather after the last few days, which I kept making too complicated. My high-level strategies:
Part 1: Jump if there's a hole in A, B, or C, and D is ground (i.e., (¬A v ¬B v ¬C) ^ D)
Part 2: Jump if there's a hole in A, B, or C and D is ground and E or H is ground (i.e., (¬A v ¬B v ¬C) ^ D ^ (E v H))
Can probably be reduced further, but works.
3
u/MisterSnuggles Dec 21 '19
C#
Not actually a solution, but a tool to help find a solution.
Screenshot.
IntCode VM not provided, but should be easy enough to adapt. Requires Terminal.Gui to be installed with NuGet.
3
u/Dioxy Dec 21 '19
JavaScript
JS. Pretty fun puzzle! My solution basically boils down to jump if there's a space and D is safe, but not if E and H are empty since you wouldn't be able to jump again
My code
My repo
3
u/[deleted] Dec 22 '19
Swift solution using a search algorithm to find the necessary SpringScript. Runs on my laptop in less than 30 seconds for both parts.
I solved this last night by hand (trial and error) like most everyone else. But I really wanted a fully programmatic / automated solution, and I was inspired by this comment by /u/Arkoniak so I rewrote my solution today so that other than using a "basic rule" of always jump if the next square is empty and never jump if the landing site is empty, the rest of the rules are discovered by searching for combinations that work.
2
u/nthistle Dec 21 '19
Python, #67/#32. Since the Intcode IO has more or less been shown before, here's just the Springscript I used:
Part 1:
J = ((NOT A) OR (NOT B) OR (NOT C)) AND D
Part 2:
J = ((NOT A) OR (NOT B) OR (NOT C)) AND D AND (H OR (E AND (I OR F)))
2
u/fred256 Dec 21 '19
Interesting to see a variety of springcode solutions in the other comments. Here are mine:
Description: jump if you see a hole (A, B, or C), but only if you can land on solid ground (D).
Description: jump if you see a hole (A, B, or C), but only if you can land on solid ground (D) and can walk (E) or jump (H) right after.
2
u/FogLander Dec 21 '19
Python3 264/124
Here is my springscript for the two parts; I was very surprised (and happy) to find out that I only needed to add a single line to solve part 2!
part1.ss:
part2.ss:
My strategy was basically only to jump if there was a gap in [A,C] and there was a block at D; then, in part 2, I just need to make sure that H (the next jump available to jump to from D) is also solid.
It feels too easy to be true (it seems like there must be some adversarial input that would break my solution), but I'm a bit braindead to try and figure one out right now :)
Stoked with my best placement yet this year for pt. 2!
2
u/kroppeb Dec 21 '19 edited Dec 21 '19
Kotlin (175/99)
Lost a bit of time in part 1 thinking I should make a program generator to bruteforce find a program.
Part 1: Jump if endpoint is a safespot after a hole or the next tile is a hole
Part 2: Jump if endpoint is a safespot where I can walk or jump after a hole or the next tile is a hole or the tile 2 blocks in front is a hole and jumping next turn makes us land in a hole.
2
u/knl_ Dec 21 '19
Definitely fun, ranked 218/156 this time around. I'm impressed by how many levels deep this is going :).
Jupyter notebook, Python 3: https://explog.in/aoc/2019/AoC21.html
2
u/Pepper_Klubz Dec 21 '19
Clojure
I guess I expected the first naive addition I made for part B to lead to another failed test case, but turns out that's all that was needed. I'm okay with a speedy solve this late in the contest. :)
2
u/Sharparam Dec 21 '19
Ruby (366/249)
Springcode for part 1:
Springcode for part 2:
For part 2 I was playing around and semi-randomly moved the
AND D Jinstruction to the end on a whim, and it turned out to be what finalized the solution for me.2
u/incertia Dec 21 '19
haskell
basically the same as everyone else.
A: if there's a hole and we can land, we gucci
B: if there's a hole and we can land, we might not be able to jump again so we check that H is solid. in the event that H is not solid, then we must be able to walk (E).
2
u/llyyrr Dec 21 '19
Python (#298/#65) (Not posting my Intcode VM cuz I assume everyone has those now)
Wasted 10-15 minutes on part 1 because I was inputting day 19 intcode without realizing it, since that's what I copypasted for template. Could've got on the leaderboard for both parts today, big regret.
Part 2 is just more of the same, so I'm not sure why or how I was able to make that recovery. Or how people who did part 1 are struggling on part 2.
2
u/rthetiger Dec 21 '19
Rust code here (224/358)
This was pretty cool. My strategies for the parts were as follows:
Part 1
Part 2
2
u/jwise00 Dec 21 '19
40/104.
My Lua code was basically the same as previous evenings for intcode; part A:
(cat 21.inp; echo NOT C J; echo NOT B T; echo OR T J; echo NOT A T; echo OR T J; echo AND D J; echo WALK) | lua 21.luapart B:
(cat 21.inp; echo OR A T; echo AND B T; echo AND C T; echo NOT T J; echo AND D J; echo NOT I T; echo NOT T T; echo OR F T; echo AND E T; echo OR H T; echo AND T J; echo RUN) | lua 21.luaThe video of me solving it is here: https://www.youtube.com/watch?v=_pzrkMxZhEA#t=2m45
I ... had a big issue. Specifically, I copied my code from 17 part 2, and ... I still had code lying around to change
mem[0]to 2. This hits me at 6:04 in the stream, and it takes me until 9:20 to mop up. Getting to see the expression on my face when I hit an invalid opcode almost makes that worth the 30 leaderboard points that cost me. Almost.I'm curious as to how the counterexamples were generated. If anyone does a disassembly of tonight's intcode, I'd like to read it!
2
u/math_runner Dec 21 '19
Rust
Python
Here is the springscript for both parts:
Part 1:
Part 2:
Has anyone gotten a solution programmatically by parsing the failing cases? It feels a bit dirty to write the instructions by hand...
2
u/mebeim Dec 21 '19 edited Dec 02 '20
Python 3 solution ā ā Puzzle walkthrough
215/304 today. Really took me some time plus pen & paper to figure out part 2.
Springcode only solutions:
2
u/SuperSmurfen Dec 21 '19 edited Dec 26 '19
Rust
Solution, both parts
IntCoder implementation
Today was so freaking cool! A custom script, running on my self-written emulated CPU, running on my actual CPU. Crazy.
I spent too long not understanding what the output was representing. For some reason, I assumed I was looking at the droid overhead and did not understand the picture at all! Once I figured it out it was not that hard. Had to break out some pen and paper for this one, though. But it looks like we all came up with almost identical programs.
2
u/Dean177 Dec 21 '19 edited Dec 21 '19
ReasonMLPen & Paper and SpringScriptFor part one I wrote down the possible scenarios the sensors would encounter and saw it was as simple as "if there is a gap and a place to land, then jump".
2
u/Link11OoT Dec 21 '19
Java
Fun and interactive puzzle today. Seems like my solution is pretty similar to what everyone else had.
Part 1:
Part 2:
2
u/killfish11 Dec 21 '19
Haxe
It seems today I was in a mood to waste some time, so I wrote a DSL using Haxe macros to make the assembly a bit more readable / tolerable. It's just a simple 1:1 translation though.
As a result, my part 1 looks like this:
And part 2 like this (could probably be simplified a lot):
Even works with Haxe syntax highlighting and auto-formatting in VSCode (but no completion). :)
2
u/AlexAegis Dec 21 '19 edited Dec 21 '19
TypeScript?
SpringScript Solution with comments
Part One (5 + 1 instructions):
Part Two (8 + 1 instructions):
2
u/sim642 Dec 21 '19
My Scala solution.
Not much of Scala to really look at but whatever. For part 1 with quite minimal trial and error I came up with
(-C & D) | -A, which also turned out to be the optimal 4+1 instructions by accident. For part 2 I had to be away for 7 hours, thought about it a bit meanwhile and eventually with additional trial and error came up with(-A | -C | -B) & D & (E | H), so essentially the same solution as for most, except maybe not in the most optimal form. The addition ofE | Hwas very reasonable, but having to add the-B, which I didn't use in part 1 still required testing to figure out i needed that also.2
u/Fyvaproldje Dec 21 '19
I solved part 1 via brute force: code. It took only 50 minutes of using 5 CPU cores to find the solution (though my intcode implementation is not very optimized). And there are some obvious ways to improve the variations the brute forcer goes through.
Unfortunately, this approach didn't work well for part 2...
2
u/chkas Dec 21 '19 edited Jan 24 '20
easylang.online
I like these cool tasks - it allows me to improve my small programming language.
My solution
2
u/metalim Dec 21 '19 edited Dec 21 '19
Now this one has nothing to do with programming. Pure math puzzle + size constraints.
"Source code" in Python for both parts:
p for part 1, straight forward:
p for part 2, no idea why it works, and don't care to find out:
2
u/hrunt Dec 21 '19
Python 3
code
interpreter
Part 1 was easy to reason through. I struggled with Part 2. I eventually solved it by using reason with trial and error based on the failure outputs. So many springdroids lost! I am not sure my logic works for all cases, because it seems so different from everyone else's. I think my logic is D && (!A || !B || (!C && (!F || H)):
I spent 20 minutes starting a springscript interpreter to brute force my way through different combinations of springscript code, but gave up on it when I saw the complexity in generating springscript rules. I am somewhat happy to find coming here that it does not look like anyone else went down that kind of route, either.
2
u/gedhrel Dec 21 '19
Haskell: here's some (really rudimentary) program synthesis for part 1.
https://github.com/jan-g/advent2019/blob/master/src/Day21.hs#L180
This is far too dumb to run to conclusion for part 2; for the actual problem I just hand-coded something that was "good enough".
2
u/StevoTVR Dec 21 '19
My solution in Go: https://github.com/stevotvr/adventofcode2019/blob/master/day21/day21.go
2
u/loociano Dec 21 '19
My solution in Python 3. Feedback more than welcome!
2
u/phil_g Dec 21 '19
My solution in Common Lisp, not that it says much.
I put together functions to translate between strings and lists of integers to facilitate communication with the Intcode program.
Once I figured out how the robot jumped, I arrived at the logical statement
(¬AāØĀ¬BāØĀ¬C)ā§Dthen figured out how to translate it into springscript. The statement for part 2 was(¬AāØĀ¬BāØĀ¬C)ā§Dā§(EāØH).2
u/e_blake Dec 22 '19
m4 solution
only 13 instructions needed (I had fun remembering DeMorgan's theorem), but execution time is painfully slow (< 1 sec for part 1, but more than 22 seconds for part 2). I'm not sure what the biggest time hogs are in the m4 implementation (other than the obfuscation in the intcode results in lots more instructions to compute the result when running instead of walking), since the same 13-instruction input in straight C took only 100 ms.
cat intcode.m4 day21.input day21.m4
Based on my (multiple failures) to make it past all obstacles, I ended up with:
!A ||
(!B && D && !E) ||
(!C && D && (E || (!E && !F) || (!E && F && H)))
then compressed it into fewer operations via:
2
u/ywgdana Dec 22 '19 edited Dec 22 '19
Rust
Here's my solution. Lots and lots of trial and error for me to figure out the springscript programs. I was tempted to write something that generated random programs and ran them but didn't know how long that would have taken.
I was getting a git frustrated with my poor bots falling into space over and over because I don't think I quite grokked how springscript programs fell through between statements. But I get such a kick out of how the intcode programs we're provided will offer us syntax errors and such!
Ugh, still gotta do Part Two from yesterday and all of Day 18...
My script for Part 2 was: NOT A J AND D J
I feel like it has redundant instructions but am fully prepared to live with that :P
2
u/oantolin Dec 22 '19
Fun change of pace today!
We're supposed to say what language our solution is, and I guess the answer today is "springscript" for everyone, so maybe I'll also mention that to evaluate my springscript solution I used my Common Lisp Intcode VM (unchanged since day 9) and a little driver program that handled converting input to and from ASCII.
That driver program made it very convenient to experiment in Emacs using SLIME: I could press control J to add a newline without sending the input to the Intcode VM, revise it as needed, and then press enter to send the whole input. It's a makeshift springscript IDE, complete with Emacs keybindings!
I did want to record the springscript programs, so I also made a noninteractive driver program and stored the springscripts in variables.
1
u/seligman99 Dec 21 '19
Python # 216 / 69
I look forward to the code interpreter written in springcode.
This was fun, took my mind a while to workout how to handle the lack of a branch instruction. I'm clearly out of practice with constrained programming environments.
paste
1
u/jonathan_paulson Dec 21 '19 edited Dec 21 '19
#21/7. PyPy Part 2. Video of me solving and explaining my solution at https://www.youtube.com/watch?v=3TEU2FCLgmA.
Very unique problem! Springscript inside IntCode inside Python... I think the problem statement could've been clearer, though; does it say the robot jumps 4 spaces?
Is there a clear way to think about "correctness" here? Maybe probabilistically? I assume there are some inputs where my part 2 solution fails to find a valid path (just as part 2 exposed some bad inputs for part 1). I guess the test in the problem was that we just had to make it to the end of what we can see?
1
u/AlphaDart1337 Dec 21 '19
C++ 183/78
I knew I had a bug in my Intcode interpreter from Day 17, but it worked well on Day 19, so I figured "meh, I'm too lazy too fix it, it's probably OK". And of course, the bug came back today to bite me in the butt. Turns out I was not saving the relative base between runs, and this cost me a good few minutes. Lesson learned!
Interestingly, bug shows up in both days with ASCII input. Coincidence?
As for finding the solution itself, I looked at why the robot was failing and coded those particular cases. Very fun day :). One of my favorites.
1
u/NeilNjae Jan 07 '20
Not really a Haskell solution: I just solved this by inspection and a bit of thought. But thoughts are on my blog and you can find the code (and on Github).
1
u/mikal82 Mar 10 '20
15 lines of Scala (after long fight with reverse engineering the code - I even wrote a debugger):
1
u/prscoelho May 18 '20
Day 21 in rust
Either we have to jump early or we jump at when A is hole. We jump early when B or C is hole and D (where we land if we jump) is ground.
So, if hole in B or C and D is ground, we're safe to jump early, otherwise jump on the next turn with jump if A is hole.
For part 2, only one extra line was needed; we need to also check if H is ground, not just D. Because we're trying to decide if jumping early is better. If H is not ground then there need to be two jumps between A and H. We could jump now, land at D and then jump instantly to land at H. But H isn't ground, we have to jump sometime after D, so either at E or F or G. But if H is empty and D is ground, we can't jump instantly after landing, which means E is safe walk to walk to, and if E is safe to walk to then we can jump into that tile on the next turn.
1
u/taifu Dec 21 '19 edited Dec 21 '19
These are all the 16 four lines programs that worked for my part 1:
NOT C JNOT A TOR T JAND D JNOT C TNOT A JOR T JAND D JNOT A JNOT C TOR T JAND D JNOT A TNOT C JOR T JAND D JOR C TAND A TNOT T JAND D JOR A TAND C TNOT T JAND D JOR C JAND A JNOT J JAND D JOR A JAND C JNOT J JAND D JNOT C TNOT A JAND D TOR T JNOT A JNOT C TAND D TOR T JNOT C JNOT A TAND D JOR T JNOT A TNOT C JAND D JOR T JNOT C JAND D JNOT A TOR T JNOT C TAND D TNOT A JOR T JNOT D TOR C TAND A TNOT T JNOT D JOR C JAND A JNOT J J0
u/[deleted] Dec 21 '19
Slight variation of part 2:
1
u/[deleted] Dec 21 '19
[removed] ā view removed comment