I am trying to solve this code challenge:
There is mountain with a popular hiking trail. At one point on the trail, the path narrows so that only a single hiker can pass through at a time. When several hikers arrive at this point simultaneously two queues can build up one for hikers ascending the mountain and one for hikers descending. It takes each hiker one second to pass completely through the narrow portion of the trail. If all the waiting hikers are all going the same direction (either ascending or descending) then they can immediately begin passing through one at a time, in the order of their arrival. When hikers going in both directions are walking, then local custom dictates the following procedure for determining which hiker has priority and, gets to pass through path. The customs are below:
If in the previous second, no hiker passed through, then the first waiting, descending hiker gets to go first
If in the previous second, a descending hiker passed though, then the first hiker in the descending goes first
If in the previous second, an ascending hiker passed through, then the hiker in the ascending queue goes first
For each hiker, find the time when they will pass through the narrow portion of the trail.
Function Description
Complete the function
getResult
getResulthas the following parameters:
int arrival[n]: an array ofnintegers where the value at indexiis the time in seconds when theith hiker arrives at the narrow portion of the trail. Ifarrival[i] = arrival[j]andi < jthen then hikeriarrives before hikerj.
int direction[n]: an array ofnintegers where the value at indexiis the direction of theith hiker: 0 for ascending and 1 for descending.Returns:
int[n]: An array ofnintegers where the value at indexiis the time when theith hiker will pass through the narrow portion of the trail.
This is the code I have written. It works for the 1st test case. However, for the 2nd test case its wrong.
def getResult(arrival, direction):
n = len(arrival)
result = [0] * n
last_direction = -1 # -1 represents no hiker passed through in the previous second
i = 0
while i < len(arrival):
ascending_queue = []
descending_queue = []
if i == 0:
if direction[0] == 0:
#ascending_queue.pop(0)
result[0] = arrival[0]
last_direction = 0
else:
#descending_queue.pop(0)
result[0] = arrival[0]
last_direction = 1
a = i + 1 if i == 0 else i
chk = False
while(a + 1 < len(arrival) and arrival[a] == arrival[a+1]):
if direction[a] == 0:
ascending_queue.append(a)
else:
descending_queue.append(a)
if direction[a+1] == 0:
ascending_queue.append(a+1)
else:
descending_queue.append(a+1)
a += 1
chk = True
if ascending_queue and descending_queue:
if last_direction == 0:
next_val = i
idx = ascending_queue.pop(0)
result[idx] = arrival[i + 1]
prev = result[idx]
next_val = max(next_val,idx)
while ascending_queue:
idx = ascending_queue.pop(0)
result[idx] = prev + 1
last_direction = direction[idx]
prev = result[idx]
next_val = max(next_val,idx)
while descending_queue:
idx = descending_queue.pop(0)
result[idx] = prev + 1
last_direction = direction[idx]
prev = result[idx]
next_val = max(next_val,idx)
i = next_val
else:
next_val = i
idx = descending_queue.pop(0)
result[idx] = arrival[i + 1]
prev = result[idx]
next_val = max(next_val,idx)
while descending_queue:
idx = descending_queue.pop(0)
result[idx] = prev + 1
last_direction = direction[idx]
prev = result[idx]
next_val = max(next_val,idx)
while ascending_queue:
idx = ascending_queue.pop(0)
result[idx] = prev + 1
last_direction = direction[idx]
prev = result[idx]
next_val = max(next_val,idx)
i = next_val
else:
if chk:
j = i
while(arrival[j] == arrival[j+1]):
result[j] = arrival[i] if j == i else result[j-1] + 1
j += 1
else:
result[i] = arrival[i]
last_direction = direction[i]
if chk:
i = a + 1
else:
i += 1
return result
# Example usage:
#arrival = [0, 1, 1, 3, 3]
#direction = [0, 1, 0, 0, 1]
# Output: [0, 2, 1, 4, 3]
arrival = [0, 0, 1, 4]
direction = [0, 1, 1, 0]
#Ouput = [2, 0, 1, 4]
For the 2nd test case, my code returns [0, 0, 1, 4]. One drawback of my approach is that I am only adding hikers that arrive at the same time but in the 2nd case when we process the hiker at index 1 in descending order, we must then process the hiker at index 2 as they are descending. But my approach would process hiker at index 0 first.
I don't see a different way to do it.
Open to any different/new approaches/languages(Java/C++) or modifications to this approach.
The idea with two queues is fine, but I would put all hikers on these queues, and then pop from them as the time elapses. I would also combine the hiker id (the index in the input lists) with their arrival time in a tuple.
Here is how I would suggest doing it:
def getResult(arrival, direction):
# Determine a time before which all hikers will have gone through the narrow pass
max_time = max(arrival) + len(arrival)
def makeQueue(filter_dir):
# We rely on the fact that `sorted` implements a *stable* sort
q = sorted((time, hiker)
for hiker, (time, desc) in enumerate(zip(arrival, direction))
if desc == filter_dir)
# Add a dummy entry to avoid empty queue issues
q.append((max_time, -1))
# Reverse so we can pop from the queue in the right order
return q[::-1]
# Put all hikers in one of the two queues, with their id and time of arrival
queues = [makeQueue(0), makeQueue(1)] # Ascending hikers, descending hikers
result = [0] * len(arrival)
current_time = 0
# As long there are hikers that didn't pass through yet... keep going.
# (NB: each queue has a dummy entry at index 0)
while len(queues[0]) + len(queues[1]) > 2:
# Get the earliest time a hiker arrived or will arrive at the narrow pass
current_time = max(current_time, min(queues[0][-1][0], queues[1][-1][0]))
# If there are descending hikers already waiting at the narrow pass,
# then give them priority
active_queue = queues[queues[1][-1][0] <= current_time]
# Let all waiting people on the selected side go through the narrow pass.
while active_queue[-1][0] <= current_time: # Someone waiting?
# One hiker walks through the narrow pass
result[active_queue.pop()[1]] = current_time
# One second passes...
current_time += 1
# All hikers went through the narrow pass
return result