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

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

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

  3. 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!

  4. I have quite simple one πŸ™‚

  5. 100% solution in c++

  6. Hello this is my solution

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

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

  8. In java .. kind of similar

  9. My 100% C# solution:

  10. 100%, 100% java solution

  11. 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_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]

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

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

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

  14. Python 100% , took me a while tho

  15. My 100% PHP -version

  16. Here is my solution in Python:

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

Leave a Reply

Your email address will not be published. Required fields are marked *

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!