-
Notifications
You must be signed in to change notification settings - Fork 103
/
process_packages.py
136 lines (109 loc) · 4.11 KB
/
process_packages.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
# python3
class Buffer:
"""Represents the queue of the times when the computer will finish
processing the packets which are currently stored in the network buffer.
Samples:
>>> size, count = 1, 0
>>> requests = []
>>> buffer = Buffer(size)
>>> responses = [buffer.process(r) for r in requests]
>>> print_responses(responses)
>>>
>>> # Explanation: If there are no packets, you shouldn't output anything.
>>> size, count = 1, 1
>>> requests = [Request(0, 0)]
>>> buffer = Buffer(size)
>>> responses = [buffer.process(r) for r in requests]
>>> print_responses(responses)
0
>>> # Explanation: The only packet arrived at time 0, and computer started
>>> # processing it immediately.
>>> size, count = 1, 2
>>> requests = [Request(0, 1), Request(0, 1)]
>>> buffer = Buffer(size)
>>> responses = [buffer.process(r) for r in requests]
>>> print_responses(responses)
0
-1
>>> # Explanation: The first packet arrived at time 0, the second packet
>>> # also arrived at time 0, but was dropped, because the network buffer
>>> # has size 1 and it was full with the first packet already.
>>> # The first packet started processing at time 0, and the second packet
>>> # was not processed at all.
>>> size, count = 1, 2
>>> requests = [Request(0, 1), Request(1, 1)]
>>> buffer = Buffer(size)
>>> responses = [buffer.process(r) for r in requests]
>>> print_responses(responses)
0
1
>>> # Explanation: The first packet arrived at time 0, the computer started
>>> # processing it immediately and finished at time 1. The second packet
>>> # arrived at time 1, and the computer started processing it immediately.
"""
def __init__(self, size):
self.size = size
self.finish_time = []
@property
def is_full(self):
"""Return True if the buffer is full, False otherwise."""
if len(self.finish_time) == self.size:
return True
return False
@property
def is_empty(self):
"""Return True if the buffer is empty, False otherwise."""
if len(self.finish_time) == 0:
return True
return False
@property
def last_element(self):
"""Returns the last element of the buffer."""
return self.finish_time[-1]
def flush_processed(self, request):
"""
Flushes processed elements of the buffer by the request's arrival time.
"""
while self.finish_time:
if self.finish_time[0] <= request.arrival_time:
self.finish_time.pop(0)
else:
break
def process(self, request):
"""Processes incoming request."""
self.flush_processed(request)
if self.is_full:
return Response(True, -1)
if self.is_empty:
self.finish_time = [request.arrival_time + request.process_time]
return Response(False, request.arrival_time)
response = Response(False, self.last_element)
self.finish_time.append(self.last_element + request.process_time)
return response
class Request:
"""Incoming network packet."""
def __init__(self, arrival_time, process_time):
self.arrival_time = arrival_time
self.process_time = process_time
class Response:
"""Response of the network buffer."""
def __init__(self, dropped, start_time):
self.dropped = dropped
self.start_time = start_time
def read_requests(count):
requests = []
for i in range(count):
arrival_time, process_time = map(int, input().strip().split())
requests.append(Request(arrival_time, process_time))
return requests
def process_requests(requests, buffer):
return [buffer.process(r) for r in requests]
def print_responses(responses):
for response in responses:
print(response.start_time if not response.dropped else -1)
if __name__ == "__main__":
size, count = map(int, input().strip().split())
requests = read_requests(count)
buffer = Buffer(size)
responses = process_requests(requests, buffer)
print_responses(responses)