/aocg/ - Advent of Code 2018 General #35

Water edition

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:

208834-4a1a9383

Attached: 9PbTiRr.jpg (604x533, 212K)

Other urls found in this thread:

ix.io/1wbU/cpp
old.reddit.com/r/adventofcode/comments/a6jb8n/day_15_part_1python_3_get_correct_answer_for/
pastebin.com/Ux72RQye
pastebin.com/t9CgG5Hd
pastebin.com/uDr98AfG
twitter.com/SFWRedditGifs

WHY

Attached: Capture.png (854x569, 15K)

>Water edition
Ah, the creativity of panicked thread creation. Not that I could do better.

I made a few mistakes when filling in the sheet but I got there eventually

Attached: chrome_OglS1xPmJJ.png (1024x149, 25K)

And of course part 2 was trivial from that

AOC is supposed to improve your programming skills user. Not your pajeet Microsoft Excel skills.

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

Actually I started late, there's a guy in the reddit thread who got 108/106 by hand

>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.

Attached: Capture.png (413x458, 28K)

I wish (anonymous user #193354) would post his solutions again
Anyway I got 193 / 182

Attached: Screenshot from 2018-12-17 02-43-00.png (958x995, 28K)

Just install a GNU/Linux distribution user

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.

>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

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.

Next year we get to play the evil us?

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.

next year the protagonist will be a sassy woman of color with an afro.

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

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.

A courtesy glance shows an even dropoff even near the top increasing since day 2.

good enough i guess.
ix.io/1wbU/cpp

flow_down flow_side do most of the work

>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

Fucking shit.

Attached: 1514403812894.jpg (1280x720, 67K)

>also takes a few minutes
Are you simulating the whole thing or breaking when a single elf dies?

I BEEN THROUGH TOO MUCH SHIT
WATER WILL NOT FILTER ME
I'LL FIGURE IT OUT

Attached: after day 15.jpg (850x1202, 206K)

The latter, starting the combat over with elf attack one higher whenever an elf dies (I'm a Pythonlet so it's to be expected desu).

>Gobbed
>Waterboarded
Good bye, it was a good run while it lasted.

Attached: 1180924547471.jpg (2000x1333, 354K)

just add 1 to your answer
the range of answers is very small, so you're likely not off by more than 1-3

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.

just finished day 14. I think I'm getting filtered.
help!

If I can do it, you can do it.
t. just starting 15

Attached: Capture.png (905x472, 33K)

you should be using with and defining your return value.

>Finally got a valid solution for the test case of today's problem
>Okay time to run my input
>It's taking minutes
Oh no

>pythonfags

...

Seems I have a strange bug where some reservoirs aren't filling after a split. Huh

This is my input, on part 2 I get 39906 (27 rounds, 1478 HP). Does anyone get anything else?

################################
###########....#################
###########......G##############
############.G......############
############........############
########..G#.............#######
#########.G.G................#.#
######..#.......G..............#
#######...G.....G.....#........#
########..............E....##.##
###....G##GG........G.....######
###.###.##............##.#######
###G##.....G..#####...#######..#
##........#..#######..#######..#
#...........#########.##.#....##
#...........#########.......####
#.......E...#########.##......##
#G...G...#..#########.###......#
#...G.......#########E#.#.....##
#....#.....E.#######.......E..##
###.###.......#####...#.E....###
######................#.E....###
#######G.#...#..##.####.......##
#######..E.........######.E.####
#######.##...G.....######..#####
#######..#.G......#######.######
#####....#.#.....#######..######
#####.E..###..##########.#######
#####..######.##########.#######
#####..######..######....#######
######.#######.#####.....#######
################################

I get 41972 on round 28.

The answer is 41972. I had the same input.
There is a pastebin with your same input in this thread if you want to debug your code.
old.reddit.com/r/adventofcode/comments/a6jb8n/day_15_part_1python_3_get_correct_answer_for/

--------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

Attached: 1534786270624.jpg (1080x1288, 181K)

Thanks, currently testing the other inputs.

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?

Reminder that if you just copy paste the solution you will get a star but you it will forever be fake in your heart.

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.

Just do it by hand, it'll take you an hour tops

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

>- 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.

Maybe consider rewriting your solution in C/C++ instead of whatever other meme language you use.

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

I'm not using grids OR lists and it's still this slow.

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.

>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?

>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.

And fuck cpython for having a default recursion limit so low that a program that runs in 0.2s can trigger it.

>Water pressure does not apply in this scenario.
This makes life way harder.

What sort of caching do you do? My C++ solution takes 10 seconds.

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.

How about you explain your superior algorithm

>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.

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?

>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

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.

>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.

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

Thank you Anons especially I cant believe I forgot to ignore the opcode as well as the number.

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

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#####################.

MOTHERFUCKER I'm about ready to jack someone else's solution and call it a fucking day with this one. Fucking DAMN IT.

Attached: output.webm (640x612, 437K)

Are they dancing?

Are they fucking?

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.

>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.

Did you forget to make them stop moving if they're in range?

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.

06:58:20 But I fucking did it.

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.

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.

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.

I did this but with a stack.

Still super fucking slow though.

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.

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

The past few days burned me out. I don't even want to parse this input.

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.

Yeah but I really want my 100 stars. I'll do it tomorrow if day 18 is comfy and motivating.

what's more important to you? "get stars and fuck bitches" or "solve it myself"?

>my 100 stars
it's 50 stars

I have 50 from last year.

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.

How long is this aoc thing going to be going on for? Until after new years?

Ends on christmas day, day 25.

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...

What kind of ballpark are people's answers for part 1 in?
Over 2k?

~30k

Oh shit I gotta speed my implementation up then

>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

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

Attached: Untitled.png (900x1100, 275K)

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

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?

Attached: Screenshot_2018-12-17_15-56-33.png (279x211, 26K)

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?

Kek nice work and trips checked