452 .idea/workspace.xml
View file

Large diffs are not rendered by default.

11 RushHour.iml
View file
@@ -0,0 +1,11 @@
<?xml version="1.0" encoding="UTF-8"?>
<module type="JAVA_MODULE" version="4">
<component name="NewModuleRootManager" inherit-compiler-output="true">
<exclude-output />
<content url="file://$MODULE_DIR$">
<sourceFolder url="file://$MODULE_DIR$/src" isTestSource="false" />
</content>
<orderEntry type="inheritedJdk" />
<orderEntry type="sourceFolder" forTests="false" />
</component>
</module>
BIN +2.2 KB out/production/RushHour/Car.class
View file
Binary file not shown.
BIN +501 Bytes out/production/RushHour/Main.class
View file
Binary file not shown.
BIN +2.01 KB out/production/RushHour/Move.class
View file
Binary file not shown.
BIN +1.81 KB out/production/RushHour/Puzzle.class
View file
Binary file not shown.
BIN +6.85 KB out/production/RushHour/State.class
View file
Binary file not shown.
14 src/Car.java
View file
@@ -58,4 +58,18 @@ public int getSize() {
public void setSize(int size) {
this.size = size;
}

public int[] getQuadFormat() {
return new int[]{this.vertical ? 1 : 0, x, y, size};
}

@Override
public String toString() {
return "Car{" +
"vertical=" + vertical +
", x=" + x +
", y=" + y +
", size=" + size +
'}';
}
}
3 src/Main.java
View file
@@ -2,7 +2,8 @@ public class Main {

public static void main(String[] args) {
Puzzle puzzle = new Puzzle();
puzzle.print();
puzzle.bestFirst(puzzle.getBoard());


}
}
55 src/Move.java
View file
@@ -1,12 +1,15 @@

