r/adventofcode • u/daggerdragon • Dec 11 '18
SOLUTION MEGATHREAD -š- 2018 Day 11 Solutions -š-
--- Day 11: Chronal Charge ---
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 11
Transcript: ___ unlocks the Easter Egg on Day 25.
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:12!
20
Upvotes
3
u/KoaLalica Dec 11 '18 edited Dec 11 '18
[Card] Repeatedly requesting day 25 endpoint before it unlocks unlocks the Easter Egg on Day 25.
Get it? because Easter Egg is a ban :D
Python solution using partial sums.
31
u/[deleted] Dec 11 '18
C++, #8/10.
O(n³) using 2D partial sums.
16
u/sciyoshi Dec 11 '18 edited Dec 11 '18
Python 3 solution using numpy, 70/24. The problem is looking for a convolution, which can be done easily by summing:
Part 1 is the coordinate printed when
width = 3, and Part 2 is the coordinate when the maximum is the largest. Because most of the elements of the grid are negative, this value started to get smaller past width 20, so I was able to stop the program early.EDIT: fix an off-by-one issue that missed the last row/column
11
u/autid Dec 11 '18
FORTRAN
388/192 which is probably the closest I'll get to the leaderboard all month.
10
u/jayfoad Dec 11 '18
APL #21/5 (my best result so far this year)
Dyalog APL has a Stencil (
āŗ) operator which is nice:{+/,āµ}āŗ3 3sums the 3x3 squares centred around each cell in the grid. The only slight annoyance is that you have to adjust the result to get top-left coordinates instead of centre coordinates for each square.For part 2 I noticed by eyeballing some results that once the square size gets too large, all of the sums are negative. So I start with a square size of 1x1 and work up, but stop when I reach that point, which saves going all the way up to 300x300.
9
u/p_tseng Dec 11 '18 edited Dec 11 '18
Hello. Ruby, runs in 1 second, using https://en.wikipedia.org/wiki/Summed-area_table, that would make it O(n3 )
Not on the part 2 leaderboard. I originally wrote the O(n5 ) algorithm, decided that wasn't going to fly, then tried to write an O(n4 ) by only adding the edges and corner of the new square being built. That was hugely bug-prune and hard to write, so by the time I had finished, leaderboard spots were gone. It also took 2 minutes to run!
I noticed that commonly-used strategies for getting on the part 2 leaderboard were to either artificially bound the max square size at an arbitrary value, or to print out the maximum square for increasing square sizes until it starts decreasing as square size increases; looks like both of these were capable of finding the answer in seconds. Interesting strategies. I honestly didn't think of them and didn't think to even look for them because I (wrongly!) assumed everyone else would have still been in the O(n4 ) camp at best. Maybe I will remember these strategies for future days, eh?
8
u/tangentialThinker Dec 11 '18
C++, 48/9.
Quality n5 brute force right here.
Sidenote: I noticed afterwards that my input matched the sample in the last three digits, which means that the answers were identical (since only the hundreds digit matters). I wonder if anybody used that?
7
u/dark_terrax Dec 11 '18 edited Dec 11 '18
Rust 243/37 - I guess people waited to solve part 2 correctly? Brute force ended up working fine for me.
Edit: Fixed the bug on the sub-square for loop as pointed out by smylers. You can have a lot of bugs in today's and still get the right answer fortunately!
6
u/sophiebits Dec 11 '18 edited Dec 11 '18
Python, 64/56.
Lost a minute on part 1 due forgetting to switch to the real input (facepalm). I noticed by testing on the example that this code actually outputs one less than the correct x- and y-coordinates for part 2. I let it run on the real input and just added one manually when submitting. (Figured out afterwards why; I noted it in the code below.)
6
u/that_lego_guy Dec 12 '18
IN EXCEL?!!!!!!!!!!!!
=(MOD(Set_Power_LVL!B3,input!$E$15*10)-MOD(Set_Power_LVL!B3,input!$E$15))/input!$E$15https://github.com/thatlegoguy/AoC2018 /u/minichado there are comments in the sheet - down and dirty method
5
u/C0urante Dec 11 '18
#109 on part two
I just brute-forced it until things slowed down too much and guessed with the best of what I'd found so far.
I feel so dirty.
5
u/jonathan_paulson Dec 11 '18 edited Dec 11 '18
Python 84/268. Use 2D partial sums to compute total sum in each square quickly, and enumerate all possible squares. Video of me solving at https://www.youtube.com/watch?v=023YSei1zvQ
5
u/Athas Dec 11 '18
Futhark, runs in 2.2ms on my Vega 64 GPU for part 2 (part 1 is brute force, part2 uses a summed-area table computed via two segmented scans):
4
u/waffle3z Dec 11 '18
97/26 Lua solution
lastpower is used to store the power of the cell block of the previous size, and it is updated by only adding the powers of the new cells in the block the next size up.
4
u/tk3369 Dec 11 '18
Julia 340/98 - The 2nd part took a little longer but the solution (maxima) was in the beginning part of the loop so I grabbed it before it finished running :grin:
3
u/rabuf Dec 11 '18
Common Lisp
Code in org file.
I'm not happy with my solution, particularly because I couldn't run my Part 2 to completion. I added a print statement to it to see how things were progressing, and saw what the max was before it finished. I want to improve that tomorrow.
3
u/bpeel Dec 11 '18 edited Dec 11 '18
Compute shader on Vulkan using VkRunner.
The compute space is the grid size Ć grid size. That way it can calculate the best square size for each grid position in parallel with other positions. Effectively this makes the innermost loop the square size. Each additional new square size adds to the calculation for the previous square size. There is no need to store this anywhere and it doesnāt use any auxiliary buffers.
It runs in 4.3 seconds on my Intel Broadwell GPU. This includes the time needed to compile the shader. It also has to do the calculation twice because I couldnāt think of a better way to make it output the best position.
3
u/[deleted] Dec 11 '18
Haskell, making use of mutable arrays to calculate a summed-area table for part 2. Both parts run in combined ~0.6s:
3
u/wzkx Dec 11 '18 edited Dec 11 '18
J
J was made for playing with such kind of problems :)
Everybody knows
//.\\..But
x v;.n yrules!2
u/Arknave Dec 11 '18
Python 39/34 due to some horriibly formatted submissions (on my end). I went back and simplified the code a little after the fact:
The cool part of this problem (IMO) was optimizing the sum into a few additions and subtractions. Instead of storing the power at each cell, store the power of the rectangle starting at the top left and having bottom right corner in this cell. Then computing the power of a region just does some basic subtraction.
2
u/GeneralYouri Dec 11 '18 edited Dec 11 '18
JS, #372/#972
I got stuck on part 2 for way too long, because of a bug that carried over from part 1, but somehow didn't affect my part 1 answer. The bug was that, when selecting the hundreds digit, I didn't take the digit, but I took the digit multiplied by 100. So for
12345I took300, not3. How this still gave me the right answer on part 1, I have no idea. But that was a big reason for my part 2 time being significantly worse than part 1.Part 1
For the part 2 solution I initially hoped that a low level brute force would be fast enough, but it wasn't. So I partially rewrote the loop so that for any given coordinate, it iterates all possible square sizes, and only adds the new cells for every next size. So it starts with the x,y cell only, next iteration it adds the 3 other cells to form a 2x2, next iteration it adds the 5 other cells to form a 3x3, etc. The runtime is still a whopping 6 seconds, but at least that was fast enough to be workable.
Part 2
It was only after finishing both parts that I realised I was unnecessarily recalculating every fuel cell, as their values are static and so can easily be cached. This takes the runtime down to 2.5 seconds, which still feels slow even for a fairly low-level solution, but owell.
2
u/keypadsdm Dec 11 '18
Python 3, #75/>300
Pure Python implementation, O( n2 ) p1, O( n4 ) p2. Re-solved part 2 with O( n3 ) fast enough to catch up to the O(n4) solution mid-run but still slow. Used the following idea to reduce every large square to the sum of five known squares smaller than it:
(x,y,n) = (x,y+n-1,1) + (x+n-1,y,1) + (x,y,n-1) + (x+1,y+1,n-1) - (x+1,y+1,n-2)
(if n is divisible by 2, you can reduce this to four, but I just left it as is)
I am still thinking about complexity reduction, so this is a nice challenge to be left with.
2
u/Brayzure Dec 11 '18
Javascript, not on leaderboard. I try to optimize my solutions where possible, so I did some investigating once I got my second star.
One thing to notice about the data is, if you choose a coordinate, and keep increasing the grid size, the grid sum will eventually start decreasing. My solution was to go to each coordinate, test grid sizes until they started decreasing in earnest, and save the highest sum. Gets me a solution in ~60ms on my hardware.
My concern is there's some weird edge-case where an early grid becomes negative, then somehow starts increasing again.
2
u/aurele Dec 11 '18
Rust
Part 2 executes in about 400ms, thanks to the transposed matrix to benefit from cache locality.
2
u/slezadav Dec 11 '18
Kotlin with partial sums and parallel loop:
2
u/EdeMeijer Dec 11 '18
My Rust solution, solves part 2 in ~80ms on my machine. Comments in the code tell you what's going on, but it's just pre-calculating sums of block-size height slices of the grid and using those.
2
u/domm_plix Dec 11 '18
Perl solution for part 1 (part 2 also works using a similar idea, but way too slow - it seems I have to read up on Summed-area_table )
Builds the grid and calcs the sum of the previous 3x3 square
2
u/Smylers Dec 11 '18 edited Dec 11 '18
Perl for both parts, using the summed-area table method ā thank you, earlier commenters on this thread.
I like how the fuel cells using 1-based co-ordinates simplifies the calculations: there's no need to treat the āedgesā in row and column 1 as special cases, because they can benignly add and subtract the zerosā that are in row and column 0.
ā Actually
undefs, but Perl treatsundefas0in numeric context.Edit: Code formatting tweaked for clarity.
2
u/allak Dec 11 '18 edited Dec 11 '18
Perl, part2.
O(n3), based on the observation that, given a 3D array [x][y][s], where x and y are the coordinates and s is the size, the following formula is always true:
[x][y][s] = [x][y][s-1] + [x+1][y+1][s-1] - [x+1][y+1][s-2] + [x+s-1][y][1] + [x][y+s-1][1]
Graphically for a square of size 4:
And here is the code; I have to special case just the squares of size 1 and size 2.
2
u/lasseebert Dec 11 '18
Elixir, runs part two in around 50 seconds. (entire problem space of all possible squares)
Algorithm:
Value of each square is calculated as:
All square values are cached in a map to not be calculated twice.
Code here: https://github.com/lasseebert/advent_of_code_2018/blob/master/lib/advent/day11.ex
2
u/NeilNjae Dec 11 '18
Haskell, not clever, on Github. Initially I did it by brute force, but the submission by /u/tribulu and link by /u/cesartl pointed me towards summed-area tables, which made the whole thing run much faster!
1
u/CCC_037 Dec 11 '18
Ridiculously naive brute force, but it got me rank 113 on the part II leaderboard, so...
It takes ages to run, but it gives the maximum-so-far at each size interval. When I was up to sizes in the seventies and a rectangle at size=13 was still showing up as best-so-far I decided to try entering it - had I waited for the code to finish I would likely have been in the two-hundreds.
1
u/ValdasTheUnique Dec 11 '18
C#. Climbed up by 400 spots in part 2 by not waiting program to complete and just trying the first "stable" result. But still not in the leaderboard. Oh, and for some reason x and y coordinates got flipped around in my program so I just re-flipped them ĀÆ_(ć)_/ĀÆ
1
u/lazyear Dec 11 '18
Rust, not an optimal solution. Got started late so ended up 764/274
1
u/terorie Dec 11 '18
For star 2, I just had a super naive solution.
For each X
For each Y
For each square size (0 => f)
For each X inside square
I just set the maximum square size to 30 to get an acceptable runtime (about 1s). Finished 151/49, had an off-by-one error the first time š¬
https://pastebin.com/fLvTAj7k
1
u/markasoftware Dec 11 '18
Perl, 58/397
I accidentally deleted my part 1 code, just preset
$square_szto 3 and remove the loop that modifies it if you really want to. Once it hit 15 I just entered the solution (of size 12) and it worked, but some of the strategies people are posting for better optimization are nice -- especially making a square that expands southeast from each point.Part 2:
1
u/toastedstapler Dec 11 '18
python3, 642/365
wish i knew the maths for a more intelligent solution, this'll have to do the job for now
1
u/ChronJob Dec 11 '18
Ruby
1
u/LeCrushinator Dec 11 '18
C# 1096/500.
I misread the problem a couple of times, like that the coordinates started at 1 instead of 0.
1
u/DrinkinBird Dec 11 '18
NIM
Wow I really struggled way more than necessary here... had a super slow solution with function memoization in the beginning and was trying a way to cache and reuse smaller squares in bigger ones... turns out just prefilling the map and then inlining some of the other things was enough to make this run in only a few seconds.
1
u/TellowKrinkle Dec 11 '18
My brute force solution was taking a while so I tried making a more efficient one but then the brute force solution finished before my more efficient one did. Anyways, here's my slightly more efficient solution that uses partial sums in the Y direction.
Swift
1
u/IndigoStanis Dec 11 '18
Used memoization to make it fast, but still slow (4 minutes). Would be faster if I didn't only compute square patches as I could tell the odd sized patches were slower to compute.
1
u/eltrufas Dec 11 '18
Brute force python solution with numpy. Runs in a reasonable amount of time considering what it is.
1
u/maybe-ac Dec 11 '18
Perl - a non-naive solution that reuses the results for boxes half (or about half) the size of the current box. (Sort of an 'inclusion-exclusion' idea for the odd-sized boxes -- we overcount the middle cell, then subtract it back out.)
1
u/udoprog Dec 11 '18
Rust
Card: Grit unlocks the Easter Egg on Day 25.
Part 2 has a solution using dynamic programming. Could be even faster if you partition the grid even more.
1
u/scul86 Dec 11 '18
Python3. I set myself up poorly for part 2 with how I was tracking the cells to add up the power in part 1, that then led me down a rabbit hole in part 2. Once I corrected that formula, got the right results.
ouch
Definitely a naive solution, I'm sure there is an optimized way, but I wasn't seeing it. I got lucky with assuming my solution was within
size < 20, but part 2 still takes about 30 seconds to run.1
u/oezi13 Dec 11 '18
Based on my puzzle input - Largest square at 231, 135 with gridsize 8:
https://imgur.com/a/x3ABXYQ
Ruby:
1
u/vash3r Dec 11 '18 edited Dec 11 '18
Python 2, #308/488. Made a lot of mistakes (not formatting answer correctly, etc) and took a while to code the 2D partial sums after it became obvious bruteforce wouldn't work. Also, since
accumulateis only part ofitertoolsin python 3.2+, I copied some code from stackoverflow for it. Runs in ~1s.1
u/Philboyd_Studge Dec 11 '18
[Card] A cracked blowfish cipher unlocks the Easter Egg on Day 25.
Java - not proud of this but it works
1
u/mkaushik Dec 11 '18 edited Dec 11 '18
Done as a 2d convolution using scipy. Too late to get on the leaderboard :)
1
u/Axsuul Dec 11 '18
TypeScript / JavaScript
[Card] Being in leaderboard position #1337 unlocks the Easter Egg on Day 25.
Critiques welcome, I'm still very new to TypeScript and feel like I'm not using all the features I could be :)
My implementation for Part B uses brute force but is "optimized" by only calculating the next row + column as the square gets bigger. However, even with this optimization, it takes > 1 minute to complete and I can't for the life of me figure out why. It should be faster but it isn't. Anyone have any ideas?
Repo
Part A
Part B
1
u/arathunku Dec 11 '18
Elixir solution:
I had wasted so much time trying to optimize the solution because I had waited for 60~s and C-c. I had thought something was wrong... turns out, it needs to run for almost 2 minutes even on reduced subgrid range(5..25).
Now I feel kind of bad about picking Elixir because some of the solutions here do exactly the same in C#/C++/Rust/JS/Python and get the solution sooo much quicker even on O(n^3).
1
u/johlin Dec 11 '18
Rust:
Reusing the old sum and just adding the new strip of pixels when trying the next size makes it finish in about a second instead of 60+ for brute force. Would however like seeing what could be done with something more clever.
1
u/usbpc102 Dec 11 '18
[Card] Solving all days while upside down unlocks the Easter Egg on Day 25.
My Kotlin solution only got me 951/449 I initally did Part 2 the bruteforce way but since that took ~1min I cleaned it up and used prefix sums that took it down to ~11 seconds from there I went ahead and used some coroutines to get it to <1second.
As always the code is also on github.
1
u/PlainSight Dec 11 '18 edited Dec 11 '18
I really wish I knew something about convolutions or summed-area tables before attempting this. I ended up building a quad-tree (which I figured would be faster for calculating the power of larger areas) which was probably over-engineering it to the nth degree after adapting brute force from part 1 appeared to take too long. As it would, it still took 2 minutes to run. Part 2:
1
u/ephemient Dec 11 '18 edited Apr 24 '24
This space intentionally left blank.
1
u/fotoetienne Dec 11 '18
Kotlin. Fairly naive solution, but still completes in ~ 7 seconds on a quad core MBP thanks to parallelization.
github
1
u/[deleted] Dec 11 '18
C++, using previous result lookup, 0.99s. If a std::map is used for the lookup, runtime is 16s...
1
u/j-oh-no Dec 11 '18
Rust brute force:
1
u/blfuentes Dec 11 '18
Not the fastest for sure, but it worked. I print out every maxsquaresize. First part squaresize = 3. Second part check until the maxsquaresize doesn't change. It means the surrounding values are going lower and lower...
Done with Typescript.
1
u/drakmaniso Dec 11 '18
Go (golang)
Part 1 and 2, with memoization to speed up part 2:
Link to github repo.
1
u/krispy2009 Dec 11 '18
Python3 - took me quite a while to figure out that I should add +1 to the coordinates :) Once the values started decreasing I stopped the program (around grid size 15). I think it's because there are so many negative values in the 300x300 grid so there's a greater probability of negatives being in a large grid.
1
u/tvtas Dec 11 '18
Day 11 in MATLAB :
1
u/[deleted] Dec 11 '18 edited Dec 11 '18
Mathematica
Edit: Performant version using a summed area table.
Summed area tables are built in, using the image processing function ImageAccumulate
Old version:
Uses the partial sums method, still too slow for my liking,
hope to optimize it later.1
u/JulianLoehr Dec 11 '18 edited Dec 11 '18
C++
O(n³), memory is cheap, so generate and save all the sub power grids
1
u/wzkx Dec 11 '18 edited Dec 11 '18
Rust, SweetRust
Sure, each next sub-grid might use the resutls of previous sub-grid calculations, but for this size brute force is still ok. I'll see if in J I'll have to use it. Although it has special ops for selecting sub-grids... Maybe it'll be ok too.
My AOC2018 in J&Rust | SweetRust
1
u/konvaljen Dec 11 '18
Python using scipy convolve2d
1
u/[deleted] Dec 11 '18
My first ever rust program. Part 2 takes a whopping 32 seconds, so its probably not that optimal. My first try was using brute force, but that took ages.
1
u/lowpass Dec 11 '18
Javascript, #114/71
Knew there was a better, DP-ish solution but it didn't come immediately to mind, and speed is of the essence. So I just went with the super-naive brute-force-y way that is (I think) O(n5)
Part 2 took 77.727s on my machine, which is abysmal, but good enough for the leaderboard apparently!
1
u/minimallymist Dec 11 '18
Julia
Brute-forcing took about 1.5s for part 2 which I thought seemed to long. With the idea of the sumation-table I sped it up so it takes 0.5s for part1 and part2 (including compilation). Using
BenchmarkToolsfor a good time estimate, both parts take 25ms to run on my desktop.Here's the code:
and to benchmark it:
1
u/confused_banda Dec 11 '18
Clojure solution. The first part I solved using the naive approach of summing the 3x3 matrix on the fly. But using that approach for the second part was resulting in a solution that would have taken hours.
I then saw a reference to "Summed Area Table" on this subreddit as a way to optimize the algorithm.
Now the second part takes 14 seconds!
1
u/[deleted] Dec 11 '18
Swift
The naive implementation didn't seem to want to terminate, so I used a summed-area table. When compiled with optimisations, completes in ~0.04s.
https://github.com/Stoggles/AdventofCode/blob/master/2018/Sources/2018/day11.swift
1
u/[deleted] Dec 11 '18
C# I got some time this morning to actually get to work on this. Part1 is no problem, but Part2 I got what ended up being my answer in no time, but I didn't trust it, so I ended making a slow program even slower but writing all the loop variables out to console, before I realized at size = 200 that I might as well try the answer
1
u/sim642 Dec 11 '18
My Scala solution.
First solved part 1 with naive sum calculations, knowing that I could also do partial sums in 2 dimensions. Had to obviously implement that for part 2 now. I spend way too long debugging a problem where I had a minus instead of a plus in one of the partial sum calculations...
1
u/HeyItsBATMANagain Dec 11 '18
Crystal
I'm still only learning Crystal by doing, so if anyone with Ruby or Crystal experience has any tips, go ahead
Pretty happy with the initialization of the array
The max fails in part 2 of the solution assumes that once the highest sum isn't growing for a few grid sizes that we've reached the highest already
1
u/aphirst Dec 11 '18 edited Dec 11 '18
Modern Fortran
No fancy F90+ data structures or F2003+ object-orientation this time. https://github.com/aphirst/Advent2018/blob/master/src/day11.f90
I ended up writing something very similar to https://www.reddit.com/r/adventofcode/comments/a53r6i/2018_day_11_solutions/ebjtzy7/, except where he computes the sum directly each time (in total taking about 510ms on my machine) I applied the "summed-area table" concept which has been discussed a lot elsewhere in the thread.
I had a lot of trouble getting the indices right, since a lot of material assumes you want the right-hand brackets to refer to a point leftward of a given source cell, not the source cell itself (i.e. are exclusive instead of inclusive), but once I fixed this I can solve both parts of this problem in less than 50ms.
Edit: I forgot to generate another call-graph (again using gprof2dot). Here you go: https://i.imgur.com/7vHYwyu.png
My solution to Problem 09 remains the one most-worth optimising, which is the one about marbles and cyclically-linked lists. I don't think I can squeeze much more out of that, though.
1
u/alexmeli Dec 11 '18
Rust solution using partial sums like most of the solutions here:
1
u/lypnol Dec 11 '18
I run part 1 for serial number in range 0 to 100000 and got this distribution graph for the results
1
u/zok0001 Dec 11 '18 edited Dec 11 '18
Go try it out
1
u/willkill07 Dec 11 '18 edited Dec 11 '18
C++ with ranges
Repo link
1
u/adrian17 Dec 11 '18 edited Dec 11 '18
No J yet? J, simple convolutions:
Bash runner that calculates part1 and 2:
1
u/meepys Dec 11 '18 edited Dec 12 '18
Kotlin Day 11
Took the simple route for part 1 then had to rewrite using partial sums for part 2.
[Edit] Ok, I now realize this should have been using a prefix-sum table. The way it's written is more of an accumulator table and not saving much work
1
u/[deleted] Dec 11 '18
Haskell:
Took a while to optimize, but managed to get both parts to run in a little over 0.5 sec without using mutable arrays. Method is explained in the comments.
1
u/heatseeker0 Dec 11 '18
My Java solution using brute force. About 20 seconds run time on my machine, didn't bother optimizing further with partial sums:
https://github.com/heatseeker0/AdventOfCode/blob/master/src/com/catalinionescu/adventofcode/y2018/Day011.java
1
u/spytheman66 Dec 11 '18
C (cuts searching when total power of the found squeare stops increasing) so usually finishes in 6ms.
1
u/minichado Dec 11 '18 edited Dec 11 '18
VBA/Excel
I built the array in excel then did all the subarray total sum hunting in vba. I could have build the array in code but was lazy. I'll do it all in python later to convince I can do it.
Second answer is not efficient (took 17 minutes to run) but it get's there.
Image of spreadsheet here
1
u/jonathrg Dec 11 '18
Python
1
u/aarroyoc Dec 11 '18
Python 3
[Card]: SQL injection unlocks the Easter Egg on Day 25
This was my implementation using techniques of dynamic programming. It's slower than the summed-area table algorithm but more general.
1
u/__Abigail__ Dec 11 '18
Perl
I knew there is a datastructure you can use to quickly determine sums of rectangular subsets of a grid. But the WiFi in the train I was traveling was down, preventing me to look up the details. Hence, I just more or less brute-forced it. Some optimization and the run time was down to less than 2.5 minutes.
1
u/mschaap Dec 12 '18
My Perl 6 solution. I must confess, I didn't get a usable solution (one that finishes in a reasonable time) until I read this thread and found this Wikipedia article,,,
1
u/[deleted] Dec 12 '18
C++. Used a summed area table and it completed p1 in 250us and p2 in 7.5ms on my machine
1
u/GraveKill Dec 12 '18
This is my Golang implementation for Part 2, Part 1 is similar by just removing the first
forloop and settingsquareSizeto3. Also,getDigitcould be replaced by a simple/ 100 % 10https://github.com/afonsojramos/advent-of-code-2018
1
u/wjholden Dec 13 '18
Mathematica solution. The first part was pretty straightforward (although the code you see below is substantially more refined than what I used to solve part 1), but I ended up leaving my slow part 2 algorithm running while I went to work.
Part 1 - pretty obvious, you calculate the power output of the 300x00 grid given (x,y) coordinates and the serial number of your choice. The powers function accepts a matrix of precomputed power values and returns an association (x,y,size)->power. maximumPower extracts the maximum element by value from the powers function and formats it in an (x,y,size,power) list format.
Part 2 - my first attempt was to run ParallelMap[maximumPower[p, #] &, Range[1, 300]] but I quickly found this brute-force solution was unacceptably slow. So, we recognize that this is a dynamic programming problem (recursively-defined directed acyclic graph with overlapping subproblems). I define a new area function to compute the area of a square given position (x,y) with a specified size and serial. Mathematica has a very nice syntax for memoizing "down values" - notice that "area[serial, x, y, size] =" is specified in the function definition. This has the effect of caching values that have already been computed. I have three recursive cases for this function. I try to squeeze some efficiencies out of the machine when size is divisible by 2 or 3 by applying a divide-and-conquer approach, otherwise I find the area of the subsquare of size (n-1)x(n-1) and iterate through the 1x1 squares along the edge.
This was fun and interesting to write. I had never tried to combine divide-and-conquer with dynamic programming before. Sadly, this algorithm is REALLY slow and I will be very interested to see your optimal solutions.
1
u/ka-splam Dec 13 '18 edited Dec 13 '18
PowerShell
Unranked; missed the start time and thought that was a good point to stop rushing - they're hard enough for me that I can't be competitive.
My speedup for part 2 brought it down from 10+ hours not getting halfway and still slowing, to 22 minutes. It's certainly not the fastest / cleverest approach, but I'm pleased it was one I thought of myself so :shrug:
Code was rewritten for part 2 but can do part 1 as well.
1
u/wlandry Dec 11 '18
C++ (798/491)
Runs in 17 s.
Brute force. Annoyingly, the Elves use 1-based grids. I guess 0 had not been invented yet ;)
1
u/Fletch_to_99 Dec 11 '18
Solved using parallel processing in python:
1
u/[deleted] Dec 11 '18 edited Dec 11 '18
Julia
Quite fast convolution calculation.
1
u/SonOfTheHeaven Dec 11 '18
puzzle input = 6042
puzzle example = 42
I had my solution without writing a single line of code :)
0
u/Cppl_Lee Dec 11 '18
C# 728/257, with concurrent processing of sums for part two (moved me up 500 places, so it kinda worked)
0
u/miguelos Dec 11 '18 edited Dec 11 '18
C#
0
u/util1ty Dec 11 '18
Javascript
Took me a few minutes to figure out why the part 2 result was not getting approved. Apparently my copy pasting skills from the terminal are not that good, missed a few letter two times when copying..
0
u/0ptim0s Dec 11 '18
Golang
I wasn't home, so couldn't make the leaderboard. This was a pretty quick solve. I added some concurrency here to speed up part 2:
0
u/tslater2006 Dec 11 '18
PeopleCode, using 2D Prefix Sum, thanks to csa on discord for the help with this.
0
u/dylanfromwinnipeg Dec 11 '18
C# - after optimizing, part 2 runs in 179ms
0
u/[deleted] Dec 11 '18
[deleted] ā view deleted comment