9
\$\begingroup\$

Problem

You are given an HxW matrix. Each element is either 0 (passable space) or 1 (wall). Given that you can remove one wall, find the shortest path from [0,0] (start) to [width-1, height-1] (end).

Test cases

Inputs:

int[][] case 1 = { 
      {0, 1, 1, 0},
      {0, 0, 0, 1}, 
      {1, 1, 0, 0},
      {1, 1, 1, 0}, 
 };

Outputs:

7

Inputs:

int[][] case2 = { 
      {0, 0, 0, 0, 0, 0},
      {1, 1, 1, 1, 1, 0},
      {0, 0, 0, 0, 0, 0},
      {0, 1, 1, 1, 1, 1},
      {0, 1, 1, 1, 1, 1},
      {0, 0, 0, 0, 0, 0}, 
 }

Outputs:

11

Note, this is one of the google foobar challenges. There are quite a few algorithms out there for this problem. However, I'm trying to solve this using a variation of A*. My problem is that currently, my algorithms works like this:

  1. Get all wall locations.
  2. For each wall:
    1. Construct maze without the wall.
    2. Use A* to find the shortest path.
  3. Return the min of the found shortest paths.
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Optional;
import java.util.stream.Collectors;

class Cell {
    // Normal Cell things..
    int x,y;
    boolean isWall;

    // A* shenanigans (should probably be decoupled).
    int localScore;  // The distance from the start.
    int globalScore; // The distance from the end (heuristic).
    boolean isVisited;
    // What I tried is to include a `canRemove` boolean here to indicate whether we can still remove walls within this point.

    Cell(int x, int y, boolean isWall) {
        this.x = x;
        this.y = y;
        this.isWall = isWall;

        this.localScore = Integer.MAX_VALUE;
        this.globalScore = Integer.MAX_VALUE;
    }

    // Copy constructor.
    Cell(Cell anotherCell) {
        this.x = anotherCell.x;
        this.y = anotherCell.y;
        this.isWall = anotherCell.isWall;
        this.isVisited = anotherCell.isVisited;
        this.localScore = anotherCell.localScore;
        this.globalScore = anotherCell.globalScore;
    }
}

class Station {
    Cell[][] cells;
    List<Cell> walls;
    int height, width;

    Station(int[][] rawStation) {
        // Create Maze
        this.height = rawStation.length;
        this.width = rawStation[0].length;
        this.cells = new Cell[height][width];
        walls = new ArrayList<>();

        for(int y=0; y<height; y++){
            for(int x=0; x<width; x++){
                Cell cell = new Cell(x, y, rawStation[y][x] == 1);
                this.cells[y][x] = cell;
                if(cell.isWall) walls.add(cell);
            }
        }
    }

    Station(Station station) {
        this.height = station.height;
        this.width = station.width;
        this.cells = new Cell[height][width];
        this.walls = new ArrayList<>();

        for(int y=0; y<height; y++){
            for(int x=0; x<width; x++){
                cells[y][x] = new Cell(station.cells[y][x]);
            }
        }
    }

    Cell start() {
        return cells[0][0];
    }

    Cell end() {
        return cells[height-1][width-1];
    }

    Optional<Cell> getCell(int x, int y) {
        if(x >= 0 && x < width && y >= 0 && y < height) {
            return Optional.of(cells[y][x]);
        }
        return Optional.empty();
    }

    List<Cell> getCellNeighbours(Cell cell) {
        List<Optional<Cell>> neighbours = new ArrayList<>();

        neighbours.add(getCell(cell.x, cell.y+1)); // TOP
        neighbours.add(getCell(cell.x, cell.y-1)); // BOTTOM
        neighbours.add(getCell(cell.x-1, cell.y)); // LEFT
        neighbours.add(getCell(cell.x+1, cell.y)); // RIGHT

        return neighbours.stream()
                .filter(Optional::isPresent)
                .map(Optional::get)
                .collect(Collectors.toList());
    }
}

