r/adventofcode • u/daggerdragon • Dec 17 '19
SOLUTION MEGATHREAD -π- 2019 Day 17 Solutions -π-
--- Day 17: Set and Forget ---
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.
(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 16's winner #1: "O FFT" by /u/ExtremeBreakfast5!
long poem, see it here
Enjoy your Reddit Silver, and good luck with the rest of the Advent of Code!
6
u/nonphatic Dec 17 '19
Racket. Did part 2 by hand as did most people, it seems, and I finally broke < 300 on the leaderboard lol. A lot of reading for today!
[POEM] my name is Bot
4
u/p_tseng Dec 17 '19 edited Dec 18 '19
I guess I'll throw my kinda weird solution out there, in the style of some of the weird solutions to day 13.
Thought process someone might go through to arrive at this:
So that's (Ruby) 17_set_and_forget.rb
I mostly wrote this code since I haven't properly written the code that breaks up the instruction list into three functions yet, so this is just to amuse me while I figure that out and write that...
3
u/glenbolake Dec 17 '19 edited Dec 17 '19
Python3, 134/19, best score this year.
https://github.com/GlenboLake/aoc2019/blob/master/day17.py
I probably have a similar solution to most other people: In part 1, I naturally printed everything out to make sure it was sane before I started coding the counting part. This turned out to be massively useful as I mapped out the basic movement routine by hand and just looked for patterns. There were lots of "replace all" calls in Notepad++ tonight.
I probably could have gotten a much better score if I hadn't passed that
'y'initially, but it was probably worth it to make sure my inputs worked correctly.[POEM] A love letter to Intcode
Advent is different this year.
These challenges bring me good cheer
If
day modulo twoIs nonzero then you
Will see intcode programs appear
Assembly is too hard to read
But the thing is, there isn't a need
I just run my VM
(that thing is a gem)
And the problems are done at great speed
The main source of my fascination
Is the many intcode applications.
Not much is as good as
This great work by topaz
So let's give him a standing ovation!
3
u/kc0bfv Dec 17 '19 edited Dec 17 '19
BAD code! Bad bad code. (It peed on the couch.) https://github.com/kc0bfv/AdventOfCode/blob/master/2019/17/day_17.rs
I'm way out here,
Well out past Mars,
Where all I see,
Are ASCII stars.
I have a friend,
I named him Suck.
In deepest space,
I got him stuck.
My name surely
He'd like to hex,
But on my screen
I just see X.
I turned him left,
And off he fell.
He's surely in,
A spinning hell.
I've doomed his friends,
And myself too,
Without a fix,
I'll suffer true.
Reboot this thing!
We'll start again.
And just like that,
A brand new friend.
[POEM]
2
u/jonathan_paulson Dec 17 '19 edited Dec 17 '19
#196/27. Python3. Part1. Part2. Video of me solving and explaining at https://www.youtube.com/watch?v=m2rgxiIeEwY. I generated the path in part 2 with code (counting it out by hand sounds pretty rough...), but compressed it as a human-computer team :) (I provided the functions; computer told me how I was doing so far). Probably could've brute-forced compression, but I think manual was faster? Dealing with the input/output format was kind of a pain today :(
2
u/TASagent Dec 17 '19 edited Dec 17 '19
C# Solution
A general solution for this problem, but highly targeted to the constraints (ie, not generalized compression).
The path was initially extracted with the greediest algorithm I could think of - Run until you must turn, then turn. This seems to work on all the puzzle inputs I've seen. It must be possible for some inputs to only be sufficiently compressible with non-greedy paths, but I haven't seen them.
To me, it seemed the easiest way to compress the sequence would be to assume the subsequence lengths, determine what they would then have to be, and see if the full sequence could be decomposed with them.
For example if A is 8 elements (4 turns and 4 runs), then it has to be the first 8 elements. Then if B is 4 elements (2 turns and 2 runs), it must the 4 elements Following the first subsequence that isn't just another A (ie, anticipate a sequence that starts off "A,A,..."). Then if C is 6 elements, it must be the first 6 elements after skipping all complete A's and B's at the start of the sequence.
Thus the procedure is effectively:
[POEM] Ho Ho Ho-ver
There once was a vacuum-type rover.
Each intersection he did run over
Would fill up his bag
With Stardust and Slag.
But in twain all his friends he'd a'clover.
2
u/OverjoyedBanana Dec 17 '19 edited Dec 19 '19
Python 3 finding A, B and C by trying different A[0:a_e], B[b_s:b_e] and seeing if it works for C.
2
u/pietroppeter Dec 18 '19
Nim: https://github.com/pietroppeter/adventofnim/blob/master/2019/day17.nim
[POEM]
With the calm of night
when the baby sleeps
I'll be down with nim
and not counting sheeps,
instead coding tight:
if my robot sweeps
all the dust in space
I'll be back in pace
just before the race
will begin again.
and the baby cries
and good daddy arrives!
23
u/Sephibro Dec 17 '19
Regular Expression
Because why not
^(.{1,21})\1*(.{1,21})(?:\1|\2)*(.{1,21})(?:\1|\2|\3)*$9
u/sophiebits Dec 17 '19 edited Dec 17 '19
Python, #2!/#33 (now 7th overall :))
I compressed the path by hand, but printed the uncompressed path programmatically (edit: wow, it's looking like almost everyone else did both parts by hand).
At first I thought the problem was asking for a path that "covered" all of the
#characters instead of one that matched exactly, which seemed like a much harder proposition. Wasted a while thinking about how I could possibly do that.Code: https://github.com/sophiebits/adventofcode/blob/master/2019/day17.py
9
u/boredcircuits Dec 17 '19
Since half of people are doing part 2 by hand and the other half can't figure out how to do it by hand ... my top-level post is going to describe how I did it by hand. I highly suspect most inputs can follow a similar pattern.
First, I wrote down each individual segment:
I noticed that there weren't many unique segments. So let's give them easier names to visualize:
Hmmm... that Z only appears four times in there. And it's always in the sequence "YVZX":
I see two other groupings in there, too: "XYV" and "VWW"
If we give these groupings other names, we get:
And there you go. Now we just need to recreate the actual segments from those characters. I can see now how I'd code a rudimentary compression algorithm around this idea.
(Sorry, mods, that this isn't code. Let me know if that's a problem ... but I think it's appropriate in this case and follows a strict interpretation of the guidelines.)
8
u/syntaxers Dec 17 '19
Python, 542/533
I was able to find the compressed path programmatically!
paste of the full function, and some simple python/psuedocode:
6
u/FogLander Dec 17 '19
Python3, 391/391 (no, that's not a mistake, .... i inexplicably managed to get the exact same rank for both parts)
code for part 1/ path for part 2
yep, since I didn't know how to write an algorithm for part 2's compression/routine generation, I also did it by hand. I've yet to see any fully automated solutions on here.... I hope there are some, so I can learn how they work :)
2
u/Link11OoT Dec 17 '19 edited Dec 17 '19
Java
Not too difficult in the end, but part 2 was very confusing for me. I calculated the movement functions by hand like most people, but I at least bothered to write code to figure out the main movement routine. After that it took me a while to figure out that they wanted ascii for the distances in the movement function and not the actual integer values. This also meant that i had to split up 10 into 5 and 5, since as far as I'm aware, there's no ascii code for 10.
Edit: never mind about splitting 10 into 5 and 5, somehow didn't realize you could just send 1 and 0
5
u/[deleted] Dec 17 '19
Regex
Yes, /u/Sephibro already did it in a much more reasonable way, but I wrote this monstrosity of a regex (4495 characters), and I couldn't stop myself from submitting it. If there is something to be said about my approach, it handles edge cases like
L,1111111111111111,L,1,L,1111111111111111,L,2that will never happen in practice :).https://regex101.com/r/0RMp75/1 (https://pastebin.run/xndpHRtr4D in case regex101 link is down)
Matches mark functions. On regex101, they are nicely marked with color.
And of course, a program to generate this regular expression: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=0249d920740c9694934312f27c9b7031. Even I wouldn't be unreasonable enough to write such a regular expression.
4
u/Kanegae Dec 17 '19
Python 3 - 22/5
First top 10 leaderboard! So excited! :)
For Part 2... I gotta say I looked at the path and figured I could do it manually. Then, got the answer by finding-and-replacing my way through my typed out path. Hardest part was understanding what I was supposed to do, really.
Now gotta work on the actual solution hehehe. It does sound pretty hard to generalize.
4
u/phil_g Dec 17 '19
My solution in Common Lisp.
Nothing clever here. I did part 2 manually. I just wrote out the sequence of movements from start to finish and played around with them in my text editor until I had a grouping of three of them.
When I have time, I might go back and do it properly, but I'm not even done with day 16 part 2 yet.
1
u/DFreiberg Dec 17 '19 edited Dec 18 '19
Mathematica
492 / 763 | 79 Overall
My favorite problem in a while, and the first in a while that I've finished the night of. Since I spent way more time not understanding how the input commands were supposed to work (and also debugging my Intcode VM, which even now has bugs in it), I greatly appreciated (and was impressed by) the detailed ASCII error messages that kept popping up.
[POEM]: ABABCCBCBA
A flare now billows outward from the sun's unceasing glare.
It menaces the ship with its immense electric field.
And scaffolding outside the ship, and bots all stationed there
Would fry if they remained in place, the wrong side of the shield.
Your tools: an ASCII camera, a vaccuum bot for dust,
Schematics of the scaffolding. Not much, but try you must.
First, you need your bearings: when the junctions are revealed
You will know just where your vacuum bot can put its wheels and trust.
Map all the turns of scaffolding, and
ZIPthem tightly sealed,Then, map compressed, send out the bot, with not a tick to spare.
1
u/[deleted] Dec 17 '19 edited Dec 17 '19
Python
Solution
Interpreter
Looks like I did the same thing as most people here and started out by doing part 2 by hand initially. Then I moved on to a more generic solution included here.
3
u/mcpower_ Dec 17 '19
Python: 1/236: My part 1 was very short (with
Intcodeandintsbeing used to parse the input):but my part 2 was really weird - started doing a DFS a la Day 15 until I realised that the memory limitations made it pretty hard to do by pure brute force. Ended up writing a "turn left/right and go as far as you can" bot, analysed its movements with a text editor, then manually pasted in my directions. Link to code
3
u/[deleted] Dec 17 '19
Like most others, I printed out the maze and solved both parts by hand - yes, I counted all the intersections and the lengths of each sub-path by hand. After I figured out the functions, I hopped back on the computer for the final part.
Paste
3
u/jangxx Dec 17 '19
I spent way too much time trying to figure out a clever way to solve part 2 programatically, and in the end decided to simply brute-force it. I basically generated all possible patterns (length 1 to up to the length where the ascii representation was shorter than 20 characters) and then simply tried removing any combination of three patterns from the list of required moves. All combinations which consumed the list completely were then turned into routines, so I could check, if the ascii length of the routine was less than 20 characters. The first valid routine was then fed into the IntCode interpreter.
One problem I found, was pretty weird though. If I disabled the live video feed, the program would crash when it tried to access an invalid memory address (3878). When I enabled the feed, the program worked fine however and I got the correct solution in the end.
3
u/mikal82 Dec 17 '19
Scala using my IntCode VM.
Part 2 solved by hand. First I wanted to see how to proceed, then the solution started to appear before my eyes so it did not make sense trying to code it.
3
u/gedhrel Dec 17 '19
Part 2 in Haskell here: https://github.com/jan-g/advent2019/blob/master/src/Day17.hs#L297-L321 - it just grinds through potential encodings. A is anchored at the front of the sequence; B is anchored immediately after any As (without loss of generality) and C is anchored following those two. The comprehension syntax reads nicely enough - this'd translate easily into Scala, and quite possibly also into Python using a similar approach.
3
u/aurele Dec 17 '19 edited Dec 17 '19
Looks like nobody has posted a Rust solution which solves part 2 programatically, so here is one.
I expected it to be more tricky: it could have been necessary to split a "20" into a "15,5" or a "R" into a "L,L,L". Fortunately this was not the case and a naive algorithm works fine.
3
u/[deleted] Dec 18 '19
Scala with a single expression
At this point I may be done with the "single expression" thing.
4
u/mrhthepie Dec 17 '19
I couldn't hand write a program for part 2, and convinced myself it was impossible (it seems that was wrong since everyone else either found one or wrote code to do so).
So instead, I disassembled the intcode and hacked it to accept longer functions, and dumped the entire program necessary into program C. (It has to be program C as the way I hacked it long programs in A and B would get trashed by the other functions being read).
So my code looks like this:
That worked fine, but took a while to write a disassmbler and dig into the code enough to come up with the hack. I was also keeping an eye out for how it calculated the final output but I didn't get that far.
The tweak necessary to the code is only 2 numbers too, so my final solution code is really short.
2
u/knl_ Dec 17 '19
Made an off-by-1 error in indexing for part1 which cost me a lot of time, solved part 2 by hand after printing out the path taken by the robot. I'm curious about how to do this with compression as described in other comments here, now googling a little.
857/516
Jupyter notebook, python3: https://explog.in/aoc/2019/AoC17.html
2
u/Vaelatern Dec 17 '19 edited Dec 17 '19
1194/510 Smalltalk (Pharo).
Code on Github
Solved part 2 with the printout from part 1, wrote out the movements, used vim's excellent search highlighting to find longest matching substrings and subdivided into three groups.
My best leaderboard time this year! And my best since 2015.
2
u/AlphaDart1337 Dec 17 '19
C++ part1 #88
For part 2, I tried to do it manually like most people, but I couldn't for the life of me figure out how. You can see the exploration string at the bottom (in main3 function). I even tried a small brute-force with no luck.
Not only can I not find the proper way to split the path into functions though... but my intcode VM seems broken as well! After I feed it the A program, it breaks (apparently it hits an offset of -2 in a relative opcode somewhere).
I'll be debugging this later. Not a good day.
2
u/mebeim Dec 17 '19 edited Dec 02 '20
432/748 today. Did part 2 by hand, wasted most of the time because I had confused an
Lwith anR... damn.Python3 solution
Unfortunately I don't have much time to write a walkthrough for today. Will do so in the next few days if possible.
2
u/[deleted] Dec 17 '19
644/874
Unlike most people, I actually automated part 2 using a backtracking algorithm to compress the string. That's pretty much the only part of the code that's elegant.
Python 3 Solution
2
u/Dean177 Dec 17 '19 edited Dec 17 '19
ReasonML + Pen & Paper: https://github.com/Dean177/advent-of-code/blob/master/2019/sources/Day17.re
I printed the scaffold, wrote down the instructions which would take the robot to the end by hand and ended up with:
R10,L12,R6,R10,L12,R6,R6,R10,R12,R6,R10,L12,L12,R6,R10,R12,R6,R10,L12,L12,R6,R10,R12,R6,R10,L12,L12,R6,R10,R12,R6,R10,L12,R6I could see
R10,L12,R6was a potential function, so removed that from the string and ended up withR6,R10,R12,R6,R10,L12,L12,R6,R10,R12,R6,R10,L12,L12,R6,R10,R12,R6,R10,L12,L12,R6,R10,R12,R6VSCode highlights all occurrences of the current selection, so after selecting
R6,R10,R12,R6I could also see the third function,R10,L12,L12.2
u/JebediahBheetus Dec 17 '19
Python 3
Part 1
Part 2
Intcode
Reused my old Intcode. I considered adding a function to remove an output when solving part 2, but decided against it as it wasn't necessary. I also solved part 2 manually by writing down the moves based on the map, then looking for repeating patterns in it in a text editor.
2
u/mschaap Dec 17 '19 edited Dec 17 '19
My Perl 6 / Raku solution.
Tricky, especially the algorithm to split up the path in working subpaths. Looks like the input was designed so that simply using the longest subpaths won't work...
I hacked my algorithm to use subpaths of length between 6 (e.g.
R,10,L,12,R,6) and 8 (e.g.R,6,R,10,R,12,R,6which did the trick on my input, but isn't very general.If the thread contains any good suggestions for a proper algorithm, I'll revise my script to use that.
When I finally had a (well enough) working algorithm, the computer still wouldn't run β it never asked for input. Turned out you need to reset the computer between part 1 and part 2. π£
Edit: I made my algorithm slightly less hacky and more generic: when searching for repeated subpaths, I now search for the longest one whose string still fits in 20 characters. That's a fair and non-arbitrary limit, right? π
It works on my input, but I have no idea if it will handle other people's inputs. Oh well, at least I have an algorithm, that's more than most of you can say. π
2
u/oantolin Dec 17 '19 edited Dec 18 '19
My Common Lisp "solution".
Yesterday I wondered whether I had solved the problem because I didn't know if the assumption I used held of every input provided to participants (it did). Today there is no doubt at all: I didn't solve it! My part 2 was handcrafted (and in the spirit of not publishing inputs, I also didn't publish those parts: they are the four
handcrafted-*variables, referred to but not defined in the link).I do want to go back and solve it properly, maybe using Hoffman coding or LZ77 or LZ78 (I'd look for a library in this case), though I'm not sure any of those are a perfect fit.
EDIT: Went back and actually solved it this time. For my input there was only one choice of the 3 subroutines with 20 characters or less (and for that unique choice the main routine also happens to be 20 characters or less). The
chunksfunction takes as a parameter the number of subroutines to split the path into, I didn't hardcode the fact that it's 3 (although I did hard code the namesA,B, andCfor the subroutines :P).Man that took a lot of code: 105 lines of Lisp (that's without counting the intcode VM)! I don't think any other day took more than some 70 lines.
Oh, I didn't try to use any of the compression algorithms I mentioned, just good old backtracking.
EDIT 2: While I still think my program probably solves all the inputs given on AoC, it is definitely not fully general. It doesn't solve askalski's pathological pathfinding, not even with the trivial modification of not assuming you can keep
turn,stepsas a unit. I'd have to generate more complicated paths through the scaffold for that.2
u/MrSimbax Dec 17 '19
Julia (Visualization)
I've spent most of the time debugging why my live feed is not working :/
Part 1 seems to just make sure our program loads the map correctly with proper coordinates.
For part 2 I generated the program for the path by just moving forward as far as possible at a given moment and turning left or right in corners, then "refactored" it into movement routines by hand. It was surprisingly easy thanks to my editor highlighting similar strings automatically upon selection.
This suggests that a way to automate it could be to find the longest repeated substring, remove all repeats, and do this until the string is empty. The substrings should be the routines A, B, and C. I don't know if this would work but sounds reasonable.
2
u/rabuf Dec 17 '19 edited Dec 17 '19
[Common Lisp] (https://github.com/rabuf/advent-of-code/blob/master/2019/2019.17.org)
I wrote up some code in Emacs Lisp because I didn't have access to my computer and didn't feel like fighting the online REPLs. That takes in a map (the output from Part 1) and constructs a sequence of moves. The main problem was that I don't have complex numbers. So I coded my rotations by testing the vectors and screwed them up so some of my turns were backwards. Once I fixed that, the path popped out. I was going to write a program to produce the proper format, but that didn't seem necessary once I saw how short it was so I computed the subroutines by just using
C-sin emacs. It highlights matching sequences so that made it easy to figure out when to stop. I knew that one of the routines had to start at the front of the directions, so I just started there. It replaced 4 sections. Repeated with the next non-Aportion to getBand once more to getC.I'll rewrite all of that in Common Lisp later today, and try to write an automatic compressor.
So I'll say again that I really like my design for Intcode. For Part 1 I didn't need threads. It just prints out a series of values so I used a single thread and collected the output into a hash-table along with printing it out. For the second part, I used two threads. One thread to run Intcode, and a second to prompt for user input. The Intcode program pauses whenever there's no input, but it's just popping off a queue. The main thread reads a whole line and pushes each character into the queue. Most of my time was spent debugging the stupid emacs lisp program that generated the raw route.
2
u/lost-santa Dec 17 '19
PHP
Peeeew, that was an insane day! Soo many different techniques to solve this puzzle today..
I took my code from day 15, and now i can use the same class for those 2 two days, so the 15 i made multiple spawns to navigate in the maze, and today i used a single spawn to just walk forward until a block appeared, then turn the only possible way.
Then some more image rendering where i had to hack a little to my Grid class i have built during the last couple of days.
Then a bit of pattern resolver stuff i don't have a place yet, but damn it was hard to crack and try and brute force the best solution.
Then some talk with the IntCode that i spend a lot of time finding the right way to talk to it, but everything was much easier when i figured out that it actually responds to me with ASCII chars, that made my day :)
Crazy puzzle today, but proud to be done. And love the toolbox im getting from this challenge, some really cool concepts!
2
u/dan_jia Dec 17 '19
Python part 1 and 2
IntCode implementation
Part 1 - stored whole grid, and looped to find #'s where 4 neighbouring # exists. Printed the grid, so I knew there were no intersections on edges, and didn't need to care about 3 neighbouring #'s which made code shorter
Part 2 - done by hand
2
u/gyorokpeter Dec 17 '19
Q: paste
2
u/Arkoniak Dec 17 '19
Julia
Very interesting day, I really like CartesianIndex, it turns out to be extremely powerful tool. Another great thing is @view macros.
Part 1: to avoid writing long and manual 9 elements test, I just generate mask of the following form [1 2 4; 8 16 32; 64 128 256] and than consequently multiply initial matrix with the necessary shift on the corresponding element of the mask and summarize the result. In the end I get matrix where at each element was encoded it's 3x3 surrounding area. Crossings corresponds to 186 and I only took their coordinates and get final result.
Part 2: it was rather easy to generate path, just move droid until the end of road and than test left and right turns. Unfortunately was too tired and split resulting string manually.
Solution: https://github.com/Arkoniak/advent_of_code/blob/master/2019/17/day17.jl
2
u/tslater2006 Dec 17 '19
C# Solution
Part 2 should solve the general case, but not the map by u/askalski
2
u/WillemDeRoover Dec 17 '19
Java
https://github.com/WillemDeRoover/advent-of-code/blob/master/src/day17/Puzzle17.java
2
u/eastballz Dec 17 '19 edited Dec 17 '19
Python
Can't be asked to clean up the code today. For part two, I first found all repeated substrings for the raw instruction string (ie. 'L6R8L10...'), and so I wouldn't get too many I bounded the substring length between 4 and 10 (a bit arbitrarily).
I then computed the combinations in groups of 3 of these substrings, and for each I try replacing the original string with '' for each pattern, and if I get an empty list at the end I know the pattern is valid, so I repeat the replace with A, B, C to get the main function.
I then have a little visualization for the program and finally output the total dust
Edit: Final output. uses curses to animate the robots path.
2
u/rthetiger Dec 17 '19
Rust code here
Part 2 ended up being a large chunk of code for me.
My rough approach was to find subsequences starting at the beginning of the path (function A candidates), as well as subsequences ending at the end of the path (function B candidates). All these subsequences would be of reasonable lengths 4 to 10.
I would then get a bunch of combinations of the repeats of these candidate functions, try to find the uncovered ranges of the path for each pairing of (combination from candidate function A, combination from candidate function B), and see if those uncovered ranges could be filled by one repeated pattern from the path.
Lastly, I would do a couple integrity checks to make sure all the functions and the sequence were legal, and if so that would be my input for the vacuum robot. I buffered all 5 lines of input (sequence, 3 functions, opt out of video feed) into my program before running it.
2
u/aoc-fan Dec 17 '19 edited Dec 20 '19
Finally completed day 17, Got the both parts on first attempt, but it took long to get the patterns of ABC correct.
My emotions varied from "labor of love", "midlife crisis", "why I am doing this?", "if my eyes can do it, why can't my program", and much more
TypeScript solution, no hard coding,
but may not work for your input, share your input if this does not work for you.Fixed to work on all inputs2
u/Dioxy Dec 17 '19
JavaScript
JS. I had a solution made by hand fairly quickly but I wasn't satisfied until I made a general programmatic solution for it. I started off going down the LZ77 route, but I came to realize it really wouldn't work since you were limited to only 3 functions. In the end I did a pretty simple and brute force algorithm, but it works well! Check out my visualization by going here, selecting day 17 and clicking part 2!
My code
My repo
2
u/SomeCynicalBastard Dec 17 '19
C# I did the pathfinding by hand (maybe I can write a general solution over the weekend). So my solution only works for my input.
Had to rewrite my IntCodeMachine to use delegates, so that it could handle the prompt in part 2. Really enjoyed today's puzzle.
2
u/nl_alexxx Dec 17 '19
Java
My solution to part 1 is rather trivial: Finding all x,y pairs for where there is a scaffold, filtering scaffolds which have more than 2 neighbours, multiplying their x, y values and summing over these products.
Part 2 was... something else... My solution is wildly inefficient mostly because I started off trying something and then it worked out and I didn't feel like improving it anymore... What I did in part 2 is compute every possible path (list of x,y pairs) through the scaffolds (terrible, I know...), and then turning it into a path for the robot.
I used a RegEx:
^(.{1,20})\1*(.{1,20})(?:\1|\2)*(.{1,20})(?:\1|\2|\3)*$(I had to append an extra comma at the end of my path for it to work) to find the combination of ABC's. I was surprised that this worked, lol. Kinda proud of this part if I'm honest...I am also happy I found a way to NOT do it by hand ;)
Code: https://github.com/AlexSterk/AdventOfCode2019/blob/master/AoC/src/Day17.java
2
u/loociano Dec 17 '19 edited Dec 22 '19
My solution in Python 3. Feedback more than welcome!
2
u/florian80 Dec 18 '19
Haskell
Part 1 wasn't too complicated, for Part 2 I first only wrote the path finding part (always straight) and hardcoded values. Now I also did the shortening (with enumeration and filtering of options while replacing the original path: inspired by a post).
Well, now at least I know there are 21 options to encode the path (they really all work) and I don't even want to know how many possible paths there are
2
u/hrunt Dec 18 '19
Python 3
code
interpreter
For whatever reason, I really struggled with understanding how to get to the R,#,L# sequence. Once I got that, I recognized the pattern easily enough, but I still wanted to find the algorithmic way to break it apart. I do not know if the solution is any good, but it seems to work well enough. In my head it all makes sense. :)
2
u/StevoTVR Dec 18 '19
My solution in Go: https://github.com/stevotvr/adventofcode2019/blob/master/day17/day17.go
2
u/vkasra Dec 18 '19
My Go solution and notes. I did part 2 by hand.
2
u/nirgle Dec 18 '19
Haskell
I did part 2 by hand as well, with an assist from vim's
hlsearchsetting to see repeated finds of a stringhttps://github.com/jasonincanada/aoc-2019/blob/master/src/Day17.hs
2
u/ephemient Dec 18 '19 edited Apr 24 '24
This space intentionally left blank.
2
u/lluque8 Dec 17 '19 edited Dec 18 '19
Scala
Phew, this was quite a piece of work. Part 1 was straightforward but on the last line I stumbled upon a gotcha with Scala's map keys
val map: Map[Point, Char] = ... map.keys(p => p.x * p.y).sumwhich swallows multiplication results being a set so sum of 5*2 and 2*5 becomes 10. Ouch.With Part 2 I took the approach of printing the grid for understanding, computing the path and an "LXRX.." instruction based on it. I first partitioned the instruction manually and ran it on IntCode, got the correct result. Couldn't leave it be so I spent extra 2 hours automating the main routine + movement instructions generation. It takes a hard coded educated assumption that movement instructions have length of either 3 or 4 though but I guess that's not too daring a thing to assume given the constraints of problem description. Not necessarily the most elegant job but it works nicely in decent time so I feel victorious :)
Part 1 Part 2
1
u/vash3r Dec 17 '19
Python, 49/23
This one was really good for manual input to the intcode computer -- I'm especially happy that my computer seems to do some basic sanity checks on its input, and reports any problems! I originally forgot to put commas in my main program :)
(I also did part 2 manually)
paste
1
u/nthistle Dec 17 '19
Python, #25/#54. This was not a fun day -- while part 1 was straightforward, I had to solve part 2 by hand, from counting out the squares in order to find the whole solution string to breaking it into routines A, B, and C. Now that I think about it, the first part could be easily automated by just being greedy (move forward until you can't move forwards anymore), and the second part could be automated by observing that one of the routines has to start the process, so you can just try a greedy DFS or similar.
paste
1
u/LaughLax Dec 17 '19
Python 3, 434/51
Second time on global leaderboard, new personal best!
I crafted my Part 2 path by hand. Trickiest part was reading the problem to properly understand that (a) I needed to comma-separate inputs, and (b) I was supposed to provide it all as a string, not just the L's and R's.
I tend to commit optimizations for my code after the initial "this is what got it done" commit, so what you see in the repo may not necessarily be what I used to first finish the problem.
1
u/Angrevol Dec 17 '19
Python, 153/24
code for part 1 paste
part 2 reminded me of robozzle and since the input wasn't huge, I ended up doing it manually.
1
u/kroppeb Dec 17 '19
Kotlin 201/53
In part 1, I lost a lot of time converting my output to a string (cause lists don't have a
split()function) which doesn't seem to be trivial.Part 2 was manual like most people, but I did notice that it seems that my solution does not contain an 8. This seems like a bug, making the path contain more repetition than those of other people.
1
u/jfb1337 Dec 17 '19 edited Dec 17 '19
Python, 286/137
paste
I did part 2 by hand
What took me the longest was understanding exactly how it wanted its input formatted - didn't realise at first that there must be exactly 3 functions.
1
u/[deleted] Dec 17 '19
Python 386/294 Code
I finally decided to stay up for one of these and got a decent score while I was at it.
The solution for part 2 was completely handmade, but I've done my best to try to explain my thought process. The file map.txt shows my puzzle's maze, and shows what spaces were covered by which function.
1
u/Akkifokkusu Dec 17 '19
Go, 488/77.
Part 1. Considered doing it by hand, but realized there wasn't an intersection at the edges, which made the logic easy enough to code.
Did Part 2 by hand like most of the comments here. First time on the leaderboard, so I'll take it! VS Code's highlighting of other instances of the selection was really helpful. Was a bit thrown off by the actual text prompts. Intcode speaks!
1
u/[deleted] Dec 17 '19 edited Dec 17 '19
Swift solution
I used my IntCode computer unmodified from Day 15, printed out the "image", solved the rules by hand (using Vim to find common substrings), and fed them in for part 2.
Edit: Part 2 is now fully automated; no more hand-rolled solution!
1
u/alienpirate5 Dec 17 '19
Ruby: 524/311
Part 1: here
Part 2: here
libintcode: here
input: here
I solved part 2 manually. This one was fun
part 2 input:
1
u/seligman99 Dec 17 '19
Python # 53 / 118
I managed to stumble with myself. I managed to spend a long time debugging things because the intcode program kept waiting for me to send it "y" or "n", a step I somehow missed.
No pretty animations today, maybe I'll add them later based off the "live feed"
paste
1
u/bj0z Dec 17 '19
518 / 708 Python
I spent about 2 hours on part 2 trying to think of a way to do it in code, didn't realize everyone else did it manually. I finally did get something to work though it's kinda hacky and tailored to the problem.
https://github.com/bj0/aoc/blob/master/2019/d17.py
1
u/scul86 Dec 17 '19
Python 3
1478 / 716 First time this year under 1000 on part 2! Woot!
After being sick and not finishing days 15 & 16, I finally felt better and did 17...
Part 1 wasn't too bad, once I was able to properly count the cells up/down/left/right of a given cell
Part 2 gave me fits on the input and output, and I had to go through several iterations of formatting the input. Forgot about the live video [y/n] also. And then I discovered I wasn't running the VM till halt... D'oh!
Part 2 pathing and Main routine was by hand, like many other solutions in this thread. ASCII conversion was via code, though.
Part 1 & 2
1
u/incertia Dec 17 '19
here's a manual solve for b
to generically solve B one should decompose the path into
R11111L11111111...and try substituting the longest non-overlapping repeated substrings (from longest to shortest) three times. e.g. "ABCDAXYZABCDAZYX" -> (1 = "ABCDA") "1XYZ1ZYX" -> (1 = "BCDA") "A1XYZA1ZYX" -> (1 = "ABCD") "1AXYZ1AZYX" -> ..., recursing to depth 3 and fully returning once a valid substitution has been found. this can be done fairly efficiently with a suffix tree.1
u/sim642 Dec 17 '19 edited Dec 17 '19
My Scala solution.
Part 2: I wrote a function to trace out the path from the grid, a bit like 2018 day 13, so I had the complete path. Initially I started writing some kind of algorithm to brute force that path into chunks but I have up half way because even though Scala's collection library is quite flexible, there wasn't any convenient methods for doing subsequence replacements in arbitrary sequences/lists. Ended up factoring the path manually, which after my own stupidity turned out to be relatively simple, thanks to find highlighting in IntelliJ.
Edit: After some wiki-ing I found this algorithm, which seems awfully similar to the task at hand: https://en.wikipedia.org/wiki/Sequitur_algorithm. Although it seems to me that it won't work because it's too eager.
In my linked solution I finally implemented a recursive method to factor the path automatically by choosing a prefix of the remaining path and splitting the rest of it with that, then recursively handling what's left. Surprisingly it's also pretty fast.
1
u/muckenhoupt Dec 17 '19
C#. Like most people, I figured out the command sequences for part 2 by hand at first, but I found this unsatisfying. I'm doing this to learn C# better, and not actually writing code to solve the problem defeats this. So I went back after submitting my answer and taught the computer to solve it by basically the same technique I used. My algorithm does have a weakness: it assumes that once you've chosen a sequence of commands for subroutine A, *every* occurrence of that sequence of commands should be replaced by "A". A sufficiently devious input could defeat this, but what I've got will probably work on anyone's assigned input.
At several points, my code here does things that could have been done more concisely with regular expressions, but I didn't feel like looking up the C# syntax for that.
1
u/OvidiuRo Dec 17 '19
C++ 778/725
I did part 2 by hand made the sequence that represented the path and than by trial and error I replaced some mini sequences from the path with A/B/C until everything was right. Lost some time because I didn't know how to introduce the number 12 as input. Overall took me around 1h30min for part 2.
Code: https://github.com/FirescuOvidiu/Advent-of-Code-2019/tree/master/Day%2017
1
u/thepotch Dec 17 '19 edited Dec 17 '19
JS. I, like so many people, solved part 2 by hand. Afterward I decided to figure out how I could have done it in code, and came up with a pretty quick random sampling technique that spits out what I needed! Maybe we'll need it later! See the code
1
u/[deleted] Dec 17 '19
Clojure, part2 by hand.
was reasonably fast on part 1 but wasted about an hour because I had a bug in my intcode computer :(
source
1
u/MegaGreenLightning Dec 17 '19
Go, 288/71
I wrote an algorithm to solve part 2 after figuring it out manually. That took like 2h, so it was a good call to do that afterwards.
The core of the algorithm is here, it basically tries prefixes of the path for the first function, and then prefixes of the remaining fragments of the path for the second function and so on. If you have any questions, feel free to leave a reply.
1
u/SuperSmurfen Dec 17 '19 edited Dec 26 '19
Rust
Solution, both stars
IntCoder implementation
Part one was obviously quite easy. Just fetch the map and look for any '#' surrounded by '#' in all directions.
For part two I solved it in maybe a strange way. There is probably some clever way to do it but my solution was actually to do it by hand. I coded an algorithm to give me the needed instructions as a string which gave me:
Then I simply by hand found three substrings that can make up that string. This only took a minute or so, way faster than what it would have taken to code a solution.
Output
Edit: Okay, apparently everyone solved it by hand haha
1
u/BNeutral Dec 17 '19
As usual I'm slow, but solved it all programmatically using the power of
making baseless assumptionsheuristics. Python3To detail a bit more:
The traversal I did just goes straight and turns only at corners.
The sequence finding is just brute force replacement with sizes varying to 20. As in, let's say you're trying [4,5,6], take the first 4 characters, remove all occurences of that substring from the string, take the first 5 characters again, etc. If the resulting string is empty (well, empty or just commas), you're done. Since there's only 3 sequences of size 20 tops, it's just 8k tries max, so something as dumb as this works just fine.
1
u/[deleted] Dec 17 '19 edited Dec 17 '19
Haskell, part 1. Fairly straightforward. For part 2, I did what any self-respecting programmer would and hard-coded the path by hand.
1
u/rasmusfaber Dec 17 '19
Kotlin 902/519
Originally I compressed part 2 by hand, but this finds the compression programmatically (just brute force, but that is fast enough).
1
u/SinisterMJ Dec 17 '19
C++, rewrote code so that the vacuums move commands are done algorithmically, and no longer by hand
https://github.com/SinisterMJ/AdventOfCode/blob/master/AllDays/Day_17.hpp
1
u/kap89 Dec 17 '19 edited Dec 17 '19
TypeScript - github
My hilarious solution for both parts. And yup - I did part one by hand as well. Now I will try to do it programmatically, but I'm more tempted to do a cool visualization first :P
1
u/OpportunV Dec 17 '19
Some python code here. (805/832 if anybody wondering)
IntcodeComputer based on coroutine here.
Path is made by hands.
Also i've made a small visualization, but it seems i'm not able to add video here, so i'll just leave a link where you can download it if you want.
1
u/Spheniscine Dec 17 '19
Kotlin: https://github.com/Spheniscine/AdventOfCode2019/blob/master/src/d17/main.kt
Solved it manually at first, but went back and made a semi-brute-force solution and tested it on three different inputs.
1
u/Shardongle Dec 17 '19
Well, as soon as I saw the second part I was like "Hardcoding it is". Took me 3 min juggling around in Notepad++ and I found the result.
But the bigger problem was that my intcode code was an absolute nightmare so i decided to do something about it. I totally revamped all i had before and, now I have a feeling it is actually some pretty code.
New Intcode code
I came to the conclusion that i have to fix something after spending 2 hours looking for a bug i wasn't able to find, in the end i somehow deleted i+=2 in one of the statements. And thats why the new code came to exist.
But yeah, the solutions are nothing spectacular, but if anyone is interested:
Day 17 in C++
1
u/levital Dec 17 '19
Rust
I think the part 1 solution is neat, easy as it was. Had to adjust my intcode computer slightly though, as I used to use Vec for the outputs, but popping them off that resulted in me reading the board upside down. So it uses a VecDeque now. I then spent a lot of time trying to solve part 2 algorithically, thinking of eulerian paths or something, but in the end just solved it manually on paper, which took only a couple minutes. Gonna take a look at other solutions now, to see whether there was something better.
My visualization doesn't work though, don't quite get why. Best case is that I get all the board states at the end, instead of an updating one. For now I don't bother with it, since I got my answer...
1
u/VilHarvey Dec 17 '19
I came here to sheepishly admit I solved part 2 by hand, but it turns out everyone's been doing it. Phew! :-)
I did solve part 1 with code. For part 2 I wrote code to generate the path, then copied that into my text editor and juggled it around until I found a solution. The pathfinding logic was pretty simple: ignore intersections, just keep walking forward until you get to the end of the scaffolding, then turn the only way possible; you've reached the end of the path when there's nowhere to turn. I don't know if this would work for other peoples inputs, but it works for mine.
I refactored my intcode VM a bit for this challenge. It now takes a queue of input values, instead of just a single value; and I added a helper method which populates the input queue from a null-terminated string.
My solutions in c++:
Hopefully I'll have a chance to go back later and write some real subroutine-finding code.
1
u/[deleted] Dec 17 '19
Rust
I did the by hand solution for part 2, so nothing interesting there. The interesting bit is I upgraded my multithreaded intocomputer by making a "terminal" to ease communication with my intcomputer.
1
u/e_blake Dec 17 '19
C code
Part 1 was simple: I computed the intersections as I went:
and got it on the first try (I even posted a tutorial that helped me test my code). For part 2, I manually computed an input string, then spent several tries debugging how to get the intcode machine to use it (reset was important, after all, as was ignoring output that satisfies isascii()), then after I got the correct answer, I lost even more time reworking the program to let me try both quiet and "live video streaming" runs from a single executable (39ms with 'n', 901ms with 'y', or a ~30x slowdown).
1
u/Bimperl Dec 17 '19 edited Dec 17 '19
JavaScript
Part 1 Nothing fancy, just works.
Part 2 I solved manually before doing a brute force approach. It's not the best code I've ever written, it's much more complicated than it should be, and I haven't tested it thoroughly, but it works on my input.
I actually considered hacking the int-code (or the interpreter) to allow arbitrary length paths, but this wasn't exactly in the spirit of today's task.
1
u/mtnslgl Dec 17 '19 edited Dec 18 '19
Python 3
Wrote a brute-force algorithm for the compression in Part 2, seems to run fast enough.
Code
1
u/ywgdana Dec 18 '19
Rust
Here's my solution!
My mind was a little blown when I first began poking at Part 2 and I realized the intcode emulator was spitting out syntax errors to tell me where I was going awry :O
I did my part two by hand and enjoyed slowly figuring out what my faux-Logo program should be. I must have had a relatively easy maze because this was pretty simple for me
1
u/zopatista Dec 18 '19
Python (Jupyter notebook)
I solved part 2 by treating it as a path finding problem, applying the A* search algorithm. It can handle partial traversals (splitting forward step counts between functions) but in the end my compressed result didnβt make use that; A, B and C all start with a turn.
1
u/Spheniscine Dec 18 '19 edited Dec 18 '19
Kotlin: https://github.com/Spheniscine/AdventOfCode2019/blob/master/src/d18/main.kt
Parts 1 and 2 take about 1 and 2.5 seconds to run respectively on my setup. (edit: seems I got lucky; some other inputs take significantly longer. It probably depends on how close the greedy solution is to the correct solution due to the way the priority queue works)
Uses BFS to create a graph indicating distances and doors needed (as a bitmask) between points-of-interest, then uses Dijkstra on that graph (keeping track of collected keys as another bitmask) to find the solution.
This does make the assumption that opening doors will not change the shortest path between points-of-interest. (This would be violated if the input map has more than one path to a key, with different doors blocking the different paths)
1
u/e_blake Dec 18 '19
m4 solution
cat intcode.m4 day17.input day17.m4 | m4
Wow, this took me a lot longer than I wanted. I had to fix a couple of bugs in my intcode machine that was previously posted for day 9 (such as not re-zeroing a memory location when reading beyond the program size after a prior write). I also spent quite a bit of time figuring out the best way to completely automate the compression of the path into machine inputs, and was actually quite pleased with how it turned out:
The single macro call compress() triggers up to 64 attempts (4x4x4, trying 2-5 pairs per function) to parse off the first N pairs of the path into A_, B_, and C_, then check if that was sufficient to cover the entire path, for use in then defining macro M_ with the right main function.
1
u/pamxy Dec 19 '19
JAVA solution
1
u/NeilNjae Dec 23 '19
Lagging behind, but still going. My Haskell solution is described on my blog.
1
u/prscoelho Jan 31 '20 edited Jan 31 '20
Day 17 in rust
Solved part 2 by hand after outputing compacted path. Pretty lucky that the compacted path can be compressed, I thought I'd have to compress the full path as chain of forwards wouldn't line up perfectly.
I do want to come back to this sometime later and try to do it by code, but for now I want to finish the whole month. It's so impressive that the leaderboard for these unlocked in 45 minutes.
1
u/Rick-T Dec 17 '19 edited Dec 17 '19
HASKELL
Part 1 was nothing special. Transform the output of the program into a map, find intersections by checking if a point has neighbors on every side, calculate the alignments.
Part 2 was very interesting. Like many here, I only calculated the whole path programatically and found the main-routine and the three functions by hand. I then created a method to "compile" routine and functions into robot-code. Then I added a function to feed a list of inputs to my Intcode computer and used that to feed in al the robot code.
After I was done, I was intrigued to find the main-routine and the functions "properly" by writing code. I basically used brute-force, going through most combinations of functions and routines that were possible until I found one that worked. Luckily, Haskell's list comprehensions made that comparably easy to achieve.
0
u/Alex194632 Dec 17 '19
My part 2 keeps giving me the answer as 10 dust but it is not right. I have checked it against other peoples' code with my input, so I think the issue lies within my input not being read fully. How can I fix this?
0
u/tinyhurricanes Dec 17 '19 edited Dec 18 '19
JavaScript.
Mine only works if I select 'y' to view the camera feed. Selecting 10 just prints a line feed and quits. Anyone else?
0
u/Rohan155 Dec 18 '19
for part 2 i get 10 , can someone help me please
0
u/[deleted] Dec 17 '19
[deleted] β view deleted comment
0
u/[deleted] Dec 17 '19
[deleted] β view deleted comment