Skip to content

Commit 5181994

Browse files
johnA1331johnA1331
authored
Merge branch 'master' into master
2 parents e59f95e + 0606cb6 commit 5181994

420 files changed

Lines changed: 7713 additions & 1297 deletions

File tree

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎algorithms-miscellaneous-2/src/main/java/com/baeldung/algorithms/play2048/Board.java‎

Lines changed: 208 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,208 @@
1+
package com.baeldung.algorithms.play2048;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.LinkedList;
6+
import java.util.List;
7+
8+
import org.slf4j.Logger;
9+
import org.slf4j.LoggerFactory;
10+
11+
public class Board {
12+
private static final Logger LOG = LoggerFactory.getLogger(Board.class);
13+
14+
private final int[][] board;
15+
16+
private final int score;
17+
18+
public Board(int size) {
19+
assert(size > 0);
20+
21+
this.board = new int[size][];
22+
this.score = 0;
23+
24+
for (int x = 0; x < size; ++x) {
25+
this.board[x] = new int[size];
26+
for (int y = 0; y < size; ++y) {
27+
board[x][y] = 0;
28+
}
29+
}
30+
}
31+
32+
private Board(int[][] board, int score) {
33+
this.score = score;
34+
this.board = new int[board.length][];
35+
36+
for (int x = 0; x < board.length; ++x) {
37+
this.board[x] = Arrays.copyOf(board[x], board[x].length);
38+
}
39+
}
40+
41+
public int getSize() {
42+
return board.length;
43+
}
44+
45+
public int getScore() {
46+
return score;
47+
}
48+
49+
public int getCell(Cell cell) {
50+
int x = cell.getX();
51+
int y = cell.getY();
52+
assert(x >= 0 && x < board.length);
53+
assert(y >= 0 && y < board.length);
54+
55+
return board[x][y];
56+
}
57+
58+
public boolean isEmpty(Cell cell) {
59+
return getCell(cell) == 0;
60+
}
61+
62+
public List<Cell> emptyCells() {
63+
List<Cell> result = new ArrayList<>();
64+
for (int x = 0; x < board.length; ++x) {
65+
for (int y = 0; y < board[x].length; ++y) {
66+
Cell cell = new Cell(x, y);
67+
if (isEmpty(cell)) {
68+
result.add(cell);
69+
}
70+
}
71+
}
72+
return result;
73+
}
74+
75+
public Board placeTile(Cell cell, int number) {
76+
if (!isEmpty(cell)) {
77+
throw new IllegalArgumentException("That cell is not empty");
78+
}
79+
80+
Board result = new Board(this.board, this.score);
81+
result.board[cell.getX()][cell.getY()] = number;
82+
return result;
83+
}
84+
85+
public Board move(Move move) {
86+
// Clone the board
87+
int[][] tiles = new int[this.board.length][];
88+
for (int x = 0; x < this.board.length; ++x) {
89+
tiles[x] = Arrays.copyOf(this.board[x], this.board[x].length);
90+
}
91+
92+
LOG.debug("Before move: {}", Arrays.deepToString(tiles));
93+
// If we're doing an Left/Right move then transpose the board to make it a Up/Down move
94+
if (move == Move.LEFT || move == Move.RIGHT) {
95+
tiles = transpose(tiles);
96+
LOG.debug("After transpose: {}", Arrays.deepToString(tiles));
97+
}
98+
// If we're doing a Right/Down move then reverse the board.
99+
// With the above we're now always doing an Up move
100+
if (move == Move.DOWN || move == Move.RIGHT) {
101+
tiles = reverse(tiles);
102+
LOG.debug("After reverse: {}", Arrays.deepToString(tiles));
103+
}
104+
LOG.debug("Ready to move: {}", Arrays.deepToString(tiles));
105+
106+
// Shift everything up
107+
int[][] result = new int[tiles.length][];
108+
int newScore = 0;
109+
for (int x = 0; x < tiles.length; ++x) {
110+
LinkedList<Integer> thisRow = new LinkedList<>();
111+
for (int y = 0; y < tiles[0].length; ++y) {
112+
if (tiles[x][y] > 0) {
113+
thisRow.add(tiles[x][y]);
114+
}
115+
}
116+
117+
LOG.debug("Unmerged row: {}", thisRow);
118+
LinkedList<Integer> newRow = new LinkedList<>();
119+
while (thisRow.size() >= 2) {
120+
int first = thisRow.pop();
121+
int second = thisRow.peek();
122+
LOG.debug("Looking at numbers {} and {}", first, second);
123+
if (second == first) {
124+
LOG.debug("Numbers match, combining");
125+
int newNumber = first * 2;
126+
newRow.add(newNumber);
127+
newScore += newNumber;
128+
thisRow.pop();
129+
} else {
130+
LOG.debug("Numbers don't match");
131+
newRow.add(first);
132+
}
133+
}
134+
newRow.addAll(thisRow);
135+
LOG.debug("Merged row: {}", newRow);
136+
137+
result[x] = new int[tiles[0].length];
138+
for (int y = 0; y < tiles[0].length; ++y) {
139+
if (newRow.isEmpty()) {
140+
result[x][y] = 0;
141+
} else {
142+
result[x][y] = newRow.pop();
143+
}
144+
}
145+
}
146+
LOG.debug("After moves: {}", Arrays.deepToString(result));
147+
148+
// Un-reverse the board
149+
if (move == Move.DOWN || move == Move.RIGHT) {
150+
result = reverse(result);
151+
LOG.debug("After reverse: {}", Arrays.deepToString(result));
152+
}
153+
// Un-transpose the board
154+
if (move == Move.LEFT || move == Move.RIGHT) {
155+
result = transpose(result);
156+
LOG.debug("After transpose: {}", Arrays.deepToString(result));
157+
}
158+
return new Board(result, this.score + newScore);
159+
}
160+
161+
private static int[][] transpose(int[][] input) {
162+
int[][] result = new int[input.length][];
163+
164+
for (int x = 0; x < input.length; ++x) {
165+
result[x] = new int[input[0].length];
166+
for (int y = 0; y < input[0].length; ++y) {
167+
result[x][y] = input[y][x];
168+
}
169+
}
170+
171+
return result;
172+
}
173+
174+
private static int[][] reverse(int[][] input) {
175+
int[][] result = new int[input.length][];
176+
177+
for (int x = 0; x < input.length; ++x) {
178+
result[x] = new int[input[0].length];
179+
for (int y = 0; y < input[0].length; ++y) {
180+
result[x][y] = input[x][input.length - y - 1];
181+
}
182+
}
183+
184+
return result;
185+
}
186+
187+
@Override
188+
public String toString() {
189+
return Arrays.deepToString(board);
190+
}
191+
192+
@Override
193+
public boolean equals(Object o) {
194+
if (this == o) {
195+
return true;
196+
}
197+
if (o == null || getClass() != o.getClass()) {
198+
return false;
199+
}
200+
Board board1 = (Board) o;
201+
return Arrays.deepEquals(board, board1.board);
202+
}
203+
204+
@Override
205+
public int hashCode() {
206+
return Arrays.deepHashCode(board);
207+
}
208+
}

