Java solution to Codility FrogRiverOne problem (Lesson 4 – Counting Elements) which scored 100%. The problem is to find the earliest time when a frog can jump to the other side of a river. The main strategy is to use java.util.Set to store all required integers for a full jump and a second java.util.Set to keep storing current leaves and to keep checking if the first set fully exists in the second set.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.HashSet;
import java.util.Set;
public class FrogRiverOne {
public int solution(int X, int[] A) {
SetrequiredLeavesSet = new HashSet();
for(int i=1; i<=X; i++) {
requiredLeavesSet.add(i);
}
SetcurrentLeavesSet = new HashSet();
for(int p=0; p<A.length; p++) {
currentLeavesSet.add(A[p]);
//keep adding to current leaves set until it's at least the same size as required leaves set
if(currentLeavesSet.size() < requiredLeavesSet.size()) continue;
if(currentLeavesSet.containsAll(requiredLeavesSet)) {
return p;
}
}
return -1;
}
}
TestNG test cases for this problem which all passed:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import org.testng.Assert;
import org.testng.annotations.*;
import com.codility.lesson04.countingelements.FrogRiverOne;
public class FrogRiverOneTests {
private FrogRiverOne solution;
@BeforeTest
public void setUp() {
solution = new FrogRiverOne();
}
@DataProvider(name = "test1")
public Object [][] createData1() {
return new Object [][] {
new Object [] { 5, new int [] { 1, 3, 1, 4, 2, 3, 5, 4 }, 6 },
new Object [] { 3, new int [] { 1, 3 }, -1 }, //never gets across
new Object [] { 2, new int [] { 1, 1, 1, 1 }, -1 }, //never gets across
new Object [] { 3, new int [] { 1, 4, 2, 3 }, 3 },
new Object [] { 2, new int [] { 1, 4, 2, 3 }, 2 },
new Object [] { 4, new int [] { 1, 2, 3, 2, 3, 3, 1, 2, 2, 4, 2, 1 }, 9 },
new Object [] { 4, new int [] { 1, 2, 3, 2, 3, 3, 1, 2, 4, 4, 2, 1 }, 8 },
new Object [] { 4, new int [] { 1, 2, 3, 4, 3, 3, 1, 2, 4, 4, 2, 1 }, 3 },
};
}
@Test(dataProvider = "test1")
public void verifySolution(int pX, int [] pA, int pExpected) {
Assert.assertEquals(solution.solution(pX, pA), pExpected);
}
}