Q:

Your task is to construct the tower in N days by following these conditions: Every day you are provided with one disk of distinct size. The disk with larger sizes should be placed at the bottom of the tower. The disk with smaller sizes should be placed at the top of the tower. The order in which tower must be constructed is as follows: You cannot put a new disk on the top of the tower until all the larger disks that are given to you get placed.

Requirements

1. Implement the above problem statement using Python 3.7

2. Read the input from a file(inputPS07.txt),

Print N lines denoting the disk sizes that can be put on the tower on the ith day. Use Queues to solve the statement.

3. You will output your answers to a file (outputPS07.txt) for each line.

4. Perform an analysis for the features above and give the running time in terms of input size: n.

Sample Input

First line: N denoting the total number of disks that are given to you in the N subsequent days.

Second line: N integers in which the i th integers denotes the size of the disks that is given to you on the i th day

Note: All the disk sizes are distinct integers in the range of 1 to N.

Input will be taken from the file(inputPS07.txt)

5

4 5 1 2 3

Note that the input/output data shown here is only for understanding and testing, the actual file used for evaluation will be different.

Sample Output

Print N lines. In the i th line, print the size of disks that can be placed on the top of the tower in descending order of the disk sizes.

If on the i th day no disks can be placed, then leave that line empty.

Display the output in outputPS07.txt.

1 >

2 > 5 4

3>

4>

5> 3 2 1

Note that the input/output data shown here is only for understanding and testing, the actual file used for evaluation will be different with all the test cases

Explanation:

On the first day, the disk of size 4 is given. But you cannot put the disk on the bottom of the tower as a disk of size 5 is still remaining.

On the second day, the disk of size 5 will be given so now disk of sizes 5 and 4 can be placed on the tower.

On the third and fourth day, disks cannot be placed on the tower as the disk of 3 needs to be given yet. Therefore, these lines are empty.

On the fifth day, all the disks of sizes 3, 2, and 1 can be placed on the top of the tower.

The code for this problem is given below:

from queue import Queue from typing import List

def bitsTower(N, discSizes): day=1 results = [] queue = {} for size in discSizes: queue[size] = True placed = str(day) +'> ' if size == N: placed += str(size) + ' ' N -= 1 while N in queue: placed += str(N) + ' ' N -= 1 day=day+1 results.append(placed) return results

def main(): # Read input from as per problmem statement with open('inputPS07.txt', 'r') as f: N = int(f.readline()) discSizes = list(map(int, f.readline().split())) # Build bits tower results = bitsTower(N, discSizes)

# Write output to file with open('outputPS07.txt', 'w') as f: print(results,'results') for result in results: f.write(result + " ")

if __name__ == "__main__": main()

So the questions are:

a. The data structure model you chose with justifications

b. Details of each operations with the time complexity and reasons why the chosen operations are efficient for the given representation

c. One alternate way of modeling the problem with the cost implications.

d. what is the use of queue[size] = True in this code

Kindly give proper justification of all these 4 points in detail.