In this post I will demonstrate how we can use data structures to abstract a problem and solve it using a Doubly Linked List. I will first present the coding problem, then I will demonstrate how the doubly linked list can be applied to solve it.
The Problem
We have a circular printer like the one depicted in Image 1. It is a wheel with the letters A through Z in sequence. It wraps so A and Z are adjacent. Every time a word will be printed, the pointer is initially pointing at A. Moving from any character to any adjacent character takes 1 second. The pointer can move in either direction. Given a string of letters, what is the minimum time needed to print the string? (Note: Assume that printing does not take any time. Only consider the time it takes for the pointer to move.)
Let's look at an example with the string “BZA”. How long will it take to print this string with the circular printer? First, move the pointer from ‘A’ to ‘B’ (1 sec), then from ‘B’ to ‘Z’ (2 sec), and finally from ‘Z’ to ‘A’ (1 sec). So the minimum time needed to print “BZA” is 4 seconds.
The Pattern
Looking back at Image 1, there are two things we can notice right away. It is a circular object with a pointer that starts off at ‘A’, we can call this the head, and that it can move in either direction one letter, or node, at a time.
This is really beginning to sound like a circular doubly linked list. A doubly linked list is a data structure where each node has a reference to its next and previous neighbor nodes as depicted in Image 2.
To turn the doubly linked list into a circular doubly linked list we simply have to set the previous pointer of the head node to point to the last node in the list, and set the next pointer of the last node to point back to the head as shown in the first graphic of Image 3.
As you can also see from the second graphic in Image 3, we have all we need to represent our circular printer with a circular linked list.
The solution
Now that we understand how we can simulate the circular printer with a circular linked list, we will use it to solve our problem. We will do this by simulating the printing of a string using the circular linked list and simultaneously keeping count of how many times we move our pointer from one node to another to get the minimum total time taken to print a word.
Now let’s look at the code! I've implemented the solution in both Python and C++.
CircularPrinter.py
CircularPrinter.cpp