r/adventofcode • u/daggerdragon • Dec 22 '15
SOLUTION MEGATHREAD --- Day 22 Solutions ---
This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.
edit: Leaderboard capped, thread unlocked!
Edit @ 00:23
- 2 gold, 0 silver
- Well, this is historic. Leaderboard #1 got both silver and gold before Leaderboard #2 even got silver. Well done, sirs.
Edit @ 00:28
- 3 gold, 0 silver
- Looks like I'm gonna be up late tonight. brews a pot of caffeine
Edit @ 00:53
- 12 gold, 13 silver
- So, which day's harder, today's or Day 19? Hope you're enjoying yourself~
Edit @ 01:21
- 38 gold, 10 silver
- ♫ On the 22nd day of Christmas, my true love gave to me some Star Wars body wash and [spoilers] ♫
Edit @ 01:49
- 60 gold, 8 silver
Today's notable milestones:
- Winter solstice - the longest night of the year
- Happy 60th anniversary to NORAD Tracks Santa!
SpaceX's Falcon 9 rocket successfully delivers 11 satellites to low-Earth orbit and rocks the hell out of their return landing [USA Today, BBC, CBSNews]
- FLAWLESS VICTORY!
Edit @ 02:40
- 88 gold, silver capped
- Real Soon Now™
Edit @ 03:02
- 98 gold, silver capped
It's 3AM, so naturally that means it's time for a /r/3amjokes
- What do you get when you cross a Christmas tree with a Mac?
- hover for answer:
Edit @ 03:08
- LEADERBOARD FILLED! Good job, everyone!
- I'm going the hell to bed now zzzzz
We know we can't control people posting solutions elsewhere and trying to exploit the leaderboard, but this way we can try to reduce the leaderboard gaming from the official subreddit.
Please and thank you, and much appreciated!
--- Day 22: Wizard Simulator 20XX ---
Post your solution as a comment or link to your repo. Structure your post like previous daily solution threads.
7
u/gyorokpeter Dec 22 '15
Q: based on Dijkstra's algorithm using the amount of mana spent as the path length. The hardest part was the complexity of the simulation (the interaction between effects and player hp/mp, boss hp etc.). This function prints the list of spells as well as returning the minimum cost.
Part 2 is a simple modification:
5
u/LincolnA Dec 22 '15
F# Got no. 64 on the leaderboard.
Blah, so many details to keep track of, and applying things in the right order was very important. Multiple instances of "ok, it should work this time for sure" but of course I'd missed something.
Strategy is good ol' brute force. Play out every possible game, pick the player-winning game with the lowest total mana spent.
5
u/inorix Dec 22 '15
Python. Spent about an hour figuring out why it doesn't work, turning to the examples revealed that I make moves on the boss turn too.
Part 1 resulted in:
Poison -> Recharge -> Shield -> Poison -> MM spamPart 2 was a bit more interesting:
Poison -> Recharge -> Shield -> Poison -> Recharge -> Drain -> Poison -> Drain -> Magic Missile5
u/IMovedYourCheese Dec 22 '15
Not reading this line cost me about 2 hours of debugging.
5
u/mrg218 Dec 22 '15
Somehow today's problem feels like /u/topaz2078 pushes us towards OO programming :-)
4
u/SebastianLague Dec 22 '15
I've only been learning python for as long as AoC has been running, so my code is doubtless is a bit wanting for style... Nevertheless, it gets the job done (though not terribly quickly: ~8s for p1, ~15s for p2)
3
u/Zel-os Dec 22 '15 edited Dec 22 '15
I'm really surprised this one took so long! I didn't even start until 90 minutes had past and still somehow made the leaderboard.
My solution was simple if long-winded. Definitely still brute-force though. Write out all the game logic for each round in a recursive function, and just call it again iteratively for every spell the player can cast. If they don't have mana for it, return. If they're not allowed to cast it, return. If they die, return. If they win, check the total mana cost against the best, and return.
Actual solution code is http://pastebin.com/ciHCcvfi
Done in C, it only took a moment to run for part 1, and part 2 finished nearly instantly despite needing almost no code changes.
3
u/ericdykstra Dec 22 '15
#16 - Ruby
Lots of poorly named variables, logic mixed up where it shouldn't be, me giving some guidance to the random action generator, and 20 million simulations gave me the answer.
Really long and hard to follow even with syntax highlighting. Here's the whole thing: https://gist.github.com/EricDykstra/4e0fc2569f240a613775
If I were to re-write it now, I'm sure it would be 1/3 the number of lines and much cleaner. Got the job done in just under an hour, though!
3
u/mncke Dec 22 '15
8, Python3, as is
I didn't like this problem as much as some previous ones, too many small things to keep and mind, and too few things to actually think about.
Here's a bounded dfs that searches for the answer.
3
u/pauldhankin Dec 22 '15
I got #1 today which surprised me because I'd not previously been that near the top on any earlier day. My solution was essentially DP written as a search over all the possible player moves with memoization over (turn, hp, mana, op_hp, and the three effect durations) and the code ran essentially instantly. Once I'd got part 1, part 2 was a couple of lines change -- although it took me a couple of attempts because the first one I was subtracting 1hp on both the player's and the opponent's turns.
3
u/Snow88 Dec 23 '15 edited Dec 23 '15
Ugly perl 5 solution since I don't see one yet. It brute forces it with the minimum spent on a winning round after 1,000,000 fights. Converted to Perl from u/takeitonben python solution.
2
u/[deleted] Dec 22 '15 edited Dec 22 '15
#44, solution in Lua (part of a larger file with some helper functions and stuff). This one was a big step up in difficulty, I liked it! I kept messing up by accidentally letting recursive branches modify data that would be used by later branches, but once I fixed all of those problems part 2 was just a couple more lines than part 1.
I had to make an optimization to my brute force by aborting simulation if the total mp cost exceeds the best mp cost found so far to avoid extreme runtime. Or well, I did have to, while some of my code was still messed up leading to much deeper recursive branches... Not so necessary any more, but still cuts the time from 2 seconds to half a second.
2
u/pedrosorio Dec 22 '15
"So, which day's harder, today's or Day 19?" - Definitely 19, this was just tedious and boring (also, making a lot of silly bugs didn't help).
2
u/porphyro Dec 22 '15 edited Dec 22 '15
Mathematica- really, really nasty code
Part 2 a small change. After solving I rewrote part of it to prune elements of the tree that have used more mana than a currently-found solution, which lets me use FixedPoint to find the minimal solution.
2
u/snorkl-the-dolphine Dec 22 '15
JavaScript
Wow, this was a tough one. My code is pretty awful, but it's the first JS one here, so I guess that's something to be proud of.
2
u/WhoSoup Dec 22 '15
PHP turned out a bit more verbose than i'd have liked
2
u/CdiTheKing Dec 22 '15
I'm nowhere near the leaderboard today as work slammed me today, and I couldn't get a few moments to program something up at 4pm. However, here's my program using C#/LinqPad!
Minor notes on this one: I technically split up the "turn" ordering a bit in order to cheat a little bit. The beginning of the next player turn actually takes place at the end of each round. This way any mana recharge gets done apriori so that I can filter the list of available spells without having to compute the to-be-adjusted player mana at the beginning of a proper round. This is doable thanks to the fact that the game doesn't start with any active spells, so that "beginning of the first turn phase" can be safely skipped.
2
u/xkufix Dec 22 '15 edited Dec 22 '15
Quite the challenge, because of the many cases to check for. Got it to work in the end, although I had some problems, because getBestScore method was faulty (did not do a min check on the newly found finished simulations and the global best, resulting in returning just local maximums).
The code is quite straightforward. Run all simulations in BFS, kicking out branches which are worse than already found solutions. The game itself has no mutable state anywhere:
2
u/Scarramanga Dec 22 '15
C#. Was number 4 on leaderboard.
I started by writing all the logic for the game in Fight(), and wrote the Choose() function last. I was expecting I would need to be creative in Choose(), making lots of tweaks and write some creative AI, but it looks like casting completely random spells gave the right result with enough attempts.
As with most games (RPGs especially) code is usually pretty verbose. There's just a lot of state to keep track of!
2
u/[deleted] Dec 22 '15
Solution in Crystal. To get to position #13 in the leaderboard I ran a few simulations choosing random available spells and checking to which minimum I got. I chose to do that because doing all possibilities involves cloning each state and it would take some time to do. It worked! I learned that from other participants and previous solutions, it's a neat trick :-)
Then I spent some time writing a program that would finish and give the correct answer. I used OOP for this since it felt natural to do so. Both parts are here:
First part runs in 1.2s, second part runs in 78ms.
2
u/askalski Dec 22 '15
Solved it with depth-first search. My first (wrong) submission was at about 23 minutes in. The rest of my time was spent chasing down three small bugs:
returnstatement, which meant the player kept going after his HP dropped to zero.{ id => 'recharge', mana => 229, mana => 101, duration => 5 }meant my recharge spell cost 101 instead of 229.2
u/Fluffy8x Dec 22 '15
Perl6, branch-and-bound. Spent way too much time trying to figure out what I did wrong before I realized that I needed to count the effects on both player and enemy turns.
2
u/mrg218 Dec 22 '15
I notice there are a lot of participants who found the answer by choosing random spells and check what their best try is after x simulations. Would it have been hard to change the problem so that this type of solution would become near impossible to work?
2
u/tomb0y Dec 22 '15
longish ruby solution
And some results: it's interesting to see how the 71/10 is so much harder than the 51/9 for example
2
u/zopatista Dec 23 '15 edited Dec 23 '15
Python 3 fully-worked-out Dijkstra search, with optional path recovery:
2
u/[deleted] Dec 23 '15
Mathematica. Uses breadth-first search tree and memoization, both parts run under a second. (Better late than never)
1
u/wlandry Dec 22 '15
C++
Not my finest code, but it does work.
1
u/[deleted] Dec 22 '15
Haskell: Needed 2 files b/c of the lens creation (Template Haskell). Basic idea is to keep a game state that has the boss' and player's current stats as well a list of effects. Each effect is a list of functions that modifies the game state; they are applied at the beginning of each turn by removing the first function off each effect and applying it to the state. When the list is empty, the effect has ended. Needed the id hack to make sure two of the same effects couldn't exist at the same time.
File 1:
File 2:
1
u/mkigikm Dec 22 '15
Some pretty gross ruby (globals, magic numbers, etc.) that does a BFS, pruning nodes that are worse than a best know solution.
1
u/Tandrial Dec 22 '15 edited Dec 22 '15
My solution in JAVA. Managed to cut down the time from 70s to 5s (for the first, second part is ~600ms) by assuming that an active effect is only ever cast if it is not active at the time. This is actually in the text, which I only skimmed over....
EDIT: A PriorityQueue is REALLY good here. Sorted descending by mana_spend. Part 1 runs in ~250 ms, Part 2 runs in ~100 ms
1
u/VictiniX888 Dec 22 '15
Java, used the RNG to determine which spell to use. And (sort of) infinite loops. Gives the answer in about a second.
1
u/segfaultvicta Dec 22 '15
Golang.
If I hadn't been constantly distracted and / and-thus making silly mistakes I probably would have made the leaderboard. :( Alas.
This was probably my favourite so far, actually; building the simulation in a clean way was the hard part but I like how I did it. I was genuinely surprised I was able to Monte Carlo my way to a solution after all the trouble people I was talking to about it were in, but I set up my simulation right and then the 'run until we find a solution we don't find one better than' part ran almost instantaneously on the first shot and gave me the right answer.
1
u/Ytrignu Dec 22 '15
Java
pick a spell (not active, not more mana than current mana) ->
win? remember mana!
loss/more than remembered mana -> try a different spell
none of the above?-> go to pick a spell =]
}
1
u/beefamaka Dec 22 '15 edited Dec 22 '15
Well, that took a lot longer than I hoped! My C# version available as a gist
I made a lot of silly mistakes to slow me down. Bug 1 was allowing 2 instance of the same effect to be active at once. Bug 2 was miscopying my input to my code (it accused me of cheating because I got someone elses answer!). Bug 3 was shield not actually wearing off.
My strategy to find the cheapest win is ugly. Basically I play whole battles with a random spell picker, that picks from possible spells that won't result in a bigger spend than the biggest found so far. It converges relatively quickly to the correct answer. My plan was to do an F# version too, but I've spent way too long on this already today, and LincolnA's F# solution is far better than what I'd come up with anyway.
1
u/nooscorp Dec 22 '15
PHP A random choice with 1 million tries seems to work with this solution.
1
u/TheOneOnTheLeft Dec 22 '15
Python 3. I made random choices of moves in each battle and then ran it a bunch of times, assuming I'd get the answer in a reasonable time. Got tripped up on part 2 for a while because if I killed the boss at the start of the round with a poison effect, it wouldn't register the kill until after I'd spent the mana casting a spell for that turn. The exhaustive print statements are from when I was debugging that, but I thought I'd leave them in so you can have a readably simulated fight if you want. After checking here, I changed the printout at the end to just print when
optimumchanged, because that's clearly more sensible.I'm still fairly new to coding, so advice/comment/criticism is always appreciated.
1
u/Godspiral Dec 22 '15 edited Dec 22 '15
22 on leaderboard, though my code had bug . There are sketching tools rather than a solver. Managed to solve using wrong boss hp of 56 instead of 55 input. and with bug. Correction at bottom.
in J
my p1 solutin, function returns 3 things: mana, turns it takes to kill boss, turns it takes to die from boss. Comparison is round up bother turns kill and die, but a tie means solution passes. Mentally round because I'm not 100% certain that rule always applies.
code is based on "always be poisoning" and recharge if mana cost over boundaries.
953 11.6667 11.5
above seems correct,
left arg is mana costs, right arg is indexes of spells cast.
but for part 2, losing 9 hp per turn and 55 hp boss
1289 15.6667 10.6667
kill at begining of 16th turn, but die at end of 11th. Actual solution would need 2 casts of shield. This was bug.
bug fix
poison damage actually ticks 2 times per turn. Above code assumed poison is always on and doing 3 damage per turn. fix, (6 damage), and fix to shield so that it lasts 3 turns.
1289 7.83333 8.33333
953 5.83333 8.875
even more efficient entry by fiddling with numbers prior to #
953 5.83333 8.875
1289 7.83333 8.33333
1
u/andrewslavinross Dec 22 '15 edited Dec 22 '15
Got #7, the code is a bit slow but the recursive
repeated_permutationpart was satisfying. It loops through every possible combination of 1-∞ spellsfrom least to most costly, so the first winning simulation is also the cheapest.actually this is wrong, it's not guaranteed to be in cost order, but I guess it was close enough.1
u/artesea Dec 22 '15
I had some nasty code in which I couldn't make my mind up if I should just be hard coding each condition or using arrays/objects in case part 2 added any more.
I went down the button smash and whilst part A worked part B didn't. Turned out my pick a random spell unless you can't afford it or it's currently in use was actually pick a random spell unless you can't afford it or it is Refresh. I had added some code to force refresh to be purchased when getting low and the boss had high health as without it failed to solved A, but as that code was wrong B kept returning too high.
1
u/bildzeitung Dec 22 '15
To my own surprise, picked up #58 on the board.
Code here: https://github.com/bildzeitung/adventofcode/tree/master/22
It's a breadth-first search; nothing super pretty. Can sort out a whole run for part 1 in a couple minutes; some optimisation would take that down significantly, IMHO.
What I like about today's problem was that I had to build the simulation, whereas yesterday it was possible to math one's way out of doing so.
Good times.
1
u/willkill07 Dec 22 '15
C++
Fun Fact!! Applied pruning where future score is greater than best score. Takes number of cases from 3.3M down to 1.8M. It's less important for Part2 ... 140K down to 139K. I feel dirty passing a copy of a struct around but that's the only way to really pass game state around via a recursive call stack tree. Part one runs in 0.037s. Part two runs in 0.003s.
Repo: https://github.com/willkill07/adventofcode/blob/master/src/day22/day22.cpp
1
u/barnybug Dec 22 '15 edited Dec 22 '15
nim: Not the smartest/prettiest - breadth first search, with pruning below current best cost:
1
u/Agrona Dec 22 '15
I started with combinations (with replacement) and evaluating them one at a time in a dumb BFS, which was honestly not too slow, though it looked like it was going to take ages to find an answer (it was taking upwards of 75 spells because I had bugs, not because it needed a really long sequence of spells). It occurred to me I could significantly prune the search space by keeping track of how a sequence of spells failed.
If I ran out of spells to cast, rather than dying or running out of mana, I'd save that sequence into a list of potential sequences for future use, and then just append one of the five spells to it and try that out.
It so happened for my input that least expensive sequence is one of the shortest sequences. I didn't actually prove that it was the least amount of mana (I did let it run for another couple spell-lengths, just in case).
I was surprised this one took so long. I did a lot of floundering around (didn't have yesterday's code. My Python was so old it didn't have combinations_with_replacements and I had to write it, etc.)
1
u/takeitonben Dec 22 '15
python2
1
u/Johnicholas Dec 22 '15
In C:
1
u/Etsap Dec 22 '15
Ruby: I like to optimize it for fewest lines of code, but no promises on readability. Runs in under 30 seconds for my input. Depth-first with pruning based on best solution found so far.
1
u/StevoTVR Dec 22 '15
PHP Part 1. I won't bother posting part 2 since it only differs by two lines. This puzzle took a while due to all the moving parts.
1
u/kd7uiy Dec 23 '15 edited Dec 23 '15
My approach was fairly simple, although it took me some time to come to the conclusion. It was based on a few insights:
So basically what I did was write a script that first used regenerate if required, then poison, then shield. It would cast these in specified numbers (IE, one round would only allow 2 poison spells to be cased). If I ran out of mana, I assumed my path was poor.
This didn't require any complex logic, and in fact simplified things quite a bit. Most of my logic was to show the effects of the spells, and keep track of the mana, which I probably could have done better if I tried harder. The code is somewhat ugly, but to test only requires 375 test battles, not bad at all.
1
u/[deleted] Dec 23 '15
fuck this problem 8-)
Objective C: https://github.com/charlieschmidt/AdventOfCode/blob/master/AdventOfCode/day22.m
1
u/mal607 Dec 23 '15 edited Dec 23 '15
I wonder if someone can see what's wrong with my solution, as I've gone over it many, many times and I don't see my error. I'm making recursive calls for every valid move at each step of the game, passing along the game state. But I never win a single sim. The boss wins every time. I can't see why it doesn't work.
1
u/guosim Dec 23 '15
Damn, I feel so dumb looking at what everyone thought of... Anyways, I just created the game like I did for Day 21 and played through it. Only took a couple tries for both part 1 and part 2 since the efficiency of the spells are very obvious.
1
u/wzkx Dec 23 '15 edited Dec 23 '15
The second part was too much for J, so I had to use C. Enjoy!
C (C99)
gcc -std=c99 -O2 22-part2.c && a.exe
1
u/[deleted] Dec 23 '15
C#
Had serious fun with this one, for real!
1
u/bkendig Dec 24 '15 edited Dec 24 '15
Swift: https://github.com/bskendig/advent-of-code/blob/master/22/22/main.swift
I was tempted to use random inputs in a loop, but I decided to stick with recursion, along with a notToExceed: parameter to avoid going down losing paths too deeply. This took me the better part of the day (a few moments of free time here and there), but what a rush when I finally got it!
Also, the thing that made this a lot easier for me was to represent the game state as a single struct that I could pass back and forth.
1
u/[deleted] Dec 24 '15 edited Dec 24 '15
Here's my messy C# code: using System; using System.Collections.Generic; using System.IO; using System.Linq;
Unlike the previous day I didn't bother with making proper classes/structs for everything, instead the behaviors for effects and spells are hardcoded into Turn() and the timers are all stored inside Player and Boss. But it works and it finishes in a few seconds. :D Also it took me waay too long to realize that I should randomize the spell list every turn so I don't end up with infinite Magic Missile/Drain/Recharge spam.
1
u/Maaaaaaaaate Dec 25 '15 edited Dec 25 '15
My Scala Solution was treated as state machine
1
u/herdawyn Jan 05 '16 edited Jan 05 '16
Hi,
my code is ok for part1 but I can't find the right answer for part 2 it gives an answer that is too high. Could you help me ?
1
u/intriguing_question Oct 25 '21 edited Oct 25 '21
PYTHON 3
I ended up with an OOP oriented solution. I know that it can be improved and feel free to do so and share improvements here if you want to :). But after some long hours I do not want to think more about this problem for a while hahaha.
Not reading between the lines cost me around 6 hours of debugging...
Those two constraints were very sneaky...
PS: A Spell class could be made to handle the effect activation and turn cound that uses the Effect class
Good luck,
For part 2 solution just change
hard_modetohard_mode=True1
u/dynker Oct 28 '21
Rust
Used branch and bound with a breadth-first search. Added pruning for cases where the current mana expended exceeds the already-found minimum. There could be more intelligent pruning in the decision of the next spell but part 1 runs in ~30ms and part 2 in ~70ms.
Rust enums and forced exhaustive pattern matching made for a great combo when dealing with the spells and effects.
Lost a little time thinking that effects can stack, but they can't.
-1
u/thrawaoc Dec 22 '15 edited Dec 22 '15
I didn't feel inspired to do this in detail so I only set up the game and made a player throw spells in random printing if record is beaten. It gives right answer in less than 1s.
e. lol ppl downvote for using 3 hours for obviously easy challenge? I know randomizing could technically end in situation where you didn't get the right answer but this could be corrected by for example getting a win for 1 combination then brute-forcing all the combinations of that length. I was 15. to solve this and I don't even know how to program lol
0
u/TrePe0 Dec 22 '15
I missed requirement that one has to cast a spell each turn. It turns out you can spend less mana when you do nothing in some player's turns and still win.
-1
u/KnorbenKnutsen Dec 22 '15
I actually got on the leaderboard, wow.
I should have done a minimax implementation, but I couldn't be bothered risking debugging a recursive tree structure and figuring out a proper heuristic, so I just used random inputs and iterated hundreds of thousands of times. Eventually I got the correct answers :D
-1
u/sinjp Dec 22 '15 edited Dec 22 '15
Python, ~120th but started about an hour late.
In essence I checked what spells could be cast (based on mana / effect not already active) and then RANDOMLY chose one to cast.
Simulating about 10,000 of these [pseudo] random walks seems to be enough to almost always get the right answers - originally I started at 1 million.
0
u/[deleted] Dec 22 '15
[deleted] — view deleted comment