‎algorithms-miscellaneous-2/src/main/java/com/baeldung/algorithms/play2048/Cell.java‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
package com.baeldung.algorithms.play2048;
2+
3+
import java.util.StringJoiner;
4+
5+
public class Cell {
6+
private int x;
7+
private int y;
8+
9+
public Cell(int x, int y) {
10+
this.x = x;
11+
this.y = y;
12+
}
13+
14+
public int getX() {
15+
return x;
16+
}
17+
18+
public int getY() {
19+
return y;
20+
}
21+
22+
@Override
23+
public String toString() {
24+
return new StringJoiner(", ", Cell.class.getSimpleName() + "[", "]").add("x=" + x).add("y=" + y).toString();
25+
}
26+
}

‎algorithms-miscellaneous-2/src/main/java/com/baeldung/algorithms/play2048/Computer.java‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package com.baeldung.algorithms.play2048;
2+
3+
import java.security.SecureRandom;
4+
import java.util.List;
5+
6+
import org.slf4j.Logger;
7+
import org.slf4j.LoggerFactory;
8+
9+
public class Computer {
10+
private static final Logger LOG = LoggerFactory.getLogger(Computer.class);
11+
12+
private final SecureRandom rng = new SecureRandom();
13+
14+
public Board makeMove(Board input) {
15+
List<Cell> emptyCells = input.emptyCells();
16+
LOG.info("Number of empty cells: {}", emptyCells.size());
17+
18+
double numberToPlace = rng.nextDouble();
19+
LOG.info("New number probability: {}", numberToPlace);
20+
21+
int indexToPlace = rng.nextInt(emptyCells.size());
22+
Cell cellToPlace = emptyCells.get(indexToPlace);
23+
LOG.info("Placing number into empty cell: {}", cellToPlace);
24+
25+
return input.placeTile(cellToPlace, numberToPlace >= 0.9 ? 4 : 2);
26+
}
27+
}

‎algorithms-miscellaneous-2/src/main/java/com/baeldung/algorithms/play2048/Human.java‎

