You are given two non-empty arrays A and B consisting of N integers. Arrays A and B represent N voracious fish in a river, ordered downstream along the flow of the river.
The fish are numbered from 0 to N − 1. If P and Q are two fish and P < Q, then fish P is initially upstream of fish Q. Initially, each fish has a unique position.
Fish number P is represented by A[P] and B[P]. Array A contains the sizes of the fish. All its elements are unique. Array B contains the directions of the fish. It contains only 0s and/or 1s, where:
- 0 represents a fish flowing upstream,
- 1 represents a fish flowing downstream.
If two fish move in opposite directions and there are no other (living) fish between them, they will eventually meet each other. Then only one fish can stay alive − the larger fish eats the smaller one. More precisely, we say that two fish P and Q meet each other when P < Q, B[P] = 1 and B[Q] = 0, and there are no living fish between them. After they meet:
- If A[P] > A[Q] then P eats Q, and P will still be flowing downstream,
- If A[Q] > A[P] then Q eats P, and Q will still be flowing upstream.
We assume that all the fish are flowing at the same speed. That is, fish moving in the same direction never meet. The goal is to calculate the number of fish that will stay alive.
For example, consider arrays A and B such that:
A[0] = 4 B[0] = 0 A[1] = 3 B[1] = 1 A[2] = 2 B[2] = 0 A[3] = 1 B[3] = 0 A[4] = 5 B[4] = 0Initially all the fish are alive and all except fish number 1 are moving upstream. Fish number 1 meets fish number 2 and eats it, then it meets fish number 3 and eats it too. Finally, it meets fish number 4 and is eaten by it. The remaining two fish, number 0 and 4, never meet and therefore stay alive.
Write a function:
def solution(A, B)
that, given two non-empty arrays A and B consisting of N integers, returns the number of fish that will stay alive.
For example, given the arrays shown above, the function should return 2, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- each element of array A is an integer within the range [0..1,000,000,000];
- each element of array B is an integer that can have one of the following values: 0, 1;
- the elements of A are all distinct.
def solution(A, B):
alive_count = 0 # The number of fish that will stay alive
downstream = [] # To record the fishs flowing downstream
downstream_count = 0 # To record the number of elements in downstream
for index in xrange(len(A)):
# Compute for each fish
if B[index] == 1:
# This fish is flowing downstream. It would
# NEVER meet the previous fishs. But possibly
# it has to fight with the downstream fishs.
downstream.append(A[index])
downstream_count += 1
else:
# This fish is flowing upstream. It would either
# eat ALL the previous downstream-flow fishs,
# and stay alive.
# OR
# be eaten by ONE of the previous downstream-
# flow fishs, which is bigger, and died.
while downstream_count != 0:
# It has to fight with each previous living
# fish, with nearest first.
if downstream[-1] < A[index]:
# Win and to continue the next fight
downstream_count -= 1
downstream.pop()
else:
# Lose and die
break
else:
# This upstream-flow fish eat all the previous
# downstream-flow fishs. Win and stay alive.
alive_count += 1
# Currently, all the downstream-flow fishs in stack
# downstream will not meet with any fish. They will
# stay alive.
alive_count += len(downstream)
return alive_count
Traceback (most recent call last): File "exec.py", line 139, in <module> main() File "exec.py", line 101, in main result = solution( A, B ) File "/tmp/solution.py", line 5, in solution for index in xrange(len(A)): NameError: name 'xrange' is not defined
def solution(A, B):
alive_count = 0 # The number of fish that will stay alive
downstream = [] # To record the fishs flowing downstream
downstream_count = 0 # To record the number of elements in downstream
for index in range(len(A)):
# Compute for each fish
if B[index] == 1:
# This fish is flowing downstream. It would
# NEVER meet the previous fishs. But possibly
# it has to fight with the downstream fishs.
downstream.append(A[index])
downstream_count += 1
else:
# This fish is flowing upstream. It would either
# eat ALL the previous downstream-flow fishs,
# and stay alive.
# OR
# be eaten by ONE of the previous downstream-
# flow fishs, which is bigger, and died.
while downstream_count != 0:
# It has to fight with each previous living
# fish, with nearest first.
if downstream[-1] < A[index]:
# Win and to continue the next fight
downstream_count -= 1
downstream.pop()
else:
# Lose and die
break
else:
# This upstream-flow fish eat all the previous
# downstream-flow fishs. Win and stay alive.
alive_count += 1
# Currently, all the downstream-flow fishs in stack
# downstream will not meet with any fish. They will
# stay alive.
alive_count += len(downstream)
return alive_count
def solution(A, B):
alive_count = 0 # The number of fish that will stay alive
downstream = [] # To record the fishs flowing downstream
downstream_count = 0 # To record the number of elements in downstream
for index in range(len(A)):
# Compute for each fish
if B[index] == 1:
# This fish is flowing downstream. It would
# NEVER meet the previous fishs. But possibly
# it has to fight with the downstream fishs.
downstream.append(A[index])
downstream_count += 1
else:
# This fish is flowing upstream. It would either
# eat ALL the previous downstream-flow fishs,
# and stay alive.
# OR
# be eaten by ONE of the previous downstream-
# flow fishs, which is bigger, and died.
while downstream_count != 0:
# It has to fight with each previous living
# fish, with nearest first.
if downstream[-1] < A[index]:
# Win and to continue the next fight
downstream_count -= 1
downstream.pop()
else:
# Lose and die
break
else:
# This upstream-flow fish eat all the previous
# downstream-flow fishs. Win and stay alive.
alive_count += 1
# Currently, all the downstream-flow fishs in stack
# downstream will not meet with any fish. They will
# stay alive.
alive_count += len(downstream)
return alive_count
def solution(A, B):
downstream = [] # To record the fishs flowing downstream
downstream_count = 0 # To record the number of elements in downstream
for index in range(len(A)):
# Compute for each fish
if B[index] == 1:
# This fish is flowing downstream. It would
# NEVER meet the previous fishs. But possibly
# it has to fight with the downstream fishs.
downstream.append(A[index])
downstream_count += 1
else:
# This fish is flowing upstream. It would either
# eat ALL the previous downstream-flow fishs,
# and stay alive.
# OR
# be eaten by ONE of the previous downstream-
# flow fishs, which is bigger, and died.
while downstream_count != 0:
# It has to fight with each previous living
# fish, with nearest first.
if downstream[-1] < A[index]:
# Win and to continue the next fight
downstream_count -= 1
downstream.pop()
else:
# Lose and die
break
else:
# This upstream-flow fish eat all the previous
# downstream-flow fishs. Win and stay alive.
alive_count += 1
# Currently, all the downstream-flow fishs in stack
# downstream will not meet with any fish. They will
# stay alive.
alive_count += len(downstream)
return alive_count
def solution(A, B):
downstream = [] # To record the fishs flowing downstream
downstream_count = 0 # To record the number of elements in downstream
for index in range(len(A)):
# Compute for each fish
if B[index] == 1:
# This fish is flowing downstream. It would
# NEVER meet the previous fishs. But possibly
# it has to fight with the downstream fishs.
downstream.append(A[index])
downstream_count += 1
else:
# This fish is flowing upstream. It would either
# eat ALL the previous downstream-flow fishs,
# and stay alive.
# OR
# be eaten by ONE of the previous downstream-
# flow fishs, which is bigger, and died.
while downstream_count != 0:
# It has to fight with each previous living
# fish, with nearest first.
if downstream[-1] < A[index]:
# Win and to continue the next fight
downstream_count -= 1
downstream.pop()
else:
# Lose and die
break
else:
# This upstream-flow fish eat all the previous
# downstream-flow fishs. Win and stay alive.
alive_count += 1
# Currently, all the downstream-flow fishs in stack
# downstream will not meet with any fish. They will
# stay alive.
return alive_count+len(downstream)
Traceback (most recent call last): File "exec.py", line 139, in <module> main() File "exec.py", line 101, in main result = solution( A, B ) File "/tmp/solution.py", line 32, in solution alive_count += 1 UnboundLocalError: local variable 'alive_count' referenced before assignment
def solution(A, B):
downstream = [] # To record the fishs flowing downstream
downstream_count = 0 # To record the number of elements in downstream
for index in range(len(A)):
# Compute for each fish
if B[index] == 1:
# This fish is flowing downstream. It would
# NEVER meet the previous fishs. But possibly
# it has to fight with the downstream fishs.
downstream.append(A[index])
downstream_count += 1
else:
# This fish is flowing upstream. It would either
# eat ALL the previous downstream-flow fishs,
# and stay alive.
# OR
# be eaten by ONE of the previous downstream-
# flow fishs, which is bigger, and died.
while downstream_count != 0:
# It has to fight with each previous living
# fish, with nearest first.
if downstream[-1] < A[index]:
# Win and to continue the next fight
downstream_count -= 1
downstream.pop()
else:
# Lose and die
break
else:
# This upstream-flow fish eat all the previous
# downstream-flow fishs. Win and stay alive.
alive_count += 1
# Currently, all the downstream-flow fishs in stack
# downstream will not meet with any fish. They will
# stay alive.
return alive_count+
def solution(A, B):
alive_count = 0 # The number of fish that will stay alive
downstream = [] # To record the fishs flowing downstream
downstream_count = 0 # To record the number of elements in downstream
for index in range(len(A)):
# Compute for each fish
if B[index] == 1:
# This fish is flowing downstream. It would
# NEVER meet the previous fishs. But possibly
# it has to fight with the downstream fishs.
downstream.append(A[index])
downstream_count += 1
else:
# This fish is flowing upstream. It would either
# eat ALL the previous downstream-flow fishs,
# and stay alive.
# OR
# be eaten by ONE of the previous downstream-
# flow fishs, which is bigger, and died.
while downstream_count != 0:
# It has to fight with each previous living
# fish, with nearest first.
if downstream[-1] < A[index]:
# Win and to continue the next fight
downstream_count -= 1
downstream.pop()
else:
# Lose and die
break
else:
# This upstream-flow fish eat all the previous
# downstream-flow fishs. Win and stay alive.
alive_count += 1
# Currently, all the downstream-flow fishs in stack
# downstream will not meet with any fish. They will
# stay alive.
alive_count += len(downstream)
return alive_count
def solution(A, B):
"""
Codility 100%
https://app.codility.com/demo/results/trainingTJQUQF-HAE/
Idea is to use stack concept
For each iteration if current fish is of type 1 add it to stack 1 fish
Create stack 1 fish - it always holds the downstream ie 1 kind of fish
and keep killing the smaller fish from the list if it is greater
else killed by current fish.
Now if stack 1 fish has no fish it means current fish can be counted as remaining fish.
0 represents a fish flowing upstream - 0 fish
1 represents a fish flowing downstream - 1 fish
A[0] = 4 B[0] = 0 alive fish
A[1] = 3 B[1] = 1 downstream
A[2] = 2 B[2] = 0 eaten by A[1]
A[3] = 1 B[3] = 0 eaten by A[1]
A[4] = 5 B[4] = 0 eat to A[1] and remain alive
"""
count = 0
# stores the 1 fish in stack
stack_1_fish = []
print(A)
print(B)
for index in range(len(A)):
if B[index] == 0:
# until stack has some 1 fish
while stack_1_fish:
# get last fish from stack and check if it can die or not
# the larger fish eats the smaller one.
# two fish P and Q meet each other when P < Q, B[P] = 1 and B[Q] = 0, and there are no living fish between them
if stack_1_fish[-1] > A[index]:
# stack 1 fish kill to current fish
# exit from while loop and else block also execute next top for loop
# check for other fish fight
print("Killed by " + str(stack_1_fish[-1]) + " Die " + str(A[index]))
break
else:
# stack 1 fish is killed by current fish
p = stack_1_fish.pop()
print("Killed by " + str(A[index]) + " Die " + str(p))
# this is the case when stack becomes empty ie. no fish of kind 1
# it would never meet previous fish but can fight with downstream fish
else:
print("Count fish as remaining......." + str(A[index]))
count += 1
else:
# fish 1 found add to stack
stack_1_fish.append(A[index])
print("1 fish found, add to stack, it can kill or killed by someone..." + str(A[index]))
print(stack_1_fish)
print("Count: " + str(count))
print("Stack 1 fish: " + str(len(stack_1_fish)))
return count + len(stack_1_fish)
def solution(A, B):
"""
Idea is to use stack concept
For each iteration if current fish is of type 1 add it to stack 1 fish
Create stack 1 fish - it always holds the downstream ie 1 kind of fish
and keep killing the smaller fish from the list if it is greater
else killed by current fish.
Now if stack 1 fish has no fish it means current fish can be counted as remaining fish.
0 represents a fish flowing upstream - 0 fish
1 represents a fish flowing downstream - 1 fish
A[0] = 4 B[0] = 0 alive fish
A[1] = 3 B[1] = 1 downstream
A[2] = 2 B[2] = 0 eaten by A[1]
A[3] = 1 B[3] = 0 eaten by A[1]
A[4] = 5 B[4] = 0 eat to A[1] and remain alive
"""
count = 0
# stores the 1 fish in stack
stack_1_fish = []
print(A)
print(B)
for index in range(len(A)):
if B[index] == 0:
# until stack has some 1 fish
while stack_1_fish:
# get last fish from stack and check if it can die or not
# the larger fish eats the smaller one.
# two fish P and Q meet each other when P < Q, B[P] = 1 and B[Q] = 0, and there are no living fish between them
if stack_1_fish[-1] > A[index]:
# stack 1 fish kill to current fish
# exit from while loop and else block also execute next top for loop
# check for other fish fight
print("Killed by " + str(stack_1_fish[-1]) + " Die " + str(A[index]))
break
else:
# stack 1 fish is killed by current fish
p = stack_1_fish.pop()
print("Killed by " + str(A[index]) + " Die " + str(p))
# this is the case when stack becomes empty ie. no fish of kind 1
# it would never meet previous fish but can fight with downstream fish
else:
print("Count fish as remaining......." + str(A[index]))
count += 1
else:
# fish 1 found add to stack
stack_1_fish.append(A[index])
print("1 fish found, add to stack, it can kill or killed by someone..." + str(A[index]))
print(stack_1_fish)
print("Count: " + str(count))
print("Stack 1 fish: " + str(len(stack_1_fish)))
return count + len(stack_1_fish)
def solution(A, B):
"""
Idea is to use stack concept
For each iteration if current fish is of type 1 add it to stack 1 fish
Create stack 1 fish - it always holds the downstream ie 1 kind of fish
and keep killing the smaller fish from the list if it is greater
else killed by current fish.
Now if stack 1 fish has no fish it means current fish can be counted as remaining fish.
0 represents a fish flowing upstream - 0 fish
1 represents a fish flowing downstream - 1 fish
A[0] = 4 B[0] = 0 alive fish
A[1] = 3 B[1] = 1 downstream
A[2] = 2 B[2] = 0 eaten by A[1]
A[3] = 1 B[3] = 0 eaten by A[1]
A[4] = 5 B[4] = 0 eat to A[1] and remain alive
"""
count = 0
# stores the 1 fish in stack
stack_1_fish = []
# print(A)
# print(B)
for index in range(len(A)):
if B[index] == 0:
# until stack has some 1 fish
while stack_1_fish:
# get last fish from stack and check if it can die or not
# the larger fish eats the smaller one.
# two fish P and Q meet each other when P < Q, B[P] = 1 and B[Q] = 0, and there are no living fish between them
if stack_1_fish[-1] > A[index]:
# stack 1 fish kill to current fish
# exit from while loop and else block also execute next top for loop
# check for other fish fight
# print("Killed by " + str(stack_1_fish[-1]) + " Die " + str(A[index]))
break
else:
# stack 1 fish is killed by current fish
p = stack_1_fish.pop()
# print("Killed by " + str(A[index]) + " Die " + str(p))
# this is the case when stack becomes empty ie. no fish of kind 1
# it would never meet previous fish but can fight with downstream fish
else:
# print("Count fish as remaining......." + str(A[index]))
count += 1
else:
# fish 1 found add to stack
stack_1_fish.append(A[index])
# print("1 fish found, add to stack, it can kill or killed by someone..." + str(A[index]))
# print(stack_1_fish)
# print("Count: " + str(count))
# print("Stack 1 fish: " + str(len(stack_1_fish)))
return count + len(stack_1_fish)
def solution(A, B):
"""
Idea is to use stack concept
For each iteration if current fish is of type 1 add it to stack 1 fish
Create stack 1 fish - it always holds the downstream ie 1 kind of fish
and keep killing the smaller fish from the list if it is greater
else killed by current fish.
Now if stack 1 fish has no fish it means current fish can be counted as remaining fish.
0 represents a fish flowing upstream - 0 fish
1 represents a fish flowing downstream - 1 fish
A[0] = 4 B[0] = 0 alive fish
A[1] = 3 B[1] = 1 downstream
A[2] = 2 B[2] = 0 eaten by A[1]
A[3] = 1 B[3] = 0 eaten by A[1]
A[4] = 5 B[4] = 0 eat to A[1] and remain alive
"""
count = 0
# stores the 1 fish in stack
stack_1_fish = []
# print(A)
# print(B)
for index in range(len(A)):
if B[index] == 0:
# until stack has some 1 fish
while stack_1_fish:
# get last fish from stack and check if it can die or not
# the larger fish eats the smaller one.
# two fish P and Q meet each other when P < Q, B[P] = 1 and B[Q] = 0, and there are no living fish between them
if stack_1_fish[-1] > A[index]:
# stack 1 fish kill to current fish
# exit from while loop and else block also execute next top for loop
# check for other fish fight
# print("Killed by " + str(stack_1_fish[-1]) + " Die " + str(A[index]))
break
else:
# stack 1 fish is killed by current fish
p = stack_1_fish.pop()
# print("Killed by " + str(A[index]) + " Die " + str(p))
# this is the case when stack becomes empty ie. no fish of kind 1
# it would never meet previous fish but can fight with downstream fish
else:
# print("Count fish as remaining......." + str(A[index]))
count += 1
else:
# fish 1 found add to stack
stack_1_fish.append(A[index])
# print("1 fish found, add to stack, it can kill or killed by someone..." + str(A[index]))
# print(stack_1_fish)
# print("Count: " + str(count))
# print("Stack 1 fish: " + str(len(stack_1_fish)))
return count + len(stack_1_fish)
def solution(A, B):
"""
Idea is to use stack concept
For each iteration if current fish is of type 1 add it to stack 1 fish
Create stack 1 fish - it always holds the downstream ie 1 kind of fish
and keep killing the smaller fish from the list if it is greater
else killed by current fish.
Now if stack 1 fish has no fish it means current fish can be counted as remaining fish.
0 represents a fish flowing upstream - 0 fish
1 represents a fish flowing downstream - 1 fish
A[0] = 4 B[0] = 0 alive fish
A[1] = 3 B[1] = 1 downstream
A[2] = 2 B[2] = 0 eaten by A[1]
A[3] = 1 B[3] = 0 eaten by A[1]
A[4] = 5 B[4] = 0 eat to A[1] and remain alive
"""
count = 0
# stores the 1 fish in stack
stack_1_fish = []
# print(A)
# print(B)
for index in range(len(A)):
if B[index] == 0:
# until stack has some 1 fish
while stack_1_fish:
# get last fish from stack and check if it can die or not
# the larger fish eats the smaller one.
# two fish P and Q meet each other when P < Q, B[P] = 1 and B[Q] = 0, and there are no living fish between them
if stack_1_fish[-1] > A[index]:
# stack 1 fish kill to current fish
# exit from while loop and else block also execute next top for loop
# check for other fish fight
# print("Killed by " + str(stack_1_fish[-1]) + " Die " + str(A[index]))
break
else:
# stack 1 fish is killed by current fish
p = stack_1_fish.pop()
# print("Killed by " + str(A[index]) + " Die " + str(p))
# this is the case when stack becomes empty ie. no fish of kind 1
# it would never meet previous fish but can fight with downstream fish
else:
# print("Count fish as remaining......." + str(A[index]))
count += 1
else:
# fish 1 found add to stack
stack_1_fish.append(A[index])
# print("1 fish found, add to stack, it can kill or killed by someone..." + str(A[index]))
# print(stack_1_fish)
# print("Count: " + str(count))
# print("Stack 1 fish: " + str(len(stack_1_fish)))
return count + len(stack_1_fish)
The solution obtained perfect score.