MyPathfinder.java

package solution;

import problem.Pathfinder;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class MyPathfinder extends Pathfinder {

    @Override
    public List<Integer> findPath(List<Integer> list, int pos) {
        if (list == null || pos < 0 || pos > list.size()) {
            return null;
        }
        if (list.isEmpty()) {
            return list;
        }
        List<Integer> shortestPath = new ArrayList<>();
        LinkedList<Integer> buffer = new LinkedList<>();
        boolean[] visited = new boolean[list.size()];
        findShortestPath(list, pos, buffer, visited, shortestPath);
        return !shortestPath.isEmpty() ? shortestPath : null;
    }

    private boolean findShortestPath(List<Integer> list, int pos,
                                     LinkedList<Integer> buffer, boolean[] visited, List<Integer> shortestPath) {
        if (list == null || buffer == null || pos < 0 || pos > list.size()) {
            return false;
        }
        if (pos == list.size()) {
            return true;
        }
        Integer max = list.get(pos);
        if (max == null || visited[pos]) {
            return false;
        }
        visited[pos] = true;//mark current pos as visited to avoid cycles
        for (Integer jump : getRange(max)) {
            buffer.addLast(jump);
            pos = pos + jump;
            boolean found = findShortestPath(list, pos, buffer, visited, shortestPath);
            if (found) {
                //success path is found, store if it's shortest
                if (shortestPath.isEmpty() || shortestPath.size() > buffer.size()) {
                    shortestPath.clear();
                    shortestPath.addAll(buffer);
                }
            }
            buffer.removeLast();
            pos = pos - jump;
        }
        visited[pos] = false; //undo if path not found
        return pos == list.size();
    }

    private List<Integer> getRange(int end) {
        List<Integer> range = new ArrayList<>();
        if (end == 0) {
            return range;
        } else if (end < 0) {
            while (end < 0) {
                range.add(end);
                end++;
            }
        } else {
            while (end > 0) {
                range.add(end);
                end--;
            }
        }
        return range;
    }
}