# Solution to Fish by codility

23 Jan

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)

### 38 Replies to “Solution to Fish by codility”

1. Max says:

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

• Sheng says:

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

• Max says:

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

• Sheng says:

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!

• Max says:

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?

• Sheng says:

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.

2. Keajer says:

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

• Sheng says:

Thanks for sharing your code. Enjoying coding!

3. Martin says:

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!

• Sheng says:

Thanks! Looking forward your novel solutions to other challenges!
Enjoy coding!

4. Ale says:

This solution got 100% correctness but 75% performance, though O(N):
EDITED BY SEHNG: you code is incomplete.

• Sheng says:

5. Damian says:

I have quite simple one 🙂

• Sheng says:

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.

6. Rafal says:

100% solution in c++

7. Hello this is my solution

• Sheng says:

Thank you very much for sharing!
Personally, I strongly discourage your coding style: while/if/else without {}.

• Giovani says:

You discourage this style and still you choose Python to present your solutions?! :p
(Sorry, I just hate Python syntax 🙂 )

• Sheng says:

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.

8. A Java Solution that uses the Stack size as a result.
https://codility.com/demo/results/demo967MY4-J2X/

9. oneraj says:

In java .. kind of similar

10. Eddie says:

My 100% C# solution:

11. Dimuthu says:

100%, 100% java solution

12. Daniel says:

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 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 and if 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. What am I missing?
From the example:
-> A[0]
A[2]
->A[3]
->A[4]

• Sheng says:

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.

13. Craig says:

Checkout my C++ solution for this problem.

• Sheng says:

14. Davtomic says:

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

• Sheng says:

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.

• Ovidiu Oprea says:

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

15. Leonard says:

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

• Sheng says:

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

17. Bianca says:

My 100% PHP -version

18. Igor says:

Here is my solution in Python:

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

• Sheng says:

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