Method: countLegalPositions()

1: package de.fhdw.gaming.ipspiel23.c4.domain.impl;
2:
3: import java.util.ArrayList;
4: import java.util.HashMap;
5: import java.util.HashSet;
6: import java.util.List;
7: import java.util.Map;
8: import java.util.Optional;
9: import java.util.Set;
10:
11: import de.fhdw.gaming.ipspiel23.c4.collections.IReadOnlyDictionary;
12: import de.fhdw.gaming.ipspiel23.c4.collections.ReadOnlyDictionary;
13: import de.fhdw.gaming.ipspiel23.c4.domain.C4Direction;
14: import de.fhdw.gaming.ipspiel23.c4.domain.IC4Board;
15: import de.fhdw.gaming.ipspiel23.c4.domain.IC4BoardSlim;
16: import de.fhdw.gaming.ipspiel23.c4.domain.IC4Field;
17: import de.fhdw.gaming.ipspiel23.c4.domain.IC4Player;
18: import de.fhdw.gaming.ipspiel23.c4.domain.IC4Position;
19: import de.fhdw.gaming.ipspiel23.c4.domain.IC4Solution;
20:
21: /**
22: * A naive implementation of {@link IC4Board}.
23: * <p>
24: * NOTE: this is a "naive" proof of concept implementation to act
25: * as a baseline for our benchmarkings. This class should never be used.
26: * </p>
27: */
28: // this is a "naive" proof of concept implementation to act
29: // as a baseline for our benchmarkings. This class should never be used.
30: // THerefore we don't care about complexity :P
31: // This class is legacy code will never undergo further development!
32: @SuppressWarnings({"PMD.GodClass", "PMD.CyclomaticComplexity", "PMD.CognitiveComplexity"})
33: public class C4BoardHeavy implements IC4Board {
34:
35: /**
36: * The players of the game.
37: */
38: private final IReadOnlyDictionary<Integer, IC4Player> players;
39:
40: /**
41: * The number of rows in the board.
42: */
43: private final int rowCount;
44:
45: /**
46: * The number of columns in the board.
47: */
48: private final int columnCount;
49:
50: /**
51: * The number of fields that must be connected to win the game.
52: */
53: private final int solutionSize;
54:
55: /**
56: * The fields of the board.
57: */
58: private final IC4Field[][] fields;
59:
60: /**
61: * Creates a new board.
62: *
63: * @param players The players of the game.
64: * @param rowCount The number of rows in the board.
65: * @param columnCount The number of columns in the board.
66: * @param solutionSize The number of fields that must be connected to win the game.
67: */
68: public C4BoardHeavy(final IReadOnlyDictionary<Integer, IC4Player> players, final int rowCount,
69: final int columnCount, final int solutionSize) {
70: this.players = players;
71: this.rowCount = rowCount;
72: this.columnCount = columnCount;
73: this.solutionSize = solutionSize;
74: this.fields = new IC4Field[rowCount][columnCount];
75: for (int row = 0; row < rowCount; row++) {
76: for (int column = 0; column < columnCount; column++) {
77: this.fields[row][column] = new C4FieldHeavy(this, new C4Position(row, column));
78: }
79: }
80: }
81:
82: /**
83: * Creates a new board.
84: *
85: * @param board The board to copy.
86: */
87: private C4BoardHeavy(final C4BoardHeavy board) {
88: final Map<Integer, IC4Player> playerMap = new HashMap<>();
89: for (final Integer key : board.players.getKeys()) {
90: playerMap.put(key, board.players.getValueOrDefault(key));
91: }
92: this.players = ReadOnlyDictionary.of(playerMap);
93: this.rowCount = board.rowCount;
94: this.columnCount = board.columnCount;
95: this.solutionSize = board.solutionSize;
96: this.fields = new IC4Field[rowCount][columnCount];
97: for (int row = 0; row < rowCount; row++) {
98: for (int column = 0; column < columnCount; column++) {
99: this.fields[row][column] = board.getField(new C4Position(row, column)).deepCopy();
100: }
101: }
102: }
103:
104: @Override
105: public int getRowCount() {
106: return this.rowCount;
107: }
108:
109: @Override
110: public int getColumnCount() {
111: return this.columnCount;
112: }
113:
114: @Override
115: public int getMinimumSolutionSize() {
116: return this.solutionSize;
117: }
118:
119: @Override
120: public boolean checkBounds(final int row, final int column) {
121: return row >= 0 && row < this.rowCount && column >= 0 && column < this.columnCount;
122: }
123:
124: @Override
125: public boolean isFull() {
126: for (int i = 0; i < this.getRowCount(); i++) {
127: for (int j = 0; j < this.getColumnCount(); j++) {
128: final Optional<IC4Field> field = tryGetField(new C4Position(i, j));
129: if (field.get().getOccupyingPlayer().isEmpty()) {
130: return false;
131: }
132: }
133: }
134: return true;
135: }
136:
137: @Override
138: public IC4BoardSlim getInternalBoard() {
139: throw new UnsupportedOperationException("'getInternalBoard' is not supported by this implementation");
140: }
141:
142: @Override
143: public Optional<IC4Field> tryGetField(final IC4Position position) {
144: if (checkBounds(position)) {
145: return Optional.of(this.fields[position.getRow()][position.getColumn()]);
146: }
147: return Optional.empty();
148: }
149:
150: @Override
151: public IC4Field getField(final IC4Position position) {
152: if (checkBounds(position)) {
153: return tryGetField(position).get();
154: }
155: throw new IndexOutOfBoundsException("Position is out of bounds");
156: }
157:
158: @Override
159: public IC4Field[][] getFields() {
160: final IC4Field[][] copiedFields = new IC4Field[this.fields.length][];
161: for (int i = 0; i < this.fields.length; i++) {
162: copiedFields[i] = this.fields[i].clone();
163: }
164: return copiedFields;
165: }
166:
167: @Override
168: public Optional<IC4Solution> tryFindFirstSolution() {
169: final Set<IC4Solution> solutions = findAllSolutionsInternal(false);
170: if (solutions.isEmpty()) {
171: return Optional.empty();
172: }
173: return Optional.of(solutions.iterator().next());
174: }
175:
176: @Override
177: public Set<IC4Solution> findAllSolutions() {
178: return findAllSolutionsInternal(true);
179: }
180:
181: /**
182: * Scans all directions for solutions.
183: *
184: * @param eagerEvaluation Whether to stop scanning after the first solution was found.
185: * @return The set of solutions to add the found solutions to.
186: */
187: private Set<IC4Solution> findAllSolutionsInternal(final boolean eagerEvaluation) {
188: final Set<IC4Solution> solutions = new HashSet<>();
189:
190: scanHorizontal(solutions, eagerEvaluation);
191: scanVertical(solutions, eagerEvaluation);
192: scanDiagonalLeft(solutions, eagerEvaluation);
193: scanDiagonalRight(solutions, eagerEvaluation);
194:
195: return solutions;
196: }
197:
198: /**
199: * Scans all horizontal lanes for solutions.
200: *
201: * @param solutions The set of solutions to add the found solutions to.
202: * @param eagerEvaluation Whether to stop scanning after the first solution was found.
203: */
204: private void scanHorizontal(final Set<IC4Solution> solutions, final boolean eagerEvaluation) {
205: if (!eagerEvaluation && !solutions.isEmpty()) {
206: return;
207: }
208: boolean foundSolution = false;
209: for (int row = 0; row < this.getRowCount() && (!foundSolution || eagerEvaluation); row++) {
210: final IC4Position startPosition = new C4Position(row, 0);
211: foundSolution = scanLane(solutions, startPosition, C4Direction.EAST, eagerEvaluation);
212: }
213: }
214:
215: /**
216: * Scans all vertical lanes for solutions.
217: *
218: * @param solutions The set of solutions to add the found solutions to.
219: * @param eagerEvaluation Whether to stop scanning after the first solution was found.
220: */
221: private void scanVertical(final Set<IC4Solution> solutions, final boolean eagerEvaluation) {
222: if (!eagerEvaluation && !solutions.isEmpty()) {
223: return;
224: }
225: boolean foundSolution = false;
226: for (int column = 0; column < this.getColumnCount() && (!foundSolution || eagerEvaluation); column++) {
227: final IC4Position startPosition = new C4Position(0, column);
228: foundSolution = scanLane(solutions, startPosition, C4Direction.SOUTH, eagerEvaluation);
229: }
230: }
231:
232: /**
233: * Scans all diagonals from top left top bottom right for solutions.
234: *
235: * @param solutions The set of solutions to add the found solutions to.
236: * @param eagerEvaluation Whether to stop scanning after the first solution was found.
237: */
238: private void scanDiagonalRight(final Set<IC4Solution> solutions, final boolean eagerEvaluation) {
239: if (!eagerEvaluation && !solutions.isEmpty()) {
240: return;
241: }
242: boolean foundSolution = false;
243: for (int row = 0; row < this.getRowCount() && (!foundSolution || eagerEvaluation); row++) {
244: final IC4Position startPosition = new C4Position(row, 0);
245: foundSolution = scanLane(solutions, startPosition, C4Direction.SOUTH_EAST, eagerEvaluation);
246: }
247: for (int column = 1; column < this.getColumnCount() && (!foundSolution || eagerEvaluation); column++) {
248: final IC4Position startPosition = new C4Position(0, column);
249: foundSolution = scanLane(solutions, startPosition, C4Direction.SOUTH_EAST, eagerEvaluation);
250: }
251: }
252:
253: /**
254: * Scans all diagonals from top right to bottom left for solutions.
255: *
256: * @param solutions The set of solutions to add the found solutions to.
257: * @param eagerEvaluation Whether to stop scanning after the first solution was found.
258: */
259: private void scanDiagonalLeft(final Set<IC4Solution> solutions, final boolean eagerEvaluation) {
260: if (!eagerEvaluation && !solutions.isEmpty()) {
261: return;
262: }
263: boolean foundSolution = false;
264: for (int row = 0; row < getRowCount() && (!foundSolution || eagerEvaluation); row++) {
265: final IC4Position startPosition = new C4Position(row, this.getColumnCount() - 1);
266: foundSolution = scanLane(solutions, startPosition, C4Direction.SOUTH_WEST, eagerEvaluation);
267: }
268: for (int column = 0; column < this.getColumnCount() - 1 && (!foundSolution || eagerEvaluation); column++) {
269: final IC4Position startPosition = new C4Position(0, column);
270: foundSolution = scanLane(solutions, startPosition, C4Direction.SOUTH_WEST, eagerEvaluation);
271: }
272: }
273:
274: /**
275: * Scans a lane for solutions.
276: *
277: * @param solutions The set of solutions to add the found solutions to.
278: * @param startPosition The position to start scanning from.
279: * @param direction The direction to scan in.
280: * @param eagerEvaluation Whether to stop scanning after the first solution was found.
281: * @return Whether a solution was found.
282: */
283: private boolean scanLane(final Set<IC4Solution> solutions, final IC4Position startPosition,
284: final C4Direction direction, final boolean eagerEvaluation) {
285: if (!eagerEvaluation && !solutions.isEmpty()) {
286: return true;
287: }
288:
289: Optional<IC4Player> lastPlayer = Optional.empty();
290: int lastPlayerCount = 0;
291:
292: IC4Position currentPosition = startPosition;
293: while (true) {
294: final Optional<IC4Field> field = this.tryGetField(currentPosition);
295: if (field.isEmpty()) {
296: break;
297: }
298: final Optional<IC4Player> currentPlayer = field.get().getOccupyingPlayer();
299: if (currentPlayer.isPresent()) {
300: if (currentPlayer.equals(lastPlayer)) {
301: lastPlayerCount++;
302: } else {
303: lastPlayer = currentPlayer;
304: lastPlayerCount = 1;
305: }
306: if (lastPlayerCount >= this.solutionSize) {
307: final var solution = scanFullSolution(lastPlayerCount, lastPlayer.get(), currentPosition,
308: direction);
309: solutions.add(solution);
310: if (!eagerEvaluation) {
311: return true;
312: }
313: }
314: } else {
315: lastPlayer = Optional.empty();
316: lastPlayerCount = 0;
317: }
318:
319: currentPosition = direction.stepFrom(currentPosition, 1);
320: }
321: return false;
322: }
323:
324: /**
325: * Scans a full solution to include as many fields as possible.
326: *
327: * @param currentCount The current count of fields in the solution.
328: * @param player The player that owns the solution.
329: * @param currentPosition The current position.
330: * @param direction The direction to scan in.
331: * @return The solution.
332: */
333: private IC4Solution scanFullSolution(final int currentCount, final IC4Player player,
334: final IC4Position currentPosition, final C4Direction direction) {
335: final int size = currentCount + scanRemaining(currentPosition, direction, player);
336: final IC4Field[] solutionFields = new IC4Field[size];
337: final IC4Position startPosition = direction.getInverse().stepFrom(currentPosition, currentCount - 1);
338: for (int i = 0; i < size; i++) {
339: final Optional<IC4Field> field = tryGetField(direction.stepFrom(startPosition, i));
340: solutionFields[i] = field.get();
341: }
342: return new C4SolutionHeavy(player, startPosition, direction.stepFrom(startPosition, size - 1),
343: direction, solutionFields);
344: }
345:
346: /**
347: * Scans the remaining fields in a direction.
348: *
349: * @param position The position to start scanning from.
350: * @param direction The direction to scan in.
351: * @param player The player that owns the solution.
352: * @return The number of fields that can be added to the solution.
353: */
354: private int scanRemaining(final IC4Position position, final C4Direction direction, final IC4Player player) {
355: int count = 0;
356: IC4Position currentPosition = position;
357: while (true) {
358: currentPosition = direction.stepFrom(currentPosition, 1);
359: final Optional<IC4Field> currentField = tryGetField(currentPosition);
360: if (currentField.isEmpty() || currentField.get().getOccupyingPlayer().isEmpty()) {
361: break;
362: }
363: final Optional<IC4Player> fieldPlayer = currentField.get().getOccupyingPlayer();
364: if (fieldPlayer.isEmpty()) {
365: break;
366: }
367: if (fieldPlayer.get().equals(player)) {
368: count++;
369: } else {
370: break;
371: }
372: }
373: return count;
374: }
375:
376: @Override
377: public boolean isEmpty(final IC4Position position) {
378: return this.fields[position.getRow()][position.getColumn()].getOccupyingPlayer().isEmpty();
379: }
380:
381: @Override
382: public boolean isEmpty(final int row, final int column) {
383: return isEmpty(new C4Position(row, column));
384: }
385:
386: @Override
387: public boolean checkBounds(final IC4Position position) {
388: return checkBounds(position.getRow(), position.getColumn());
389: }
390:
391: @Override
392: public boolean isSolid(final IC4Position position) {
393: // we need to also shift the row by one to the top because
394: // the row below the board is also considered solid and
395: // therefore for the context of this method, the board is
396: // one row higher than it actually is
397: if (!this.checkBounds(position) && !this.checkBounds(C4Direction.NORTH.stepFrom(position, 1))) {
398: throw new IndexOutOfBoundsException("The provided position is not within the defined bounds of the board!");
399: }
400: final Optional<IC4Field> field = tryGetField(position);
401: if (field.isPresent()) {
402: return field.get().getOccupyingPlayer().isPresent();
403: }
404: // bottom border is always solid
405: return tryGetField(C4Direction.NORTH.stepFrom(position, 1)).isPresent();
406: }
407:
408: @Override
409: public boolean isSolid(final int row, final int column) {
410: return isSolid(new C4Position(row, column));
411: }
412:
413: @Override
414: public Optional<IC4Player> getOccupyingPlayerOrDefault(final IC4Position position) {
415: if (!this.checkBounds(position)) {
416: throw new IndexOutOfBoundsException("The provided position is not within the defined bounds of the board!");
417: }
418: final Optional<IC4Field> field = tryGetField(position);
419: if (field.isPresent()) {
420: return field.get().getOccupyingPlayer();
421: }
422: return Optional.empty();
423: }
424:
425: @Override
426: public IC4Position[] getEmptyPositions() {
427: final List<IC4Position> emptyPositions = new ArrayList<>();
428: for (int row = 0; row < getRowCount(); row++) {
429: for (int column = 0; column < getColumnCount(); column++) {
430: final IC4Position position = new C4Position(row, column);
431: if (isEmpty(position)) {
432: emptyPositions.add(position);
433: }
434: }
435: }
436: return emptyPositions.toArray(new IC4Position[0]);
437: }
438:
439: @Override
440: public IC4Position[] getPositionsByPlayer(final IC4Player player) {
441: final List<IC4Position> positions = new ArrayList<>();
442: for (int row = 0; row < getRowCount(); row++) {
443: for (int column = 0; column < getColumnCount(); column++) {
444: final IC4Position position = new C4Position(row, column);
445: final Optional<IC4Player> occupyingPlayer = getOccupyingPlayerOrDefault(position);
446: if (occupyingPlayer.isPresent() && occupyingPlayer.get().equals(player)) {
447: positions.add(position);
448: }
449: }
450: }
451: return positions.toArray(new IC4Position[0]);
452: }
453:
454: @Override
455: public IC4Position[] getLegalPositions() {
456: final List<IC4Position> legalPositions = new ArrayList<>();
457: boolean inAir = false;
458: for (int column = 0; column < getColumnCount(); column++) {
459: int row = this.getRowCount() - 1;
460: for (; row >= 0 && !inAir; row--) {
461: inAir = this.getField(new C4Position(row, column)).getOccupyingPlayer().isEmpty();
462: }
463: if (inAir) {
464: inAir = false;
465: legalPositions.add(new C4Position(row + 1, column));
466: }
467: }
468: return legalPositions.toArray(new IC4Position[0]);
469: }
470:
471: @Override
472: public int countEmptyPositions() {
473: return getEmptyPositions().length;
474: }
475:
476: @Override
477: public int countPositionsByPlayer(final IC4Player player) {
478: return getPositionsByPlayer(player).length;
479: }
480:
481: @Override
482: public int countLegalPositions() {
483: return getLegalPositions().length;
484: }
485:
486: @Override
487: public IC4Board deepCopy() {
488: return new C4BoardHeavy(this);
489: }
490: }