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

### 29 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!

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:

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.