CS260 Programming Assignment 3

• Write a Python3 program project3.py that operates as described below.
• Your program will read from standard input and write to standard output. The input has four lines. The first three lines are integer values (n, f, b) and the fourth line is a string (s). The output will be a single integer value, which is explained below.
• Your program will implement a doubly-linked circular list. Do not use Pythons built-in list, or array, or any other pre-defined type!
• Begin by constructing a linked list with values 0,1,2,3,,n. Initially the current position is at node 0, and the current direction is forward.
• The size of the list can be very large, so your program should use efficient linked list operations. Otherwise your program might be too slow for some larger data sizes.
• Your linked list must support at least these six operations:
  • Toggle the current direction between forward and backward
  • Move either f nodes forward or b nodes backward, depending on the current direction
  • Increment the current nodes value, modulo n+1, so the value remains in range 0n
  • Decrement the current nodes value, modulo n+1, so the value remains in range 0n
  • Copy the current nodes value to a new node; insert this new node before the current node if current direction is forward, or after the current node if current direction is backward
  • Remove the current node; print the removed value if the list becomes empty; otherwise move to the previous node if current direction is forward, or to the next node if current direction is backward
• The input string s indicates a sequence of list operations to be performed. Each character of s must be the first letter of one of the six linked list operations described above (either uppercase or lowercase). Your program will perform the indicated sequence of list operations, and continue repeating this same sequence of operations as many times as necessary, until the list becomes empty and the final removed value is displayed.
• Example: Here are an input file input0.txt and its corresponding output file output0.txt, which can be created via this command: python3 project3.py < input0.txt > output0.txt

5
2
1
mrimrtmcd

4

• Here is an annotated trace using this input file input0.txt:

M
R
I
M
R
T
M
C
D
M
R
I
M
R
T
M
C
D
M
R
I
M
R
T
M
C
D
M
R
I
M
R
T
M
C
D
M
R
I
M
R

Initial constructed list
Move forward f=2 nodes
Remove node 2
Increment node 1 to 2
Move forward f=2 nodes
Remove node 4
Toggle direction to backward
Move backward b=1 node
Copy node 2
Decrement node 2 to 1
Move backward b=1 node
Remove node 0
Increment node 1 to 2
Move backward b=1 node
Remove node 5
Toggle direction to forward
Move forward f=2 nodes
Copy node 3
Decrement node 3 to 2
Move forward f=2 nodes
Remove node 2
Increment node 2 to 3
Move forward f=2 nodes
Remove node 2
Toggle direction to backward
Move backward b=1 node
Copy node 3
Decrement node 3 to 2
Move backward b=1 node
Remove node 3
Increment node 2 to 3
Move backward b=1 node
Remove node 3
Toggle direction to forward
Move forward f=2 nodes Copy node 3
Decrement node 3 to 2
Move forward f=2 nodes
Remove node 2
Increment node 3 to 4
Move forward f=2 nodes
Remove node 4
-> 0 <-> 1 <-> 2 <-> 3 <-> 4 <-> 5 <->
-> 2 <-> 3 <-> 4 <-> 5 <-> 0 <-> 1 <->
-> 1 <-> 3 <-> 4 <-> 5 <-> 0 <->
-> 2 <-> 3 <-> 4 <-> 5 <-> 0 <->
-> 4 <-> 5 <-> 0 <-> 2 <-> 3 <->
-> 3 <-> 5 <-> 0 <-> 2 <->
-> 3 <-> 5 <-> 0 <-> 2 <->
-> 2 <-> 3 <-> 5 <-> 0 <->
-> 2 <-> 2 <-> 3 <-> 5 <-> 0 <->
-> 1 <-> 2 <-> 3 <-> 5 <-> 0 <->
-> 0 <-> 1 <-> 2 <-> 3 <-> 5 <->
-> 1 <-> 2 <-> 3 <-> 5 <->
-> 2 <-> 2 <-> 3 <-> 5 <->
-> 5 <-> 2 <-> 2 <-> 3 <->
-> 2 <-> 2 <-> 3 <->
-> 2 <-> 2 <-> 3 <->
-> 3 <-> 2 <-> 2 <->
-> 3 <-> 2 <-> 2 <-> 3 <->
-> 2 <-> 2 <-> 2 <-> 3 <->
-> 2 <-> 3 <-> 2 <-> 2 <->
-> 2 <-> 3 <-> 2 <->
-> 3 <-> 3 <-> 2 <->
-> 2 <-> 3 <-> 3 <->
-> 3 <-> 3 <->
-> 3 <-> 3 <->
-> 3 <-> 3 <->
-> 3 <-> 3 <-> 3 <->
-> 2 <-> 3 <-> 3 <->
-> 3 <-> 2 <-> 3 <->
-> 2 <-> 3 <->
-> 3 <-> 3 <->
-> 3 <-> 3 <->
-> 3 <->
-> 3 <->
-> 3 <->
-> 3 <-> 3 <->
-> 2 <-> 3 <->
-> 2 <-> 3 <->
-> 3 <->
-> 4 <->
-> 4 <-> 4