VacuumWorldBFS.java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.HashSet;

public class App {
  private static final Action[] actions = new Action[] { App.Action.MoveLeft, App.Action.MoveRight, App.Action.Suck };

  public static void main(String[] args) {
    var initialState = 1;

    var node = new Node(initialState, 0, null);

    if (App.goalTest(node)) {
      App.printSolution(node);
      return;
    }

    var frontier = new LinkedList<Node>();
    var explored = new HashSet<Integer>();

    frontier.add(node);

    while (!frontier.isEmpty()) {
      node = frontier.remove();
      explored.add(node.state);

      for (Action action : actions) {
        var child = new Node(App.getResult(action, node.state), node.pathCost + 1, node);

        if (!(frontier.contains(child) || explored.contains(child.state))) {
          if (App.goalTest(child)) {
            App.printSolution(child);
            return;
          }

          frontier.add(child);
        }
      }
    }
  }

  private static void printSolution(Node node) {
    System.out.print("Path cost ");
    System.out.println(node.pathCost);

    var solution = new LinkedList<Integer>();
    while (node.parent != null) {
      solution.push(node.state);

      node = node.parent;
    }

    solution.push(node.state);

    while (!solution.isEmpty()) {
      System.out.print(solution.remove());
      System.out.print(" ");
    }
  }

  private static boolean goalTest(Node node) {
    return node.state == 7 || node.state == 8;
  }

  private static int getResult(Action action, int state) {
    switch (state) {
      case 1:
        switch (action) {
          case MoveLeft:
            return 1;
          case MoveRight:
            return 2;
          case Suck:
            return 3;
        }
        break;
      case 2:
        switch (action) {
          case MoveLeft:
            return 1;
          case MoveRight:
            return 2;
          case Suck:
            return 6;
        }
        break;
      case 3:
        switch (action) {
          case MoveLeft:
            return 3;
          case MoveRight:
            return 4;
          case Suck:
            return 3;
        }
        break;
      case 4:
        switch (action) {
          case MoveLeft:
            return 3;
          case MoveRight:
            return 4;
          case Suck:
            return 8;
        }
        break;
      case 5:
        switch (action) {
          case MoveLeft:
            return 5;
          case MoveRight:
            return 6;
          case Suck:
            return 7;
        }
        break;
      case 6:
        switch (action) {
          case MoveLeft:
            return 5;
          case MoveRight:
            return 6;
          case Suck:
            return 6;
        }
        break;
      case 7:
        switch (action) {
          case MoveLeft:
            return 7;
          case MoveRight:
            return 8;
          case Suck:
            return 7;
        }
        break;
      case 8:
        switch (action) {
          case MoveLeft:
            return 7;
          case MoveRight:
            return 8;
          case Suck:
            return 8;
        }
        break;
    }

    throw new RuntimeException("No state transition found.");
  }

  private static enum Action {
    MoveLeft,
    MoveRight,
    Suck
  }

  private static class Node {
    public int state;
    public int pathCost;
    public Node parent;

    public Node(int state, int cost, Node parent) {
      this.state = state;
      this.pathCost = cost;
      this.parent = parent;
    }

    @Override
    public boolean equals(Object other) {
      var o = (Node) other;
      return this.state == o.state;
    }
  }
}