Previous Thread adventofcode.com/ >Advent of Code is a series of small programming puzzles for a variety of skill levels. They are self-contained and are just as appropriate for an expert who wants to stay sharp as they are for a beginner who is just learning to code. Each puzzle calls upon different skills and has two parts that build on a theme. You need to register with an account but you can appear as anonymous.
Private leaderboard join code:
368748-e33dcae3
People who are inactive for 5 days will be kicked, but other leaderboards can be made if desired.
Alternative leaderboard for those waiting for inactives to be kicked from the first:
AOC is supposed to improve your programming skills user. Not your pajeet Microsoft Excel skills.
Jeremiah Wright
This is actually useful data Now we can say that anyone who takes longer than this to do their water simulation code would have been better off simply doing it by hand
Sebastian James
Actually I started late, there's a guy in the reddit thread who got 108/106 by hand
Justin Sanders
>about to start programming >windows update memory leak steals all of my ram, freezing computer for 5 minutes, even though it's "disabled" God damn it. It'd probably be easier to put up with lesser windows compatibility in linux than this fuckfest.
If a problem can be done by hand in this short a time span then it's a bad problem.
Btw it took me 1h 2m to fill the sheet by hand including time to debug my human error. Add another minute or two because I produced the base CSV in perl 6 because I'm not *that* much of a masochist.
Samuel Foster
>108/106 by hand if he were a little faster, he'd have made the leaderboard which means we can say that this was a really shit problem
Lincoln Long
Story prediction: After helping the elves on year 18 we fix the time machine and we are finally able to return to 2018. There we find out that there were no anomalies: the elves are staging a rebellion against Santa and wanted us out of the way! Worse, the leader of the rebellion is none other than *us* from an alternate timeline! After seeing the trouble elves go through every year the us from the alternate timeline has decided to depose Santa and stop Christmas forever! But our trip through time as taught us that it doesn't matter how many elves get raped by goblins, it's all worth it for Chrismas. There's only one thing we can do to stop the insurrection: we have to travel back to november 30th and kill ourselves.
As we lie in the snow in our last moments of life we look to the sky and see a single star. It's the 50th star that we collected.
We smile, as we die, knowing that we saved Christmas.
Evan Johnson
Next year we get to play the evil us?
Jonathan Mitchell
Reminder leaderboard postions are becoming less and less relevant as less people participate. Some of the people who were getting decent times early on have dropped out. So don't pat yourself on the back for filling their spots.
Dylan Smith
next year the protagonist will be a sassy woman of color with an afro.
Jaxon Bell
Do we have those stats? Maybe the early leaderboard people are just good at adding numbers together in 72 seconds, but they're not top-100 tier at simulating overflowing water
Eli King
finally got it after fixing a few special cases in my recursive flow functions. the code might actually look nice if i clean it up.
Jason Gutierrez
A courtesy glance shows an even dropoff even near the top increasing since day 2.
>got part 1 of day 15 done after several hours (a good chunk of which were figuring out how to do pathfinding efficiently >set it up for part 2, get it working on all the examples, fails on my actual input (too low apparently), also takes a few minutes
just add 1 to your answer the range of answers is very small, so you're likely not off by more than 1-3
David Smith
Are you using pypy? Some of these puzzles are absurd to do in python without using pypy. One of my solutions (made it into the calendar this year) takes longer than all my solutions last year combined, and would probably take literally an hour to run (I haven't tested it for obvious reasons). Fortunately, with pypy, it only takes about a minute.
Colton Lewis
just finished day 14. I think I'm getting filtered. help!
Nathan Carter
If I can do it, you can do it. t. just starting 15
--------Part 1-------- --------Part 2-------- Day Time Rank Score Time Rank Score 15 >24h 3016 0 >24h 2807 0 finally did it lads, shoutout to the user who told me to use bfs
its much easier if you consider the different types of water like they did in the example
Just running a few hundred loops as a test takes minutes. I put a horizontal flood in but it's just not fast enough, maybe the problem is that it loops through all flowing water to check its floor. But I thought I had to do that since the 'floor' of stagnant water can rise. Any useful speed tips?
Logan Taylor
Reminder that if you just copy paste the solution you will get a star but you it will forever be fake in your heart.
Evan Moore
I'm getting fucking rekt by this problem. I had a working solution but it was too slow, trying to optimize it now and failing hard.
Isaac Ramirez
Just do it by hand, it'll take you an hour tops
Elijah Garcia
i had this issue as well. - use a list to store the positions of all flowing water tiles (be absolutely sure not to add a tile twice) - if flowing water has flowing water to its left and right, don't check it
Jacob Wood
>- use a list to store the positions of all flowing water tiles (be absolutely sure not to add a tile twice) I put all clay-occupied squares in a set, all flowing water tiles in a set, and all static water in a set, making sure that these sets never contain the same points. I'm not even working with a grid, but I'll try the second part I guess, if my current test ever finishes. Maybe keep surrounded froth tiles in a fourth set that never gets tested.
Samuel Allen
Maybe consider rewriting your solution in C/C++ instead of whatever other meme language you use.
Dylan Cruz
you should be using a grid as well as a list. otherwise you're looping through the entire list of clay squares just to see if a point contains clay
Julian Torres
I'm not using grids OR lists and it's still this slow.
Evan Hughes
But that's not the point
Finally did it, takes 30 seconds to run in pypy. Thank heavens part2 is the same as part1 if you didn't fuck up.
Wyatt Green
>get halfway through complex solution for day 15 >think of a better way to do the whole thing Why does this always have to happen?
Camden Allen
>it takes 30 seconds to run in pypy What the fuck? I have a recursive solution (with caching) that takes 0.2s in cpython. Even my old horrific hacked-togher repeatedly call until the amount of water doesn't change solution that was born of a failed recursive algorithm only took like 2s in cpython.
As an aside, did anyone find a nice recursive way to deal with the problem? Mine is decent now but it deals with horizontal movement as a special case. It would be nice to avoid this but I couldn't find any reasonable way.
Noah Ross
And fuck cpython for having a default recursion limit so low that a program that runs in 0.2s can trigger it.
Asher Turner
>Water pressure does not apply in this scenario. This makes life way harder.
Parker Bell
What sort of caching do you do? My C++ solution takes 10 seconds.
Dominic Lee
The dumb Go solution takes half a second. If your C++ takes more than that you have a problem. It should take substantially less due to lack of bounds checking and superior vectorization.
Jordan Bennett
How about you explain your superior algorithm
Jacob White
>Even my old horrific >only took like 2s in cpython. Sorry, that was a lie. Went back and it was 3s in pypy and 20s in cpython. My new one is still 0.2s . >As an aside, did anyone find a nice recursive way to deal with the problem? Mine is decent now but it deals with horizontal movement as a special case Never mind, I figured it out. I was looking at it the entire time but the way it bookkeeps is just slightly different and not quite compatible with the way I started.
You don't need to use a grid. I used only sets/dicts and my solution finishes in 0.2s in cpython now.
I just cache the result of my recursive function (which returns a bool). It turns out there's water flowing from two places that reaches the same square a lot of the time. Dealing with this with no special cases becomes easy if you think of this as a graph problem; you don't want to revisit nodes.
Dylan Richardson
in my part 2 for day 16 I only ever have one instruction that is solved by exactly one opcode. Even if I go back and check once that opcode is accounted for they all still have at least two possible opcodes. Am I going about this wrong or have I fucked up somewhere?
Ayden Mitchell
>I now know that opcode 123 means blah >now let me delete all occurrences of 'blah' >and let me delete any other occurrences of 123 when I go the other way: find that an instruction appears only once, and therefore must be the opcode it appears next to
Dylan Lopez
I don't want to totally spoil it but I'll try and explain enough to make it obvious. I recurse on a function that takes a coordinate. The function returns true if water from that coordinate flows and false otherwise. It caches the result in a dict to avoid repeating a bunch of time unnecessarily when water from two places reaches the same spot. First it tries to flow downward. If it can, it returns true. If it can't, then it tries to flow left and right and returns the OR of these recursive calls.
That's the basic idea. My implementation is slightly more complicated because I was stupid and treated clay vs water squares as different things and horizontal movement as a special case, but you shouldn't have to do this if you keep a visited set and treat it as a graph problem.
James Thompson
>I only ever have one instruction that is solved by exactly one opcode As it should be. Now remove that option from all of the other candidate lists and check again.
Jonathan Watson
you start by checking all opcodes that have 1 or less opcode solutions, add them to your set/dict/whatever, do it again with all opcodes that have 2 or less solutions, remove from their possible solutions the ones you already have in your set/dict/whatever, then if they have more than one possible opcode you just ignore them, until you've checked opcodes that have 16 or less solutions. you should have the full dictionary once you're done
Austin Rodriguez
Thank you Anons especially I cant believe I forgot to ignore the opcode as well as the number.
Jose Johnson
Doesn't really explain much. I suspect the bulk of my wasted time comes from two places: 1) Redoing the traversal from the tile above a split in case the level below gets filled with water 2) Checking wall boundaries sequentially after a water flow that is going right hits a wall
Aaron Stewart
Maybe this helps? t/f are bools. I handle horizontal movement as a special case which is why they aren't all filled with f's instead of water. ................t......... ...|||||||||||||t|||||||#. ...t#~~~~~~~~~~~f~~~~~~~#. ...t#~~~~~~~~~~~f~~~~~~~#. ...t#~~~~~~~~~~~f~~~~~~~#. ...t#~~~~~~f#f#~f~~~~~~~#. ...t#~~~~~~f#f#~f~~~~~~~#. ...t#~~~~~~f###~f~~~~~~~#. ...t#~~~~~~~~~~~f~~~~~~~#. ...t#~~~~~~~~~~~f~~~~~~~#. ...t#~~~~~~~~~~~f~~~~~~~#. ...t#####################.
Bentley Reed
MOTHERFUCKER I'm about ready to jack someone else's solution and call it a fucking day with this one. Fucking DAMN IT.
you only need all the stars for part2 of day 25. just leave it as a protest against AoC for the awful design of the puzzle.
Carson Fisher
>did anyone find a nice recursive way to deal with the problem
I solved it recursively. The general idea was to treat it as a binary tree problem, searching depth first, left to right.
>take starting point and search downwards until # or ~ was found >step left and right to find the bounds on the current line >if there's walls on both sides, fill that line with water >loop, until you get a cliff >call function again on whichever sides had a cliff, using the cliff edge as the new starting point >if the function reaches the bottom of all it's children, save its "wet sand" as it can't change any more >function returns 1 if it's search went all the way to the bottom, 0 if it finished filling but didn't hit the bottom of the level. This second case comes up when you're pouring onto a closed box inside a pool, so you need to call the function on that same cliff again.
My data structures could have been better, but it works at least.
Easton Butler
Did you forget to make them stop moving if they're in range?
Luis Garcia
True, but if I get all stars, I get an extra raffle ticked for 200 euros
... FUCK that might actually be it. No fucking clue how I didn't check that. This is what sleep deprivation does to you.
Hudson Sullivan
06:58:20 But I fucking did it.
Grayson Nelson
Yeah, that's basically what I did (see and ). >>step left and right to find the bounds on the current line I do this part in two loops, by stepping left/right and trying to flow downward until it succeeds (in which case I break) or I hit the wall. If either the leftward or rightward movement had a successful flow it fills it with flowing water and returns true, if it didn't, it fills it with ~ and returns false. What I wanted was a recursive solution that didn't treat horizontal movement as a special case like this. I now think it's doable but the issue would be that it would be tough to keep track of whether a square was flowing or not (because you would visit nodes before knowing whether the adjacent nodes were flowing or not). So you may need an extra pass to figure that out.
David Roberts
Are you taking all steps at the end of the turn? They move one by one. Looking at the GEG column on the right, the topmost gobling should move right because that's the fastest way (in reading order) to get to the E below him. When E's turn comes he should see that there's already a gobling on top of him and not move at all.
Chase Hernandez
It's not stopping movement when there's an enemy in range, and the pathfinding code does not recognize directly adjacent as the closest possible, since the space is occupied with itself. This makes it try to move around to the side, freeing up the closest space, causing the oscillations. I have no idea if the pathfinding actually works properly since I haven't got the fighting code done, but that's the cause of that, at least. Steps are being taken as they're decided, I'm just showing them all at the same time. I really think I should just take a break, I've been at this for 4 hours non-stop. Thanks anyway.
Isaiah Garcia
I did this but with a stack.
Still super fucking slow though.
Gabriel Sullivan
I think we are all doing something quite similar. When you would hit something down, flow right and left. My issue is, when a flow hits something downwards, I make it flow left, right, but also retry from the top, or I fall in an edge case with reservoirs that have blocks in the middle, since the water flows there but falls before completing a line, so it gets treated the same as the case when the reservoir just got flooded. Maybe tomorrow I'll check it better to see how to optimize that.
Julian Peterson
This code of mine gives the right answer for part two, but not for part one. My algorithm is fundamentally ok but off somewhere. pastebin.com/Ux72RQye Input: pastebin.com/t9CgG5Hd
Brody Campbell
The past few days burned me out. I don't even want to parse this input.
Jacob Ward
You don't have to. The creator says he intends for his puzzles to be fun or to be used as a teaching example and if you find the puzzles boring then it's ok to just skip it. He's also said he has a different target audience in mind for each puzzle, some are all about finding the most efficient solution, others are meant to produce cool visualizations, others involve a lot of parts you need to figure out for yourself and some are incredibly detailed but involve a lot of complexity. He also said the leaderboard is only there for that small portion of people into speed programming competitions which almost nobody is and even he doesn't pay attention to it.
One puzzle might be something you love while another seems like a waste of time.
Brandon Lee
Yeah but I really want my 100 stars. I'll do it tomorrow if day 18 is comfy and motivating.
Ayden Bailey
what's more important to you? "get stars and fuck bitches" or "solve it myself"?
Anthony Myers
>my 100 stars it's 50 stars
Colton Lopez
I have 50 from last year.
Robert Morgan
I'm going back to finish days I missed and wtf is day 9? it took me minutes to work out what they actually want me to do.
Landon Hill
How long is this aoc thing going to be going on for? Until after new years?
Eli Williams
Ends on christmas day, day 25.
Jayden Lee
I can forgive mudslimes for not knowing how long advent takes... but being so stupid to not be able to plainly see how many tasks/daus there are on aoc site...
Henry Nelson
What kind of ballpark are people's answers for part 1 in? Over 2k?
Isaac Hall
~30k
Nolan Nelson
Oh shit I gotta speed my implementation up then
Nathaniel Hall
>As an aside, did anyone find a nice recursive way to deal with the problem pastebin.com/uDr98AfG the basic idea is the same as as far as I can tell
Jack Walker
try printing the final grid so you can look for errors, they should be pretty easy to spot another possibility would be counting too many rows. in my input I had three rows between the source and the first y in the input, so my initial answer was off by 3
Spoiler for a recursive solution (adapted and simplified from a reddit comment): def flow(clay, bottom): still, moving = set(), set()
def traverse(p): if p in moving: return
moving.add(p)
x, y = p
if y >= bottom: return False
below = (x, y + 1)
if below not in clay: traverse(below)
if below not in clay and below not in still: return False
left = (x - 1, y) right = (x + 1, y)
left_finite = left in clay or traverse(left) right_finite = right in clay or traverse(right)
if left_finite and right_finite: still.add(p) while left in moving: still.add(left) left = (left[0] - 1, y) while right in moving: still.add(right) right = (right[0] + 1, y)
return left_finite or right_finite
traverse((500, 0)) return still, moving
Matthew Smith
I'm at day10. Since the draw area isn't defined in the puzzle, I've just based it on the initial positions of the lights. That works fine for the example input, but not for the "real" input. How do I know what the size of the frame is I should draw for any given input?
Quick update just spent ages thinking part two meant I had to have the last score be 100 times higher. Lost a lot of time not know why the result was wrong. Am an idiot or is loads of Day 9 worded in an insane way?