How to order list by nearest value

Question

So i have this small list as follows which represents warehouse locations:

30 09 05
30 04 05
30 02 01 
31 07 05 
31 07 04 
31 03 05 
31 03 06 
31 09 05 
31 02 05 

The first column represents the location row, the second location height and the third the location position (forward)

I need to calculate the optimal path (row, position, height) for a forklift operator to retrieve different items based on different locations

For this I am using Collection.sort to sort the list first by rows then position (forward) and lastly by height.

The rows are grouped by pairs because it makes sense for the operator to retrieve items from the even row (operator left) and odd row (operator right) without moving the fork lift position and height

I am almost there i just need a hand for when the pos moves forward i need to keep the same height and get the nearest height instead of starting at the bottom which makes the operator lose time going up and down

Here is the code:

Collections.sort(unoptimizedLocations, new Comparator<ItemOrderLocation>() {
    @Override
    public int compare(ItemOrderLocation item1, ItemOrderLocation item2) {

        int rowCmp = item1.row.compareTo(item2.row);
        int heightCmp = item1.height.compareTo(item2.height);
        int posCmp = item1.pos.compareTo(item2.pos);

        int item1Row = Integer.parseInt(item1.row);
        int item2Row = Integer.parseInt(item2.row);

        boolean onForkLiftPath = false;

        if (item1Row == (item2Row + 1) && (item2Row % 2 == 0)) {
            onForkLiftPath = true;
        }

        if (!onForkLiftPath && rowCmp != 0) {
            //Two differents rows which are not on Fork Lift Path
            return rowCmp;
        }

        //If are on forklift path we compare the position
        if (posCmp != 0) {
            return posCmp;
        }

        //Lastly if row is on forklift path and we are on same position we need to sort by nearest height
        return heightCmp;
    }
});

With this code the list gets ordered like this:

30 02 01 
31 07 04 
31 02 05 
31 03 05 
30 04 05 
31 07 05 
30 09 05 
31 09 05 
31 03 06

And for better understanding the final sorted list (nearest height for less height traveling) should look like this:

30 02 01 
31 07 04
31 07 05 
30 09 05
31 09 05 
30 04 05
31 03 05    
31 02 05
31 03 06 

Any ideas how can reach this result using my sorting algorithm?

Answer 1

The following solves the fork lift problem, given the constraints.

ALGORITHM
Input:  All locations
Output:  Shortest path given constraints
1.  For all row/pairs, in increasing order
2.  For all positions in that row, in increasing order
3.  For all heights with same row/pair and position, add locations to minimize the height change given a starting height

The code uses Java 8 streams. The code attempts to have single purpose methods; so feel free to rewrite any method in a more familiar syntax. It is not guaranteed to be optimized, but given the low size of the input, that should not be a concern. Let me know if you have any questions.

And the code:

