/aocg/ - Advent of Code 2018 General #33

Gobbed 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: snapshot.jpg (1280x720, 115K)

Other urls found in this thread:

pastebin.com/u0CBgaPz
pastebin.com/M8yGU6f2
youtube.com/watch?v=KiCBXu4P-2Y
pastebin.com/4DvvGtZU
pastebin.com/tcrsVt4D
twitter.com/NSFWRedditVideo

everyone: we want hard problems!
eric wastl: did you say you want tedious problems with novel length descriptions?

>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

attack power is always 3 right?
why are people putting it into a variable as if it was dynamic

part 2

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

>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

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

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

>day 15
>implement roguelike game
fuck this

who /copypaste/ on this one but waiting a few hours so it looks more legit

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

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

>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

Oh I get it, it wants me to use a less efficient algorithm.

My go solution:

real 0m1,432s
user 0m1,492s
sys 0m0,012s


(first and second parts, second part ends in 19 iterations)

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

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

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

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

Fuck I'm way too lazy today. I need to hype myself up somehow.

Best of luck, I've got a christmas party later today to go be depressed at, I need the sleep.

Post proof that you're not being filtered.

Attached: stats.png (584x82, 10K)

great job being a /copypaste/ but waiting a few hours to make it look "legit"

I'm being filtered because I can't be bothered to do tedious problems

yea this is the kind of shit that people would get paid to do but here we are doing it for free

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.

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

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.

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.

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

welp, this is my stop

>Input taking forever
>I forgot to remove repeats from the bfs and it was doing n^2 steps instead of n
Fug

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

>Took me 5 hours due to endless bugs
Someone tell me of a python debugger for vscode, I can't keep doing retarded prints

I mean, probably most people outright read the spec incorrectly.

Brainlet here. I misread the problem and spends 5 hours too until I finally figure it out..

Attached: Screenshot_2018-12-15-18-41-36-139_org.mozilla.firefox~2.png (1080x256, 145K)

You're not a brainlet if you're in the top 1000.

Today wasn't the filter because I made it.

>using vscode
That's the problem right here

Big boy for day 15 when?

As someone in the top 1000...keep telling yourself that. I'm even a brainlet in top 200.

>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 was very close to getting filtered today.

Attached: 1537673629472.jpg (700x700, 47K)

brute force it

Ah, finally my suit is here

Attached: CWp_pHYUkAArea9.jpg (334x640, 22K)

All the Python ides I have tried have been worse

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.

God I wish that were me

I thought this was too much for me but the elf rape in the OP has motivated me to continue

Advent of Wall of Text

You're not gonna like part 2 then

>370 lines of code
sweating.jpg

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?

>Python reddit answers give wrong outputs
lmao

>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

Attached: 1524387244515.jpg (640x427, 46K)

I tried one which game the right output for part1 but the wrong output for part2 (too high).
I think I'll just leave this one.

The pythonic way is solving this using unity

Give me my answers nerds
################################
################.#.#..##########
################.#...G##########
################...#############
######..##########.#..##########
####.G...#########.G...#########
###.........######....##########
##..#.##.....#....#....#########
#G.#GG..................##.#####
##.##..##..G........G.........##
#######......G.G...............#
#######........................#
########.G....#####..E#...E.G..#
#########G...#######...........#
#########...#########.........##
#####.......#########....G...###
###.........#########.....E..###
#...........#########.........##
#..#....G..G#########........###
#..#.........#######.........###
#G.##G......E.#####...E..E..####
##......E...............########
#.....#G.G..............E..#####
#....#####....E........###.#####
#...#########.........####.#####
#.###########......#.#####.#####
#....##########.##...###########
#....#############....##########
##.##############E....##########
##.##############..#############
##....##########################
################################

DUDE WALL OF TEXT LMAO
fuck this day

Look up BFS

yeah im gonna try that tomorrow. i dont understand when you're supposed to use one over the other

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

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.

even caring about rank at all already puts you in the subhuman bucket

also you fucks need to read norvig's book jesus christ

Artificial Intelligence: A Modern Approach?

Can you actually do this without writing tons of lines of code?

you can copy/paste

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.

It's around 400 lines of code in a verbose language.

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

feedback is very welcome. I always feel like I suck at structuring my code.

So is the idea to create the field as a BFS instead of a 2d array?

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.

BIGBOI INCOMING
maybe a bit too much... (we'll see)
pastebin.com/M8yGU6f2
I may tweak it a little if this is impossible actually

youtube.com/watch?v=KiCBXu4P-2Y
helpful video if you're new to algorithms and a brainlet (like me)

X = 640 , Y = 477 , Elfs = 121 , Gobs = 438

Jesus

way too big for me, how long does your solution take on this?

I'm very happy to see the Rabbi climb back in the private top ten.

Attached: rabbi_yisrael_rosen.jpg (330x376, 19K)

Mine's 17 seconds in plain old cpython3, with no optimization
7 seconds when using binary search to find the right atk

Still running

I'm at 19 steps of part1 myself.
what have I done...

I did part 1 in 132 lines of Java and 200ms

I give up
Gobs should use a heuristic instead of doing the full BFS every time they want to move in a map that big

*sip*

Attached: aoc comfy.png (750x417, 10K)

wait, shouldnt we use an informed search algorithm like a*? im not sure if bfs would yield the shortest path to the selected position

i used astar, its pretty gud

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

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.

Attached: 1516402252471.jpg (449x440, 18K)

there's no need to be clever, the brute force solution is fast enough for the input given.

a bit smaller boi
pastebin.com/tcrsVt4D
my crappy algorithm took

Next year the ascii art should depict BABY JESUS CHRIST. Christmas is a Christian holiday, goddamit.

I used naive BFS,so there may be a lot of potential.

Hint: given the bounding box of containing all the points, areas that touch the borders of this box are infinite areas.

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.

Loop through all the starting points and calculate the distance from each one.

>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

>meme slayer

2437785
5 min and 20 sec

I'm not doing part 2