BruteForceLevelsGenerator - click to expand!
public class BruteForceLevelsGenerator {
private static final int MIN_NODE_COUNT_INCLUDED = 4;
private static final int MAX_NODE_COUNT_EXCLUDED = 7;
private static final int SIDE_SIZE = 4; // 16 --> max 12 min 10
private static final int SIDE_WITHOUT_CORNERS_SIZE = SIDE_SIZE - 2;
private static final int MAX_COUNTER = 750_000_000;
private final BruteForceLevelsChecker bruteForceLevelsChecker = new BruteForceLevelsChecker(SIDE_SIZE);
private final Random random = new Random();
private final List<Integer> cornerPositions = new ArrayList<>();
private final List<Integer> sidePositions = new ArrayList<>();
private List<Integer> innerPositions = new ArrayList<>();
public void Execute(LevelsData levelsData) {
SetupSidePositions();
var generatedLevels = Stream.of(levelsData.levels).collect(Collectors.toCollection(ArrayList::new));
var startLevel = generatedLevels.size() + 1;
var gson = new Gson();
for (var level = startLevel; level <= 4; level++) {
GenerateLevels(generatedLevels, level);
}
levelsData.levels = generatedLevels.toArray(new LevelsData.LevelData[0]);
System.out.println(gson.toJson(levelsData));
}
private void SetupSidePositions()
{
cornerPositions.add(0);
cornerPositions.add(SIDE_SIZE - 1);
cornerPositions.add(SIDE_SIZE * SIDE_SIZE - SIDE_SIZE);
cornerPositions.add(SIDE_SIZE * SIDE_SIZE - 1);
for (var i = 1; i < SIDE_SIZE - 1; i++)
{
sidePositions.add(i);
}
for (var i = SIDE_SIZE; i < cornerPositions.get(2); i += SIDE_SIZE)
{
sidePositions.add(i);
}
for (var i = SIDE_SIZE + SIDE_SIZE - 1; i < cornerPositions.get(3); i += SIDE_SIZE)
{
sidePositions.add(i);
}
for (var i = SIDE_SIZE * SIDE_SIZE - SIDE_SIZE + 1; i < cornerPositions.get(3); i++)
{
sidePositions.add(i);
}
for (var i = 0; i < SIDE_SIZE * SIDE_SIZE; i++)
{
innerPositions.add(i);
}
innerPositions.removeAll(cornerPositions);
innerPositions.removeAll(sidePositions);
}
private void GenerateLevels(List<LevelsData.LevelData> generatedLevels, int level)
{
System.out.println("Starting for level " + level);
var count = 0;
List<Integer> occupiedPositions;
List<Integer> counts;
while (true)
{
var nextNodesCount = ThreadLocalRandom.current().nextInt(MIN_NODE_COUNT_INCLUDED, MAX_NODE_COUNT_EXCLUDED);
occupiedPositions = GeneratePositions(nextNodesCount);
counts = GenerateCounts(nextNodesCount, occupiedPositions);
if (LevelUnique(generatedLevels, occupiedPositions, counts) && bruteForceLevelsChecker.isLevelPassable(occupiedPositions, counts))
{
System.out.println("*********************************");
break;
}
if (count++ > 250)
{
throw new IllegalArgumentException("Reached LevelPassable counter state!");
}
}
generatedLevels.add(new LevelsData.LevelData(level,
SIDE_SIZE + "x" + SIDE_SIZE,
occupiedPositions.toArray(new Integer[0]),
counts.toArray(new Integer[0])));
}
private static boolean LevelUnique(List<LevelsData.LevelData> generatedLevels, List<Integer> occupiedPositions, List<Integer> counts)
{
return generatedLevels.stream().noneMatch(generatedLevel ->
Arrays.equals(generatedLevel.nodes, occupiedPositions.toArray()) && Arrays.equals(generatedLevel.connectionsCount, counts.toArray()));
}
private List<Integer> GeneratePositions(int nextNodesCount)
{
var occupiedPositions = new ArrayList<Integer>();
var counter = 0;
var currentFreeCellsCount = SIDE_SIZE * SIDE_SIZE - nextNodesCount;
for (var i = 0; i < nextNodesCount; i++)
{
while (true)
{
if (counter++ > MAX_COUNTER)
{
throw new IllegalArgumentException("Reached positions counter state!");
}
var nextPosition = random.nextInt(SIDE_SIZE * SIDE_SIZE);
if (occupiedPositions.contains(nextPosition) || IsNotAvailablePosition(nextPosition, occupiedPositions))
{
continue;
}
var isFitForOtherPositions = true;
for (var occupiedPosition : occupiedPositions)
{
var tempOccupiedPositions = new ArrayList<>(occupiedPositions);
tempOccupiedPositions.remove(occupiedPosition);
tempOccupiedPositions.add(nextPosition);
if (IsNotAvailablePosition(occupiedPosition, tempOccupiedPositions))
{
isFitForOtherPositions = false;
break;
}
}
if (!isFitForOtherPositions) continue;
occupiedPositions.add(nextPosition);
break;
}
}
var result = new ArrayList<Integer>(occupiedPositions.size());
result.addAll(occupiedPositions.stream().filter(cornerPositions::contains).collect(Collectors.toList()));
result.addAll(occupiedPositions.stream().filter(sidePositions::contains).collect(Collectors.toList()));
result.addAll(occupiedPositions.stream().filter(innerPositions::contains).collect(Collectors.toList()));
return result;
}
private List<Integer> GenerateCounts(int nextNodesCount, List<Integer> occupiedPositions)
{
var counter = 0;
while (true)
{
var counts = new ArrayList<Integer>();
if (counter++ > MAX_COUNTER)
{
throw new IllegalArgumentException("Reached counts counter state!");
}
for (var i = 0; i < nextNodesCount; i++)
{
var nextCount = ThreadLocalRandom.current().nextInt(1, 5);
if (i == nextNodesCount - 1 && (counts.stream().mapToInt(Integer::intValue).sum() + nextCount) % 2 != 0)
{
break;
}
var nextPosition = occupiedPositions.get(i);
if (cornerPositions.contains(nextPosition) && nextCount > 2 - NodesCountOnCornerNextToGiven(nextPosition, occupiedPositions))
{
break;
}
if (sidePositions.contains(nextPosition) && nextCount > 3 - NodesCountOnSideNextToGiven(nextPosition, occupiedPositions))
{
break;
}
if (innerPositions.contains(nextPosition) && nextCount > 4 - NodesCountOnInnerNextToGiven(nextPosition, occupiedPositions))
{
break;
}
counts.add(nextCount);
}
if (counts.size() == occupiedPositions.size())
{
return counts;
}
}
}
private boolean IsNotAvailablePosition(int nextPosition, List<Integer> occupiedPositions)
{
return NodesCountOnCornerNextToGiven(nextPosition, occupiedPositions) > 1 ||
NodesCountOnSideNextToGiven(nextPosition, occupiedPositions) > 2 ||
NodesCountOnInnerNextToGiven(nextPosition, occupiedPositions) > 3;
}
private int NodesCountOnCornerNextToGiven(int nextPosition, List<Integer> occupiedPositions)
{
var downLeftCorner = cornerPositions.get(0);
var downRightCorner = cornerPositions.get(1);
var upLeftCorner = cornerPositions.get(2);
var upRightCorner = cornerPositions.get(3);
if (nextPosition == downLeftCorner)
return (int) occupiedPositions.stream().filter(index -> index == nextPosition + SIDE_SIZE || (index == nextPosition + 1))
.count();
if (nextPosition == downRightCorner)
return (int) occupiedPositions.stream().filter(index -> index == nextPosition + SIDE_SIZE || index == nextPosition - 1).count();
if (nextPosition == upLeftCorner)
return (int) occupiedPositions.stream().filter(index -> index == nextPosition - SIDE_SIZE || index == nextPosition + 1).count();
if (nextPosition == upRightCorner)
return (int) occupiedPositions.stream().filter(index ->index == nextPosition - SIDE_SIZE || index == nextPosition - 1).count();
return 0;
}
private int NodesCountOnSideNextToGiven(int nextPosition, List<Integer> occupiedPositions)
{
var downLine = sidePositions.subList(0, SIDE_WITHOUT_CORNERS_SIZE);
var leftLine = sidePositions.subList(SIDE_WITHOUT_CORNERS_SIZE, 2 * SIDE_WITHOUT_CORNERS_SIZE);
var rightLine = sidePositions.subList(2 * SIDE_WITHOUT_CORNERS_SIZE, 3 * SIDE_WITHOUT_CORNERS_SIZE);
var upLine = sidePositions.subList(3 * SIDE_WITHOUT_CORNERS_SIZE, 4 * SIDE_WITHOUT_CORNERS_SIZE);
if (downLine.contains(nextPosition))
{
return (int) occupiedPositions.stream().filter(index -> index == nextPosition - 1 ||
index == nextPosition + 1 ||
index == nextPosition + SIDE_SIZE).count();
}
if (leftLine.contains(nextPosition))
{
return (int) occupiedPositions.stream().filter(index -> index == nextPosition + 1 ||
index == nextPosition - SIDE_SIZE ||
index == nextPosition + SIDE_SIZE).count();
}
if (rightLine.contains(nextPosition))
{
return (int) occupiedPositions.stream().filter(index -> index == nextPosition - 1 ||
index == nextPosition - SIDE_SIZE ||
index == nextPosition + SIDE_SIZE).count();
}
if (upLine.contains(nextPosition))
{
return (int) occupiedPositions.stream().filter(index -> index == nextPosition - 1 ||
index == nextPosition + 1 ||
index == nextPosition - SIDE_SIZE).count();
}
return 0;
}
private int NodesCountOnInnerNextToGiven(int nextPosition, List<Integer> occupiedPositions)
{
if (innerPositions.contains(nextPosition))
{
return (int) occupiedPositions.stream().filter(index -> index == nextPosition - 1 ||
index == nextPosition + 1 ||
index == nextPosition - SIDE_SIZE ||
index == nextPosition + SIDE_SIZE).count();
}
return 0;
}
}
