package kata;

import java.util.*;

/**
 * https://leetcode.com/problems/frog-jump/
 *
 * <p>A frog is crossing a river. The river is divided into x units and at each
 * unit there may or may not exist a stone. The frog can jump on a stone, but
 * it must not jump into the water.
 *
 * <p>Given a list of stones' positions (in units) in sorted ascending order,
 * determine if the frog is able to cross the river by landing on the last stone.
 * Initially, the frog is on the first stone and assume the first jump must be 1
 * unit.

 * <p>If the frog's last jump was k units, then its next jump must be either k -
 * 1, k, or k + 1 units. Note that the frog can only jump in the forward
 * direction.
 */
public class FrogJump {
  static boolean frogJump(int[] stones) {
    if (stones.length <= 1) {
      return true;
    }
    if (stones[0] != 0) {
      return false;
    }
    List<Set<Integer>> jumps = new ArrayList<>();
    for (int i = 0; i < stones.length; i++) {
      jumps.add(new HashSet<>());
    }
    jumps.get(0).add(0);
    jumps.get(1).add(1);
    for (int i = 1; i < stones.length - 1; i++) {
      Set<Integer> prevJumps = jumps.get(i);
      int curStone = stones[i];

      for (int j : prevJumps) {
        List<Integer> curJumps = new ArrayList<>();
        curJumps.add(j - 1);
        curJumps.add(j);
        curJumps.add(j + 1);
        
        for (int curJump : curJumps) {
          if (curJump <= 0) {
            continue;
          }
          int nextLandedStone = curStone + curJump;
          for (int k = i+1; k < stones.length; k++) {
            int nextStone = stones[k];
            if (nextStone < nextLandedStone) {
              continue;
            } else if (nextStone > nextLandedStone) {
              // stones are in increasing positiions, so we found no landed stone
              break;
            } else {
              // nextStone == nextLandedStone
              Set<Integer> nextJumps = jumps.get(k);
              nextJumps.add(curJump);
              break;
            }
          }
        }
      }
    }

    return !jumps.get(jumps.size() - 1).isEmpty();
  }

  public static void main(String args[]) {
    runSample(new int[]{0,1,3,5,6,8,12,17}); // true
    runSample(new int[]{0,1,2,3,4,8,9,11}); // false
  }

  static void runSample(int[] nums) {
    System.out.printf("%s = %s\n", Arrays.toString(nums), frogJump(nums));
  }
}

@@ -724,16 +724,692 @@
 gJump %7B%0A
+  /*%0A    // Leetcode solution%0A%09%09public class Solution %7B%0A%09%09%09%09public boolean canCross(int%5B%5D stones) %7B%0A%09%09%09%09%09%09HashMap%3CInteger, Set%3CInteger%3E%3E map = new HashMap%3C%3E();%0A%09%09%09%09%09%09for (int i = 0; i %3C stones.length; i++) %7B%0A%09%09%09%09%09%09%09%09map.put(stones%5Bi%5D, new HashSet%3CInteger%3E());%0A%09%09%09%09%09%09%7D%0A%09%09%09%09%09%09map.get(0).add(0);%0A%09%09%09%09%09%09for (int i = 0; i %3C stones.length; i++) %7B%0A%09%09%09%09%09%09%09%09for (int k : map.get(stones%5Bi%5D)) %7B%0A%09%09%09%09%09%09%09%09%09%09for (int step = k - 1; step %3C= k + 1; step++) %7B%0A%09%09%09%09%09%09%09%09%09%09%09%09if (step %3E 0 && map.containsKey(stones%5Bi%5D + step)) %7B%0A%09%09%09%09%09%09%09%09%09%09%09%09%09%09map.get(stones%5Bi%5D + step).add(step);%0A%09%09%09%09%09%09%09%09%09%09%09%09%7D%0A%09%09%09%09%09%09%09%09%09%09%7D%0A%09%09%09%09%09%09%09%09%7D%0A%09%09%09%09%09%09%7D%0A%09%09%09%09%09%09return map.get(stones%5Bstones.length - 1%5D).size() %3E 0;%0A%09%09%09%09%7D%0A%09%09%7D%0A%09*/%0A
   static
@@ -1438,24 +1438,24 @@
 %5D stones) %7B%0A
-
     if (ston
@@ -1789,53 +1789,8 @@
 ) %7B%0A
-      Set%3CInteger%3E prevJumps = jumps.get(i);%0A
     
@@ -1841,17 +1841,20 @@
 j : 
-prevJumps
+jumps.get(i)
 ) %7B%0A

Add Leetcode solution