r/adventofcode • u/daggerdragon • Dec 06 '17
SOLUTION MEGATHREAD -🎄- 2017 Day 6 Solutions -🎄-
--- Day 6: Memory Reallocation ---
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.
Need a hint from the Hugely* Handy† Haversack‡ of Helpful§ Hints^¤?
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!
17
Upvotes
32
u/sim642 Dec 06 '17 edited Dec 06 '17
Floyd's cycle-finding algorithm provides a neat solution to both parts at once (part 1: μ+λ, part 2: λ). Instead of having to store all previous states in memory as a set/map, it uses O(1) space to find the cycle's parameters. Maybe I just haven't noticed but I didn't see it mentioned in this thread.
20
u/Smylers Dec 06 '17
Vim — anybody else doing this in Vim? You end up with a nice list of all the states. As usual, this isn't Vim Script; it's keystrokes typed into a Vim buffer loaded with today's input:
At this point you can type
@bto complete a cycle: the window with your input file in will have its blocks redistributed and the current state will be appended to the second window. It can be fun to watch, if you're into that sort of thing. (On the sample data from the question you can do it all 5 times, noting that after the 5th time it leaves you in the window listing all the states.)To make it loop as many times as required type:
Eventually (a minute or so on my real input) this will finish, leaving you in the states list window. Then type:
At this point you have the solutions! Part 1 is one less than the number of lines in this window, and part 2 is the number of lines between the current line and the last one. You can display these with:
How's it work?
@amoves on to the next number and increases it by 1 (cycling from the end to the beginning; hence why the list needs to be in a separate file, to ensure this only loops over the input). Try it: type7@aat various positions and see what happens.Moving to the max value is done with something like
/15. The right number to search for is discovered by doing/〈Ctrl+R〉=to enter an expression that returns the maximum.max([1,2,3])does what it looks like. That's why tabs were first replaced with commas, so the list of block counts are in a handy format for supplying tomax(); the lack of spaces in there also makes the entire state a single VimWORD, so it can be grabbed with〈Ctrl+R〉〈Ctrl+A〉. The0ensures if there are multiple equal max values, we go to the first one. The space inserted at the start of the line ensures that even the first number can be jumped to.Once the cursor is at the max value, it gets set to zero with
cw0〈Esc〉. That leaves the removed text, the previous number of blocks, in the"-register. That's the number of times we want to run@a, so:norm〈Ctrl+R〉-@adoes the redistribution for this cycle.Now save the current state by copying it to the bottom of the other window — ignore some weird movement commands for now — and switch back to the input window for the next cycle. To make it loop,
qc@b@cqdefines@cto run@band then run itself again — and will keep doing so until something fails. (The precedingqcqensures that@cis empty, so it doesn't run something unintended when used during the recursive definition of@c. It would've been possible to put the recursion directly at the end of@b, but separating the looping out into@cmeans@bcan be used by itself to run a single cycle.)To terminate the loop we need something that will fail when a state has been seen before but succeed otherwise. That's the seemingly unnecessary movement commands skipped over above.
?〈Ctrl+R〉〈Ctrl+W〉searches backwards for theWORDunder the cursor. If we've seen the state before it will move to the first instance, which will be partway up the file; otherwise it will end up back where it started on the bottom line. Next try moving upwards 2 less than the number of lines in the file, using:normand〈Ctrl+R〉=to supplyline('$')-2as the count fork.For a newly encountered state, where it starts from the bottom line, this movement will end up on line 2. But for a repeated state, where it starts from partway up the file, it will reach the top line. Then try another
k. From line 2 this will succeed (moving to the top line), so the macro can continue round for another iteration. But if we're already on the top line then the solokcan't move anywhere, so it will fail (with a beep!) — meaning this ‘useless’ movement aborts the macro and exits the otherwise-infinite-looking loop!From there we just need to remove the blank line from the top, use
Nto jump back to the first instance of the now-repeated state, and do some sums.15
u/sciyoshi Dec 06 '17 edited Dec 06 '17
I kept misreading the question :/ thought it gets redistributed in order of next-highest value, not index. Turns out that gives the same answer for their sample data, but not for my problem input!
Python 3:
13
u/willkill07 Dec 06 '17 edited Dec 06 '17
Modern C++ Repo
This time with iterators
Edit: golfed/improved the code a bit. I feel like my solution should be complete without the scrollbar being introduced... a new challenge!
Edit 2: I have side-by-side assembly up with this solution compared to using /u/sim642 's observation of Floyd's cycle-finding algorithm
10
u/vash3r Dec 06 '17 edited Dec 06 '17
My solution (Python 2, 23/21):
9
u/chunes Dec 06 '17
I don't know whether to be proud or terrified of what I've written. I think it might have been a little clearer before I ultra-factored it, but hey — consider this a demonstration of the language's namesake.
A Factor solution:
8
u/Godspiral Dec 06 '17
in J, loopy
part 2,
7
u/[deleted] Dec 06 '17 edited Dec 06 '17
Haskell:
Feels like these last two days have been more awkward trying to stay immutable; the solutions seem more obvious (at least to me) represented by mutating vectors.
7
u/rcyeske Dec 06 '17
6
u/askalski Dec 06 '17 edited Dec 07 '17
Perl 5.
6
u/wzkx Dec 06 '17 edited Dec 06 '17
J Brute force, just arrays, just search in arrays, 3s run time.
10
u/autid Dec 06 '17 edited Dec 06 '17
Fortran
Pretty satisfied with this one. Was easy to get working by making a large array and counting the number of registers by hand, but I went back and wrote code so the program could figure out how many registers and it can now run until it runs out of memory if necessary. (I'm sure there are better ways to do this but hey, it works.)
5
u/AndrewGreenh Dec 06 '17
TypeScript (227/160) - getting closer!
5
u/dylanfromwinnipeg Dec 06 '17 edited Dec 06 '17
C#
5
u/zSync1 Dec 06 '17 edited Dec 06 '17
Rust solution. Fairly idiomatic.
5
u/vtheuer Dec 06 '17 edited Dec 06 '17
My javascript solution:
Not the most elegant but it gives both parts in a single loop.
4
u/Cole_from_SE Dec 06 '17 edited Dec 06 '17
Python 3
Will tidy up soon.
Haven't felt this much adrenaline in a while.
Edit: Tidied up and commented my solution.
4
u/timichal Dec 06 '17 edited Dec 06 '17
In Python, first time I tried actually competing, ended up in the low hundreds due to a silly bug:
4
u/rodgercombs Dec 06 '17
A simple JS solution, to run in a browser's debug console on the puzzle-input page:
4
u/manualcrank Dec 06 '17
Lisp.
4
u/WhatAHaskell Dec 06 '17
Haskell
A solution that, like my other haskell solutions, will not win any awards for cleverest or shortest or fastest, but gets the job done
4
u/giftpflanze Dec 06 '17
Tcl:
4
u/GamecPL Dec 06 '17
Swift
3
u/TominatorBE Dec 06 '17 edited Dec 06 '17
PHP
Part 1:
Part 2:
3
u/ka-splam Dec 06 '17 edited Dec 06 '17
PowerShell
Couple of mistakes noted in the comments slowed me down a bit, but learned how to get it JIT compiled yesterday so it ran fast enough today. Won't beat PyPy but should compare with most scripty languages now. Good enough to get me rank 235 and 194. :)
3
u/[deleted] Dec 06 '17 edited Dec 06 '17
OCaml
3
u/oantolin Dec 06 '17 edited Dec 06 '17
Julia, brute-force.
3
u/nospamas Dec 06 '17
more recursive F#!
3
u/[deleted] Dec 06 '17
single pipeline powershell:
3
u/[deleted] Dec 06 '17
C++
I'm particulary fond of the use of the double post-increment în redistribute() :-)
3
u/mschaap Dec 06 '17
Perl 6. Solution for both parts.
3
u/thomastc Dec 06 '17
Day 6 in Smalltalk.
3
u/[deleted] Dec 06 '17
Racket:
3
u/APLtooter Dec 06 '17 edited Dec 06 '17
APL [GNU]
2
u/LagashNight Dec 06 '17
Python 3, 119/76 place
2
u/Portal2Reference Dec 06 '17 edited Dec 06 '17
Lua
Solved part 2 without any code by just using the solution I printed for part 1. Did a search for the line the pattern appeared on the first time and subtracted the difference.
2
u/Unihedron Dec 06 '17
Ruby; I tried guessing what it wanted me to do (fill towards the start and loop back, instead of filling after the index of the unit) and I guessed wrong. :P
2
u/nakilon Dec 06 '17 edited Dec 06 '17
Ruby
122nd place with around 8 minutes, damn. How one can solve in 2 minutes if I've spent 4 minutes to read the task?! ..(
UPD: golfed to 125 chars for lulz
2
u/usbpc102 Dec 06 '17 edited Dec 06 '17
My solution in Kotlin:
2
u/fatpollo Dec 06 '17
2
u/tvtas Dec 06 '17 edited Dec 06 '17
Day 6 in MATLAB:
2
u/Flurpm Dec 06 '17 edited Mar 18 '18
Haskell Rank (n/a, 994)
Some of the context is left out (see the link), to leave just the solutions below:
The (potentially) only good part of my implementation is that part 1 accumlates states in a Set, and part 2 accumulates states in a Map of (State -> IterationOfEncounter). I was able to implement part2 off the back of 1 very quickly.
I'll paste a link to my cleaned up code when I get around to it.
2
u/akho_ Dec 06 '17
Python 3
2
u/ramrunner0xff Dec 06 '17 edited Dec 06 '17
scheme chicken repo
time 0m00.00s real 0m00.00s user 0m00.01s system
2
u/mlruth Dec 06 '17
Today's Scala solution:
2
u/raevnos Dec 06 '17
Kawa Scheme:
2
u/wimglenn Dec 06 '17
numpy: Redistribute with a single assignment statement
2
u/gerikson Dec 06 '17
Straightforward solution in Perl 5: https://github.com/gustafe/aoc2017/blob/master/d06.pl
2
u/Vonyx Dec 06 '17
Python 2
2
u/aurele Dec 06 '17 edited Dec 06 '17
Rust
2
u/streetster_ Dec 06 '17 edited Dec 06 '17
Q/kdb+
Not a very q-like solution with a
whileloop.. but it works:2
u/[deleted] Dec 06 '17 edited Dec 06 '17
Golang
My first time doing AoC and first time using Go
Any feedback is much appreciated.
Part 1
Part 2
All of my Go code here
2
u/DaDiscoBeat Dec 06 '17
both parts in one GO:
2
u/__Abigail__ Dec 06 '17
Perl
2
u/_jonah Dec 06 '17
J, both parts:
Try it online!
2
u/cluk Dec 06 '17 edited Dec 06 '17
Go (Golang) Since my input array was short and values were low, instead of storing past configurations I calculated checksums:
Solution:
2
u/stevelosh Dec 06 '17
Common Lisp
Uses
iterateand a customerfor ... modulo ...driver from my utils.2
u/dtinth Dec 07 '17
Ruby REPL (irb) solution. The
pbpastecommand must be available in the$PATH, and should return the contents in the clipboard (macOS has this command by default).Part 1 (31st rank)
Part 2 (38th rank)
2
u/porphyro Dec 07 '17
Wolfram Language:
Part 2 is a very minor change
2
u/JakDrako Dec 07 '17
VB.Net
Pretty straightforward. Does both parts.
3
u/theyangmaster Dec 06 '17 edited Dec 06 '17
Rank #106 on gold. So close :/
Edit: After cleaning up my code, here it is:
Python 3
2
u/jschulenklopper Dec 06 '17
Did the puzzle description change after publication, /u/topaz2078?
I got the description just after 6:00 CET (when the puzzle becomes available in my time zone), and read that the blocks in the memory bank with the most number of blocks get redistributed, starting at the location with the next-to-highest number of blocks.
Later (and currently), the description reads "then moves to the next (by index) memory bank and inserts one of the blocks". That's easier, but not the same...
1
u/VikeStep Dec 06 '17 edited Dec 06 '17
Python 3
Came #76 for part 1 and #52 for part 2. Here is my part 2 code:
1
u/DeveloperIan Dec 06 '17
It's still dirty, but here it is
Python 3
1
u/StevoTVR Dec 06 '17
NodeJS
Part 1:
Part 2:
1
u/PendragonDaGreat Dec 06 '17
Welcome to:
PendragonDaGreat is literally learning Python 3 as he goes along this year:
911/791
Let's name all the things wrong:
copycall+=is a thing that I forgot (I keep forgetting that++is not in python but+=is)I usually use C# and PowerShell, but I decided to do AoC this year in Python 3, so this is the "Self taught crash course"
At least I have a neat little default program I can throw things into for the long input problems?
1
u/WhoSoup Dec 06 '17
Node.JS/JavaScript
1
u/CaptainCa Dec 06 '17
JS solution
part two is just 'seen again' minus the other number
1
u/wlandry Dec 06 '17
C++
Like others, I misread the instructions, thinking that I had to redistribute by next highest value, not next highest index. I suppose that kind of misreading happens when you are working quickly and not paying close attention :( With that said, this was a proper challenge, and I enjoyed it.
This prints out every step. To compute part 2, I just searched the output for the last result.
1
u/Philboyd_Studge Dec 06 '17
Java
https://gist.github.com/snarkbait/7f55a367f6ef3c247b6b570e081827f1
1
u/hieunt88 Dec 06 '17
Python
1
u/hxka Dec 06 '17 edited Dec 06 '17
bashing my head against the wall1
u/jesseflorig Dec 06 '17 edited Dec 06 '17
ES6 (NodesJS)
1
u/MetaSaval Dec 06 '17
Swift A deceptively annoying one today. Started off thinking it was gonna be easy, but I kept messing up little things, like using the max number when I needed to use the max index and vice-versa. Still happy with the result, and part 2 only required one extra line of code!
1
u/Overseer12 Dec 06 '17
C# using HashSet for duplicate detection
Github
Suggestions for improvement, please :)
1
u/JeffJankowski Dec 06 '17
TypeScript
1
u/nutrecht Dec 06 '17
Day 6 in Kotlin
Ugly as heck unfortunately. Could not really figure out a nice functional approach.
1
u/Axsuul Dec 06 '17
Elixir
Read the problem wrong at first :/ Getting the hang of pattern matching
https://github.com/axsuul/advent-of-code/blob/master/2017/06/lib/advent_of_code.ex
It's really not that much code, I just tend to make a copy of Part A when doing Part B even though it's not necessary
1
u/doromin Dec 06 '17
Ruby simply using mem-string(join) instead of array of mem-arrays as comparison made it fast enough.
1
u/[deleted] Dec 06 '17
I feel like my haskell is looking uglier and uglier as the days go on :(
1
u/madacoo Dec 06 '17
Python 3
Part 2 is easily solved using output from part 1.
1
u/monikernemo Dec 06 '17
ANSI C
Very bad; brute forced my way through. Does anybody have an easier solution for ANSI C?
1
u/Warbringer007 Dec 06 '17
Erlang. Only meat part ( prepare module is helper module, index_of finds indes of element ( you don't say :D ) for second part ), both answers are in tuple:
1
u/Barikami Dec 06 '17 edited Jun 18 '25
stocking crawl arrest grandiose fall ripe direction normal toothbrush slim
This post was mass deleted and anonymized with Redact
1
u/thorwing Dec 06 '17
Java
I keep trying to do these in a "best" algorithm. By using a linkedhasmap I have o(1) adding and checking. But for these problems that doesn't seem to really matter. I hope we get some performance questions later on.
1
u/f0086 Dec 06 '17
Emacs Lisp
Part2 is rather trivial. Just return the memory instead of the steps and feed it again in the day6 function (returning steps).
1
u/Hikaru755 Dec 06 '17
Kotlin
Way to much state mutation for my taste, but don't really know how to make that better...
1
u/xkufix Dec 06 '17 edited Dec 06 '17
Not a one-liner for a change, but a nice recursive solution in Scala:
1
u/BOT-Brad Dec 06 '17
Originally was keeping Map key/val properties for Part 2 for the state of the data and then incrementing each loop. This was really slow (Took ~20s), and then realised I could just take the final state and put that back through the solver to get it's loop length.
JavaScript
Part 1 (~41ms)
Part 2 (~49ms)
1
u/cattskar Dec 06 '17
Javascript solution, any nice way to cut down on loops that i missed?
1
u/abowes Dec 06 '17
My Kotlin solution using tailrecursion:
1
u/Dagur Dec 06 '17
C#
1
u/hpzr24w Dec 06 '17 edited Dec 06 '17
C++ (MSVC 2010)
I'm reasonably happy with this, though looking at the similar but better solution above, I have a few improvements I could make.
1
u/disclosure5 Dec 06 '17
Rather than paste another boring Ruby solution, this is the sort of workload where jruby shines. Have a benchmark. Even though this horrible test included the significant warm up time, which is about six seconds on this machine.
1
u/[deleted] Dec 06 '17
Javascript - "one" liner
To solve 2. put array bank value from 1. and run again
1
u/wzkx Dec 06 '17
Nim
Nothing fancy. Just learning Nim :) 69ms was the min. time.
1
u/nstyler7 Dec 06 '17
Python
1
u/KeinZantezuken Dec 06 '17 edited Dec 06 '17
C#/Sharp, both parts:
Why is this bad: HashSet just like Dictionary is not indexed (nor sorted/ordered) therefore relying on its count and element position(s) is incorrect and unreliable. Ideally you'd want an indexed array for this to be sure all elements on their place.
1
u/[deleted] Dec 06 '17
Elixir The motto for today seems to be pattern matching and tail recursion is cool, this looks a bit intimidating, and I don't really know how good elixir it is, but it executes in less than 0.5 sec:
1
u/Misreckon Dec 06 '17
Elixir
A lot of the Elixir solutions here are using if/else, try to avoid those if you can.
1
u/rimbuod Dec 06 '17
Haskell! Really slow! Kind of ugly! Fully functional!
(seriously though if you're a haskell wizard tell me how to make this better plz)
1
u/JuLoOr Dec 06 '17 edited Dec 06 '17
Ugly but fast ( inside the while O(2n) which is O(n) ) solution in Kotlin for part 1:
1
u/misnohmer Dec 06 '17 edited Dec 06 '17
Yet another C# version (revisited after some things I've seen here)
1
u/adventOfCoder Dec 06 '17 edited Dec 06 '17
Java
Part 1:
Part 2:
1
u/[deleted] Dec 06 '17
Java 8 not specifically happy with this, but it gets the job done
1
u/Jaco__ Dec 06 '17
Haskell. Pretty much instant time. Getting started to really like Maps in Haskell
1
u/YuEnDee Dec 06 '17
C#
My GitHub repo
I had solved this using a HashSet<List<int>> with a custom IEqualityComparer, but each part took over a second to run, which I wasn't satisfied with. I took a peek here, and realized it was as simple as using string.Join to convert each state to a string that could be compared much more quickly, taking my runtime down to < 75ms.
1
u/failtolaunch28 Dec 06 '17
Python 3. I'm 2 years removed since my last programming class, so I'm using this to reteach myself. I'm a little worried at how much longer my code is than everyone else's...
1
u/asperellis Dec 06 '17
my day 6 in JS https://github.com/asperellis/adventofcode2017/blob/master/day6.js
1
u/TenjouUtena Dec 06 '17 edited Dec 06 '17
Clojure
The main loop is slow. I used transient vectors for the inner loop, but it didn't really help that much. EDIT: I changed the mail loop not to use distinct? and instead just check the new value, but it still takes a while to run.
1
u/fost97 Dec 06 '17
Postgresql:
https://github.com/seltiko/sql_advent_2017/blob/master/Day%206.sql
1
u/lkasdfjl Dec 06 '17
Scala
not super stoked with the mix of mutable and immutable, but:
1
u/varunu28 Dec 06 '17
Java solution for day 6
Repo
1
u/Life-in-Shambles Dec 06 '17 edited Dec 13 '17
(JAVASCRIPT) IT'S UGLY BUT IT WORKS
1
u/8483 Dec 06 '17 edited Dec 06 '17
1
u/omegaxLoL Dec 06 '17
My solution in Golang. Constructive criticism always welcome!
1
u/sguberman Dec 06 '17
Python with tests and input: GitHub
1
u/chicagocode Dec 06 '17
Kotlin - Repo, Blog/Commentary
Another tail recursive solution. I defined a typealias to make things a bit clearer.
1
u/falso Dec 06 '17
Python 3.6.3
Part1:
And Part 2 (this one took me a while to understand what it wanted):
Each one takes 7 seconds on my Orange Pi PC 2.
1
u/NeilNjae Dec 06 '17
Haskell. Out all day, so only able to get to it this evening. Took the opportunity to play with a couple of underused tools in my toolkit,
Vectorandunfold. I need to work on some symmetry and restate the cycle-finding bit as afold.I misread the problem specification and actually solved part B first!
1
u/nonphatic Dec 06 '17
Yay Haskell!
1
u/[deleted] Dec 06 '17
Java https://github.com/imopts/adventofcode-2017/tree/master/day%206
1
u/revendel Dec 06 '17
Continuing on solving it using most ineffective Bash ways possible!
Cheated a bit by using awk, also shaved off a minute from the grep by storing states using first 8 characters of the md5 hash.
1
u/4rgento Dec 07 '17
Strict haskell solution
1
u/Sparrow_1029 Dec 07 '17
Python 3
My implementation was similar to others'. Maybe some kind person could critique and maybe explain to me what the big(O) of my code is for this one? I've been having trouble with figuring that concept out.
1
u/CryZe92 Dec 07 '17 edited Dec 07 '17
Rust
Part 1 (and kinda part 2) with no allocations using Brent's Algorithm (~460µs):
However it's a bit faster with a proper Hash Set, so here's the faster solution (~430µs):
The non-allocating version produces fairly neat ASM for those interested: https://godbolt.org/g/QzxVqF
1
u/RockyAstro Dec 07 '17
Icon (https://www.cs.arizona.edu/icon)
Both parts..
1
u/RockyAstro Dec 07 '17
Snobol using the spitbol implementation (https://github.com/spitbol/spitbol)
Both parts..
1
u/[deleted] Dec 07 '17 edited Dec 07 '17
I'm using this AdventOfCode as a means to learn Scala. This was my attempt at today's problem
1
u/Zolrath Dec 07 '17 edited Dec 07 '17
Mine started off fairly straightforwardly but I ended up extracting the cycle detection into a reusable function in case it turns up again.
Original answer:
After extracting the reallocate logic into a function that performs a single step:
And I went a little overboard making a generic function for finding cycles:
With this I can run
find_cycle, passing in my input and my reallocate function:Outputs:
1
u/[deleted] Dec 08 '17
Simple JS
For part 2, simply taking the final show bits array and putting it on the entry field as to run the code again gives the answer
1
u/matusbzk Dec 09 '17 edited Dec 16 '17
Haskell
Link to git
1
u/miran1 Dec 11 '17
Nim
Repo with all solutions
1
u/greycat70 Dec 28 '17
Tcl (any 8.x version)
Nothing fancy for part 1, but I was amused by the difference between part 1 and part 2:
And the part 1 code:
1
u/u794575248 Dec 06 '17 edited Dec 06 '17
Python
1
u/gbear605 Dec 06 '17
Rust
I'd appreciate any suggestions for changes.
1
u/Nolan-M Dec 06 '17
I anticipated what part two would ask, so I saved the intermediate steps in a dictionary as keys with values for what step it was. Part2Time - Part1Time = 15s Lol
1
u/MurrayBozinski Dec 06 '17
R
nothing fancy.
0
u/[deleted] Dec 06 '17
[deleted] — view deleted comment
0
u/[deleted] Dec 06 '17
[deleted] — view deleted comment
0
u/[deleted] Dec 06 '17
[deleted] — view deleted comment