Rotating turn order with deque
![](/assets/img/posts//rotating-turn-order-with-deque/rotating-turn-order-with-deque-cover.png)
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.