class BunnySaver {
    Station station;
    List<Cell> discoveredCells;
    boolean hasBomb;

    BunnySaver(Station station) {
        this.station = station;
        this.discoveredCells = new ArrayList<>();
        this.hasBomb = true;
    }

    int findShortestPath() {
        Cell current = station.start();
        current.localScore = 1;
        current.isVisited = false;
        current.globalScore = distance(current, station.end());

        discoveredCells.add(station.start());

        while(!discoveredCells.isEmpty() && current != station.end()) {
            // Get the cell that has the lowest global score - aka lowest potential
            // distance from end. Also remove it from the discovered list.
            discoveredCells = discoveredCells.stream()
                    .sorted(Comparator.comparingInt(cell -> cell.globalScore))
                    .filter(cell -> !cell.isVisited)
                    .collect(Collectors.toList());

            if(discoveredCells.isEmpty()) break;

            current = discoveredCells.remove(0);
            current.isVisited = true;

            for(Cell neighbour : station.getCellNeighbours(current)) {
                // If the neighbour is not already visited and it's not a wall,
                // mark it as discovered.
                if(neighbour.isVisited || neighbour.isWall)
                    continue;

                discoveredCells.add(neighbour);

                // If the neighbour's new localScore is lower than
                // the old one => update the cell.
                int possibleNeighbourLocalScore = current.localScore + distance(current, neighbour);
                if(neighbour.localScore > possibleNeighbourLocalScore) {
                    neighbour.localScore = possibleNeighbourLocalScore;
                    neighbour.globalScore = neighbour.localScore + distance(neighbour, station.end());
                }
            }
        }

        if (current == station.end())
            return current.localScore;

        return Integer.MAX_VALUE;
    }

    // Manhattan distance used for A*.
    int distance(Cell cell1, Cell cell2) {
        int deltaX = Math.abs(cell1.x - cell2.x);
        int deltaY = Math.abs(cell1.y - cell2.y);
        return deltaX + deltaY;
    }
}

public class Solution {

    public static int solution(int[][] map) {
        Station station = new Station(map);
        int minPath = Integer.MAX_VALUE;

        // Edge case: there are no walls.
        if(station.walls.isEmpty()) {
            BunnySaver saver = new BunnySaver(station);
            return saver.findShortestPath();
        }

        // Remove check all possible wall removals.
        for(Cell wall : station.walls) {
            Station copy = new Station(station);
            copy.cells[wall.y][wall.x].isWall = false;
            BunnySaver saver = new BunnySaver(copy);
            minPath = Math.min(minPath, saver.findShortestPath());
        }

        return minPath;
    }
}

This as you can guess is very inefficient. What would be a good way of implementing the wall logic to be within the A* algorithm? I've tried to simply add a canRemove boolean to the Cell object (which is holding the state), however, that causes backtracking issues as diverged paths can alter the same state. I need to find a way of decoupling the state away from the Cell object and ultimately the A* algo.

\$\endgroup\$
6
\$\begingroup\$

The high level approach

What would be a good way of implementing the wall logic to be within the A* algorithm? I've tried to simply add a canRemove boolean to the Cell object (which is holding the state), however, that causes backtracking issues as diverged paths can alter the same state.

The way I see it, the main issue is that you're not treating "number of bombs left" as part of the coordinate, but that is what it should be. The state space that is being explored is not just positions, it has a (small, in this case) extra dimension representing how many bombs are left. A* relies on the property that how long a path is going to be from a given coordinate depends only on the coordinate and not on how you got there, in order to make it work you need to ensure that that property is true, and you can make it true by treating the number of bombs as part of the coordinate.

It would cost an extra layer of cells to represent that dimension, but that's no big deal - if the state space was large, I would have recommended creating nodes on-demand only, but that's not the case here. Anyway, the most important part is that there are also extra neighbours possible: the bunny can make a step from a has-a-bomb-left coordinate to a spacially-adjacent no-bombs-left coordinate with a wall on it (a move which represents using the bomb to blow up that wall and then stepping onto the rubble).

I suppose that is "the trick" of this problem, hopefully explaining it didn't ruin the experience.

If a coordinate with more than just a physical position in it sounds weird to you, consider that in additional to finding a path through a maze, an other common "example use" of A* is to solve N-puzzles. In that application, an entire board-state is a coordinate in the state space (all possible board states) which is being explored. That is also an example where the nodes really have to made on-demand only, the 16-puzzle has 20922789888000 potential states that clearly cannot all get a node pre-made for them.

Data structures

// A* shenanigans (should probably be decoupled).

If there was a map on which multiple searches are done (effectively that does happen now, which I guess is why you copy the Station, but with the change of approach you would no longer need that), it's good to split the state into "state the map has" and "temporary state used by A*" (for example to absolutely positively avoid cross-contamination between searches). But in this case, what would you gain? I think it's fine to leave that as it is.

List<Cell> discoveredCells

If I'm reading your implementation of A* right, that's the Open Set. It's not a priority queue, which resulted in .sorted on a stream. That's not really a great way to do it, it's more heavy-duty than necessary. Changing the list to a PQ is not as easy as it sounds, since the cost-update step (the if in the loop over the neighbours) requires finding the position of an element within the PQ to be able to reestablish the heap property for it. Java's built-in PQ has no facility to do so.

On the other hand, the Closed Set (implemented via the isVisited field) is already implemented efficiently. A separate grid of booleans or a hash set of coordinates is also possible.

\$\endgroup\$
2
  • \$\begingroup\$ Correct me if I'm wrong, but you're basically saying that the station object should be a 3-dimensional space (x,y, and hasBomb)? - and whenever the bunny destroys a wall, we move within the 3rd dimension. That allows us to not contaminate the map within different searches (say search A reaches cell x using bomb and search B reaches cell x without bomb) \$\endgroup\$ – Mitch Nov 15 '20 at 21:15
  • \$\begingroup\$ @Mitch yes, not just for the purpose of not contaminating the map though (it's a nice bonus), the main improvement that creates is not needing to try every wall \$\endgroup\$ – harold Nov 15 '20 at 21:49
3
\$\begingroup\$

You could try creating a parent object Node that has Cell as a member and canRemove as another member. Getting neighbors might be messier but should be doable with member functions.

I need to find a way of decoupling the state away from the Cell object and ultimately the A* algo.

I don't think you want to decouple state from the algorithm, because A-star needs state to calculate the heuristic, but putting Cell in a parent object at least decouples it from canRemove.

Edit: My answer is an implementation of what harold is saying below. He explains it in more detail. Treating Cell and canRemove as different members of parent Node, is like having three dimensions in your state space: x, y, and canRemove.

\$\endgroup\$
1
\$\begingroup\$

What would be a good way of implementing the wall logic to be within the A* algorithm?

This question is outside the scope of this site, but I will answer it anyways.

A good way to solve these sort of problems is to alter the graph, rather than altering the pathfinding algorithm. Then any normal pathfinding algorithm (such as A*) can be used. We will "store" the state by having multiple copies of each node; which copy we're in determines whether or not a wall can still be removed.

Start with two identical copies of the directed graph (if the graph is undirected, you can make it directed by replacing each undirected edge with two directed edges, one in each direction). In the second graph (representing "wall cannot be removed"), add one node for each wall, with outgoing but not incoming edges for each neighbor. Then from the first graph (representing "wall can be removed"), add incoming but not edges to each wall-node for each neighbor. Make the start node in the first graph, and make sure both graphs have end-nodes.

That's it. The algorithm will search through the first copy of the graph like usual, and allow one, and only one, jump into the second graph through a wall. You only need to run A* one time.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.