Part 1: Given a shop full of weapons (buy exactly one), armor (buy zero or one), and rings (buy 0, 1, or 2), determine the set of items that will defeat a given enemy for the minimum cost (see the original writeup for more details).
First, a bit of code to parse the shop:
shop = {}
category = None
with open('shop.txt', 'r') as fin:
for line in fin:
line = line.strip()
if not line:
continue
if ':' in line:
category = line.split(':')[0]
shop[category] = []
continue
name, cost, damage, armor = line.rsplit(maxsplit = 3)
shop[category].append({
'Name': name,
'Cost': int(cost),
'Damage': int(damage),
'Armor': int(armor),
})
# Allow for no armor or rings
shop['Armor'].append({'Name': None, 'Cost': 0, 'Damage': 0, 'Armor': 0})
shop['Rings'].append({'Name': None, 'Cost': 0, 'Damage': 0, 'Armor': 0})
Using that, we can write some code to generate all possible players:
def all_players():
for weapon in shop['Weapons']:
for armor in shop['Armor']:
for left_ring in shop['Rings']:
for right_ring in shop['Rings']:
# Cannot have two of the same ring unless they're both None
if left_ring and right_ring and left_ring == right_ring:
continue
items = [weapon, armor, left_ring, right_ring]
player = {
'Hit Points': 100,
'Items': [item['Name'] for item in items if item['Name']],
'Damage': sum(item['Damage'] for item in items),
'Armor': sum(item['Armor'] for item in items),
'Cost': sum(item['Cost'] for item in items),
}
yield player
Additionally, we can read our opponent’s stats from stdin:
enemy = {}
for line in sys.stdin:
key, val = line.strip().split(':')
enemy[key] = int(val)
def get_enemy():
return copy.copy(enemy)
It’s important to return a new copy each time; otherwise you end up badly beating up the same guy over and over again.
Finally, fight:
def player_wins(player, enemy):
while True:
enemy['Hit Points'] -= max(1, player['Damage'] - enemy['Armor'])
if enemy['Hit Points'] <= 0:
return True
player['Hit Points'] -= max(1, enemy['Damage'] - player['Armor'])
if player['Hit Points'] <= 0:
return False
With all of this in a separate file called lib.py (I should probably refactor some of the previous days this way), we can solve the actual problem in about a half dozen lines:
import lib
best_player = {'Cost': float("inf")}
for player in lib.all_players():
if lib.player_wins(player, lib.get_enemy()):
if player['Cost'] < best_player['Cost']:
best_player = player
print(best_player['Cost'])
A brute force solution feels a bit ugly. We could instead have iterated over the solutions from the cheapest up until we found one that worked, or even done a binary search by cost, but what’s the point? There are only 1260 possible inventories. That’s nothing to a computer.
Part 2: Invert the problem. Find the most expensive set of items you can buy and still lose.
This is why I factored out all of the library code. I know that something like this would be part 2. :)
import lib
best_player = {'Cost': float("-inf")}
for player in lib.all_players():
if not lib.player_wins(player, lib.get_enemy()):
if player['Cost'] > best_player['Cost']:
best_player = player
print(best_player['Cost'])
In case you were curious, my winner for part 1 had a longsword, chainmail, and a Ring of Damage +2. Part 2 had a Dagger, Leather Armor, and Rings of Damage +3 and Defense +3. It’s interesting that the cheaper option actually had a more expensive weapon and armor, but the pair of rings more than made up for it.