Advent of Code: Day 21

Source

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.