FrogRiverOne – Codility – Solution

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]