Solution to Frog-River-One by codility

19 Jan

Question: https://codility.com/demo/take-sample-test/frog_river_one

Question Name: FrogRiverOne

If coding with C, bitmap is preferred to store which positions are covered.

51 Replies to “Solution to Frog-River-One by codility

  1. 100 / 100 FrogRiver PHP

    • First of all, thanks for sharing your solution!

      Secondly, if you want to post code in the comment, please place the code inside a <pre> … </pre> block.

      Finally, you could move your second if block into the first one to get a little improvement.

      PS: when you consider to submit your code, it will be better if the solution is using a different method or algorithm. Difference on programming language does not mean much to the readers.

  2. Here is my solution. Got 100/100:

    • Sorry, when I tried it on Codility. Some error happened:
      Solution.cs(10,21): error CS1061: Type int[]' does not contain a definition for Distinct’ and no extension method Distinct' of type int[]’ could be found. Are you missing `System.Linq’ using directive?

      Could you please help me to fix it?

  3. Here is my Java solution:

  4. Thank you Sheng for solutions. Your website is very helpful. I am new in Python, so using your tutorials…
    Just want to share my first attempt to resolve this task with “if element not in covered_a” which had fail of performance and second one which stole from you to improve it.

  5. lean and mean:

  6. JavaScript version

    • Thanks for Sharing,

      I am learning software development, and I am a little confuse with
      count[index] = true;

      I understand that with this code you prevent that some element is repeat it in the array, but how does it work?

  7. PHP – 100% / 100%

  8. UPDATE by victor zhong on February 19, 2015 at 7:58 am:
    why my code lost indent…..

  9. Sets again:

    • It works. While from my point, there are some suggestions about this solution.

      On one hand, set is kind of too much for such a small question, especially consider the array is perfectly fit in such case.

      On the other hand, after the for loop, we’d better to have a “return -1” statement and/or a comment “Not reachable.”

      • I understand the concerns. However, this is a set problem in disguise and I presume that implementation yields the fastest computing time.

        Also, the “return -1” statement after the loop will never be reached. The only case that could return -1 is if set(A) does not contain all the leaves, which is being taken care of at the start.

        • These two solution should not have any noticeable difference in computing time, in practice.

          The “return -1” statement is my personal preference on coding style. Your code is neither bug nor bad 🙂

          Finally, thanks for being an active contributor.

  10. Hi Sheng, I apologize if the question is not very productive. But I’m a Python learner and I don’t get the part where you assign the value -1, X times to the “covered_time” list and then you test “if covered_time[A[index]-1] != -1”.
    Would python return an out of range error when the element you get from A[index] translates to a position greater than X (the size of the list)?

  11. Ruby 100%

  12. Here’s my C++ solution, got 100%:

    • There are some test cases where this program terminates:

      Your test case: [0, [0]]
      Output (stderr):
      Segmentation Fault
      RUNTIME ERROR (tested program terminated unexpectedly)

      Your test case: [0, [0, 5, 1, 4, 2, 3]]
      Output (stderr):
      Segmentation Fault
      RUNTIME ERROR (tested program terminated unexpectedly)

      Detected some errors.

  13. EDIT by Admin: Java solution.

  14. C# 100%

  15. Sorry but I think this case is not covered by this code.

    • There is an assumption in the problem: each element of array A is an integer within the range [1..X]. But your test case breaks it.

  16. Hi Sheng,

    You mentioned bitmap in C. I just want to make a comment here: variable length array is only allowed in C99… BTW, you can’t use C++ STL bitset either, since it also requires a const size_t to initialize the length.

    My 2cents!

    • Well. in the most “native” C, I would use an int pointer, allocate the memory when need, and manipulate it mannually as bitmap.

  17. Javascript

  18. JS solution 100%

  19. Solution using Java HashSet

  20. FrogRiverOne: Python (simple and sleek)

Leave a Reply

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