Codility - FrogRiverOne (Find the earliest time when a frog can jump to the other side of a river)

This is the fourth lesson in Codility. You need to find the fastest (earliest) time possible for a frog to start jumping towards the other side of the river. You will be given an array that reflecting the position of jumping/landing point for the frog. 

The frog will start to jump when all landing point is in the right position. Two input is given; X as the final jumping position and Y array of integer. For each element in the array, every index is considered as seconds. You need to arrange the number in the array and trigger when all are in sequence with X as the last element.

---

It took me another 1 full day and many try-n-error to get it perfect 100%

In the beginning, I’m using 2 Array of Integer as shown below. There are few test cases that failed because the time taken to process is more than the limit given.

100% accuracy but the overall score is 18%

With an improvement in the code, I managed to improve the overall score to 54%. I managed to reduce some of the performance issues.

100% accuracy but overall score is 54%

It looks like Array.copyOf and Arrays.stream do take a longer time to process.

Another improvement has lessened the length of the code and improve the overall score to 63%

63% overall score

The code above simply set the C array to value one of the position indexes of A. Here are the list of test that it fails

▶medium_range
 arithmetic sequences, X = 5,000✘TIMEOUT ERROR
 running time: 0.112 sec., time limit: 0.100 sec.
 1.0.112 sTIMEOUT ERROR, running time: 0.112 sec., time limit: 0.100 sec.
 ▶large_random
 10 and 100 random permutation, X = ~10,000✘TIMEOUT ERROR
 running time: 1.128 sec., time limit: 0.880 sec.
 1.1.128 sTIMEOUT ERROR, running time: 1.128 sec., time limit: 0.880 sec.
 2.0.200 sOK
 ▶large_permutation
 permutation tests✘TIMEOUT ERROR
 running time: 1.716 sec., time limit: 0.880 sec.
 1.1.716 sTIMEOUT ERROR, running time: 1.716 sec., time limit: 0.880 sec.
 2.6.000 sTIMEOUT ERROR, Killed. Hard limit reached: 6.000 sec.
 ▶large_range
 arithmetic sequences, X = 30,000✘TIMEOUT ERROR
 Killed. Hard limit reached: 6.000 sec.
 1.6.000 sTIMEOUT ERROR, Killed. Hard limit reached: 6.000 sec.

I changed my strategy. Instead of using a normal Array of integer, I implement List & ArrayList.

Bad improvement - 54% overall

Instead of getting better, it is getting worse. I google on it and found that List do have performance issues and found few suggestions on it. Either use Hashmap, HashSet, TreeSet or GapList. 

I tried the GapList first (see some explanation here https://dzone.com/articles/gaplist-lightning-fast-list and https://github.com/GabrielRStella/Utility/blob/master/src/org/magicwerk/brownies/collections/GapList.java)

I do improve the process on my laptop and surprisingly, it was way faster than List or ArrayList. Unfortunately, Codility does not support the library. Hence, I need to look for another alternative.

Based on the performance comparison between Hashmap, HashSet, and TreeSet, HashSet seems promising. And so it did. My final code is using HashSet and finally, the result shown is 100%. Here is part of the code:

1. Definition

HashSet list= new HashSet();

2. Used

           for(int idx = 0; idx < A.length; idx++){

         if ( !list.contains(A[idx]) ){

            list.add(A[idx]);

         }

         if ( list.size() == X ){

            return idx;

         }

      }

I also found a few solutions which score 100%

    This solution was shared by someone and it claims score 100/100

    public int solution(int X, int[] A) {

        int[] B = A.Distinct().ToArray();

        return (B.Length != X) ? -1 : Array.IndexOf(A, B[B.Length - 1]);

    }

    

    This solution was shared too and score 100/100 for correctness, task, and performance

    public int solution(int X, int[] A) {

        HashSet unique= new HashSet();

        for (int i = 1; i<= X; i++){

            unique.add(i);

        }

        for(int j = 0; j< A.length; j++){

            if(unique.contains(A[j])){

                unique.remove(A[j]);

                   if(unique.isEmpty()){

                         return j;

                    }

            }

        }

        return -1;

    }

Full source code is accessible at

1. Bitbucket — git clone https://masteramuk@bitbucket.org/fullstacksdev/codility-frogriverone.git
2. Github — git clone https://github.com/masteramuk/codility-lessoncode.git