Lines changed: 126 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,126 @@
1+
package com.baeldung.algorithms.play2048;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.Comparator;
6+
import java.util.List;
7+
import java.util.stream.Collectors;
8+
import java.util.stream.Stream;
9+
10+
import org.apache.commons.math3.util.Pair;
11+
import org.slf4j.Logger;
12+
import org.slf4j.LoggerFactory;
13+
14+
public class Human {
15+
private static final Logger LOG = LoggerFactory.getLogger(Human.class);
16+
17+
public Board makeMove(Board input) {
18+
// For each move in MOVE
19+
// Generate board from move
20+
// Generate Score for Board
21+
// Return board with the best score
22+
//
23+
// Generate Score
24+
// If Depth Limit
25+
// Return Final Score
26+
// Total Score = 0
27+
// For every empty square in new board
28+
// Generate board with "2" in square
29+
// Calculate Score
30+
// Total Score += (Score * 0.9)
31+
// Generate board with "4" in square
32+
// Calculate Score
33+
// Total Score += (Score * 0.1)
34+
//
35+
// Calculate Score
36+
// For each move in MOVE
37+
// Generate board from move
38+
// Generate score for board
39+
// Return the best generated score
40+
41+
return Arrays.stream(Move.values())
42+
.parallel()
43+
.map(input::move)
44+
.filter(board -> !board.equals(input))
45+
.max(Comparator.comparingInt(board -> generateScore(board, 0)))
46+
.orElse(input);
47+
}
48+
49+
private int generateScore(Board board, int depth) {
50+
if (depth >= 3) {
51+
int finalScore = calculateFinalScore(board);
52+
LOG.debug("Final score for board {}: {}", board,finalScore);
53+
return finalScore;
54+
}
55+
56+
return board.emptyCells().stream()
57+
.parallel()
58+
.flatMap(cell -> Stream.of(new Pair<>(cell, 2), new Pair<>(cell, 4)))
59+
.mapToInt(move -> {
60+
LOG.debug("Simulating move {} at depth {}", move, depth);
61+
Board newBoard = board.placeTile(move.getFirst(), move.getSecond());
62+
int boardScore = calculateScore(newBoard, depth + 1);
63+
int calculatedScore = (int) (boardScore * (move.getSecond() == 2 ? 0.9 : 0.1));
64+
LOG.debug("Calculated score for board {} and move {} at depth {}: {}", newBoard, move, depth, calculatedScore);
65+
return calculatedScore;
66+
})
67+
.sum();
68+
}
69+
70+
private int calculateScore(Board board, int depth) {
71+
return Arrays.stream(Move.values())
72+
.parallel()
73+
.map(board::move)
74+
.filter(moved -> !moved.equals(board))
75+
.mapToInt(newBoard -> generateScore(newBoard, depth))
76+
.max()
77+
.orElse(0);
78+
}
79+
80+
private int calculateFinalScore(Board board) {
81+
List<List<Integer>> rowsToScore = new ArrayList<>();
82+
for (int i = 0; i < board.getSize(); ++i) {
83+
List<Integer> row = new ArrayList<>();
84+
List<Integer> col = new ArrayList<>();
85+
86+
for (int j = 0; j < board.getSize(); ++j) {
87+
row.add(board.getCell(new Cell(i, j)));
88+
col.add(board.getCell(new Cell(j, i)));
89+
}
90+
91+
rowsToScore.add(row);
92+
rowsToScore.add(col);
93+
}
94+
95+
return rowsToScore.stream()
96+
.parallel()
97+
.mapToInt(row -> {
98+
List<Integer> preMerged = row.stream()
99+
.filter(value -> value != 0)
100+
.collect(Collectors.toList());
101+
102+
int numMerges = 0;
103+
int monotonicityLeft = 0;
104+
int monotonicityRight = 0;
105+
for (int i = 0; i < preMerged.size() - 1; ++i) {
106+
Integer first = preMerged.get(i);
107+
Integer second = preMerged.get(i + 1);
108+
if (first.equals(second)) {
109+
++numMerges;
110+
} else if (first > second) {
111+
monotonicityLeft += first - second;
112+
} else {
113+
monotonicityRight += second - first;
114+
}
115+
}
116+
117+
int score = 1000;
118+
score += 250 * row.stream().filter(value -> value == 0).count();
119+
score += 750 * numMerges;
120+
score -= 10 * row.stream().mapToInt(value -> value).sum();
121+
score -= 50 * Math.min(monotonicityLeft, monotonicityRight);
122+
return score;
123+
})
124+
.sum();
125+
}
126+
}

‎algorithms-miscellaneous-2/src/main/java/com/baeldung/algorithms/play2048/Move.java‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
package com.baeldung.algorithms.play2048;
2+
3+
public enum Move {
4+
UP,
5+
DOWN,
6+
LEFT,
7+
RIGHT
8+
}

0 commit comments

Comments
 (0)