Qfyilyi

I have task to find the simplest way to the point of destination.

I found all paths and stored in vector for example:

1. R R R R P P L L P P   

2. R R R R P P R R R R P P L L L L L L   

3. R R R R P P R R R R P P P P L L L L L L P P   

Where R - right, L - left, P - straight.

And in addition, I have the priority of following the path:

rightHanded: straight, right, left   

leftHanded: straight, left, right   

Following the path by priority I want to get to the end.

e.g. using the above example of paths for rightHanded

R -> R -> R -> R -> P -> P -> (1)R -> R -> R -> R -> P -> P -> (2) P -> end I find the shortest path

ad.1 I see that best is 2 and 3 because I have R

ad.2 I again chose R instead L and I have the last path left and its the simplest

I don't know how write that program.

Tested for cases like duplicate paths, a path having another path as a sub-path in the beginning, etc.

public static void main(String args) {

    Map<Integer, List<Character>> paths = new LinkedHashMap<>();

    paths.put(1, Arrays.asList('R', 'R', 'R', 'R', 'P', 'P', 'L', 'L', 'P', 'P'));

    paths.put(2, Arrays.asList('R', 'R', 'R', 'R', 'P', 'P', 'R', 'R', 'R', 'R', 'P', 'P', 'L', 'L', 'L', 'L', 'L', 'L'));

    paths.put(3, Arrays.asList('R', 'R', 'R', 'R', 'P', 'P', 'R', 'R', 'R', 'R', 'P', 'P', 'P', 'P', 'L', 'L', 'L', 'L', 'L', 'L', 'P', 'P'));



    System.out.println("Path " + bestPath(paths, DrivingDirection.RIGHT_HANDED) + " is the best for " + DrivingDirection.RIGHT_HANDED);

    System.out.println("Path " + bestPath(paths, DrivingDirection.LEFT_HANDED) + " is the best for " + DrivingDirection.LEFT_HANDED);

}



private static List<Character> getTurnPreferences(DrivingDirection drivingDirection) {

    return drivingDirection == DrivingDirection.RIGHT_HANDED

            ? Arrays.asList('P', 'R', 'L')

            : Arrays.asList('P', 'L', 'R');

}



private enum DrivingDirection {

    RIGHT_HANDED,

    LEFT_HANDED

}



private static int bestPath(Map<Integer, List<Character>> paths, DrivingDirection drivingDirection) {

    List<Character> turnPreference = getTurnPreferences(drivingDirection);

    final AtomicInteger i = new AtomicInteger(0);

    while (paths.size() > 1) {

        Map<Integer, List<Character>> tempMap = eliminateUnpreferredPaths(paths, turnPreference, i);

        if (tempMap.size() == 0) return getShortestPath(paths).getKey(); // when all paths are bad

        i.incrementAndGet();

        Optional<Map.Entry<Integer, List<Character>>> pathWithNoMoreDirections = getPathWithNoMoreDirectionsLeft(i, tempMap);

        if (pathWithNoMoreDirections.isPresent()) return pathWithNoMoreDirections.get().getKey();

        paths = tempMap;

    }

    return paths.keySet().iterator().next();

}



private static Optional<Map.Entry<Integer, List<Character>>> getPathWithNoMoreDirectionsLeft(

        AtomicInteger i, Map<Integer, List<Character>> tempMap) {

    return tempMap.entrySet().stream()

            .filter(e -> e.getValue().size() == i.get())

            .findFirst();

}



private static Map.Entry<Integer, List<Character>> getShortestPath(Map<Integer, List<Character>> paths) {

    return paths.entrySet().stream().min(Comparator.comparingInt(e -> e.getValue().size())).get();

}



private static Map<Integer, List<Character>> eliminateUnpreferredPaths(

        Map<Integer, List<Character>> paths, List<Character> turnPreference, AtomicInteger i) {

    Map<Integer, List<Character>> tempMap = null;

    for (int j = 0; j < turnPreference.size(); j++) {

        final int finalJ = j;

        tempMap = paths.entrySet()

                .stream()

                .filter(e -> e.getValue().size() > i.get() && e.getValue().get(i.get()).equals(turnPreference.get(finalJ)))

                .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));

        if (tempMap.size() > 0) break;

    }

    return tempMap;

}

Output

Path 3 is the best for RIGHT_HANDED

Path 1 is the best for LEFT_HANDED