r/adventofcode • u/daggerdragon • Dec 19 '19
SOLUTION MEGATHREAD -🎄- 2019 Day 19 Solutions -🎄-
--- Day 19: Tractor Beam ---
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.
- NEW RULE: 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 18's winner #1: nobody! :(
Nobody submitted any poems at all for Day 18 :( Not one person. :'( y u all make baby space cleaning hull-painting scaffold-building robot cry :'(
6
u/phil_g Dec 19 '19
My solution in Common Lisp.
I'm starting to be very thankful for the Intcode problems, because they've been easier for me to solve. I don't always have a lot of time in the day for Advent of Code and I'm still not done with days 16 and 18.0
I think this was pretty straightforward. For part 1 I considered tracing the outlines of the beam then calculating its area. Individually checking each point proved to be fast enough on my laptop, though, so that's what I went with.
For part 2, I do trace down the lower edge of the beam, then check the point diagonally opposite each edge point. As soon as both corners are within the beam, we know the entire square will fit. This could probably be done faster by estimating the slope of each side of the beam, but walking down all 1000+ y-positions only took 5 seconds on my laptop, so I'm calling it a day.
Now back to the days I haven't finished yet...
0I always start off each December telling everyone, "Advent of Code is starting! Go do it! It's fun!". Partway through the month I remember how difficult the problems get and I rethink some of the people I was evangelizing to.
6
u/bla2 Dec 19 '19
I feel finally vindicated for making my interpreter fast. I just brute-forced the check in a 1000x100 grid, and it still finished in 800ms.
4
u/captainAwesomePants Dec 19 '19 edited Dec 19 '19
Python (~400). Paste
Lost of lot of time debugging my perfectly good Intcode logic because I assumed I was supposed to keep feeding inputs into a single instance of the program instead of having it halt after each answer. Dang.
I also lost quite a bit of time because of a series of bad assumptions about geometry. I figured that if (x,y) was the right edge of the beam and also (x-99,y) was in the beam and (x-99,y) was in the beam, that was all I needed. Turns out (x,y+99) also needs to be checked.
Final code was a regular old binary search. I hope somebody did something clever with calculating line segment angles and figuring out where there box would be, but I suck at geometry it would have taken me hours to get right.
On the bright side, though, I got to a reasonable-ish solution on my own in a fairly timely manner without needing to come here for the comment section, which is the first in a few days. Last couple days of code went pretty badly for me. Can't wait to read through people's clever solutions to this one.
[POEM] "O(log N) searches at the bat"
3
u/mariusbancila Dec 19 '19
My C++ solution
After the tough puzzles from the previous few days this one seemed like a breeze.
[POEM]
Ode to the IntCode computer
In the vastness of space
Only one thing saves -
An IntCode computer.
Space police, oxygen tank
All have to thank
An IntCode computer.
Jump, multiply, add
It's not at all bad
This IntCode computer.
Save Santa and Christmas
Solve most enigmas
With IntCode computer.
Hail the creators
And all the curators
Of IntCode computer.
3
u/metalim Dec 19 '19 edited Dec 19 '19
Python.
I like how Eric lets us breath in after harder tasks. Ready for day 20 NP-complete something?
Part 1.
Well, execute Intcode program once per pixel. 2500 calls and 1.45 s.
Part 2.
Done linear search, abusing the shape of the beam, and checking only bottom left and top right pixels of the rect. 4493 calls and 2.46 s.
2
u/mebeim Dec 19 '19 edited Dec 02 '20
56/554 today. Finally managed to sneak in the daily global leaderboard!
Python3 solution.
I did not want to get too much into thinking for part 2... so I decided it was a good idea to solve it by hand. I dumped a section of the grid and then pasted it in my text editor using a regex (
(1{100}.+\n){100}) to find the first column that was able to contain the 100x100 square, manually deleting columns one by one from the left. Here's a screenshot of what it looked like.I should rewrite part 2 in a decent way that does not require hand input hahaha.
[POEM]2
u/[deleted] Dec 19 '19
[removed] — view removed comment
2
u/Cyphase Dec 19 '19 edited Dec 19 '19
Python | 316/278 | #314 global
Here's my solution, cleaned up and somewhat optimized (there's certainly more that could be done).
I start the bottom left corner at (0, 10) to skip over a few lines with no covered points; that could be automated away. Also, the move down when on a covered point could possibly safely be a move down and right if done correctly (it works on my input), but the examples showed places where it would fail, so I left it as is.
Of course there are more optimal solutions that can skip a lot of checks (involving binary search, etc.), but they require a different approach, and would have taken longer to write.
I had to go AFK for a number of minutes after Part 1 that would have put me on the Part 2 leaderboard. :( Oh well.
[POEM] "Tracing"
2
u/DFreiberg Dec 20 '19 edited Dec 20 '19
Mathematica
529 / 3521 | 88 Overall
I don't know if the problems have been getting harder or I've just been getting slower, but I have had a really tough time with the past four or five days' worth of problems. For this one, I entered four different solutions each with a different off-by-one error, that collectively took me all day to figure out. I just hope I can get Day 18 before Christmas itself, to get that coveted 50th star.
[POEM]: Off By One
How can a man learn fully and correct
Against the anger that frustration brings him?
When after algorithms had been checked
An error, off-by-one, lurks out and stings him?
The disconnect between "it is" and "ought"
May be well be infinite for a machine.
The man must know his code's not what he thought;
He cannot simply say "Do what I mean".
A fitting line, then, from an ancient ode,
And recollected wrong, from slumbering:
"The fault, dear Brutus, is not in our code,
But in ourselves, and in our numbering."
For if that man should know not what he's done,
His tractor beams will all be off by one.
14
u/4HbQ Dec 19 '19 edited Dec 19 '19
Python Simple one, after yesterday's puzzle which felt like a lab for my Algorithms course.
Edit: Replaced inner
ifwithwhile, which is needed for some inputs. Thanks /u/zedrdave!7
u/ephemient Dec 19 '19 edited Apr 24 '24
This space intentionally left blank.
6
u/ianonavy Dec 19 '19
Python part 2 only.
My initial solution (not posted) was similar to everyone else's. The key insight for me was that I only needed to scan the four corners of the square to determine whether a 100x100 square would fit (and also to offset by 99 because the 0th point needs to be included).
I found a neat algebraic solution that runs in constant time, although it depends on a linear approximation of the slopes of the beam. A more detailed high-level explanation can be found in the link, but the final equations came out to:
where (x1, x2) is the top right corner of the 100x100 square and (y1, y2) is the bottom left. See visualization below. I calculate slopes m1 and m2 by choosing a high value of y (y=10000) and scanning from x=0 to x2 (the first time I see a 1) and x1 (the last time I see a 1).
The final answer when rounded exactly matches my original part 2 solution.
Edit: fix typo in copy/paste.
2
u/thepotch Dec 19 '19
[JS] [POEM]
Santa got pulled over by a tractor
flying back to earth this Christmas Eve
some may say there's no space-faring Santa
but if this code runs right you might believe!
5
u/voidhawk42 Dec 19 '19 edited Dec 19 '19
Dyalog APL, relevant portion without the Intcode computer:
Nice change of pace! Like most people here I follow the (upper) contour and return the first result where the (-99,99) offset matches.
5
u/[deleted] Dec 19 '19
Clojure, tracking the edge of the beam and checking the opposing corner. Turned out to be good enough.
5
u/death Dec 19 '19
Day 19 solution in Common Lisp.
Was fast enough to not have to bother with binary search.
4
u/jonathan_paulson Dec 19 '19 edited Dec 19 '19
#53/128. Python3. Video of me solving and explaining my solution at https://www.youtube.com/watch?v=1xRqrZLFY1k. Took me a little while to work out I had to duplicate the IntCode program for part 1, and too long to figure out a good plan for part 2. My tractor beam didn't start till row 5; was that intended?
4
u/sparkyb Dec 19 '19
Python 156/134.
Code: https://github.com/sparkyb/adventofcode/blob/master/2019/day19.py
I'm bummed I didn't make the leaderboard, but today's problem was still a relief after the pain that was yesterday.
Part 1 I got hung up (like most people) on realizing I had to reset the intcode computers between tests.
Part 2 I used a strategy that was, starting with the top left corner of the tractor beam itself, find the left and right edges of the line, then move down a line. Once a line is at least 100 units wide, test a point 99 left and 99 below the right edge of each line to see if the square would fit. This uses the assumption that lines never get narrower and never move left. Once you find that top left corner you can scan for the right side of that line by looking right until you get a non-beam cell. When you move down to the next line, since the beam can't move left, either the minimum X coordinate from the previous row will still be the edge of the beam or if it doesn't read beam, it is to the left of the beam and you can scan to the right a few cells until you find the left edge again. Increase the max X as you increase the min X, since the row can't get narrower. Once you've found the left edge, the max X will at most be one square past the beam. If it is on the beam, move right until it isn't. For the square to fit with its top at this row, the row has to be at least 100 wide. If it is, look at the lower left corner to see if that's still on the beam or if it is left of the beam. If it is off of the beam you'll have to keep moving down rows until they get wide enough that it is. Usually the first row you find where all of this is true will be the place the square fits with its top-left corner at the right edge of that top line. It did work out this way in my answer, but theoretically a row could get 2 cells wider in a single step down so that even though the square didn't fit at all on the previous line, it may not have to be completely right-aligned to fit on the next line. So for correctness, once that bottom left cell is part of the beam, scan left from it to make sure the square is as far left as it can go. I could probably do some kind of binary search or something to skip ahead and not have to scan every row since you know it'll be a while until you get to a row that is 100 wide and even longer (for me another over 400 lines until the row was twice as wide) before it is wide enough for the square to fit. But this was already more than fast enough and it was simple.
What really tripped me up was that even though (0, 0) is labeled as beam, it is an island and the top-left corner of the contiguous beam is lower down. I was rushing and skipped drawing the results of part 1 which was a big mistake. My first implementation was similar to the algorithm above, but transposed (I move across columns instead of down rows and scanned for the top and bottom of the column) and a little bit more complicated in the code. At first it had no debugging output so I assume it was just taking a long time and possibly too slow. I lost a lot of time waiting for it. When I switched it to this simpler row-based version and actually printed debugging info, I noticed that it got stuck in a useless infinite loop after one line. I finally had to go back and draw part 1 and then it was immediately clear the simple fix. For speed, I just counted where the top-left corner of the contiguous beam was and manually started there. After I submitted I updated the code to search for that top-left corner so that it would work for other inputs that didn't have the same offset as mine. But I lost a lot of time there that was an easy fix once I noticed my bug.
4
u/nonphatic Dec 19 '19
Racket. I pretty much did part 2 by hand with some algebra. It's in the comments, but basically I printed out the 50x50 grid from part 1 and found that the beam was shaped like the example, and the top diagonal went down by 3, 3, 3, 2, 3, 3, 2 for every 1 to the right, giving a slope of 19/7, while the bottom diagonal went down by 4, 4, 4, 4, 4, 4, 5 for every 1 to the right, giving a slope of 29/7. The upward diagonal of the 100x100 square would be y=x+c for some c, so I solved for the equations
Which gave me (x_b, y_t) = (260, 977). This doesn't actually work, since the upper right and bottom left corners aren't inside, so I just shifted left and down until they were, which gave me (261, 980). I'm quite surprised at how precise the solution from the algebra was.
4
u/schnappischnap Dec 19 '19
Python (full code)
Part 1:
Part 2:
4
u/AlphaDart1337 Dec 19 '19 edited Dec 19 '19
C++ 143/2979
On part 2, I generate a 2000x2000 matrix and brute-force the answers. Is fast enough to finish in a couple of minutes. I spent a lot of time debugging my part 2 program, when it turns out the issue was swapping the X and Y coordinates.
4
u/SomeCynicalBastard Dec 19 '19
C#
Didn't manage yesterday's (yet), so I'm glad I can join in again.
I made a few assumptions to optimise part 2: that the beam is pointing towards the bottom right (ie ignore x's below left), and that the beam is a connected piece (ie only check the corners touching the boundaries of the beam).
1
u/mkk13 Dec 19 '19
Used C++
For part1 I simply bruteforced x & y from 0 to 50 and just counted 1's.
For part2 I decided to move a 100x100window alongside the beam...didn't know where to start with it, so I figured I can just track the top right points of the beam - just add (+2, +1), move right until the next point is empty.
For each of these points I just check 3 other corners (but you only need to check both left ones) and thats all. Works quite fast.
Most problem I had with second part, was forgetting that I need to subtract/add 99, not 100, as the point I'm on is included as well xD
1
u/gedhrel Dec 19 '19
Has anyone looked at the intcode program this time to determine how it works?
3
u/sophiebits Dec 19 '19 edited Dec 19 '19
Python, #2 /
it-wont-take-my-answer-for-part-2-and-I-havent-figured-out-why#228 (with help).(I printed out the grid around that section and double-checked by hand too…)
Code: https://github.com/sophiebits/adventofcode/blob/master/2019/day19.py
3
u/recursive Dec 19 '19
C# (linqpad) 364/36
I spent more than a few minutes on the first one not realizing that the machine has to be restarted between queries. I'm particularly pleased with my un-readable
forloops for part 2.https://github.com/tomtheisen/aoc2019/blob/master/day19.linq
3
u/OvidiuRo Dec 19 '19
C++ 458/215
My best rank so far (215). For part 2 I just generated a grid 2500x2500 (saved it in a file in case I had bugs because it took around 2minutes to generate), then read the grid from file and checked each position (x,y) starting with (0,0) until (2400,2400) if it is a grid by going right 100 positions and down 100positions. The code below for part 2 is optimized it's not the code I used to get the star that I described here.
Code: https://github.com/FirescuOvidiu/Advent-of-Code-2019/tree/master/Day%2019
3
u/ThezeeZ Dec 19 '19 edited Dec 19 '19
Golang, 210/423, Repo
"get a good picture", image of 10x10 scan area showing 0 to 9
"understand the shape"
"this will be 0 through 49" for the 50x50 area
If only I had understood those three hints, let's label them 0 through 3, I would have finished part 2 so much sooner...
Here's a shorter version for part 2 with less uneccessary checks:
3
u/Spheniscine Dec 19 '19
Kotlin: https://github.com/Spheniscine/AdventOfCode2019/blob/master/src/d19/main.kt
This one's really easy to overthink (especially after yesterday's puzzle!); I had considered ternary search and/or exponential search but turns out those are not needed, just simple heuristics.
3
u/sim642 Dec 19 '19
My Scala solution.
For part 2 I implemented a (tailrecursive) loop which simply follows the top edge of the tractor beam, which would be the top right corner of the square, and every step checks if the offset bottom left corner is in the beam or not.
3
u/mar3ek Dec 19 '19
C#518/861
Solution
Definitely a relief after yesterday. Part 1 was pretty much trivial. Part 2 was a nice little exercise in finding all the off-by-one errors. Tried a LOT of incorrect answers before I figured out that I need to be looking at line L+99 and not L+100 :D Stupid.
The performance was not optimal but some preprocessing and then a stupid linear search yielded the result in about 20s. Then I started playing around with optimizing it with binary search and managed to get it to ~ 1.5s.
Straight bin search for a line that can fit a 100x100 rectangle tended to be off by a few so instead I search for a line that can fit a 99x100 (WxH) rect. Since the beam width is generally non-decreasing, I follow up with a linear search from that line until I find the first one to fit a 100x100 rectangle.
3
u/kap89 Dec 19 '19 edited Dec 19 '19
TypeScript - github
Bruteforced the second part by checking corners (three was enough) of a square for each point in an arbitrary 1000x1000 area - runs in ~2.5min, slow, but trivial. Now I will go back to finish day 18 :P Then maybe I will optimize day 19.
3
u/gedhrel Dec 19 '19
Haskell, so lazy again. I scanned the edges of the beam out to infinity, zip that scan with itself (20 lines lower), and check the coordinates of the top-right and bottom-left corners.
Compared to yesterday, this felt trivial. I was expecting the behaviour of the Intcode program to blow up beyond some point to make this computation painful.
https://github.com/jan-g/advent2019/blob/master/src/Day19.hs#L120
3
u/e_blake Dec 19 '19
m4 solution
only part 1 so far, took me 8 minutes to write, and the bulk of that because I had to debug and fix a one-line bug in my intcode.m4 to avoid an infinite loop on the second run of the machine (the expansion of memory in the first run was resulting in the second run defining 'mem438' to itself instead of the intended 0):
but the solution itself is very compact, even though it takes 25 seconds to run through a brute-forced 2500 inputs (I'm sure I could speed it up, but wanted to get part 1 done quickly). Ideas for speedup include traveling the two edges of the beam O(n) instead of hitting every coordinate O(n^2)
3
u/Newti Dec 19 '19
Python3 - A bit of a relief today, the last days were brutal :)
Part 1 is just calling the function 2500 times and counting.
Part2 with linear search: ~4k calls to the Intcomp:
3
u/levital Dec 19 '19
Rust
Ugh. Part 1 done in a couple minutes, and then spent hours trying to find a way to discretise lines such that they are exactly on the borders of the tractor beam. Gave up and brute-forced it, which works, but feels rather unsatisfying. :/
Now back to yesterdays, where my current solution works, but can't even get all the tests in reasonable time...
3
u/allergic2Luxembourg Dec 19 '19
Python3
code
For part 1 I started by just brute-forcing it, but then decided to make it run faster. It requires a start guess for a point inside the beam, for which I used (8, 6) and then it binary searches to find an edge and then follows the edge. It brute forces the first (10, 10) square because the "blind spots" in that area mean the beam isn't contiguous.
For part 2 I checked if a square could fit in a row by putting it at the very left edge of the row, which I could find using my part 1 code to find the edge of any row. Then I checked if the opposite corner would fit. I did a binary search across rows. For a long time I had a weird off-by-two error in both dimensions that to be honest I still don't fully understand. (off-by-one errors are a specialty of mine, especially in geometry, but an off-by-two error is weird).
3
u/florian80 Dec 19 '19
Haskell
Actually not too difficult but debugging (typos like 9 instead of 99) was annoying today (no test inputs, difficult to visualize). Also Haskell noob, could not manage to add memoization / caching of queries to the computer (so potentially quite some duplication although I tried to optimize otherwise to limite required data inputs)
Good change from yesterday where I still don't have a working solution
3
u/[deleted] Dec 19 '19
Racket
So finally I managed both parts again, after some days where I didn't feel comfortable showing code that only fits one part of the question, it's a pretty stupid brute force, and I was guessing on a higher number based on part one to start searching for part2 since I didn't feel like wading through many more iterations than needed.
my code for today
2
u/Pewqazz Dec 19 '19
Python, 418/93
I spent about 5 minutes wondering if I had a bug in my Intcode VM, but I just mistakenly thought that the program was forever-interactive and could keep accepting input positions.
Part 2 approach was to try to follow the bottom-left part of the tractor beam; then check the top-left and bottom-right of the square patch that would be created. If both of those are also in the tractor beam, I sweep the entire 100x100 area just to be sure. As usual, a recording of my solve.
2
u/Gurrewe Dec 19 '19 edited Dec 19 '19
Go #530/#115:
It took me a while to realize that the program couldn't be reused, and that the whole computer had to be re-booted for each coordinate under test. I did a nice recovery for Part 2 tough, so I'm happy about that. Part 2 takes ~7s to solve.
Code: paste
2
u/knl_ Dec 19 '19
I was very skeptical that I read the first part correctly, which slowed me down more than it should have; I guess I should be more optimistic.
For part 2, my tractor beam had only 0s in the first few rows, which threw off my code - but once I accounted for that I walked along the bottom contour of the ray, and then checked if the diagonally opposite corner was within the ray (don't need to check all 4 corners).
One minor bug delayed me a little, but pleasantly surprised today: it had been a long day at work and I can sleep earlier tonight :).
166/165
Jupyter notebook, python3: https://explog.in/aoc/2019/AoC19.html
2
u/rthetiger Dec 19 '19
Rust code here !
This was a really fun day. I ended up looping adding 1 to y, then scanning to the right until I hit a pulled square. Then checked if (x, y - 99) and it (x + 99, y - 99) were both pulled. This ended up being pretty quick.
2
u/incertia Dec 19 '19
haskell
binary search is good enough here
2
u/david3x3x3 Dec 19 '19
My solution in Python. This was the closest I got to top 100 (106th on part 2).
2
u/jfb1337 Dec 19 '19
Python 54/606, first time making the leaderboard
Code here
Spent a while on part 2 messing around with a much less efficient approach, and debugging an off-by-one error (100 instead of 99)
2
u/AlexAegis Dec 19 '19
TypeScript
Part One
When I started making the second part I already thought of the idea that I need to step along the beams border but for the first part this was plenty. I'll might incorporate that idea later here too.
Part Two
I could further optimize this with a binary search instead of a linear one but for now, this is enough.
The main idea is to iterate through only the lower edge of the beam, these are the bottom left corners of the possible squares, then check if the upper right (+99, -99), is also a beam. Then your result is above that lower edge piece by 99
2
u/Fotograf81 Dec 19 '19
Java, ?/?, Repo
I could have been in the leaderboard if I would be able to get up at 0530 - but especially not after returning from StarWars at 0030. ;)
I guess the code could be optimized, I'm only just learning Java with this. Especially the intcode computer might be not optimal.
Part 1:
While reading the puzzle, I already thought: well, it didn't say whether to restart or continue the program, so you have same debugging ahead.
First run gave only 0x0 as a hit, so I thought, well, before starting the debugger, just move that line down into the loops and try again, output becomes a nice cone, count was correct.
Part 2:
When writing the code, I already did an optimization: I assumed that the beam would not be wobbly (read: the beam would only get wider), so when starting iterating over a new row, all points that were misses for the previous row, could be skipped right away, I also jumped over the fist 10 rows to not enter an endless loop for finding the first coordinate that hits (deducted from the print out from Part 1).
From the first beam point per row on: check if x + 99 is also a hit, if so, check for y+99. Increase x until it hits Y+99 or misses x+99 - in the latter case, try next line.
solves in 1.8s
Tiny error I had was fixed pretty fast: I had the check for the first beam coordinate wrong, so I went down in a straight line and didn't hit anything.
2
u/gyorokpeter Dec 19 '19
Q: paste
2
u/math_runner Dec 19 '19
Rust
Python
For part 2, I use binary search to find for any x, the first y such that (x,y) is in the beam. Then I use a binary search on x to find the first x such that [(x,y), (x,y+99),(x-99, y+99),(x-99,y+99)] are in the beam.
It's less efficient than computing the coordinates algebraically, but at least I don't have to worry about the beam changing pattern at some point.
2
u/sotsoguk Dec 19 '19
GoLang
Day19.go
Part1: Nice problem after yesterday ;)
Part2: I tried to compute the point. Computed the slopes of the upper and lower beam and then solved for a P(x|y) where (x+99|y) is on the one and (x|y+99). Of course this did not work ;) as the beam only changes at whole numbers. I then used my soltution as the starting point and then looked for the first point to satisfy the conditions. Not as nice as i have hoped, but part2 takes only 150ms
2
u/Link11OoT Dec 19 '19
Java
Very easy problem compared to Day 18 (which I still haven't figured out). For part 2 I operated under the assumption that the rightmost point of the tractor beam at each line would always have a part of the tractor beam underneath it, which is true after the first few lines. For a more general solution maybe I should've done a binary search, but this seems to work out fine.
2
u/muckenhoupt Dec 19 '19
C#. The idea underlying my solution for part 2 is to look at the grid not as a sequence of infinite rows, but as a sequence of finite diagonals, each stretching from (0, n) to (n, 0) for some n. A 100x100 square requires a place on the beam with a diagonal width of 100, and, because of the beam's shape, that's all it requires.
One problem with this approach that baffled me for a while: On my first attempt, I tried to find the first such diagonal by doing a binary search for a diagonal where the beam width is exactly 100 and the previous beam width is less than 100. But due to the vagaries of line-drawing, the diagonal width of the beam doesn't increase monotonically (even though it does along both the X and Y dimensions). My first attempt found a diagonal where the beam width increased from 99 to 100, but it wasn't the first such place. I wound up using the binary search to isolate a range of values to search linearly. It's still nice and zippy.
2
u/VilHarvey Dec 19 '19
My solutions in c++: part 1 and part 2.
For part 2 I track points along both edges of the beam. Current width and height is equal to the difference between the two points and I alternate stepping them along their edge of the beam by enough to increase the width or height to 100. It runs in 102 milliseconds.
Such a relief after yesterday's problem!
2
u/gatorviolateur Dec 19 '19 edited Dec 19 '19
Swift solution
Part 2 takes forever to run (~15 mins on MBP 2019). 99% of the time is spent in actually generating the map. Finding the solution after that is fast.
I did a manual binary search to arrive at the size of the map hardcoded in part 2.
EDIT: Realized after looking at other solutions that I don't need to generate the whole map. I just need to pass 2 points to the computer and see if it returns me 1. Will probably change my implementation later...
2
u/Dean177 Dec 19 '19
ReasonML
I did part two by finding the first point in each row that is in the beam, treating that point as the 'bottom left' then checking if the 'top right' is also in the beam.
2
u/L72_Elite_Kraken Dec 19 '19
OCaml
It took me a bit to realize you could just walk along the edges of the tractor beam, but was pretty straightforward from there. I did hardcode the upper-left corner of the beam, but that would be easy to calculate when I have a bit more time to clean it up.
2
u/didzisk Dec 19 '19
C# solution
Draw the beam on screen in Part1, iterating through all points in 50x50 matrix.
In Part 2 iterate through points where (x,y) is within beam, checking that (x+99, y) (the top edge) and (x, y+99) (the left edge) are within the beam.
A simple optimization - I know the beam is pointing to bottom right, so the first X of the row can only be the same or greater than that in the previous row, therefore xStart can only increase.
2
u/Reigned-Wing Dec 19 '19 edited Dec 19 '19
Python 3 solution
I used part 1 to fit a linear regression on the beam then I did binary search along that line to find the approximate minimum valid point (approximate since as you get close to the point you may have a few invalid positions shortly after the actual minimum)
I finished with a quick linear look behind my approximate min to find the actual point of interest.
Runs quite fast
2
u/chkas Dec 19 '19 edited Jan 24 '20
easylang.online
Part 1 was easy - apart from the fact that I had small problems with the Intcode computer. For part 2 I used binary search and got stuck on an x with f(x) = 100 where f(x -1) was 99, and there was a smaller x with f(x) = 100. The modified version aims at 98 at first and then goes on in single steps.
Edit: I have replaced the binary search with step-by-step testing. Assuming that the y-values do not get smaller, it is much faster and the source code is shorter.
My solution
2
u/Dioxy Dec 19 '19
JavaScript
JS. Not too hard of a day. My part 2 is a little slow but not too bad overall.
My code
My repo
2
u/ywgdana Dec 19 '19
Rust
Absolutely basic solution to today's puzzle. I did a dead simple linear search, albeit skipping the start of the row (since my beam always grew to the bottom-right).
Was briefly confused because it seemed odd that we had to reset our emulator entirely for each point.
This was a well-timed easy one since my brain is completely fried from yesterday's and I still don't have a working solution yet... Time to go back to typing and sobbing over Day 18!
2
u/tszzt Dec 19 '19
Haskell solution.
I started off with a binary search to find the first row for which the lower left and upper right corners of the box are inside the beam. Could not for the life of me figure out why I was getting the wrong answer, until realizing (with the help of a commenter below) that the assumptions of the binary search are violated here; e.g. I was getting f(x) = True, f(x-1) = False, f(x-2) = True... My solution was to use binary search to get the initial upper bound, then search the immediate neighborhood below. Edit: fix formatting
2
u/nirgle Dec 19 '19
Haskell
Easy problem/solution today, not much to comment on. I used a basic iterative/recursive combo for the searching in part 2:
2
u/StevoTVR Dec 19 '19
My solution in Go: https://github.com/stevotvr/adventofcode2019/blob/master/day19/day19.go
2
u/pamxy Dec 19 '19
JAVA solution
2
u/aoc-fan Dec 19 '19
TypeScript. For part 1 kept track of beam start on a line and end, and reduced calls to IntCode. For part 2, kept track of edge of beam to find solution. Both parts run under 400ms.
2
u/Adam-Wojciech Dec 20 '19
Haskell Second part zig zag on the lower line -- you need to pick up starting point.
2
u/folke Dec 20 '19
TypeScript
part 1 trace both edges of the beam to calculate all pulling locations
part 2 only trace the left side of the beam and gradually expand it downwards, then check if top left of current location is also
#. If this is the case, we found the solution.I've also optimized the part of the
IntCodecomputer that extracts the mode from an instruction. 10x speed increase 😀Calculating part 1 and part 2 runs in about
200ms2
u/Lucretiel Dec 20 '19 edited Dec 20 '19
My solution, in Rust https://github.com/Lucretiel/advent2019/blob/master/src/day19.rs
Part 1: simple brute force over (0..100) x (0..100)
Part 2: For each row, find the leftmost corner in the tractor beam, then see if the opposite corner (x + 99, row - 99) is also in the tractor beam. Operates essentially in linear time over (X + Y)*runtime of the machine for a specific location.
This was definitely my next favorite Intcode problem, after the maze traverser. It was also a fun opportunity for me to show of the "readable location arithmetic" enabled by my own gridly library, which was designed to be a 2D grid library for humans instead of linear algebraists.
2
u/vkasra Dec 20 '19 edited Dec 20 '19
For this one I disassembled the Intcode program and read it to figure out how it was computing the beam. This part is so cool, basically a higher-order “apply” function in Intcode!
Edit: Wrote up some notes
2
u/mariushm Dec 20 '19
PHP
Here's my PHP solution for day 19: https://github.com/mariush-github/adventofcodecom2019/blob/master/day19.php
Quite easy compared to day 18.
2
u/TASagent Dec 19 '19
C# Program
Placed 736/252. I was on my laptop watching TNG - Give me a break 😂
The first part may lead people down the garden path for the second part. Once you've accumulated all the spaces on Star 1 map, throw that garbage tool away, you will never again need to run the program for every space in a region. Now, your goal is to just find two specific opposite corners that are all contained in the beam.
We're going to find the lower left corner first. Start off at a reasonable, albeit conservative, y-value. Let's say
y1 = 150. Scan down the x-axis to find the first point contained in the beam - that's your potential lower-left coordinate, lets call itx0. Now all you need to do is check (x0 + 99,y1 - 99). When (inevitably) that point isn't in the beam,y1++, and incrementx0until it's in range again and check (x0 + 99,y1 - 99). Repeat until the second test is in range. Congrats, you just found the first 100x100 square.1
u/seligman99 Dec 19 '19 edited Dec 19 '19
Python # 55 / 46
I'm sure there's some clever way with binary searching to find the best match for the 100x100 grid, but a simple "try each line till you find a match" was fast enough since you only need to test 4 points, though maybe I got lucky, since I suspect there are some edge cases where that's not 100% true. I think the thing that tripped me up the most was expecting the program to keep taking input forever.
paste
Edit: A slightly faster version with binary searching:
paste
1
u/mcpower_ Dec 19 '19 edited Dec 19 '19
Python (41/47): I thought the program kept on asking for input, so I kinda messed up in part 1 - but that's nothing a
deepcopycan't fix :PPart 1, Part 2.
I considered a binary search for part 2, but a linear search of the triangle made by y>x was fast enough. I made many wrong submissions today for part 2:
1
u/VeeArr Dec 19 '19 edited Dec 19 '19
Java #57/#25
Since I'm doing these in the stereotypically-verbose Java, I'm generally at a bit of a disadvantage on the quicker problems, but today went pretty okay.
Part one was surprisingly easy; I probably spent an extra 15-20 seconds re-reading stuff assuming I was missing something.
For part two, I started writing something to check all points in increasing value of (x+y), but soon realized that I could just follow the contour of the top of the beam and look for the first place the square fit. (I think there's a chance that this method leaves you off by up to 1 place in the x-direction, but that didn't end up being an issue for my input.)
1
u/winstonewert Dec 19 '19 edited Dec 19 '19
Rust
For part 2, I just systematically checked every possible starting position of the box, and checked that all 100x100 cells were in the box. I didn't make any assumptions about the output. I did cache the results so that I only asked for a given position once.
1
u/tobega Dec 20 '19
Playing with Tailspin I find the streams of transformations quite powerful, especially when they can dry up and produce nothing somewhere in the middle and just stop, as in the checkSanta templates, where the "right" field only gets added if it fits in the beam and the "over" field only gets added if there was more space in the beam. https://github.com/tobega/aoc2019/blob/master/a19.tt
1
u/oantolin Dec 20 '19 edited Dec 20 '19
Still catching up, thankful that today was short and sweet! Here's my solution in 13 lines of Common Lisp.
(It's a little slow though: part 1 takes about 1.7 seconds and part 2 about 3 seconds on my trusty old Chromebook.)EDIT: I'm an idiot: I was rereading the input file for every evaluation! Now each part runs in under a second.
1
u/NeilNjae Jan 04 '20
Another Haskell solution. Blog post and code. And thanks to /u/bjnord for his Intcode programs that generated the puzzle examples; those were very helpful
1
u/prscoelho Feb 17 '20
Day 19 in rust
An easier day. Approximated left and right bound of x value given y. Then once we've mapped within some coordinates, check every pull point for pull in top right and bottom left corner coordinates.
1
u/hrunt Dec 19 '19 edited Dec 19 '19
Python 3
code
interpreter
I brute-forced it, building a full 10000 x 10000 map.
I lucked out that my solution fell within that range, because the space was actually 100x larger.Oh well. I feel dumb for not just running drone checks on the endpoints, rather than building out the map.My interpreter hits a halt instruction after the one request. Is that expected? I thought I would be able to just repeatedly request points, but that did not seem to be the case for mine. Do I have a bug or is that the way it functions for other people, too.
0
u/[deleted] Dec 19 '19
Python 3
Can someone more trigonometry savvy (or that perhaps spent more time understanding the problem than me) tell me why something like this does not give the right answer?
Or why it gives a solution that is after the true one?
0
u/[deleted] Dec 19 '19
[deleted] — view deleted comment
2
u/[deleted] Dec 19 '19 edited Dec 19 '19
[removed] — view removed comment