Question: http://codility.com/demo/take-sample-test/fish

Question Name: Fish

**UPDATE** 03-14-2014: “downstream_count” is a redundant variable. It could be replaced with len(downstream) safely. (Thanks to the reminder from Max)

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 | 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 |

Hi Shen, what is the use of ‘downstream_count’ if you increase it everytime you push to ‘downstream’ stack and decrease it everytime you pop from ‘downstream’ stack, and you have len(downstream) at your disposal?

Am I wrong or that variable has no use? you could substitute ‘downstream_count != 0’ condition with len(downstream) != 0, am I not right?

thank you for this solutions, you are helping me a lot when I get stuck on something… T_T

Yes, you are right. It is a redundant variable. It could be replaced with len(downstream).

Eheh, it’s just your code is so neat and your logic is so good it seemed odd you used a redundant variable! 😀

Since I am already writing, how come you have completed all codility tasks? Was it for a job application or for fun?

I am having quite a hard time, because it’s been a while since I am not coding seriously and last time I handled logic problems like this, it was in first year at university. I would love to put myself to challenge and learn them myself, but I have been assigned a test for a job application and I only have four days to perform it…so I am just trying to learn as much as I can, as best as I can.

I obviously do not know what test they have for me, what do you think, what is your experience?

thanks a lot, congrats again for your logic skills

I did these questions for both fun and internship hunting. For some hard questions, they cost me days or even weeks to solve one. But to be honest, I am a Muggle in interviews… So I cannot give you any valuable suggestion. Good luck and enjoy coding!

Good to know I am not the only one who does not solve them in 120 mins!

It is quite reassuring, although not very useful.

I am curious now, what do you do in your life?

A long story short, a computer science student. In terms of the time, I wish I could finish the hard problem in even 1200 mins~ But I cannot in most cases. That is why I enjoy it. Coding and improving.

My solution to this problem (looks a little bit stupid tho..):

Thanks for sharing your code. Enjoying coding!

I like your use of the pythonic while/else. It makes the code more simple.

Just for completeness sake, here my 100/100 solution.

Great job with the blog!

Thanks! Looking forward your novel solutions to other challenges!

Enjoy coding!

This solution got 100% correctness but 75% performance, though O(N):

EDITED BY SEHNG: you code is incomplete.

Please read my post. I think it shows the idea clearly.

I have quite simple one 🙂

Thanks!

I like your solution. If I understand correctly, It works by taking fish, have them battle and then place the winner on the stack.

100% solution in c++

Hello this is my solution

Thank you very much for sharing!

Personally, I strongly discourage your coding style: while/if/else without {}.

You discourage this style and still you choose Python to present your solutions?! :p

(Sorry, I just hate Python syntax 🙂 )

I know. Programming language is extremely personal preference.

C/C++ use bracelets { and } to solve the dangling else problem, while Python use indentation. As a result, to me, the bracelets is strongly recommended when I used any while/for/if.

A Java Solution that uses the Stack size as a result.

https://codility.com/demo/results/demo967MY4-J2X/

In java .. kind of similar

My 100% C# solution:

100%, 100% java solution

Can you explain me in your answer why you’re taking into account this?

# NEVER meet the previous fishs. But possibly it has to fight with the downstream fishs.

downstream.append(A[index])

downstream_count += 1

Since, what I understand is that the first fish will never “see” the second one…”If P and Q are two fish and P

Yes, you are right:

1. If A[0] = 1 and B[0] = 0 and A[1] = 2 and B[1] = 0 they will not meet since are flowing the same direction;

2. If A[0] = 1 and B[0] = 0 and A[1] = 2 and B[1] = 1, they will not meet since P < Q (0 A[1] is ahead of A[0] so they will be separating more and more and never meet.

My fault. There is an implicit condition for the statement "# NEVER meet the previous fishs. But possibly it (P) has to fight with the downstream fishs (Q)": the mentioned downstream fishes Q are swimming toward the this fish P. Because:

1. they are swimming in different directions; And

2. P < Q.

In other words, the P is on the left end and swimming toward the right side; and the Q is on the right end (we scan the fishes from left to right, or say, from index 0 to index N-1. We get Q later than P, so Q is on the righter sider than P.), and swimming toward the left side. So they might meet.

Checkout my C++ solution for this problem.

Please read the “Guideline for Comments” in the right column to post the complete code. Thanks!

I am wondering, is in all this solutions complexity actually O(n2) because we have for loop and while loop in it?

Short answer is: yes, it’s actually O(N).

It’s a common trap to count the complexity by checking the number of nested for/while. However, that’s not always correct. Please note that during the whole function, the

`while`

loop is executed at most N times, independently with the`for`

loop.It’s the reason why it took me 2 weeks to finish this task (in the context of adult life with non-dev job). I was trying to avoid a for-while combination, thinking back to the for-while combination in Insertion Sort, which does have O(n^2) time.

Thank you, Sheng for pointing out that this is a common trap, to assume that any for-while is O(n^2). Actually wrote down your comment, hopefully to never repeat this mistake again.

Indeed, like Sheng said, most times the while gets executed is n times. Worst case, when the while-loop has the largest number of fish to go through, is when you have n-1 downstreamers and one upstreamer at the end, bigger than all.

The last fish, the upstreamer, eats them one by one in the while loop. This means your program goes through all the n fish once in the for-loop, then once more through all the downstreamers in the while-loop. So thats n + (n-1). Technically, Sheng is right to say that while gets executed n times, as any while or for-loop will have the test executed one more time compared to its loop body.

At any rate, this is 2n (or 2n +1, to be more precise) number of times the for + while statements are evaluated in total. So worst case is 2n, therefore O(n).

Here’s a solution that uses only stack i.e. the result is the length of the stack and scores 100%.

Python 100% , took me a while tho

I updated the code as your follow-on comment. Thanks for sharing your code!

My 100% PHP -version

Here is my solution in Python:

Where do you handle the case where an upstream fish doesn’t eats all downstream ones but survive (they are of the same size).

We do not need to care about that. Problem description says “the elements of A are all distinct.”