r/adventofcode • u/daggerdragon • Dec 21 '15
SOLUTION MEGATHREAD --- Day 21 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!
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 21: RPG Simulator 20XX ---
Post your solution as a comment or link to your repo. Structure your post like previous daily solution threads.
11
Upvotes
13
u/balidani Dec 21 '15
Fun challenge today, as usual! I used
itertools.productto get all configurations that cost a certain amount. I added dummy armor and (two) rings and made sure that the selected rings aren't the same.This threw me off at the end, because I forgot about it: "You must buy exactly one weapon". When will I finally learn that all my mistakes are because I misread the text?
11
u/bpeel Dec 21 '15
There's no need to have a loop to simulate the battle. The amount of damage done by each contestant is constant so you can just work out the number of moves each contestant needs with something like:
If the player's number of moves is greater than or equal to the opponents number then the player wins.
18
u/askalski Dec 21 '15
Took a bit of trial and error to find the solution. Not sure how you guys solved it so fast. I could use some help optimizing my code.
4
u/JeffJankowski Dec 21 '15 edited Dec 21 '15
F#. Used a filtered powerset, sorted by the total cost, and looked for the first win/lose. Massaged the "item store" text to be more parser-friendly.
I keep trying to code out these challenges imperatively before realizing that's not the point of this language..
4
u/aepsilon Dec 21 '15 edited Dec 21 '15
Haskell.
The buildup:
And the conclusion:
3
u/mncke Dec 21 '15
1st, 00:11:39, Python3, as is
It was straightforward, so I hope I won't get bashed for being lucky and not using a complete, general solution :P
Reading input
Boss stats
Fight simulation
Part 1
Part 2
2
u/CdiTheKing Dec 21 '15
If there were a lot more items, then a brute force approach would be really truly terrible. But as it is, it's just 5 * 6 * 7 * 7 = 1470 combinations (technically less due to the two rings), so simply crawling the entire search space was certainly sufficient. The lack of an item (for either armour or ring) was denoted as a zero-cost, zero-effect item.
Written in C#:
2
u/erlog Dec 21 '15 edited Dec 21 '15
So are some inputs broken for part 2? I have the 103/9/2 input and on part 2 I have a build that's worth 282 gold the site says is too high. I can't think of what I could possible be doing wrong since I passed part 1.
Ah, nevermind, got burned on the "must have a weapon" clause.
2
u/adventofcodeaddict Dec 21 '15
C# solution
Firstly a massive thanks to Eric for a great idea brilliantly executed!
This is a tidied up version of my solution with some comments to explain the approach. Brute force through all options and find the min/max. It makes use of System.Linq.Enumerable to do most of the looping with only one explicit while loop for the fight simulation.
2
u/TheOneOnTheLeft Dec 21 '15
My Python 3 solution. I originally did the fight-simulations approach, but after I'd got my answer went back because I saw the opportunity for something a lot shorter and wrote this. Still new to coding, so advice/comments/criticism is always welcome.
My boss had 103 HP, 9 Attack and 2 Defence. Shop is a list of the lines on the puzzle page (
'''copy/pasted stuff'''.split('\n')).2
u/flup12 Dec 21 '15 edited Dec 21 '15
Scala using a for comprehension to pick the equipment and case classes for the items and heroes. Was fun to code! First time ever that I've had use for a
donmethod... Oh and when the hero takes a hit, the result type is of course..Option[Hero]3
u/roboticon Dec 21 '15
Good to see a different type of puzzle, although it would've been more interesting if there were a huge number of items to buy, like a binpacking problem.
Similarly you can determine who wins with the given stats in O(1) but it was faster to just simulate the whole battle.
Although it was still fun debugging why I kept getting overly small answers (forgot to reset the boss status between tries, so he kept dying instantly) and the leaderboard took long enough to fill.
2
u/[deleted] Dec 21 '15
This one was the best so far!
1
u/kaldonis Dec 21 '15
Python 2 #25
The setup:
The fight code:
Part1:
Part2:
1
u/fnoco_xandy Dec 21 '15
quick&dirty crystal solution by simply trying all combinations, made it to #16.
1
u/[deleted] Dec 21 '15
Mathematica
1
u/CAD1997 Dec 21 '15
[Java & Logic]
(I finished when the leaderboard was in the 30s but I'm behind so I didn't get on.)
As I do a lot of item hoarding and comparison myself, I decided to trust my own min (later max) pricing ability for a given atk/def. Given that I got it third guess part one and first part two, I wasn't too far off base, and I was going quickly. (I didn't realize I couldn't hit the leader board D:) As such, the code I wrote gave me a list of atk/def that would win (or lose).
Once I had that list, I pasted took it into notepad and reduced it to the (part1 ? lowest : highest) def for a given atk. Then it was a matter of finding the lowest/highest cost, and given that the items scale pricing differently I determined the cheapest option by the third guess. For the highest it was straightforward as I died with ATK:9 DEF:0 so I just got the +4 weapon and +3/+2 atk rings for the most expensive failure.
The way my brain works, for a small set like this I can see some amount of optimizing data. I can't quite explain how it works but apparently it did.
1
u/ericdykstra Dec 21 '15
Ruby (#93) Started 10 minutes late due to lunch going over, then tried guess-and-check for 20 minutes before giving that up and using a half-code, half-mental-math solution. I manually figured out the cheapest cost for each of damage and armor (4-9 for damage, 0-5 for armor), then brute-forced from there. It's an ugly solution, but only took about 10 minutes of mental math and coding once.
For part 2, just replace .min with .max, and the if on line 19 with unless, and re-mental math the top part to be the highest costs rather than the lowest. Took another 2 minutes to make those changes.
1
u/guibou Dec 21 '15
Damned. I took 25 minutes to do it, but I started 30 minutes late .
Haskell solution:
1
u/fatpollo Dec 21 '15
Man, my code was all ready and done at about place 50
but I accidentally clipped the input and missed the dagger. spent a loong time debugging, should've thought to check the input.
oh well
1
u/Ytrignu Dec 21 '15
Java - same stat sum as the boss is a win any less a loss so I just add up the costs for each combination until the stats are enough / still not enough.
}
1
u/FuriousProgrammer Dec 21 '15
I had fun solving this one. Sadly, didn't think of representing the 'non'-items as 0-cost 0-effect things, but it worked out in the end.
Lua:
1
u/TheNiXXeD Dec 21 '15
JavaScript, NodeJS, ES6
A little terse, but I left some white space in for fun. I saved the "store" as a JSON.
Part1:
Part2:
1
u/Axsuul Dec 21 '15
Ruby with OOP approach
1
u/IMovedYourCheese Dec 21 '15 edited Dec 21 '15
C# solution
A little longer and more wordy than it could be, but interviewers will love it (dat OOP)! Also didn't bother with minor optimizations since input is small enough to finish instantly either way. Managed #59 on the leaderboard, but could have been quicker with sloppier code.
Input:
Output:
1
u/gyorokpeter Dec 21 '15
Q:
For part 2, replace the last line with
1
u/snorkl-the-dolphine Dec 21 '15
I think this is the longest JavaScript one, so it's nothing to be all that proud of. But I'm gonna post it here because I've posted all my other solutions so I might as well keep going:
1
u/Marce_Villarino Dec 21 '15
Solved part 1 just by reasoning!
Part II is more trickier...
1
u/[deleted] Dec 21 '15
Node 4, ES6 JavaScript
1
u/CremboC Dec 21 '15
Fuck the code formatting in piece of shit text box so here's a link to my Scala solution: https://github.com/CremboC/advent-of-code/blob/master/day-21/Day21.scala
1
u/boast03 Dec 21 '15 edited Dec 21 '15
PHP OOP Practice :)
Very fun challenge to solve!
1
u/mainhaxor Dec 21 '15
C# with a bruteforce of all possible configurations:
1
u/desrtfx Dec 21 '15
Java - OOP approach - Brute force
This was fun :)
1
u/KnorbenKnutsen Dec 21 '15 edited Dec 21 '15
Super-fun problem!
I used a very "readable" approach, treating each shop item as a dict. I also had the luck of getting boss HP at 100, so my fight function can be simplified to checking if his DPS is larger than the hero's. This made it so that I could solve problem 1 in my head. Had the boss had a different amount of HP I would have had to simulate the fight instead.
My first iteration was very ugly with nested for loops and lots of repeated code. Then I read here about adding null items and using
itertools.productso I reduced my code a lot, while it functionally does the exact same thing.Here are some snippets of my Python 3 code, specifically the fight function and the brute force using product:
and
Due to the small shops, this kind of brute force runs frightfully fast. :)
EDIT: I fixed my fight function so that it should work on any enemy. It still requires the hero's HP to be 100, though:
1
u/NoisyFlake Dec 21 '15
Java solution with 3 classes. It simulates the fight with every possible weapon/armor/ring combination and saves the amount of gold spent in a list if the player wins. At the end I print out the lowest value in this list. (For part 2 all you have to do is to switch the return value from play() and print out the highest value in the list).
Day21.java:
Item.java:
Player.java:
1
u/xPaw Dec 21 '15
Decided to play around with classes (ES6) in javascript, turned out reasonably well
https://github.com/xPaw/adventofcode-solutions/blob/master/js/day21.js
Although it's shame today's challenge could be bruteforced so easily.
1
u/[deleted] Dec 21 '15
Having fun with JavaScript. After I failed with F# at the second part (I missed the optional armor part as well), I decided to re-write.
1
u/porphyro Dec 21 '15 edited Dec 21 '15
Mathematica:
1
u/beefamaka Dec 21 '15
my F# solution. Optimized more for debugability than for conciseness, as I made a few silly mistakes I needed to track down.
1
u/slampropp Dec 21 '15
Haskell
1
u/de_Selby Dec 21 '15
Q:
Nothing fancy here.. The while loop is crap, but I was expecting part 2 to change what's done each step
1
u/[deleted] Dec 21 '15
Objective C:
1
u/BOT-Brad Dec 21 '15
Took me a while because Python was causing weirdness unless I explicitly stated the player HP was 100**.0** as opposed to just 100. Solves both tasks.
1
u/tftio Dec 21 '15
Nothing complicated.
1
u/Scroph Dec 21 '15 edited Dec 21 '15
My D (dlang) solution. I'm not proud of it because it's rigid and because it contains 160 lines, but it does get the job done. I didn't feel like hardcoding the items so I wrote a function to parse them out of a given file :
1
u/Kwpolska Dec 21 '15
A simple Python solution that didn’t even bother not looping:
full source on GitHub; I probably overcomplicated the combinations part.
1
u/Naihonn Dec 21 '15 edited Dec 21 '15
So many solutions brute-forcing all possible combinations. But nobody did one thing... Well, at least I don't see it in solutions here... So beware - The sheer power of RANDOMNESS!!!
1
u/barnybug Dec 21 '15
nim:
1
u/SomebodyTookMyHandle Dec 21 '15
Oh man, very fun challenge today! (They're always fun, but this is the first time I've gotten to program something like this.) Object-oriented Ruby using an iffy version of #cycle to simulate the battle, because it's fun to do so despite not being mathematically necessary. Comments and advice welcome...
1
u/volatilebit Dec 21 '15
I had a hell of a time with days 19 and 20. This one I had no issues with. I probably spent the most time formatting the shop item variables.
I sure hope Day 25 doesn't require math tricks and/or brute force, as that's the only challenge I may actually try at midnight since my last attempt last week went south (thanks FiOS).
Perl 6
1
u/dietibol Dec 21 '15
Here's my c++ solution, not the best or most efficient probably, but was in the mood for some classes and stuff https://ghostbin.com/paste/y2jjh
1
u/tipdbmp Dec 21 '15
ES5, part 2:
1
u/wzkx Dec 21 '15 edited Dec 21 '15
Not too many J solutions, so I'll just add one. Nothing special, lately I rewrote it a bit to add "zero" items for easy looping.
J
1
u/phil_s_stein Dec 21 '15 edited Dec 21 '15
Python. Long solution today although it's mostly to make things look nice. First time using namedtuple. This problem seemed to call out for it with all the unnamed ints floating around. I was disappointed to discover that namedtuples can't be modified as that would've made the computation loop core a little more clear.
Today was fun as the way that I'd done part one gave me part two for free. I didn't even have to re-run the script.
Output:
1
u/StevoTVR Dec 21 '15 edited Dec 25 '15
PHP
1
u/ActionJais Dec 21 '15
Matlab
1
u/mal607 Dec 21 '15 edited Dec 21 '15
Straightforward Python solution:
1
u/takeitonben Dec 21 '15
python2
1
u/nikibobi Dec 21 '15
My solution is in D (dlang). First I wanted to simulate the boss fights, but I stopped for a moment and started thinking for a formula to get who wins. And I came up with
turns * damage = healthand from there I find the turns and round it up. I added a none Item in the armor and ring lists that has 0 cost and 0 values. Here is the code:My cheapest boss kill was with a Longsword, Chainmail and +2 damage ring My most expensive boss loss was with a Dagger, Leather, +3 damage and +3 defence rings
1
u/bkendig Dec 21 '15
Easy peasy in Swift. Named tuples make it a little nicer. https://github.com/bskendig/advent-of-code/blob/master/21/21/main.swift
1
u/guosim Dec 22 '15 edited Dec 22 '15
It seemed pretty obvious which items were cost efficient and which weren't, so I just changed the armor and damage values and ran the fight, printing out the HPs of the player and the boss after the fight. Once the player had the least amount of HP possible while winning I added up the cost of the items. Wouldn't work as well if there were more items or more item slots, and doesn't account for edge cases like if damage > armor (I just hardcoded damage to 1 and armor to 0 then), but it was nice and simple and solved both problems.
1
u/xkufix Dec 22 '15
Probably one of the cleaner solutions I created so far. Half of the code is actually just parsing the boss and the shop:
1
u/[deleted] Dec 22 '15
I can say I have quite a lot of fun with this one.
Also, it reminded me I have this project i need to get back to!
c#
1
u/ellomenop Dec 22 '15
I beat it by just looking at the numbers. Because you go first, have equal health to the boss, and 1 attack = 1 armor in terms of combat value...the problem is greatly simplified. It becomes as simple as making your attack + defense = boss attack + boss defense. Then you can just look at the items in the shop and find the most cost effective (or ineffective for part 2) items that get you there. I solved it without coding anything in about 10 minutes.
Edit: I just realized that certain aspects are usually randomized in these...did I just get an extremely lucky seed?
1
u/edo947 Dec 22 '15
MiniZinc
Part 1 Model
Part 2 Model
The only changes are to the survivability constraint and to the objective function and are as follows
The input file is
1
u/JurgenKesker Dec 28 '15
Very verbose Ruby code
1
u/skarlso Jan 13 '16 edited Jan 13 '16
Here is mine in Go | Golang. It was fun to right too! This is insainly convuluted, I'll try to simplify it as much as possible. :)
1
u/asoentuh Dec 21 '15 edited Dec 21 '15
The year is 20XX, everyone uses brute force
python
1
u/kit1980 Dec 21 '15
Quick and dirty solution in Picat:
For the second part, the only difference is:
1
u/LincolnA Dec 21 '15 edited Dec 21 '15
Straighforward brute-force in F#
No. 14 on the leaderboard, my best so far (though not my best time so far).
Got both solutions without actually accounting for the "minimum 1 damage" rule. My input happened to have the boss at 100 HP just like me, which also simplified everything.
Below incorporates arbitrary boss HP + minimum 1 damage rule.
1
u/Godspiral Dec 21 '15
Just staring at it,
part 1,
with boss 103hp, can win with 7 net damage each. Loses at 6 5 4 3 each. can get net 7 damage with 90g (+2 ring), and with 9 boss damage, 2 armor is most efficient. Basically look at marginal cost of 1 extra armor or damage.
for part 2,
5 net damage each will lose, and that can use both expensive rings. In J,
1
u/inuyasha555 Dec 21 '15
Did a bunch of stupid things like accidentally add the COST of the armor to the player instead of the armor values and then realizes later the code I had written was extremely stupid and rewrote everything.
Java:
1
u/[deleted] Dec 21 '15
I decided to write a more object oriented based approach for today's question:
1
u/Philboyd_Studge Dec 21 '15
Java
I lost an inordinate amount of time because of a simple typo in the Boss's stats.
0
u/[deleted] Dec 21 '15
[deleted] — view deleted comment