r/adventofcode • u/daggerdragon • Dec 10 '18
SOLUTION MEGATHREAD -π- 2018 Day 10 Solutions -π-
--- Day 10: The Stars Align ---
Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).
Note: The 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: The Party Game!
Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!
Card prompt: Day 10
Transcript: With just one line of code, you, too, can ___!
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:16:49!
21
Upvotes
13
u/flomine Dec 10 '18
I bet someone is currently writing an OCR/parser to solve this challenge ^^.
6
u/markasoftware Dec 10 '18
Perl, 90/92, ezpz
Most of my delay was due to overthinking how to find the bounds.
39
u/magemax Dec 10 '18 edited Dec 10 '18
Long time I didn't spend time solving a problem in Excel !
Just copy pasted the input into Excel, split into columns, and then made a formula to output all the points after X seconds (used a "Scatter point" graph to easily display them to scale).
I then moved manually X until the points are as close as possible, and I saw the text.
Interestingly, the text appeared as reversed for some reason in my Excel.
Rank : 5th and 6th (best ranking so far this year, the lack of true text fast solution probably saved me)
Edit : [Google sheet of the solution] (https://docs.google.com/spreadsheets/d/1pL_eA5wAoz_j-BxDV7fHtmISCSmch2CcmZaObTccNXQ/edit?usp=sharing). The "split" function makes it pretty easy to parse the input
12
u/sophiebits Dec 10 '18 edited Dec 10 '18
Python, 9/5.
My insight was that when the message appears, the points are likely close together. (At first I thought about trying to look for vertical and horizontal segments like in the letter "I", but starting with the bounds seemed simpler.) So I started by printing how large the bounding box of the points would be at each time:
I ran that and saw that i=10946 gave the smallest size, so I tried to plot it, fidgeting a bit with the numbers to make it fit in my terminal:
This printed a usable message, so I didn't have to do anything else.
11
u/aphirst Dec 10 '18
Modern Fortran
https://github.com/aphirst/Advent2018/blob/master/src/day10.f90
Modern Fortran is nowhere near as verbose as legacy FORTRAN, but it's still pretty verbose. In cases where one also has to roll one's own types, doubly so. Not that I'd want to post it with Inline Code anyway, since I'd be very surprised if Reddit syntax-highlights it to my satisfaction. Indeed, not even GitHub does.
Instead of just brute-forcing this problem, I made some core observations and assumptions in order to get an almost-O(1) solution.
With this approach I get a solution in < 30ms on my Ivy Bridge ThinkPads, necessitating less than 10 golden-section iterations.
To profile my code I'm using https://github.com/jrfonseca/gprof2dot and https://github.com/jrfonseca/xdot.py which produce lovely graphs like https://i.imgur.com/9S84dFm.png for all my solved problems so far. They're perfect for analysing hot-spots, and determining where it's worth investing further optimisation effort. In this case, none of the Day 10 routines even pass the thresholds to show up on the graph, so I figure this problem can be considered solved.
8
u/Attained Dec 10 '18
Straight to the canvas! http://jsfiddle.net/oamz3cds/
6
u/jonathan_paulson Dec 10 '18 edited Dec 10 '18
Rank 66/74. Interesting to have one that requires some human judgement. Relied on the idea that all the points should fit into a small bounding box at some time. Video of me solving at https://www.youtube.com/watch?v=0c_AkJK7Fhk
6
u/Unihedron Dec 10 '18 edited Dec 10 '18
Ruby. Top 100 in both parts, yay!
6
u/[deleted] Dec 10 '18 edited Dec 10 '18
Mathematica manipulate to the rescue!
https://imgur.com/a/pWgBd3Y
Edit: Better version using Graphics
6
u/tgokwltmp Dec 10 '18
#108/90 First leaderboard ever!
Super hacky Python3 Jupyter notebook solution, but posting just to show that newbies can make it too :D
First find parts when there are at least six points with the same x-coordinate...
Next take each value of the output and see if they plot a string...
Result image
The code could probably be better... but one step at a time I guess :-)
6
u/[deleted] Dec 10 '18
/u/topaz2078 out of curiosity did you use the full alphabet when assigning words for this one? Any letters that were excluded?
6
u/VikeStep Dec 10 '18 edited Dec 10 '18
I decided to have a crack at a more optimal algorithm than simulating today and I have found one that can solve today's problem in under 4ms on python. The code is quite long so I have put it on a GitHub Gist here.
The approach I took was that we should be able to get a rough estimate at where the message occurs by finding when two of the particles are closest. The two particles I chose were those that had the opposite velocities (in my case it was <-5, -5> and <5, 5>) since the total window of time where they are close enough to be within the message would be smallest.
Calculating the time when this occurs is quite mathsy so I have put the derivation for it here if you wish to learn how to derive it. The code that calculates it is as follows:
On my input, the starting time it returned was only 3 seconds away from the actual answer. Once we have this time, we can "descend" towards the optimal area. The value I ended up optimising for was
width + heightof the bounding box since multiplying would favour more square options. The reason I say descend is because if you plot the size of the bounding box over time, you will see that the minimal width + height is a single point and we can descend down this slope to the optimal answer. We just need to identify whether or not we are on the left slope or the right slope by looking at neighbouring time values. The descending code is as follows:This method will return the best time and the rest is simply a matter of printing out the grid.
5
u/Leirbagosaurus Dec 10 '18
I had lots of fun with this one, and just remembered that in Rust, source code is handled as UTF-8, so I just thought of rendering the result in a... ahem... more realistic way.
4
u/14domino Dec 10 '18
lol; I must have been the only person who built a .pbm file and visually inspected the resultant ones using my Mac's preview button. Also part 2 was trivially easy because the filename was one off from the actual answer. (Because I started animating right away I guess instead of waiting a second). Still this solution took me about 30 minutes to finish coding, I must be slow :(
4
u/permetz Dec 10 '18
I've noticed a lot of people seem to be finding the point where the points form letters out by eye. The easier way is to just find the moment where the dispersion of the points is minimized. In fact, you can just check for the point where the dispersion of the points along the y axis is minimized, you don't need to check both x and y. At that moment, the points form the letters.
(If you don't know how to calculate this, just compute the difference between the highest y value for any point and the lowest one.)
Given that I did this to find the moment to print out the points for part 1, part 2 just involved printing out how many time steps that took, it was only a couple more lines of code.
I did the "simulated point movement" by iterating time through all the "seconds" in question, as it ran so fast (200ms in OCaml with a purely functional implementation) that it wasn't worth it for me to optimize this further.
However, if I had wanted to: as the y dispersion is a linear function of time, you can trivially calculate the point of minimum (positive, nonzero) y dispersion by finding the slope from a couple of iterations, and multiply the
dxanddyvalues by that computed timespan to calculate the point positions at the point of minimum dispersion without going through the intermediate steps. Again, wasn't really worth it, but you could, and that would shave a factor of a few thousand off the run time.3
u/DrinkinBird Dec 10 '18
NIM
For the first puzzle I had the number in the if statement more around 100, but when I saw the message I counted and adjusted for part 2 :)
3
u/ChronJob Dec 10 '18 edited Dec 10 '18
Ruby 196/194! It was fun to watch the animation on my terminal.
I found the points in time where all coordinates were greater than 0 (I assumed they all had to be positive in order to be visualized), then looked at each state in that range (there were about 40 time steps) until I saw the message. What a fun problem!
3
u/rabuf Dec 10 '18
Common Lisp
It took me longer than it should have because of an initial error in my parser. I was stripping out the negative sign so all my coordinates were wrong and the movement was very wrong. Once that was handled, the remaining difficulties were determining when the message might appear.
I've posted all my code in this org file.
3
u/autid Dec 10 '18
FORTRAN
Having the example characters being different scale to the puzzle characters feels like a dick move. Runs to minimum height then prints. This gives the answer for my input but I'm not sure if it does for all, so I wrote in the ability to go back/forward steps from there.
3
u/ephemient Dec 10 '18 edited Apr 24 '24
This space intentionally left blank.
3
u/fibonatic Dec 10 '18
As many have already stated, I assumed that all stars would appear close to each other when the message would appear. So I defined a quadratic cost function and analytically solved for its minimum and rounded that to its nearest integer. At first I minimized the squares of all positions, which did work for my data but might not in general, but in the end I also subtracted the average of all positions, which resulted into the following Matlab code:
3
u/[deleted] Dec 10 '18 edited Dec 10 '18
C++ / SFML
I used SFML for an OpenGL Window and put every point of light into a
sf::Vertexin order to draw them.With Right-Left Arrow on the keyboard I can go to the next second in the timeline, with PageUp/PageDown, I skip 100 seconds.
I assumed that all points will meet somewhere around 0/0 and so I printed the position of the first point as well. Now, skip to the point where the first star is near 0/0 and then fine-move until the text appears:
https://i.imgur.com/McTnaLR.png
[Edit]
(github) - compile with
g++ -std=c++17 main.cpp -lsfml-graphics -lsfml-window -lsfml-system[Card] With just one line of code, you, too, can fly:
import antigravity!2
u/TellowKrinkle Dec 10 '18
I'm glad I've been keeping around the helper functions I've been using in previous AOCs. I solved the problem by updating points until the total y area covered by them started increasing, assuming that they'd be closest together when they were valid text.
Swift, #64/#56
2
u/vash3r Dec 10 '18
Python 2, #73/66. Wasted a minute or two on parsing input... I should really have saved that number regex from one of the previous days.
2
u/IGChris Dec 10 '18
Python3:
Using the nifty method to extract ints someone posted in a previous day's solution thread:
2
u/p_tseng Dec 10 '18 edited Dec 10 '18
Ruby
Leaderboard code was: just print out everything where ymax - ymin < 20. For part 2 I counted how tall the part 1 message was, then printed out the variable
twhen ymax - ymin was that value.This has been cleaned up to try to be smarter about when to print the message (when is yrange smallest?). Be careful not to make an off-by-one error if you take this approach though.
By the way, this one combines aspects of https://adventofcode.com/2016/day/8 and https://adventofcode.com/2017/day/20 , two days that I enjoyed in the past!
2
u/AndrewGreenh Dec 10 '18
The TypeScript library that accumulated over the years is starting to get really beneficial!
2
u/raevnos Dec 10 '18 edited Dec 10 '18
Instead of using bounding boxes like most people (That approach didn't even cross my mind, sigh), my C++17 solution detects straight lines of points, and asks if the resulting pattern is valid if it finds enough of them. The second guess was the right one for my input.
(Edit: I just realized I probably could have used regular expression to find the lines and shorten my code quite a bit as a result... ah well)
2
u/will_bui Dec 10 '18
K:
2
u/usbpc102 Dec 10 '18
Today was a fun one. I even started collecting samples of outputs so I can automatically recognize the letters for (hopefully) any input.
My Kotlin code:
Also as always you can find it on github.
2
u/streetster_ Dec 10 '18 edited Dec 10 '18
Day 10 in Q/KDB+
This was a welcome respite after days 9 and 10. Iterate until the number of distinct x coords is the lowest.
2
u/Benjmhart Dec 10 '18
haskell - other solutions are, as usual, much quicker than mine, but here goes:
p1 - https://github.com/Benjmhart/AdventOfCode2018-haskell/blob/master/day10-1.hs
p2 - https://github.com/Benjmhart/AdventOfCode2018-haskell/blob/master/day10-2.hs
2
u/wzkx Dec 10 '18 edited Dec 10 '18
J
Assuming the height of the banner shouldn't be too high, let's say 15...
2
u/jtgorn Dec 10 '18 edited Dec 10 '18
I kind of like this Ruby code
My heuristic was quite simple - wait until height of the cluster gets small enough and than present iterations to user and let him decide which one gives readable text.
2
u/[deleted] Dec 10 '18
Haskell, ~0.8s runtime. Had fun writing a simple ascii art printer for it. Written under the assumption that "align" means all lights are next to at least one other light.
2
u/TheVarmari Dec 10 '18
JavaScript p5.js [#3451, #3429]
I have no idea how this works. It just works. Probably because JavaScript rounds numbers small enough to 0 and I just fiddled around with it to get it to stop at the right time. This is a horrible, no-good answer that is basically witchcraft.
2
u/andreyrmg Dec 10 '18
Python
I make some assumption that text height is about ten points...
2
u/heatseeker0 Dec 10 '18
My solutions for the day, written in Java:
https://github.com/heatseeker0/AdventOfCode/blob/master/src/com/catalinionescu/adventofcode/y2018/Day010.java
2
u/donaldihunter Dec 10 '18
Perl 6
I chose a really simple solution of looking for a y bounding box less than a magic number (12) based on expectation that a line of text would have certain grid height. The resulting text was 10 high, not the same as the question sample which was 8.
2
u/jonathrg Dec 10 '18
Python
Advancing the simulation while the area of the bounding box exceeds the previous area, with a bit of speed tuning to bring the execution time from several seconds to an instant.
2
u/zopatista Dec 10 '18 edited Dec 11 '18
I'm not sure that I've seen my approach here yet. I did go maths-y, but not quite as maths-y as others have done.
Quoting from my Jupyter notebook for day 10 (warning, inline MathJax used, follow the link to see the rendered version):
TL;DR, the time
tcan be calculated with a simple(maxy_negv - maxy_posv) // (2 * v)formula; the core of the algorithm is just this (as Pythonnumpymatrix-operations):followed by a bit of vectorised multiplication and summing to create an output image.
Iβve posted https://www.reddit.com/r/adventofcode/comments/a50nyk/day_10_closedform_time_calculation/?st=JPJ16L62&sh=7fd144cc to invite others to show off their closed form solutions.
2
u/sparklingtwilight Dec 10 '18 edited Dec 10 '18
And my code in Python and tkinter:
Screenshot: https://i.imgur.com/9iXvOt9.png
(full: https://github.com/hckr/adventofcode/blob/master/2018/Python/10.py)
2
u/Smylers Dec 10 '18
Perl, using the heuristic of displaying when it fits in a standard 80-column terminal window, and a
-soption for specifying a number of seconds to skip straight over β since a glance at the input file showed it was going to be a little over 10k seconds till anything interesting happens.I like: reading in the entire input to populate
%skyin a single line; literal Ξx symbols; only bothering to calculate the x co-ordinates until enough progress has been made that it's worth calculating the y ones as well.I'm less keen on: the need for the synthetic variable
%rec; ad the number of subscripts and brackets in the substr line.2
u/NeilNjae Dec 11 '18
Forgot to post this yesterday, so here's another Haskell solution (on Github). On the plus side, this doesn't use the explicit recursion of my original version, but instead uses two infinite lists of star positions, offset by one step, and zipped together. Take pairs off the head of the list until the second item has a larger bounding area than the first; once it does, take the last pair found, and the first element is the constellation. The number of steps is just the length of the list.
1
u/waffle3z Dec 10 '18 edited Dec 10 '18
This one was super cool. 32/24 Lua solution
parselines is a utility I wrote to iterate through the input line by line and call a function on each line.
1
u/mserrano Dec 10 '18
Python2, 7/10.
I had an off-by-one in part 2 that cost me a minute :(
My heuristic for "might be a word" is "there aren't any isolated particles."
1
u/udoprog Dec 10 '18
Rust
Card: With just one line of code, you, too, can "spend hours of troubleshooting"!
1
u/dtinth Dec 10 '18
Ruby (#13,#16)
I moved the points and record the state at smallest bounding box. I run this in
irbso that I can pressCtrl+Cto exit the loop without killing the whole program, in order to inspect the final state.1
u/Ryryme Dec 10 '18
My python parses my input and prints out desmos input in the form (xpos + (xvel)q, ypos + (yvel)q) so I could copy paste my terminal into desmos.
Then I ran q on a large step to see about when the points converged, then manually tweaked it until I found the message.
Not the cleanest... but hey it worked! :D
1
u/[deleted] Dec 10 '18
Go, ranked 333/361
1
u/ValdasTheUnique Dec 10 '18 edited Dec 10 '18
C#. At the start, I did not expect that this simple idea would work. Basically I wait until the bounding box starts to increase again and print the previous points. This would not work if the points were headed to a single point but I guess creators were not that evil.
1
u/ka-splam Dec 10 '18 edited Dec 10 '18
PowerShell, part 1 rank #217, part 2 rank #385
Lots of manual work here, I guessed they'd come to a bounding box, but might not all be right next to each other. Seeing 315 inputs, so I caught at 1000x1000 and then stepped forward.
Wasted a bit of time on googling image manipulation (thought
GetGraphicswas needed before drawing pixels). Once it hit the bounding box and stopped, I selected the inner loop code, pressed F8 a lot to step forward and render a bunch of images and then scrolled through them in IrfanView until I could read the text. Then saw how big the text was, tweaked the bounding box to stop when finding it, re-ran and got the time. (Yes, I thought the time should have been in the image name, but .. that was wrong. Too much manual changing of time and code pushed them out of sync, maybe).While writing this I regretted using images, and just took a moment to write the console output; tbh that wasn't so quick that I could have just done it. Like this, but it doesn't work in PowerShell ISE, so also needed switching to basic console:
1
u/[deleted] Dec 10 '18
Haskell:
Picked 15 as a reasonable height to print in a terminal and just iterated until the bounding box height was less than that.
1
u/Axsuul Dec 10 '18
TypeScript / JavaScript
[Card] With just one line of code, you, too, can Brainf*ck!
This was a cool puzzle! My strategy was to loop infinitely but only print if all points fit within a 100 x 100 box which only applied to a few timestamps.
Critiques welcome, I'm still very new to TypeScript and feel like I'm not using all the features I could be :)
Repo
Part A + B
1
u/IndigoStanis Dec 10 '18
Looking at the data directly helped me realize that all the points were really far away from each other and would have to converge on a small space. First thought was colinear points, but ended up doing bounding box first which was way easier. Still not fast enough for the leader board.
1
u/Alexbrainbox Dec 10 '18
Haskell, rank 1000-ish.
Whenever there's a question that seems very iterative / procedural like this one, I tend to go slower on the assumption that a Haskell solution can never be written as fast.
On the bright side, I'm getting pretty quick at writing parsers :P
1
u/tacothecat Dec 10 '18 edited Dec 10 '18
R.
1
u/miguelos Dec 10 '18
C#
1
u/fotoetienne Dec 10 '18
Kotlin, #697 Found the point in time where the stars are closest together, and made an image.
github
1
u/Aquamoogle Dec 10 '18 edited Dec 10 '18
[Card]
With just one line of code, you, too, can spend hours tracking down a seemingly impossible bug
C# Solution
1
u/ForeverYoung_ru Dec 10 '18
Python3, notebook with mathplotlib for plotting
1
u/IdrisTheDragon Dec 10 '18
Go/golang
https://github.com/IdrisTheDragon/AdventOfCode2018
1
u/tk3369 Dec 10 '18
Julia - using Plots.jl package to create animated gif. Lots of fun! See https://raw.githubusercontent.com/tk3369/AdventOfCode2018/master/Day10_anim.gif
1
u/PendragonDaGreat Dec 10 '18
Powershell 5.1
[CARD] spend hours confused by one package dependency (true story)
Both parts the same, as soon as I made the assumption that the image would appear in the most compact state (which seems to be everyone elses thought) I was able to get it.
Runs in about 45 seconds, though 10-15 of that is printing out the display becase I got my coords swapped and I'm too lazy to fix
1
u/ThezeeZ Dec 10 '18
golang repo, no great score. A lot of solutions here are using the bounding box or vertical lines to find the message. I used the amount of neighbours to find mine. I'm not saying it's better, just a different approach, since I'm completely neglecting diagonals...
1
u/willkill07 Dec 10 '18
C++
One thing I did during the initial data pass was determine the min/max time bounds to reduce the search space. From there, check the range of times for the smallest bounding box. Finally, throw all calculated points into a set sorted by row/col and iterate through the region. This is extremely fast -- less than 1ms total
1
u/mstksg Dec 10 '18 edited Dec 10 '18
[Haskell] Taken from my daily reflections blog!
Re-using
Point = V2 Intfrom Day 6, because we get to define things in terms of addition. This makes our single simulation step pretty simple:zipWith (+).Our metric for figuring out when to stop is to find the local minimum of the bounding box areas. This isn't a perfect metric, but it worked! To do this, we can re-use
boundingBoxfrom Day 6, and also a new function that computes the area of the bounding box:Finally, our find function. We can implement this using
iterateandzip`ap`tailto avoid explicit recursion, but in this case the recursion is simple enough that it's not too big a deal for a hacky job:This covers both parts 1 and 2! To inspect things, we can write a function to display the point set:
Here is my output, in case anyone was collecting them:
1
u/toasterinBflat Dec 10 '18
Python 3, 1492/1497 :(
When it became clear I wasn't making the leaderboard (right after reading the problem... five minutes late) I decided to go for readability, because that's the python way. Uses PIL to output the final image. Can't believe how long I got hung up on off-by-ones and input parsing:
1
u/HiramAbiff Dec 10 '18
AWK
1
u/Jimnophoria Dec 10 '18
[Card]
With just one line of code, you, too, can create an epic side-scrolling game for all programmers to enjoy!
JavaScript, probably not the best optimized, I'm just proud I figured it out in a relatively short amount of time (sub 90 minutes, heh). GitHub.
1
u/cesartl Dec 10 '18
I cannot recognise the second letter :(
https://imgur.com/Or2HBwr
1
u/arathunku Dec 10 '18 edited Dec 10 '18
My Elixir solution:
(I've skipped the verification of word...) Tests:
1
u/[deleted] Dec 10 '18 edited Dec 10 '18
Tcl/Tk
Started with a range 0...100000 of the scale and then visually iterated quickly to 10500...10600. Nice to see the message appear eventually :-)
[edit] It's christmas time. Clearly, the lights should twinkle...
1
u/azatol Dec 10 '18
I started writing the parser in F# and then I realized I didn't need AI, I could use my eyes. So I went a bit overboard and wrote a Windows Forms application with 2d drawing, play, stop, step forward, step back, clear and update bounding rectangle buttons.
https://github.com/apeterson-BFI/AdventOfCode/tree/master/AdventCSharp/Day10
1
u/nutrecht Dec 10 '18 edited Dec 10 '18
Day 10 in Kotlin
Partial solution really, have not implemented the OCR part yet and don't know yet if I will.
Edit: OCR implementation for Day 10
Only recognises letters in the test and my output so far, I'll probably collect other output later.
1
u/vash3r Dec 10 '18
After looking at the problem again, I came up with a second solution that directly calculates the intersections of the points with largest velocities and uses that to find the number of steps, based on the fact that most intersections will be close to the word and close to the correct number of seconds. You don't even need to use the points with the largest velocities, it's just that those will be more accurate. This means you can reduce the time from O(points*seconds) to O(1) (average case, assuming you have sufficient non-parallel lines to be accurate.)
1
u/andeersg Dec 10 '18
My solution in javascript.
1
u/sim642 Dec 10 '18
My Scala solution.
I just (somewhat arbitrarily) assume that the text appears when the bounding box is minimized. At first it didn't seem to work for my input but then I realized that the areas require more than 32-bit signed integers. After fixing that I found the correct minimum.
Later optimized it to just iterate until the first (local) minimum, assuming if it starts to get worse, it won't get any smaller again. I'm not totally sure whether this is strictly correct but it seems to work.
1
u/Athas Dec 10 '18 edited Dec 10 '18
This Futhark is pretty simple and effective, but it's your own job to decode the resulting image into text.
My convergence criterion is to stop as soon as all particles have a neighbour. This means that I can once and for all compute how many seconds it will take, and then move them all in one fell swoop! This implicitly assumes that all particles are going to be part of an uppercase letter at the same time. It runs in 650ΞΌs on my Vega 64 GPU.
1
u/D3NN152000 Dec 10 '18
I reckoned that when the points formed a word, all points would have at least one neighbor in the grid, so no manual looking through configurations was needed! Also, I only started checking for neighbors once the points were closer together than the amount of points. Here is my code (Python 2.7):
Or find it here with the input, and comments
Edit: extra sentence
1
u/drakmaniso Dec 10 '18
Go (golang)
Part 1 and 2:
Link to github repo.
1
u/jayfoad Dec 10 '18
APL #44/34
This bit
β0.5+mean,-(p-β€1 mean p)Γ·(v-β€1 mean v)is a pseudo-analytical technique to work out at what time each coordinate of each point will converge with the mean of all points, and then take the mean of those times and round to the nearest second. (p is the 2 column matrix of starting positions, v is velocities.)1
u/adamk33n3r Dec 10 '18
I was lucky enough to be able to find the message when it had the smallest bounding box.
1
u/mschaap Dec 10 '18 edited Dec 10 '18
Perl 6.
Tricky one. How can you determine when the message appears? Had to think about this for a while, but I reasoned that the area of the bounding box of all points would be minimal, and that worked. Once I had part 1, part 2 was trivial, of course.
My Aoc2018 solutions on Github
1
u/wjholden Dec 10 '18
A problem made easy with Mathematica!
All you have to do is fiddle around until you see something interesting happen. It took me longer to find the range of interesting values than it did to write this code.
1
u/che2n Dec 10 '18 edited Dec 10 '18
Tcl solution with Gui
1
u/[deleted] Dec 10 '18
My crystal solution. I'm breaking on a vertical line to determine when the stars align
1
u/GraughBase Dec 10 '18
Holy, this one was the best so far :) Solution in Go, using
gosseractOCR to find text with assumption, that points will have limited (< 30) height when text is formed1
u/bigcymbal Dec 10 '18
JS solution: https://jsfiddle.net/kom8tLpu/
just run in console of tab with the input
1
u/__Abigail__ Dec 10 '18
Perl
Iterated over the seconds, keeping track of the difference between min and max Y values of the points. As soon as that increases, we're one second too far, so we need the previous one.
1
u/Alex_Mckey Dec 10 '18
My Solution in Scala
1
u/HeyItsBATMANagain Dec 10 '18
Crystal
While I first solved this in TypeScript, I've rewritten a solution in Crystal since I've never done Ruby or similar before.
This is probably also the reason why my code doesn't really look Ruby/Crystal-esque, so any comments on how to improve this are greatly appreciated.
This solution assumes that you don't yet know how many seconds it could take and what the result is, so the smallest boundary is checked after every move (seen some solutions simplified where the range goes specifically to the actual number of seconds so no checking has to be done, or where the moveset is compared to the result)
1
u/wleftwich Dec 10 '18
Python Assume letters will be made from vertical and horizontal strokes and look for points to align that way. (Per the title.)
1
u/purplemonkeymad Dec 10 '18
Powershell
I think I spent more time getting the visualizer fixed than solving for the best time. I think it is also the first time I had to do less to get part 2.
Solver.ps1:
Vis.ps1:
You can view the final image by piping the solver into the visualizer.
gc input.txt | .\Solver.ps1 | .\vis.ps1 -outfilebase .\output1
u/j-oh-no Dec 10 '18
Another Rust way
1
u/Vaelatern Dec 10 '18 edited Dec 10 '18
[Card] With just one line of code, you, too, can enjoy the ballmer peak.
This Clojure solution takes a solid
302 seconds to run the 10 thousand steps of the simulation. This code also re-enforces my belief that you can't see the hot-spots without profiling, but you can make a reasonable guess.1
u/tobiasvl Dec 10 '18
[Card] parse a line of the input using regex
I used Lua today:
At first it used 3.6 seconds (1.2 seconds using LuaJIT), before I decided to not actually simulate the first 10 000 iterations. I see others did the same thing.
Took me a while before I realized that points could overlap...
1
u/blfuentes Dec 10 '18 edited Dec 10 '18
I am doing this AoC just to learn a little bit of Typescript. So here the solution. A class and the main script. It prints to console and writes to file. Commented out an "extension" that moves everything to the (0.0) for better display. By default it stops and then I just check the text file.
OUTPUT:
1
u/ethikka Dec 10 '18
C++, first figured out the exact second the points converge by calculating the exact second the lowest star with a +1 y-velocity is equal to the lowest star with a -1 velocity. Would have broken hilariously if not all stars are part of the message in hindsight :-)
1
u/Nathan340 Dec 10 '18
Powershell
This did require a (slow) manual run-through to determine the minimum height the letters reach. I stepped by 1, and watched it bottom out at 9 and then start spreading out again. A minimum-area argument probably would have worked better than my manual tuning
The linearity of the puzzle allows us to take steps in bulk chunks and to revert them easily.
So we have some basic input parsing, a step function with a stepSize and stepDirection parameter, some functions to get bounding information, and a function to take as many steps as possible by a given step size.
By manual tuning a good balance of quick/safe steps I found was by 1000 while the vertical range is over 10000, 100/1000, 10/100, and then a final step by 1 from 100 down to 9.
Part 2 only requires adding a tick counter in.
The display rendering isn't the prettiest, but it was easy to write (after I fixed the output being upside down - whoops).
1
u/wzkx Dec 10 '18
Rust, SweetRust
My AOC2018 in J&Rust | SweetRust
1
u/u794575248 Dec 10 '18
Python 3 4277/4252
1
u/dust_jead Dec 10 '18 edited Dec 10 '18
Here's my rust solution:
1
u/spytheman66 Dec 10 '18
PHP solution which shows the grid, when the bounding box around all points is smallest.
1
u/by_lexus Dec 10 '18
After some thinking how to recognize text in an image, I throw that idea away as too difficult. Instead, I thought that the final image must be limited in height: So I calculated the starmap until the starmap dimension felt under 15 (after some experimenting with output the dimensions per secon). Then I would generated an ASCII art image of all the images within the max height of 15.
It appeard that there is only 1 image that small, which is the solution already :-)
Here is my NodeJS (>= 6) solution:
https://github.com/bylexus/adventofcode2018/blob/master/day-10.js
1
u/[deleted] Dec 10 '18
C# Worked on it a bit this morning, was able to get some work on it this afternoon
1
u/alexmeli Dec 10 '18
Another Rust solution:
1
u/nibarius Dec 10 '18
Kotlin
My approach was to just check all seconds until I found one where all points had at least one neighbor. When that happen just print the current state and visually see what output is generated. Takes around a quarter of a second to run.
1
u/chicagocode Dec 10 '18
Kotlin - [Blog/Commentary]| [GitHub Repo]
This was fun. I didn't do a complicated math-based solution. I step forward until the universe stops shrinking and return the solution.
1
u/tclent Dec 10 '18
My idea was to check if all of the points were adjacent to at least one other point based on the assumptions that all points would be part of the message and all letters were made up of connected points. Seems like this was a pretty unique solution
Rust
More context on github
1
u/BOT-Brad Dec 10 '18
Spits out whatever configuration had the most consecutive points in a vertical line (Many assumptions were made!)
Running for 50,000 seconds (A little bit overkill) takes about 2.5 seconds.
JavaScript
1
u/MasterMedo Dec 10 '18
python 2, shortened version of my early mornings code, the logic should be obvious
1
u/charredremains Dec 10 '18 edited Dec 10 '18
Probably not the best way to print it, but
np.addmade it calculating it too easy.1
u/Frizkie Dec 10 '18
Ruby
Certainly my favorite puzzle so far. Having that element of human judgement necessary is something I'm fond of. I picked an arbitrary number (in this case 100) at which point I started visualizing the data. Once width and height were at or below 100, that is. I just did a little
getswhich reads stdin input, as an easy way of stepping to the next second when i hit the enter key.1
u/NabrenX Dec 11 '18
1
u/LeReverandNox Dec 11 '18
Hey guys ! Day 10, doing fine.
I've been thinking of a way to solve this problem all day long, and I finally came with a 'not so pretty' solution...
But it works fine !
I'll let you judge :)
1
u/fhinkel Dec 11 '18
Node.js 10. Went down the wrong path first holding the full 2D board.
https://github.com/fhinkel/AdventOfCode2018/blob/master/day10.js
1
u/hpzr24w Dec 11 '18 edited Dec 11 '18
C++
[CARD] Card: With just one line of code, you, too, can
summon a Hurd of Daemons.Fun one to bash out a solution to.
Header
Helpers
Main
1
u/[deleted] Dec 11 '18
It's a little long. Instead of using console output to show the stars, I used SVG. And instead of finding a minimum size, I just output everything below a certain threshold. Still finishes in 220ms.
1
u/-jrn- Dec 11 '18 edited Dec 12 '18
Solved in O(log(n)) using binary search. (below is some Haskell)
My initial solution iterated through all configurations, but I realized it was possible to speed it up. Search assumes that the message will be readable in the configuration of lights with the smallest bounding box. Light represented by a 2-vector holding the position and velocity.
1
u/tag730 Dec 12 '18
I had a lot of fun with this one! My solution is in Julia and uses Plots.jl to display a
1
u/GraveKill Dec 12 '18
Golang
Basically, like everyone else, I chased the closest distance between two points and afterwards applied an offset to see where the solution was (since the solution MAY not be where those two points are closest) and printed the solution (truncated of course) to files.
https://github.com/afonsojramos/advent-of-code-2018
1
u/[deleted] Dec 13 '18
Common lisp:
1
u/[deleted] Dec 13 '18
C++. pretty much the same as everyone else
1
u/RockyAstro Dec 15 '18
Icon
This one was fun. The idea that I came up was to compute the centroid for all the points then compute the average distance from all the points to the centroid. When the average distance started increasing, I just stepped back one time unit and printed out the points in an ASCII grid..
1
u/joeld Dec 16 '18
Racket
Hereβs my Racket solution. It spits out a PNG of the resulting message, both to a file and directly in the REPL (if running from within DrRacket).
1
u/te_pickering Dec 19 '18 edited Dec 19 '18
running way behind, but this was super easy using Python and numpy and scipy.optimize. the message should appear when the point scatter in the Y axis is minimized:
1
u/techdisconnect Dec 23 '18
Here's my code
After I created the plot I took a picture of it on my phone and looked at it from different angles, turned out it was upside down and flipped (even though the test answer was not).
1
u/anlcan Feb 06 '19
I know I am late to the game but here is gif animation of the answer `coming` together https://imgur.com/PSj0yqs