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
everyone: we want hard problems! eric wastl: did you say you want tedious problems with novel length descriptions?
Dominic Allen
>user, it's called BFS and is very simple and suitable for this problem. I can sort of imagine how that might be used to solve it, but not really. some sort of flood-fill where the shortest paths propagate up? the issue is accounting for cases with multiple shortest paths to multiple destinations
Matthew Taylor
attack power is always 3 right? why are people putting it into a variable as if it was dynamic
Ryan Campbell
part 2
Nathan Hernandez
# time pypy3 prob15.py 68932758 Part 1: Ended with 70 rounds and 2713 total hp 189910 Part 2: Trying ap 4 Trying ap 5 Trying ap 6 Trying ap 7 Trying ap 8 Trying ap 9 Trying ap 10 Trying ap 11 Trying ap 12 Setting attack power to 12 Ended with 59 rounds and 980 total hp 57820
real 0m39.684s
Anyone got a faster implementation? I made my code quit immediately after the first elf death (rather than after the first round with an elf death) and didn't see any improvement. I figure the issue is that I'm using pure python with python lists for my bfs "arrays" which are slow to create and pass around even though they're small.
>the issue is accounting for cases with multiple shortest paths to multiple destinations This isn't an issue at all. I suspect you may misunderstand the problem. First you choose your destination by finding the closest one. After fixing the destination, only then do you consider which path to actually take. For this, you can set your "starting point" as your destination so you only have to run BFS once.
Not on part 2.
William Allen
>First you choose your destination by finding the closest one. there's a theoretically unlimited number of "closest ones" and each "closest one" may have multiple paths to it that are equally short
Ryder Barnes
>Once the Goblins and Elf reach the positions above, they all are either in range of a target or cannot find any square in range of a target, and so none of the units can move until a unit dies. My gobs are too efficient.
Benjamin Wilson
No I can't get mine any faster than 59 seconds on pypy3 (on my input the attack power needs to go up to 25) I get the feeling there must be some way to intelligently skip the battles where elves have less than 12 AP or so, like intuitively the elves would need to be at least 4 times as strong as the goblins so that any elf that is surrounded can survive, but there's always some counterexample you could create with a bunch of goblins ganging up on one elf with the elf reinforcements too far off
Thomas Ross
>day 15 >implement roguelike game fuck this
Colton Lewis
who /copypaste/ on this one but waiting a few hours so it looks more legit
Ethan Green
Also most of the battles are more than halfway done by the time the first elf dies so quitting at the first elf casualty doesn't save as much time as you might hope
Camden Torres
>there's a theoretically unlimited number of "closest ones" Uh, no. There are a finite number of squares adjacent to enemies that are possible destination points. There can be multiple, but you can get the distances to all of them with bfs., find the minimum, and then choose one using the order specified. >and each "closest one" may have multiple paths to it that are equally short It doesn't matter, to decide you just need to find the distance, which bfs does.
I'm using the user I replied to's input; so you could check the time with that if you want, I wonder if I just need to numpy everything. Yeah, I figured that out since it saved me no time at all.
Christian Carter
>It doesn't matter, to decide you just need to find the distance, which bfs does. but that's not true it specifically says in the problem statement that if there are multiple shortest paths you need to take the one in which you move in read-order
Jose Johnson
Oh I get it, it wants me to use a less efficient algorithm.
Ryder Young
My go solution:
real 0m1,432s user 0m1,492s sys 0m0,012s
(first and second parts, second part ends in 19 iterations)
Christian Walker
>you can get the distances to all of them with bfs Just tell the user to use Dijkstra's algorithm; when all edges are 1 then Dijkstra reduces to bfs but when you say "use bfs to calculate distance" then user's gonna be like "wtf are you talking about"
Christopher Walker
>There can be multiple, but you can get the distances to all of them with bfs would this even be faster than, say a dijkstra map?
Isaiah Ortiz
>read todays task >yah, this will take more than few hours I think I am filtering myself out. Good luck to elves in their fight.
Caleb Long
Nice. Yeah I'm betting the python lists are killing me.
It says to find the closest target, and if there are multiple then chose the earliest one in the order. Only after you find the this target do you have to think about the shortest paths to it. Most algorithms determine all the distances from a given starting point to any point. So simply use the algorithm to find the distances FROM this target point. Look at the distances from the target point to the adjacent points of your unit, and take the minimum (using the order if there are multiple). BFS is commonsense and is basically how you, a human, could make a diagram like:
Distance: ####### #4E212# #32101# #432G2# #######
Mark everything adjacent to your point with a 1. Mark everything adjacent to your 1s with a 2, etc.
I'm not sure what a Djikstra map is. Some structure that makes it simple to use Djikstra's algorithm? Like says, Djikstra's algorithm is just a generalization of BFS for weighted graphs
Caleb Bennett
Fuck I'm way too lazy today. I need to hype myself up somehow.
Jaxon Gray
Best of luck, I've got a christmas party later today to go be depressed at, I need the sleep.
great job being a /copypaste/ but waiting a few hours to make it look "legit"
Jason Rogers
I'm being filtered because I can't be bothered to do tedious problems
Logan James
yea this is the kind of shit that people would get paid to do but here we are doing it for free
Ayden Myers
It's a bit tedious to read. If they speced it out more succinctly it would be nicer. But implementation isn't that tedious at all.
Elijah Lee
pretty much anyone who isn't top 10 globally on this one is suspect the amount of time available to copy/paste is just too large to trust it
Lucas Martin
but the time to write a working implementation is also large at this point, i doubt most people doing advent of code are doing it purely to have stars next to their name, they're doing it for fun etc.
Joseph Howard
Did the pathfinding and the parsing but can barely be fucked going over this wall of text again to decipher the details of the simulation. Feels like work today.
Parker Wilson
tasks like this is where advent of code goes from being fun to being "work" Gonna take my time with this and go to bed
Christian Ward
welp, this is my stop
Leo Ramirez
>Input taking forever >I forgot to remove repeats from the bfs and it was doing n^2 steps instead of n Fug
Anthony Myers
I think a lot of people on this problem, like many problems, just hack something together that happens to work for their input. I often look at the subreddit to find ugly and sometimes incorrect implementations to laugh at. vash3r on the subreddit, for example, ranked but his code breaks with input >>
Jaxson Rivera
>Took me 5 hours due to endless bugs Someone tell me of a python debugger for vscode, I can't keep doing retarded prints
Juan Martin
I mean, probably most people outright read the spec incorrectly.
James Anderson
Brainlet here. I misread the problem and spends 5 hours too until I finally figure it out..
As someone in the top 1000...keep telling yourself that. I'm even a brainlet in top 200.
Cooper Hernandez
>0-20 Genius can't relate to most people, women find your intelligence offputting, will probably die a virgin >20-30 Getting too intelligent Doable if you have been training from child and at least 230lbs 10% bf >30-100 Perfect Intelligence This is the perfect male intelligence. Period. >100-130 Brainlet cutoff Even girls are now this intelligent. >130-200 King of the brainlets Tantalizingly close to intelligence but too far to ever get there. >below 200 Consider suicide.
I used to do these kinds of puzzles in codeforces. They divide the users into 2 divisions, basically to categorize brainlets and non-brainlets. Most contests have the leaderboards for div1 & 2 separated. Usually only top 100 of div 2 get promoted to div 1. And even then if you rank like 200+ in div 1, you get demoted to div 2.
Josiah Johnson
God I wish that were me
Dylan Moore
I thought this was too much for me but the elf rape in the OP has motivated me to continue
Nicholas Sullivan
Advent of Wall of Text
Luke Perez
You're not gonna like part 2 then
Dylan Morgan
>370 lines of code sweating.jpg
Anthony Price
This. Part 2 is basically this: >oh no the cute elves are getting gobbed!! >if we give the least plot armor possible to the elves such that not even a single one of them get gobbed, what's the outcome now?
Jack Peterson
>Python reddit answers give wrong outputs lmao
Matthew Martin
>be me >start reading problem >'haha this explanation is too overly broke down i can do three steps at once' >start reading dijkstra on wikipedia >'haha this was a fucking pain to implement in that course i'll just do it freestyle since there arent any weights'
now i have 400 lines of java code including a 100 line recursive function that is pretty much impossible to debug and i am considering filtration
yeah im gonna try that tomorrow. i dont understand when you're supposed to use one over the other
Josiah Butler
Damn, you nerds made me open up github, I thought we were friends... Because I'm a good friend here is the correct answers to debug yours. part 1 183300 part 2 40625
Bentley Scott
Dijkstra is basically just Breadth-First Search (BFS) but with priority queue instead of queue. The priority queue is a queue but with the least weight in the front-most of the queue instead of the normal FIFO order.
BFS is a graph traversal algorithm, just like DFS. Its breadth-first order of traversal implies that nodes are visited in the order of the distance from the source. So if you do BFS from the root of a tree, the root gets visited first, then the children, and then the children of children, etc. Since nodes nearer to the source (root) gets visited first, you can be sure that the path by which you visit a node from the source the very first time is also a shortest path to it.
Jordan Miller
even caring about rank at all already puts you in the subhuman bucket
also you fucks need to read norvig's book jesus christ
Brody Gray
Artificial Intelligence: A Modern Approach?
Cameron Morris
Can you actually do this without writing tons of lines of code?
Julian Murphy
you can copy/paste
Jackson Jenkins
No one is going to pay you to solve an elf vs goblin fighting simulation problem. I'm considering self filtering for the exact opposite reason, this is the kind of shit no job is ever going to require you to do.
Brody Wood
It's around 400 lines of code in a verbose language.
Jackson Martin
almost 3 hours coding and 4 seconds in pypy without any smart binary search for part2. 95 lines of code still quite messy. pastebin.com/u0CBgaPz
Jaxon Martin
feedback is very welcome. I always feel like I suck at structuring my code.
Kayden Powell
So is the idea to create the field as a BFS instead of a 2d array?
Blake Gray
BFS isn't a data structure, it's an algorithm. A 2D array is just like a graph, you can think of a cell as a node and adjacent cells as adjacent nodes. Thus you can apply BFS on a 2D array as you would apply it on a graph.
Jaxon Butler
BIGBOI INCOMING maybe a bit too much... (we'll see) pastebin.com/M8yGU6f2 I may tweak it a little if this is impossible actually
wait, shouldnt we use an informed search algorithm like a*? im not sure if bfs would yield the shortest path to the selected position
Jose Roberts
i used astar, its pretty gud
Tyler Bailey
but it seems to go into an infinite loop for me, 10 minutes passed and i still get nothing here is the code: pastebin.com/4DvvGtZU
Nicholas Turner
I just started this. Help with day 6 day 1 (taxicab area)? I'm really fucking stuck. Everything I could find online was basically complete answers, which I don't want.
Next year the ascii art should depict BABY JESUS CHRIST. Christmas is a Christian holiday, goddamit.
Jonathan Miller
I used naive BFS,so there may be a lot of potential.
Oliver Green
Hint: given the bounding box of containing all the points, areas that touch the borders of this box are infinite areas.
Kayden Ross
Thing is I have no idea how to even approach this. The only thing I can think about is that I place all the points on a finite array, an area would be infinite if there are points that are closest to it, that are on the edge of the array. (which mentioned while I was typing this)
But I have no clue how to calculate the closest point to a given point given its surroundings.
Matthew Mitchell
Loop through all the starting points and calculate the distance from each one.
Josiah Campbell
>But I have no clue how to calculate the closest point to a given point given its surroundings. just calculate the distance to every point and take the one with the smallest distance