public class ForkLiftOperator {

public static void main(String[] args) {
    new ForkLiftOperator().start();
}

private void start() {

    List<Location> locations = new ArrayList<Location>();
    locations.add(new Location(30, 9, 5));
    locations.add(new Location(30, 4, 5));
    locations.add(new Location(30, 2, 1));
    locations.add(new Location(31, 7, 5));
    locations.add(new Location(31, 7, 4));
    locations.add(new Location(31, 3, 5));
    locations.add(new Location(31, 3, 6));
    locations.add(new Location(31, 9, 5));
    locations.add(new Location(31, 2, 5));
    locations.add(new Location(32, 2, 5));  // Extra to simulate additional row/pair

    List<Location> solution = solve(locations);
    System.out.println(solution);
}


private List<Location> solve(List<Location> locations) {

    List<Location> shortestPath = new ArrayList<Location>();
    int activeRow, activePosition, activeHeight;
    while ((activeRow = getNextRow(locations)) != 0) {
        System.out.println("Working on row="+activeRow);
        List<Location> activeLocations = getLocationsByRowPair(activeRow, locations);
        activePosition = 0;
        activeHeight = 0;
        while ((activePosition = getNextPos(activePosition, activeLocations)) != 0) {
            System.out.println("Working on pos="+activePosition);
            List<Location> activePositionLocations = getLocationsForRowAndPosition(activeRow, activePosition, activeLocations);
            shortestPath.addAll(minimizeHeight(activeHeight, activePositionLocations));
            activeHeight = shortestPath.get(shortestPath.size()-1).height;
        }
    }


    return shortestPath;
}

enum Direction { UP, DOWN }
/**
 * For the given locations (which are guaranteed to be at the same row/position), minimize the total height change
 * @param activePositionLocations The locations at this row/pair and location (they will only differ in height)
 * @return The order will minimize the height change
 */
private List<Location> minimizeHeight(int currentHeight, List<Location> activePositionLocations) {
    List<Location> optimizedHeightLocations = new ArrayList<Location>();
    System.out.println("Processing locations="+activePositionLocations);
    int minHeight = activePositionLocations.stream().mapToInt(location -> location.height).min().getAsInt();
    int maxHeight = activePositionLocations.stream().mapToInt(location -> location.height).max().getAsInt();
    /*
     * There are only two options to minimize (if the current height falls between min and max):
     * 1)  Travel down then up
     * 2)  Travel up then down
     */
    // First determine the first direction to go
    Direction direction;
    if (currentHeight == minHeight)
        direction = Direction.UP;
    else if (currentHeight == maxHeight)
        direction = Direction.DOWN;
    else {
        int distanceUp = maxHeight-currentHeight;
        int distanceDown = currentHeight-minHeight;
        direction = distanceUp < distanceDown ? Direction.UP : Direction.DOWN;
    }
    // Now travel in that direction (must sort the correct way first
    List<Location> sortedAscending = activePositionLocations.stream().sorted((l1, l2) -> Integer.compare(l1.height, l2.height)).collect(Collectors.toList());
    List<Location> sortedDescending = activePositionLocations.stream().sorted((l1, l2) -> Integer.compare(l2.height, l1.height)).collect(Collectors.toList());
    if (direction == Direction.UP) {
        optimizedHeightLocations.addAll(sortedAscending.stream().filter(location -> location.height >= currentHeight).collect(Collectors.toList()));
        optimizedHeightLocations.addAll(sortedDescending.stream().filter(location -> location.height < currentHeight).collect(Collectors.toList()));
    } else {    // Direction = DOWN
        optimizedHeightLocations.addAll(sortedDescending.stream().filter(location -> location.height <= currentHeight).collect(Collectors.toList()));
        optimizedHeightLocations.addAll(sortedAscending.stream().filter(location -> location.height > currentHeight).collect(Collectors.toList()));
    }

    return optimizedHeightLocations;
}

/**
 * Determine all the locations for this current row/pair and position
 * @param activeRow The current row/pair
 * @param activePos The current position
 * @param locations The locations for this row/pair
 * @return The locations at this exact row/pair and position
 */
private List<Location> getLocationsForRowAndPosition(int activeRow, int activePos,
        List<Location> locations) {
    int minRow = activeRow;
    int maxRow = ((activeRow & 1) == 0) ? activeRow + 1 : activeRow;    // If even, then pair includes the next higher row
    return locations.stream().filter(location -> location.row >= minRow && location.row <= maxRow && location.position == activePos)
            .collect(Collectors.toList());
}

/**
 * Determine the next position, given the current position
 * @param currentPosition Where the operator is currently
 * @param locations The locations for this row/pair
 * @return The next closest, or zero if they are at the end
 */
private int getNextPos(int currentPosition, List<Location> locations) {
    if (locations.isEmpty())
        return 0;
    OptionalInt min = locations.stream().filter(location -> location.position > currentPosition)
            .mapToInt(location -> location.position)
            .min(); 
    return min.isPresent() ? min.getAsInt() : 0;
}

/**
 * Filter out any locations for this row pair.
 * The locations for this row will be removed from the original list
 * @param nextRow The current row being processed
 * @param locations The remaining locations
 * @return The locations for the active row
 */
private List<Location> getLocationsByRowPair(int nextRow, List<Location> locations) {
    List<Location> activeLocations = new ArrayList<Location>();
    Iterator<Location> i = locations.iterator();
    int minRow = nextRow;
    int maxRow = ((nextRow & 1) == 0) ? nextRow + 1 : nextRow;  // If even, then pair includes the next higher row
    while (i.hasNext()) {
        Location current = i.next();
        if (current.row >= minRow && current.row <= maxRow) {
            activeLocations.add(current);
            i.remove();
        }
    }
    return activeLocations;
}

/**
 * Determine the lowest row from the locations provided
 * @param locations All remaining locations
 * @return The minimum row number remaining
 */
private int getNextRow(List<Location> locations) {
    if (locations.isEmpty())
        return 0;
    return locations.stream().mapToInt(location -> location.row)
            .min().getAsInt();
}

class Location {
    final int row;
    final int position;
    final int height;
    public Location(int row, int height, int position) {
        this.row = row;
        this.position = position;
        this.height = height;
    }
    @Override
    public String toString() {
        return "[" + row + ", " + height + ", " + position + "]";
    }

}

}

Produces the following output, which matches the desired output:

