How should I store the fighters in a battle with complex interactions?
Mild spoilers for Advent of Code 2018 Day 24 follow.
I'm working my way through Advent of Code's back catalog. 2018 Day 24 looks fun. Well, part 1 looks fun. I'm dreading whatever search part 2 will likely require. Anyway, AoC problems tend to be written in a style that suggests a way to implement. For example:
Each fight consists of two phases: target selection and attacking.
From this I could immediately write:
def fight():
select_targets()
attack()
This code already captures at least two ideas: There will be many fights. Target selection is completed before attacking. Of course, at a minimum this is missing what is fighting, how they will be passed into the fight, and whether the fighters will have their stats updated or be replaced with the results of the fight.
Each side has an army, and each army contains several groups. I briefly considered representing a group as a tuple (ordered list), but as I would have to unpack it each time to write code I could read, it's more convenient to make it an object with named attributes. So I created a Group class. I should also create an Army class, right? Well, that immediately caused me problems. The order in which the groups act does not depend on which army a group is in. If I explicitly created two armies, I would need to maintain a separate list of the initiative order to identify the group up next. Then that group would need to know which army it was in, and its army would need to know the opposing army, and that army would need to know its groups.
I decided it would be enough for each group to know what army it was in. Any time a group needs to act (on groups of the opposing army), I would consider the full list of groups, and filter out the groups from the same army.
for group2 in groups:
if group1.army == group2.army:
continue
This has the added benefit of preventing a group from targeting itself.
So I was going to store the groups in a single collection, but what kind of collection? During target selection, I wouldn't know whether a target would be selected at the time I computed its potential damage received. And I needed way to exclude a selected target from later target selection in that fight. I decided I wanted some way to access the right group.
Each group's initiative value looked to be a useful identifier. I could have just assigned a unique ID to each group, and hopefully I won't have to rework this in part 2, but the initiative values in the test input and my real input appear to be distinct positive integers starting from 1 with no gaps. I thought about just using a list with access by index (position in the list), but aside from having to handle index 0 — or get back into a language with 1-based indexing — relying on a list index to remain unchanged would prevent me from deleting groups that have no units remaining. And I wanted to delete groups with no units so I wouldn't have to check for that in many places.
I settled on a dictionary, with the initiative as the key and the group itself as the value. This way, any time I wanted to track which groups had already been targeted, or anything else, I could just track the initiative values. This would spare me from having to write code to determine whether two groups were the same. Then when I wanted to retrieve the group itself, I'd get it from the dictionary. Deleting a group, deleting the key-value pair, would have no effect on accessing remaining groups.
I was still a bit hung up on sorting. Python dicts preserve order starting in 3.6, and at first I thought I wanted to store the groups in initiative order. This isn't always the order in which groups act, though. Effective power is sometimes used, and this changes throughout the battle. What eventually seemed best to me was just sorting the groups as needed, when needed.
for group in sorted(groups,
key=lambda g: g.initiative,
reverse=True):
Turns out part 2 was also fun! A search, of course, but with a neat twist.
Top comments (0)