BruteForceLevelsChecker - click to expand!
class BruteForceLevelsChecker {
private final int sideSize;
BruteForceLevelsChecker(int sideSize) {
this.sideSize = sideSize;
}
boolean isLevelPassable(List<Integer> occupiedPositions, List<Integer> counts) {
var graph = new Graph(sideSize, occupiedPositions, counts);
var results = graph.PerformSearch();
if (results.size() <= 0) {
return false;
}
for (var connections : results) {
System.out.println(connections.stream().map(Connection::toString).collect(Collectors.joining(",")));
}
return true;
}
// https://www.geeksforgeeks.org/find-paths-given-source-destination/
public static class Graph {
private static final int THREAD_POOL_SIZE = 18;
private final int verticesInGraph;
private final int sideSize;
private final int totalCount;
private final int requiredPathLength;
private List<Integer>[] adjacencyList;
private final List<Integer> corners;
private final List<Integer> downSide;
private final List<Integer> leftSide;
private final List<Integer> rightSide;
private final List<Integer> upSide;
private final List<Integer> inner;
private final List<Integer> occupiedPositions;
private final Map<Integer, Integer> positionToCount;
private final Map<Integer, List<Connection>> connectionsMapping = new HashMap<>();
private ExecutorService executorService = Executors.newFixedThreadPool(THREAD_POOL_SIZE);
Graph(int sideSize, List<Integer> occupiedPositions, List<Integer> counts) {
this.sideSize = sideSize;
verticesInGraph = sideSize * sideSize;
this.occupiedPositions = occupiedPositions;
positionToCount = new HashMap<>();
for (var i = 0; i < this.occupiedPositions.size(); i++) {
positionToCount.put(this.occupiedPositions.get(i), counts.get(i));
}
totalCount = positionToCount.values().stream().mapToInt(value -> value).sum();
requiredPathLength = verticesInGraph - this.occupiedPositions.size();
corners = List.of(
0,
this.sideSize - 1,
this.sideSize * this.sideSize - this.sideSize,
this.sideSize * this.sideSize - 1
);
downSide = new ArrayList<>();
for (var i = 1; i < corners.get(1); i++) {
downSide.add(i);
}
leftSide = new ArrayList<>();
for (var i = this.sideSize; i < corners.get(2); i += this.sideSize) {
leftSide.add(i);
}
rightSide = new ArrayList<>();
for (var i = corners.get(1) + this.sideSize; i < corners.get(3); i += this.sideSize) {
rightSide.add(i);
}
upSide = new ArrayList<>();
for (var i = corners.get(2) + 1; i < corners.get(3); i++) {
upSide.add(i);
}
inner = new ArrayList<>();
for (var i = 0; i < this.sideSize * this.sideSize; i++) {
inner.add(i);
}
inner.removeAll(corners);
inner.removeAll(downSide);
inner.removeAll(leftSide);
inner.removeAll(rightSide);
inner.removeAll(upSide);
}
@SuppressWarnings("unchecked")
private void InitAdjList() {
adjacencyList = new ArrayList[verticesInGraph];
for (var i = 0; i < verticesInGraph; i++) {
adjacencyList[i] = new ArrayList<>();
}
}
private void AddEdge(int from, int to, List<Integer> remainingOccupiedPositions) {
if (remainingOccupiedPositions.contains(from) || remainingOccupiedPositions.contains(to)) {
return;
}
adjacencyList[from].add(to);
}
private void CollectAllPaths(int from, int to) {
var isVisited = new boolean[verticesInGraph];
var pathList = new ArrayList<>(List.of(from));
FindAllPaths(from, to, isVisited, pathList);
}
private void FindAllPaths(int from, int to,
boolean[] isVisited,
List<Integer> localPathList) {
isVisited[from] = true;
if (from == to) {
List<Integer> path = new ArrayList<>(localPathList);
var originalFrom = path.get(0);
path = path.subList(1, path.size() - 1);
if (path.size() > 0) {
var con = new Connection(originalFrom, to, path);
if (connectionsMapping.containsKey(originalFrom)) {
var values = connectionsMapping.get(originalFrom);
values.add(con);
connectionsMapping.put(originalFrom, values);
} else {
connectionsMapping.put(originalFrom, new ArrayList<>(List.of(con)));
}
}
isVisited[from] = false;
return;
}
for (var i : adjacencyList[from]) {
if (!isVisited[i]) {
localPathList.add(i);
FindAllPaths(i, to, isVisited,
localPathList);
localPathList.remove(i);
}
}
isVisited[from] = false;
}
Set<List<Connection>> PerformSearch() {
GatherCombinations();
return ProcessResults();
}
private void GatherCombinations() {
for (var i = 0; i < occupiedPositions.size(); i++) {
var from = occupiedPositions.get(i);
for (var j = 0; j < occupiedPositions.size(); j++) {
if (i == j) continue;
var to = occupiedPositions.get(j);
var remainingOccupiedPositions = new ArrayList<>(occupiedPositions);
remainingOccupiedPositions.remove(from);
remainingOccupiedPositions.remove(to);
InitAdjList();
for (var index = 0; index < verticesInGraph; index++) {
if (index == corners.get(0)) {
AddEdge(index, index + 1, remainingOccupiedPositions);
AddEdge(index, index + sideSize, remainingOccupiedPositions);
} else if (index == corners.get(1)) {
AddEdge(index, index - 1, remainingOccupiedPositions);
AddEdge(index, index + sideSize, remainingOccupiedPositions);
} else if (index == corners.get(2)) {
AddEdge(index, index + 1, remainingOccupiedPositions);
AddEdge(index, index - sideSize, remainingOccupiedPositions);
} else if (index == corners.get(3)) {
AddEdge(index, index - 1, remainingOccupiedPositions);
AddEdge(index, index - sideSize, remainingOccupiedPositions);
} else if (downSide.contains(index)) {
AddEdge(index, index - 1, remainingOccupiedPositions);
AddEdge(index, index + 1, remainingOccupiedPositions);
AddEdge(index, index + sideSize, remainingOccupiedPositions);
} else if (leftSide.contains(index)) {
AddEdge(index, index + 1, remainingOccupiedPositions);
AddEdge(index, index + sideSize, remainingOccupiedPositions);
AddEdge(index, index - sideSize, remainingOccupiedPositions);
} else if (rightSide.contains(index)) {
AddEdge(index, index - 1, remainingOccupiedPositions);
AddEdge(index, index + sideSize, remainingOccupiedPositions);
AddEdge(index, index - sideSize, remainingOccupiedPositions);
} else if (upSide.contains(index)) {
AddEdge(index, index + 1, remainingOccupiedPositions);
AddEdge(index, index - 1, remainingOccupiedPositions);
AddEdge(index, index - sideSize, remainingOccupiedPositions);
} else if (inner.contains(index)) {
AddEdge(index, index + 1, remainingOccupiedPositions);
AddEdge(index, index - 1, remainingOccupiedPositions);
AddEdge(index, index + sideSize, remainingOccupiedPositions);
AddEdge(index, index - sideSize, remainingOccupiedPositions);
}
}
CollectAllPaths(from, to);
}
}
}
private Set<List<Connection>> ProcessResults() {
BigInteger expectedCombinations = BigInteger.ONE;
for (List<Connection> value : connectionsMapping.values()) {
expectedCombinations = expectedCombinations.multiply(BigInteger.valueOf(value.size()));
}
System.out.println("expected combinations count " + expectedCombinations);
if (expectedCombinations.compareTo(BigInteger.valueOf(Integer.MAX_VALUE)) > 0) {
return new HashSet<>();
}
var stopwatch = new StopWatch();
stopwatch.start();
final List<List<Connection>> allPossibleCombinations = Lists.cartesianProduct(new ArrayList<>(connectionsMapping.values()));
System.out.println("all possible combinations " + allPossibleCombinations.size() + " in " + stopwatch.formatTime());
stopwatch.stop();
stopwatch.reset();
stopwatch.start();
List<Callable<Set<List<Connection>>>> callableTasks = new ArrayList<>();
Lists.partition(allPossibleCombinations, allPossibleCombinations.size() / THREAD_POOL_SIZE).forEach(combinations -> {
callableTasks.add(() -> processCombinations(combinations));
});
try {
Set<List<Connection>> result = new HashSet<>();
final List<Future<Set<List<Connection>>>> allResults = executorService.invokeAll(callableTasks);
for (Future<Set<List<Connection>>> res : allResults) {
result.addAll(res.get());
}
executorService.shutdown();
stopwatch.stop();
System.out.println("winning combinations " + result.size() + " in " + stopwatch.formatTime());
System.gc();
return result;
} catch (InterruptedException | ExecutionException e) {
System.err.println("Couldn't compute all results! " + e);
return new HashSet<>();
}
}
private Set<List<Connection>> processCombinations(List<List<Connection>> allPossibleCombinations) {
var result = new HashSet<List<Connection>>(100);
for (int outerIndex = 0; outerIndex < allPossibleCombinations.size(); outerIndex++) {
List<Connection> allPossibleCombination = allPossibleCombinations.get(outerIndex);
var currentPath = new ArrayList<Integer>(verticesInGraph);
var counts = new HashMap<>(positionToCount);
var countLeft = totalCount;
var combinationConnections = new ArrayList<Connection>(totalCount);
for (int innerIndex = 0; innerIndex < allPossibleCombination.size(); innerIndex++) {
Connection connection = allPossibleCombination.get(innerIndex);
var path = connection.getPath();
if (currentPath.stream().anyMatch(path::contains)) {
break;
}
var fromCount = counts.get(connection.getFrom());
var toCount = counts.get(connection.getTo());
if (fromCount <= 0 || toCount <= 0) {
continue;
}
currentPath.addAll(path);
counts.put(connection.getFrom(), --fromCount);
counts.put(connection.getTo(), --toCount);
combinationConnections.add(connection);
countLeft -= 2;
if (countLeft <= 0) {
break;
}
}
if (countLeft == 0 && currentPath.size() == requiredPathLength) {
result.add(combinationConnections);
}
}
return result;
}
}
}