[[30, 2, 1], [31, 7, 4], [31, 7, 5], [30, 9, 5], [31, 9, 5], [30, 4, 5], [31, 3, 5], [31, 2, 5], [31, 3, 6], [32, 2, 5]]

Here are the Java7 versions of the current Java8 code:

Java8:

private List<Location> getLocationsForRowAndPosition(int activeRow, int activePos,
        List<Location> locations) {
    int minRow = activeRow;
    int maxRow = ((activeRow & 1) == 0) ? activeRow + 1 : activeRow;    // If even, then pair includes the next higher row
    return locations.stream().filter(location -> location.row >= minRow && location.row <= maxRow && location.position == activePos)
            .collect(Collectors.toList());
}

Java 7:

private List<Location> getLocationsForRowAndPosition(int activeRow, int activePos,
        List<Location> locations) {
    int minRow = activeRow;
    int maxRow = ((activeRow & 1) == 0) ? activeRow + 1 : activeRow;    // If even, then pair includes the next higher row
    List<Location> positionLocations = new ArrayList<Location>();
    for (Location location : locations) {
        if (location.row >= minRow && location.row <= maxRow && location.position == activePos)
            positionLocations.add(location);
    }
    return positionLocations;
}

Java 8:

private int getNextPos(int currentPosition, List<Location> locations) {
    if (locations.isEmpty())
        return 0;
    OptionalInt min = locations.stream().filter(location -> location.position > currentPosition)
            .mapToInt(location -> location.position)
            .min(); 
    return min.isPresent() ? min.getAsInt() : 0;
}

Java 7:

private int getNextPos(int currentPosition, List<Location> locations) {
    if (locations.isEmpty())
        return 0;
    int minValue = Integer.MAX_VALUE;
    for (Location location : locations) {
        if (location.position > currentPosition && location.position < minValue)
            minValue = location.position;
    }
    return minValue == Integer.MAX_VALUE ? 0 : minValue;
}

Java 8:

private int getNextRow(List<Location> locations) {
    if (locations.isEmpty())
        return 0;
    return locations.stream().mapToInt(location -> location.row)
            .min().getAsInt();
}

Java 7:

private int getNextRow(List<Location> locations) {
    if (locations.isEmpty())
        return 0;
    int minValue = Integer.MAX_VALUE;
    for (Location location : locations) {
        if (location.row < minValue)
            minValue = location.row;
    }
    return minValue;
}

And last the Java 7 for minimizeHeight:

private List<Location> minimizeHeight(int currentHeight, List<Location> activePositionLocations) {
    List<Location> optimizedHeightLocations = new ArrayList<Location>();

    int minHeight = Integer.MAX_VALUE;
    int maxHeight = Integer.MIN_VALUE;
    for (Location location : activePositionLocations) {
        if (location.height < minHeight)
            minHeight = location.height;
        if (location.height > maxHeight)
            maxHeight = location.height;
    }

    /*
     * There are only two options to minimize (if the current height falls between min and max):
     * 1)  Travel down then up
     * 2)  Travel up then down
     */
    // First determine the first direction to go
    Direction direction;
    if (currentHeight == minHeight)
        direction = Direction.UP;
    else if (currentHeight == maxHeight)
        direction = Direction.DOWN;
    else {
        int distanceUp = maxHeight-currentHeight;
        int distanceDown = currentHeight-minHeight;
        direction = distanceUp < distanceDown ? Direction.UP : Direction.DOWN;
    }
    // Now travel in that direction (must sort the correct way first
    List<Location> sortedAscending = new ArrayList<Location>(activePositionLocations);  // Clone it
    Collections.sort(sortedAscending, new Comparator<Location>() {
        @Override
        public int compare(Location l1, Location l2) {
            return Integer.compare(l1.height, l2.height);
        }
    });
    List<Location> sortedDescending = new ArrayList<Location>(activePositionLocations); // Clone it
    Collections.sort(sortedDescending, new Comparator<Location>() {
        @Override
        public int compare(Location l1, Location l2) {
            return Integer.compare(l2.height, l1.height);
        }
    });

    if (direction == Direction.UP) {
        for (Location location : sortedAscending) {
            if (location.height >= currentHeight)
                optimizedHeightLocations.add(location);
        }
        for (Location location : sortedDescending) {
            if (location.height < currentHeight)
                optimizedHeightLocations.add(location);
        }
    } else {    // Direction = DOWN
        for (Location location : sortedDescending) {
            if (location.height <= currentHeight)
                optimizedHeightLocations.add(location);
        }
        for (Location location : sortedAscending) {
            if (location.height > currentHeight)
                optimizedHeightLocations.add(location);
        }
    }

    return optimizedHeightLocations;
}