Last active
September 27, 2019 11:27
-
-
Save liilac/35b92749e52168aeef317a683a91ef4f to your computer and use it in GitHub Desktop.
Sample solution
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from collections import deque | |
# defines a type of "object", that represents a ticket-seeking visitor | |
class Visitor: | |
# stores how many tickets the visitor needs | |
needs = 0 | |
# stores how many tickets the visitor has | |
has = 0 | |
# defines method to create a new visitor | |
def __init__(self, needs): | |
self.needs = needs | |
self.has = 0 | |
# defines method to buy ticket, returns (outputs) whether they have enough now | |
def buy(self): | |
self.has += 1 | |
return self.hasEnough() | |
# defines method to check if visitor has enough tickets | |
def hasEnough(self): | |
return self.has >= self.needs | |
def waitingTime(tickets, p): | |
# track visitor needs | |
visitors = [ Visitor(n) for n in tickets ] | |
numVisitors = len(tickets) | |
# queue represents the ticket line as a doubly-linked list | |
queue = deque( range(numVisitors) ) | |
# track time units | |
t = 0 | |
# run ticket queue until alex has enough tickets | |
while not visitors[p].hasEnough(): | |
# increment time counter by one unit | |
t += 1 | |
# remove leftmost (front) visitor from the line, grab visitor num | |
cur = queue.popleft() | |
# give visitor one extra ticket | |
# if they still need more, add to back of the line | |
if not visitors[cur].buy(): | |
queue.append(cur) | |
# output how long it took alex to get their tickets | |
return t |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from collections import deque | |
class Visitor: | |
needs = 0 | |
has = 0 | |
def __init__(self, needs): | |
self.needs = needs | |
self.has = 0 | |
def buy(self): | |
self.has += 1 | |
return self.hasEnough() | |
def hasEnough(self): | |
return self.has >= self.needs | |
def waitingTime(tickets, p): | |
visitors = [ Visitor(n) for n in tickets ] | |
numVisitors = len(tickets) | |
queue = deque( range(numVisitors) ) | |
t = 0 | |
while not visitors[p].hasEnough(): | |
t += 1 | |
cur = queue.popleft() | |
if not visitors[cur].buy(): | |
queue.append(cur) | |
return t |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment