Path Finder #2: shortest path

public class Finder {
    private final static int INF = Integer.MAX_VALUE;
    private static int[][] graph;

    public static int pathFinder(String maze) {
        initGraph(maze);
        goTo(0, 0, 0);
        return (graph[graph.length - 1][graph.length - 1] == INF) ? -1 : graph[graph.length - 1][graph.length - 1];
    }

    private static void initGraph(String maze){
        String[] lines = maze.split("\n");
        graph = new int[lines.length][lines.length];
        for(int i=0; i<lines.length; i++)
            for(int j=0; j<lines.length; j++)
                graph[i][j] = (lines[i].charAt(j)=='W')?-1:INF;
    }

    private static void goTo(int i, int j, int step){
        if(i==-1 || i==graph.length || j==-1 || j==graph.length || graph[i][j] <= step)
            return;
        graph[i][j] = step;
        goTo(i, j-1, step+1);
        goTo(i, j+1, step+1);
        goTo(i+1, j, step+1);
        goTo(i-1, j, step+1);
    }
}

import java.util.*;
import java.util.stream.*;
import java.awt.Point;

public class Finder {

    final static private Point[] MOVES = {new Point(0,1), new Point(1,0), new Point(-1,0), new Point(0,-1)};

    public static int pathFinder(String maze) {
        
        char[][]    board = Stream.of(maze.split("\n")).map(String::toCharArray).toArray(char[][]::new);
        List<Point> bag   = Arrays.asList(new Point(0,0));
        int         step  = 0,
                    S     = board.length;
        Point       end   = new Point(S-1,S-1);
        
        board[0][0] = 'W';
        while (!bag.isEmpty() && !bag.contains(end)) {
            step++;
            bag = bag.stream().flatMap( p -> Stream.of(MOVES).map( m -> new Point(p.x+m.x, p.y+m.y) ))
                              .distinct()
                              .filter(  p -> 0<=p.x && p.x<S && 0<=p.y && p.y<S && board[p.x][p.y]=='.' )
                              .peek(    p -> board[p.x][p.y] = 'W' )
                              .collect(Collectors.toList());
        }
        return bag.contains(end) ? step : -1;
    }
}

import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Objects;

/**
 * @author Jonathan Bradley Whited (@esotericpig)
 */
public class Finder {
  public static int pathFinder(String mazeStr) {
    Maze maze = new Maze(mazeStr);
    Glader glader = new Glader();
    
    int result = glader.run(maze);
    
    // Uncomment for fun
    //glader.printPath(maze);
    //System.out.println("Path:   " + glader);
    //System.out.println("Result: " + result);
    
    return result;
  }
}

// Do you like Maze Runner?
class Glader {
  private LinkedList<Step> path = new LinkedList<>();
  private int x,y,goalX,goalY;
  
  public int run(Maze maze) {
    return run(maze,0,0,maze.getWidth() - 1,maze.getHeight() - 1);
  }
  
  // A* algorithm
  // http://www.growingwiththeweb.com/2012/06/a-pathfinding-algorithm.html
  public int run(Maze maze,int x,int y,int goalX,int goalY) {
    path.clear();
    this.x = x; this.y = y;
    this.goalX = goalX; this.goalY = goalY;
    
    LinkedList<Pos> open = new LinkedList<>();
    LinkedList<Pos> closed = new LinkedList<>();
    
    open.addLast(new Pos(x,y,goalX,goalY));
    
    Pos goalPos = null;
    
    while(!open.isEmpty()) {
      Pos pos = open.removeLast();
      
      // Goal!
      if(pos.getX() == goalX && pos.getY() == goalY) {
        // Don't break to guarantee shortest path
        if(goalPos == null) {
          goalPos = pos;
        } else {
          if(pos.getSteps() < goalPos.getSteps()) {
            goalPos = pos;
          }
        }
      }
      
      closed.addLast(pos);
      
      // Process neighbors
      for(Step s: Step.values()) {
        Pos neighbor = s.takeStep(pos.getX(),pos.getY());
        
        // Not a wall?
        if(maze.isEmpty(neighbor.getX(),neighbor.getY())) {
          // Skip if in closed
          if(!closed.contains(neighbor)) {
            // Calc necessary stuff
            neighbor.setParent(pos);
            neighbor.setSteps(pos.getSteps() + 1);
            neighbor.updateDistance(goalX,goalY);
            
            // Find in open
            Pos neighborInOpen = null;
            for(Pos p: open) {
              if(p.equals(neighbor)) {
                neighborInOpen = p;
                break;
              }
            }
            
            // Not in open?
            if(neighborInOpen == null) {
              boolean isAdded = false;
              
              // Put in open, sorted by min cost last
              for(ListIterator<Pos> li = open.listIterator(); li.hasNext();) {
                // Don't use cost to guarantee shortest path
                //if(neighbor.getCost() > li.next().getCost()) {
                if(neighbor.getSteps() > li.next().getSteps()) {
                  li.previous();
                  li.add(neighbor);
                  isAdded = true;
                  break;
                }
              }
              
              if(!isAdded) { open.addLast(neighbor); }
            } else {
              // Update the neighbor in open
              if(neighbor.getSteps() < neighborInOpen.getSteps()) {
                neighborInOpen.setParent(neighbor.getParent());
                neighborInOpen.setSteps(neighbor.getSteps());
              }
            }
          }
        }
      }
    }
    
    if(goalPos != null) {
      for(Pos p = goalPos.getParent(); p != null; p = p.getParent()) {
        if(p.getStep() != null) { path.addFirst(p.getStep()); }
      }
    }
    
    return (goalPos != null) ? goalPos.getSteps() : -1;
  }
  
  // Use this to watch a Glader run for fun
  public void printPath(Maze maze) {
    maze = maze.clone();
    int x = this.x,y = this.y;
    
    System.out.println(maze.toString(x,y));
    
    for(Step s: path) {
      int lookX = s.takeStepX(x);
      int lookY = s.takeStepY(y);
      
      if(maze.isEmpty(lookX,lookY)) {
        maze.setSpace(x,y,'o'); // Just a little o.g.
        x = lookX; y = lookY;
        
        System.out.println("Step: " + s);
        System.out.println(maze.toString(x,y));
        
        if(x == goalX && y == goalY) { break; }
      }
    }
  }
  public String toString() {
    StringBuilder sb = new StringBuilder(path.size());
    for(Step s: path) { sb.append(s.toString().charAt(0)); }
    return sb.toString();
  }
}

class Maze implements Cloneable {
  public static final char EMPTY = '.';
  public static final char WALL  = 'W';
  
  private char[][] maze;
  private int width,height;
  
  public Maze(Maze maze) {
    width = maze.width;
    height = maze.height;
    
    // Should be NxN
    this.maze = new char[maze.maze.length][maze.maze.length];
    for(int y = 0; y < this.maze.length; ++y) {
      for(int x = 0; x < this.maze.length; ++x) {
        this.maze[x][y] = maze.maze[x][y];
      }
    }
  }
  
  public Maze(String mazeStr) {
    String[] rows = mazeStr.split("\n");
    width = rows.length; // Should be NxN
    height = rows.length;
    maze = new char[width + 2][height + 2]; // +2 for outer walls
    
    for(int y = 0; y < height; ++y) {
      for(int x = 0; x < width; ++x) {
        setSpace(x,y,Character.toUpperCase(rows[y].charAt(x)));
      }
    }
    // Top & Bottom outer walls
    for(int x = 0; x < maze.length; ++x) {
      maze[x][0] = WALL; maze[x][maze.length - 1] = WALL;
    }
    // Left & Right outer walls
    for(int y = 0; y < maze.length; ++y) {
      maze[0][y] = WALL; maze[maze.length - 1][y] = WALL;
    }
  }
  
  public Maze clone() { return new Maze(this); }
  
  public void setWall(int x,int y) { setSpace(x,y,WALL); }
  public void setSpace(int x,int y,char c) { maze[x + 1][y + 1] = c; }
  public int getSpace(int x,int y) { return maze[x + 1][y + 1]; }
  
  public boolean isEmpty(int x,int y) { return getSpace(x,y) == EMPTY; }
  public boolean isWall(int x,int y) { return getSpace(x,y) == WALL; }
  
  public int getWidth() { return width; }
  public int getHeight() { return height; }
  public int getSize() { return width * height; }
  
  public String toString() { return toString(0,0); }
  public String toString(int gladerX,int gladerY) {
    // *2/+1 for spaces/newlines
    StringBuilder sb = new StringBuilder((width * 2 + 1) * height);
    
    for(int y = 0; y < height; ++y) {
      for(int x = 0; x < width; ++x) {
        if(x == gladerX && y == gladerY) {
          sb.append('g');
        } else {
          sb.append((char)getSpace(x,y));
        }
        sb.append(' '); // Prettier
      }
      sb.append('\n');
    }
    return sb.toString();
  }
}

class Pos {
  private int distance = 0;
  private Pos parent = null;
  private Step step = null;
  private int steps = 0;
  private int x = 0,y = 0;
  
  public Pos(int x,int y) { this(x,y,null); }
  public Pos(int x,int y,int goalX,int goalY) {
    this(x,y);
    updateDistance(goalX,goalY);
  }
  public Pos(int x,int y,Step step) {
    this.step = step;
    this.x = x; this.y = y;
  }
  
  public Pos updateDistance(int goalX,int goalY) {
    this.distance = Math.abs(x - goalX) + Math.abs(y - goalY);
    return this;
  }
  
  public void setParent(Pos parent) { this.parent = parent; }
  public void setSteps(int steps) { this.steps = steps; }
  
  public int getCost() { return distance + steps; }
  public int getDistance() { return distance; }
  public Pos getParent() { return parent; }
  public Step getStep() { return step; }
  public int getSteps() { return steps; }
  public int getX() { return x; }
  public int getY() { return y; }
  
  public boolean equals(Object o) {
    if(o == null || !(o instanceof Pos)) {
      return false;
    }
    Pos p = (Pos)o;
    return (this == p) || (x == p.x && y == p.y);
  }
  public int hashCode() { return Objects.hash(x,y); }
}

enum Step {
  NORTH(0,-1),SOUTH(0,1),EAST(1,0),WEST(-1,0);
  
  private int stepX,stepY;
  
  private Step(int stepX,int stepY) {
    this.stepX = stepX;
    this.stepY = stepY;
  }
  
  public Pos takeStep(int x,int y) {
    return new Pos(takeStepX(x),takeStepY(y),this);
  }
  public int takeStepX(int x) { return x + stepX; }
  public int takeStepY(int y) { return y + stepY; }
  
  public int getStepX() { return stepX; }
  public int getStepY() { return stepY; }
}

import java.util.Queue;
import java.util.LinkedList;
public class Finder {
  public static int pathFinder(String maze) {
    String[] rows = maze.split("\n");
    Character[][] cmaze = new Character[rows.length + 2][rows.length + 2];
    boolean[][] isVisited = new boolean[rows.length + 2][rows.length + 2];
    int cmazeLen = cmaze.length;
    for (int i = 0; i < cmaze.length; i++) {
      cmaze[0][i] = 'W';
      cmaze[cmazeLen - 1][i] = 'W';
      cmaze[i][0] = 'W';
      cmaze[i][cmazeLen - 1] = 'W';
    }
    for (int i = 0; i < rows.length; i++) {
      for (int j = 0; j < rows.length; j++) {
        cmaze[i+1][j+1] = new Character(rows[i].charAt(j));
      }
    }
    Queue<int[]> queue = new LinkedList<int[]>(); 
    queue.add(new int[] {1, 1, 0});
    isVisited[1][1] = true;
    while(!queue.isEmpty()) {
      int[] cp = queue.remove();
      int x = cp[0];
      int y = cp[1];
      int d = cp[2];
      if (x == rows.length && y == rows.length) {
        return d;
      }
      addQueueS(cmaze, isVisited, queue, x - 1, y, d + 1);
      addQueueS(cmaze, isVisited, queue, x + 1, y, d + 1);
      addQueueS(cmaze, isVisited, queue, x , y - 1, d + 1);
      addQueueS(cmaze, isVisited, queue, x , y + 1, d + 1);
    }
    return -1;
       
  }

  private static void addQueueS(Character[][] cmaze, boolean[][] isVisited, Queue<int[]> queue, int x,
      int y, int d) {
    if (!isVisited[x][y] && cmaze[x][y] == '.') {
        queue.add(new int[] {x, y, d});
        isVisited[x][y] = true;
    }
  }
}

import java.util.*;
public class Finder {

    static boolean isSafe(int r, int c, char[][] chart, Set<String> extlist) {
        int n = chart.length;
        return 0 <= r && r < n && 0 <= c && c < n && !extlist.contains(r+":"+c) && chart[r] != 'W';
    }
    public static int pathFinder(String maze) {
        Set<String> extlist = new HashSet<>();
        String[] rows = maze.split("\n");
        int n = rows.length;
        if (n == 1) return 0;
        char[][] chart = new char[n][];
        for (int i = 0; i < n; i++) chart[i] = rows[i].toCharArray();
        int[][] DRLU = {{1,0},{0,1},{0,-1},{-1,0}};
        List<ArrayList<Integer[]>> queue = new ArrayList<>();
        queue.add(new ArrayList<>());
        queue.get(0).add(new Integer[]{0,0});
        
        while (!queue.isEmpty()) {
            int r = -1, c = -1;
            int shortest_list_len = Integer.MAX_VALUE;
            ArrayList<Integer[]> shortlist = new ArrayList<>();
            for (ArrayList<Integer[]> l : queue) {
                int sz = l.size();
                if (sz <= shortest_list_len) {
                    shortest_list_len = sz;
                    Integer[] rc = (Integer[])l.get(sz-1);
                    r = rc[0];
                    c = rc[1];
                    shortlist = l;
                }
            }
            queue.remove(shortlist);
            extlist.add(r+":"+c);
            for (int[] dir : DRLU) {
                int v1 = r+dir[0], v2 = c+dir[1];
                if (isSafe( v1, v2, chart, extlist )) {
                    if (v1 == n-1 && v2 == n-1) return shortest_list_len;
                    List<Integer[]> newpath = new ArrayList<Integer[]>(shortlist);
                    newpath.add(new Integer[]{ v1, v2 });
                    extlist.add(v1+":"+v2);
                    queue.add(new ArrayList<Integer[]>(newpath));
                }
            }
        }
        return -1;
  }
}

import java.util.*;
public class Finder {

  public static int pathFinder(String maze) {
    String[] s = maze.split("\n");
    char[][] grid = new char[s.length][s[0].length()];
     if(grid[grid.length - 1][grid[0].length - 1] == 'W')
            return -1;
    for(int i = 0; i < s.length; i++)
      grid[i] = s[i].toCharArray();
    Queue<Point> q = new LinkedList<Point>();
    q.add(new Point(0,0,0));
    boolean[][] visited = new boolean[grid.length][grid[0].length];
    while(q.size() != 0)
    {
      Point p = q.remove();
      if(p.row == grid.length - 1 && p.col == grid[0].length - 1)
        return p.d;
      else if(grid[p.row][p.col] != 'W' && !visited[p.row][p.col])
      {
        visited[p.row][p.col] = true;
        if(p.row > 0)
          q.add(new Point(p.row-1,p.col,p.d+1));
        if(p.col > 0)
          q.add(new Point(p.row,p.col-1,p.d+1));
        if(p.row < grid.length - 1)
          q.add(new Point(p.row+1,p.col,p.d+1));
        if(p.col < grid[0].length - 1)
          q.add(new Point(p.row,p.col+1,p.d+1));
      }
        
    }
    return -1;
  }
}

class Point{
  public int row;
  public int col;
  public int d;
  public Point(int row,int col,int d)
  {
    this.row = row;
    this.col = col;
    this.d= d;
  }
}

import java.util.*;
import java.util.stream.Stream;

import static java.util.stream.Collectors.*;

public class Finder {

    private final Map<Node, Queue<Node>> adjacencyMatrix;

    public Finder(String maze) {
        adjacencyMatrix = buildAdjacencyMatrix(maze);
    }

    public static int pathFinder(String maze) {
        return maze == null || maze.isBlank() ? -1 : new Finder(maze).findShortestPath();
    }

    private int findShortestPath() {
        Deque<Node> nodes = new LinkedList<>(adjacencyMatrix.keySet());
        if (nodes.isEmpty()) {
            return -1;
        }
        Node start = nodes.peekFirst();
        Node finish = nodes.peekLast();

        start.distance = 0;
        visitNeighbours(start);
        Queue<Node> unvisited = getNeighbours(start);
        while (!unvisited.isEmpty()) {
            Node next = unvisited.poll();
            visitNeighbours(next);
            getNeighbours(next).stream()
                    .filter(neighbour -> !neighbour.visited && !unvisited.contains(neighbour))
                    .forEach(unvisited::add);
        }
        if (finish.visited) {
            finish.printPath();
            return finish.distance;
        }
        return -1;
    }

    private void visitNeighbours(Node v) {
        Queue<Node> neighbours = getNeighbours(v);
        while (!neighbours.isEmpty()) {
            Node neighbour = neighbours.poll();
            int distanceToNeighbour = v.distance + 1;
            if (neighbour.distance > distanceToNeighbour) {
                neighbour.distance = distanceToNeighbour;
                neighbour.addToPath(v);
            }
        }
        // Visited means the distance to all it's neighbours was calculated.
        v.visited = true;
    }

    private Queue<Node> getNeighbours(Node xy) {
        return new LinkedList<>(adjacencyMatrix.get(xy));
    }

    private Map<Node, Queue<Node>> buildAdjacencyMatrix(String maze) {
        String[] mazeRows = maze.split("\n");
        Map<String, Node> nodeMap = new HashMap<>();
        for (int x = 0; x < mazeRows.length; x++) {
            for (int y = 0; y < mazeRows.length; y++) {
                if (mazeRows[x].charAt(y) == 'W') {
                    continue;
                }
                Node xy = new Node(x, y);
                nodeMap.put(xy.toString(), xy);
            }
        }
        return nodeMap.values().stream()
                .collect(toMap(node -> node, node -> node.neighbourCoordinates()
                                .filter(nodeMap::containsKey)
                                .map(nodeMap::get)
                                .collect(toCollection(LinkedList::new)),
                        (a, b) -> b, TreeMap::new));
    }
}

class Node implements Comparable<Node> {
    static final int INFINITY = 10_000_000;

    final int x;
    final int y;
    final List<Node> path;

    int distance;
    boolean visited;

    public Node(int x, int y) {
        this.x = x;
        this.y = y;
        visited = false;
        distance = INFINITY;
        path = new ArrayList<>();
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Node node = (Node) o;
        return x == node.x && y == node.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }

    @Override
    public String toString() {
        return coordinate(x, y);
    }

    @Override
    public int compareTo(Node other) {
        int compare = Integer.compare(x, other.x);
        return compare == 0 ? Integer.compare(y, other.y) : compare;
    }

    public Stream<String> neighbourCoordinates() {
        return Stream.of(
                coordinate(x - 1, y),
                coordinate(x + 1, y),
                coordinate(x, y - 1),
                coordinate(x, y + 1)
        );
    }

    public void addToPath(Node previous) {
        path.add(previous);
        path.addAll(previous.path);
    }

    public void printPath() {
        List<Node> shortestPath = new ArrayList<>(this.path);
        Collections.reverse(shortestPath);
        shortestPath.add(this);
        System.out.printf("Shortest path(%3d): %s.%n", shortestPath.size() - 1,
                shortestPath.stream().map(Node::toString).collect(joining(", ")));
    }

    private String coordinate(int x, int y) {
        return String.format("(%2d, %2d)", x, y);
    }
}