Rotating turn order with deque

Batteries included is a blog series about the Python Standard Library. Each day, I share insights, ideas and examples for different parts of the library. Blaugust is an annual blogging festival in August where the goal is to write a blog post every day of the month.

A while back in the spring I was in a technical job interview where I was tasked to implement a Kimble game engine. While the idea didn’t unfortunately pop into my head during the interview, when I was revising my approach later, I realized that deque is a nice data structure for rotating turn order.

Initial solution

My interface into the game ended up looking a bit like this

players = [
  Player('Lion'),
  Player('Two reeds'),
  Player('Twisted flax'),
  Player('Horned viper')
]
 
game = Kimble(players=players)
 
while not game.is_finished():
  game.advance()

The game had to keep track of the players and keep them running in a loop until the game is over.

Initially in the job interview phase, that part ended up looking like this:

def next_player(self):
  next = self.players[
      (self.players.index(self.current_player) + 1) % len(self.players)
  ]
  self.current_player = next
  return next

That looks very much like code that was written in an interview situation: under stress, within a time limit and having to balance thinking, coding and communicating at the same time.

Improved with deque

Later when I returned to reflect on the solution, I realized this would make great use for a deque so I refactored:

from collections import deque

players = deque([
  Player('Lion'),
  Player('Two reeds'),
  Player('Twisted flax'),
  Player('Horned viper')
])
 
game = Kimble(players=players)
 
while not game.is_finished():
  game.advance()

First, my change was to turn players from list to a deque.

And in the part of the code where I had to find the current player, I would write

current_player = self.players[0]
# Do all the things
self.players.rotate(-1)

Thanks to deque.rotate, I was able to simplify the entire thing into a single rotation of the deque at the end of each turn.

To demonstrate how it works, let’s look at a simpler, isolated example that can be run:

animals = deque(['🐍', '🐤', '🐼', '🦄']) # Create a deque of animals

for _ in range(10):
  print(animals)
  animals.rotate(-1)
  
# deque(['🐍', '🐤', '🐼', '🦄'])
# deque(['🐤', '🐼', '🦄', '🐍'])
# deque(['🐼', '🦄', '🐍', '🐤'])
# deque(['🦄', '🐍', '🐤', '🐼'])
# deque(['🐍', '🐤', '🐼', '🦄'])
# deque(['🐤', '🐼', '🦄', '🐍'])
# deque(['🐼', '🦄', '🐍', '🐤'])
# deque(['🦄', '🐍', '🐤', '🐼'])
# deque(['🐍', '🐤', '🐼', '🦄'])
# deque(['🐤', '🐼', '🦄', '🐍'])

You can see here that on every iteration, we move each item one to the left (with -1 ) and anything that would fall off from the edge gets added to the end of the deque.