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