public class Move {
private State currentState;
private Car car;
private int destinationX;
private int destinationY;
private int destX;
private int destY;

public Move(Car car, int destinationX, int destinationY) {
public Move(Car car, int destX, int destY, State state) {
this.car = car;
this.destinationX = destinationX;
this.destinationY = destinationY;
this.destX = destX;
this.destY = destY;
this.currentState = state;
}

public Car getCar() {
@@ -17,19 +20,45 @@ public void setCar(Car car) {
this.car = car;
}

public int getDestinationX() {
return destinationX;
public int getDestX() {
return destX;
}

public void setDestX(int destX) {
this.destX = destX;
}

public void setDestinationX(int destinationX) {
this.destinationX = destinationX;
public int getDestY() {
return destY;
}

public int getDestinationY() {
return destinationY;
public void setDestY(int destY) {
this.destY = destY;
}

public void setDestinationY(int destinationY) {
this.destinationY = destinationY;
public boolean isLegal() {
if (car.isVertical()) {
if (destX != car.getX()) return false;
if (Math.abs(destY - car.getY()) > 1) return false;
} else {
if (destY != car.getY()) return false;
if (Math.abs(destX - car.getX()) > 1) return false;
}

Car newCar = new Car(car.getQuadFormat());
newCar.setX(destX);
newCar.setY(destY);
for (int[] cord: newCar.getCoordinatesOccupied()) {
if (cord[0] < 0 || cord[0] >= State.ROW_COUNT) return false;
if (cord[1] < 0 || cord[1] >= State.COL_COUNT) return false;
if (!currentState.isOpen(cord[0], cord[1])) {
if (currentState.getCarAt(cord[0], cord[1]).isPresent()) {
if (!currentState.getCarAt(cord[0],cord[1]).get().equals(car)) {
return false;
}
}
}
}
return true;
}
}
104 src/Puzzle.java
View file
@@ -1,96 +1,40 @@
import java.util.*;
import java.util.stream.Collectors;

public class Puzzle {

private final static int ROW_COUNT = 6;
private final static int COL_COUNT = 6;

private Set<Car> cars = new LinkedHashSet<>();
private State board = new State();

public Puzzle() {
cars.add(new Car(new int[]{0, 2, 2, 2}));
cars.add(new Car(new int[]{0, 0, 4, 3}));
cars.add(new Car(new int[]{0, 3, 4, 2}));
cars.add(new Car(new int[]{0, 4, 1, 2}));
cars.add(new Car(new int[]{1, 2, 0, 2}));
cars.add(new Car(new int[]{1, 4, 2, 2}));
// generateMoves(new ArrayList<>(cars).get(3)).forEach(m -> System.out.println(Integer.toString(m.getDestinationX()) + "," + Integer.toString(m.getDestinationY())));
getCoordinatesOccupiedByCar(new ArrayList<>(cars).get(5)).forEach(cord -> System.out.println(Integer.toString(cord[0]) + "," + Integer.toString(cord[1])));
this.board.addCar(new Car(new int[]{0, 2, 2, 2}));
this.board.addCar(new Car(new int[]{0, 0, 4, 3}));
this.board.addCar(new Car(new int[]{0, 3, 4, 2}));
this.board.addCar(new Car(new int[]{0, 4, 1, 2}));
this.board.addCar(new Car(new int[]{1, 2, 0, 2}));
this.board.addCar(new Car(new int[]{1, 4, 2, 2}));
}

private boolean isOpen(int x, int y) {
return cars.stream()
.map(Car::getCoordinatesOccupied)
.flatMap(Collection::stream)
.filter(cord -> cord[0] == x && cord[1] == y)
.collect(Collectors.toSet()).isEmpty();
public State getBoard() {
return board;
}

private Set<int[]> getCoordinatesOccupiedByCar(Car car) {
Set<int[]> occupied = new HashSet<>();
occupied.add(new int[]{car.getX(), car.getY()});
for (int i = 1; i < car.getSize(); i++ ){
if (car.isVertical()) {
occupied.add(new int[]{car.getX(), car.getY() + i});
} else {
occupied.add(new int[]{car.getX() + i, car.getY()});
public State bestFirst(State initial) {
Set<State> closed = new HashSet<>();
Queue<State> open = new PriorityQueue<>();
open.add(initial);
while(!open.isEmpty()) {
System.out.println(closed.size());
State current = open.poll();
if (!closed.contains(current)){
closed.add(current);
if (current.isSolution()) return current;
for (State successor: current.generateSuccessors()) {
if (closed.contains(successor)) continue;
if (!open.contains(successor)) open.add(successor);
}
}
}
return occupied;
}

private Optional<Car> getCarAt(int x, int y) {
return cars.stream().filter(car -> car.getCoordinatesOccupied().contains(new int[]{x,y})).findFirst();
}

public boolean isLegalMove(Move move) {
if (!isOpen(move.getDestinationX(), move.getDestinationY())){
}
if (move.getCar().isVertical()) {
if (move.getDestinationX() != move.getCar().getX()) return false;
if (Math.abs(move.getDestinationY() - move.getCar().getY()) > 1) return false;
} else {
if (move.getDestinationY() != move.getCar().getY()) return false;
if (Math.abs(move.getDestinationX() - move.getCar().getX()) > 1) return false;
}
Car newCar = new Car(new int[]{move.getCar().isVertical() ? 1 : 0, move.getDestinationX(), move.getDestinationY(), move.getCar().getSize()});
return newCar.getCoordinatesOccupied().stream()
.filter(cord -> cord[0] > ROW_COUNT || cord[0] < 0 || cord[1] > COL_COUNT || cord[1] < 0)
.collect(Collectors.toSet()).isEmpty();
return null;
}

private Set<Move> generateMoves(Car car) {
if (!cars.contains(car)) throw new IllegalArgumentException("Car do not exist");
Set<Move> moves = new HashSet<>();
Move m1 = new Move(car, car.getX(), car.getY() + 1);
Move m2 = new Move(car, car.getX(), car.getY() - 1);
Move m3 = new Move(car, car.getX() + 1, car.getY());
Move m4 = new Move(car, car.getX() - 1, car.getY());
if (isLegalMove(m1)) moves.add(m1);
if (isLegalMove(m2)) moves.add(m2);
if (isLegalMove(m3)) moves.add(m3);
if (isLegalMove(m4)) moves.add(m4);
return moves;
}

public void print() {
String[][] board = new String[ROW_COUNT][COL_COUNT];
for (String[] row : board) {
Arrays.fill(row, "*");
}
int counter = 0;
for (Car car : this.cars) {
for (int[] cord: car.getCoordinatesOccupied()) {
int x = cord[0];
int y = cord[1];
board[y][x] = Integer.toString(counter);
}
counter++;
}
for (String[] row : board) {
System.out.println(Arrays.toString(row));
}
}

}
128 src/State.java
View file
@@ -0,0 +1,128 @@
import java.util.*;
import java.util.stream.Collectors;

public class State implements Comparable{

public final static int ROW_COUNT = 6;
public final static int COL_COUNT = 6;

private Set<Car> cars;

public State() {
this.cars = new LinkedHashSet<>();
}

public boolean isOpen(int x, int y) {
return cars.stream()
.map(Car::getCoordinatesOccupied)
.flatMap(Collection::stream)
.filter(cord -> cord[0] == x && cord[1] == y)
.collect(Collectors.toSet()).isEmpty();
}

public Optional<Car> getCarAt(int x, int y) {
for (Car car: cars) {
for (int[] cord: car.getCoordinatesOccupied()) {
if (cord[0] == x && cord[1] == y) {
return Optional.of(car);
}
}
}
return Optional.empty();
}

public Car getCarZero() {
return cars.iterator().next();
}

public boolean isSolution() {
return getCarAt(5, 2).isPresent() && getCarZero().equals(getCarAt(5, 2).get());
}

public void addCar(Car c) {
cars.add(c);
}

public Set<Car> getCars() {
return cars;
}

public void print() {
String[][] board = new String[ROW_COUNT][COL_COUNT];
for (String[] row : board) {
Arrays.fill(row, "*");
}
int counter = 0;
for (Car car : cars) {
for (int[] cord: car.getCoordinatesOccupied()) {
int x = cord[0];
int y = cord[1];
board[y][x] = Integer.toString(counter);
}
counter++;
}
for (String[] row : board) {
System.out.println(Arrays.toString(row));
}
System.out.println();
}

public Set<State> generateSuccessors(){
Set<Move> moves = new HashSet<>();
getCars().forEach(car -> {
Move m1 = new Move(car, car.getX(), car.getY() + 1, this);
Move m2 = new Move(car, car.getX(), car.getY() - 1, this);
Move m3 = new Move(car, car.getX() + 1, car.getY(), this);
Move m4 = new Move(car, car.getX() - 1, car.getY(), this);
if (m1.isLegal()) moves.add(m1);
if (m2.isLegal()) moves.add(m2);
if (m3.isLegal()) moves.add(m3);
if (m4.isLegal()) moves.add(m4);
});
Set<State> successors = new HashSet<>();
moves.forEach(move -> successors.add(performMove(move)));
return successors;
}

public State performMove(Move move) {
State newState = cloneBoard();
newState.cars.forEach(car -> {
if (car.getX() == move.getCar().getX() && car.getY() == move.getCar().getY()) {
car.setX(move.getDestX());
car.setY(move.getDestY());
}
});
return newState;
}

public State cloneBoard() {
State newState = new State();
cars.forEach(car -> {
Car newCar = new Car(car.getQuadFormat());
newState.getCars().add(newCar);
});
return newState;
}

@Override
public int compareTo(Object o) {
return 0;
}

@Override
public boolean equals(Object o) {
return this.toString() .equals(o.toString());
}

@Override
public int hashCode() {
return cars != null ? cars.hashCode() : 0;
}

@Override
public String toString() {
return "State{" +
"cars=" + cars +
'}';
}
}