Skip to content

Instantly share code, notes, and snippets.

@liilac
Last active September 27, 2019 11:27
Show Gist options
  • Save liilac/35b92749e52168aeef317a683a91ef4f to your computer and use it in GitHub Desktop.
Save liilac/35b92749e52168aeef317a683a91ef4f to your computer and use it in GitHub Desktop.
Sample solution
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
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