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.
[cc lang="java" escaped="true"] package com.codility.lesson04.countingelements; 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; } } [/cc]
TestNG test cases for this problem which all passed:
[cc lang="java" escaped="true"] package test.com.codility.lesson04.countingelements; 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); } } [/cc]