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.

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

      • I for one, as a self-taught programmer, find it quite helpful to see the different language versions. Thank you for this great blog!

  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?

    • This is not a valid Java code, even for Java8. You cannot find any Java method name in JDK started with a upper case, to start with.

    • Very interesting approach. Haven’t tried in Java, although, I’ve recreated the same logic using python and it works wonders. If anyone’s curious, the python code would look like this:

      Very very elegant

  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:

    • Just a small correction, instead of “5” in the third line it should be the variable X.

      BTW superb solution. Thanks for sharing. It not only uses bitwise to come with an “equation” to solve that specific problem, which is always an interesting approach, but with that it is possible to have auxiliary space of O(1).

      That solution also shows how powerful is the internal system that deals with numbers in python. I tried that solution with java, using BigInteger(because if X passes the value of 64 not even long can represent that, because long is 64 bit), and I got a 54% in codility because of the overhead the BigInteger leaves us.

  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%

    • Another way with dictionary, 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)

  21. Here my solution in Java. It works 100% but the time complexity is O(N) or O(N * log(N))

  22. The solution of mohammad is really good and elegant. 50% shorter than the last solution in java for example. Is it python2? if you use enumerate() you can access the index of the for and don’t have to calculate the max(pos.values())
    something like:

  23. My C++ solution.

  24. Another Java solution:

    • I recommend adding one more condition, which causes no error for numbers in table A greater than X.

  25. Javascript 100% using Set

    • I think it doesn’t work if there are not enough leaves to create a path. Consider an array:
      A = [2,3,4,5,6];
      And parameters:
      solution(5, A);
      It return “4” for me, while there is no first leaf to jump on to. You only check if the Set has enough unique leaves, while the description never mentioned that those leaves will ever fall. The only time your solution returns -1 is when in the entirety of a table there are less than X unique leaves.
      Am I understanding it right?

  26. Hey folks solution in python using hash map 100%Succ

  27. my 100/100 O(N) solution

  28. Test result shows the performance is O(N ** 2). But it is one loop. Do you know why?

  29. Small suggestion. I’ve added “if v <= X:" Because you could have an input like X = 1, A = [2]

    Well I think you could have that input. From reading the explainer I'm not 100% sure

  30. Another 100/100 aproach in python:

    • Sorry guys, i tried to make the code look more pleasent before posting here, but even trying to use the same principle to solve in a more asthetic way, it doesn’t work in some cases. Therefore i’m leaving here my initial code that worked 100/100. Tks

Leave a Reply

Your email address will not be published.

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