On the night of Thursday, January 16, 2020, I was doing absolutely nothing.
I decided to browse Twitch to see what games people were streaming. At some point, I came across Campaign 2, Episode 91 of CRITICAL ROLE, a web series where a bunch of voice actors sit around and play DUNGEONS & DRAGONS (D&D).
I was instantly floored.
I had never played or seen anyone play D&D before. As I watched the stream, I kept thinking, This is what D&D is? This is awesome! Naturally, I went back to the first episode and caught up.
At its core, D&D is a game of storytelling, problem-solving, and improvisation. Players take on the roles of fantastical characters navigating a world brought to life by a Dungeon Master (DM), who serves as the storyteller and arbiter of the game. Success in D&D often requires creative thinking and resourceful problem-solving, attributes that are also helpful in programming. In both domains, finding efficient solutions to problems is beneficial. And sometimes, if we’re lucky, the solutions might even overlap.
In Episode 80 of Campaign 2, the party attempts to rescue their friend Yussa, who is trapped within an extra-dimensional manor. The manor consists of a series of rooms interconnected by portals. Before entering, they find a map that Yussa left detailing all the rooms he had explored and how they’re connected:
They discover that Yussa had only mapped out 20–25% of the manor. Given 21 rooms, this means the place contains between 84 and 105 rooms in total.
Now they have their objective: find the needle in the haystack. Since it’s D&D, there are hundreds, if not thousands, of ways to go about solving this. To find which room Yussa is in, they could look for clues, ask non-player characters (NPCs), use one of the dozens of available spells, or some mix of the three.
Alternatively, they could use brute force and manually search every room until they find Yussa. However, this approach is incredibly inefficient. In the worst-case scenario, they would have to scour 105 rooms before finding their friend.
If we imagine the rooms as a list of integers, it might look something like this:
And if we put that in Python and write out a linear search function, it would look like this:
def linear_search(nums: list[int], target: int) -> int:
for index, i in enumerate(nums):
if i == target:
return index
return -1
nums = [13, 9, 21, 15, 39, 19, 27]
target = 39
print(linear_search(nums, target))
But can we find a more efficient solution?
If the list is already sorted, we can use an algorithm called binary search. Binary search compares the target value to the middle element of the list. If they are not equal, the half in which the target cannot lie is eliminated, and the search continues on the remaining half, again taking the middle element to compare to the target value. This repeats until the target value is found. If the search ends with the remaining half being empty, the target is not in the list.
Here’s a demonstration of the algorithm:
The list being sorted allows binary search to make use of the fact that with any element we look at, we know whether the target value lies to the left or right of it. Furthermore, at each iteration, we remove 50% of the list.
Whereas the worst-case scenario with linear search is searching all n elements, the worst-case scenario with binary search is searching log₂(n) elements. For example, if you have 1024 elements, you only need to look at 10 of them:
If we write out the binary search function in Python, it would look like this:
def binary_search(nums: list[int], target: int) -> int:
left = 0
right = len(nums) - 1
while left <= right:
middle = (left + right) // 2
if nums[middle] == target:
return middle
elif nums[middle] < target:
left = middle + 1
elif nums[middle] > target:
right = middle - 1
return -1
Okay, so how does this algorithm help the party find Yussa? If binary search is only useful with sorted data, how does it apply here?
The thing is, what truly makes binary search useful is knowing the answer to a yes-or-no question that removes 50% of the data at each step.
Earlier in the episode, for an unrelated reason, one of the players casts the spell Commune. This spell allows a player to ask their god up to three questions:
The first two questions should probably be: Is Yussa definitely in the manor? and, Is he in one of the rooms on the map?
Realistically, a DM probably wouldn’t draw up a map with 21 rooms and then have the person the party is searching for be in one of the 63–84 uncharted ones — or worse, not in the manor at all. That would just be evil and not in the interest of fun.
So let’s assume that Yussa is, in fact, in the manor and in one of the 21 rooms they know about. If we put ourselves in the players’ shoes, we could list out the 21 rooms on a sheet of paper and cast Commune. Then, draw a line halfway through the list and ask the deity, Is Yussa in a room on the top half of the list? The deity will respond Yes or No, and then we can eliminate the half that doesn’t contain Yussa’s room. Repeat until we locate the target room.
Given that there are 21 rooms, the number of splits we need to make is the log of the next highest power of 2. Since 21 is between 16 and 32, we need log₂(32), which gives us 5. And since we can only ask three questions per casting, we would need to cast the spell twice.
But look how much of an improvement that is. When we considered brute-forcing earlier, we were talking about physically searching through 21 rooms — rooms that might contain traps or monsters. But here we have a solution that takes only a few minutes and requires asking five questions.
Technically, whether this would work depends entirely on the DM. The DM might consider this a cheap way to obtain the answer, or they may want the party to explore the extra rooms they’ve planned. As a result, they might have the deity provide a non-answer, claim the deity isn’t omniscient and doesn’t know which room Yussa is in, assert the deity lacks access to the plane where the manor resides, or come up with any similar justification. But sometimes, if a solution is creative enough, the DM will concede and say, I’ll allow it.
They didn’t end up doing this in CRITICAL ROLE, by the way. It was just a thought I had while watching. I thought, Hmm, they could have tried to binary search for the room with Commune.
But perhaps it was better this way. In the end, they walked through each room one at a time, fighting enemies until they found Yussa, which was equally a delight for them to play as it was for everyone to watch.
