Rookie Single Round Match 3 Editorials

JudgedScoring

This one is simply a matter of following the directions as stated. An easy way to do this is to first sort the list of scores, then add up all elements except the first and the last:

public int overallScore(int[] scores) {
Arrays.sort(scores);
int ret = 0;
for (int i = 1; i < scores.length - 1; i++)
ret += scores[i];
return ret;
}


TakeStones

There are two basic approaches to the problem. The first, using dynamic programming, looks to see if any of the possible moves taking 1..maxStones stones can leave your opponent in a losing position. If so, then the current position is winnable, otherwise it’s a losing position.

However, if we think about the problem a little, we can make an observation to actually make the solution much easier.  Ever value 1..maxStones is clearly a winning position. maxStones+1, however, is a losing position, because no matter how many we take, our opponent can take the remainder and win the game. So, if we can leave our opponent with maxStones+1, we leave them in a losing position. More generally, any position n*(maxStones+1) is a losing position for similar reasons, because whatever move is made, the opponent can make a move to keep us in a losing position. This makes a very simple one-line solution:

public String result(int stonePile, int maxStones) {
return stonePile % (maxStones + 1) == 0 ? "LOSE" : "WIN";
}


SoFarAway

Once we have found which point is the start and destination, we need to figure out the distance. Because there can be walls in our way, we can’t do a simple distance calculation to figure out the number of steps. Instead, we need to do a breadth-first search.

To do this, we begin at our starting point, which we know we can reach in 0 steps. Every adjacent open space can thus be reached in 1 step. And every open space adjacent to each of those (that we haven’t already considered) can thus be reached in two steps, and so on. Once we find our destination, we know the minimum number of steps needed.

We implement a simple queue of “next cells to look at” to ensure we do this in the proper order. If after running out of cells to explore, we still haven’t found the destination, it must not be reachable, so we return -1.

public int distance(String[] map) {
int startX = 0;
int startY = 0;
int endX = 0;
int endY = 0;
int[][] m = new int[map.length + 2][map[0].length() + 2];
for (int y = 0; y < map.length; y++)
for (int x = 0; x < map[y].length(); x++) {
m[y + 1][x + 1] = (map[y].charAt(x) == 'X') ? -2 : -1;
if (map[y].charAt(x) == 'S') {
startX = x + 1;
startY = y + 1;
}
if (map[y].charAt(x) == 'D') {
endX = x + 1;
endY = y + 1;
}
}
int[] q = new int[3000];
q[0] = startY * 52 + startX;
m[startY][startX] = 0;
int cur = 0;
int end = 1;
while (cur < end) {
int y = q[cur] / 52;
int x = q[cur] % 52;
if (y == endY && x == endX)
return m[y][x];
if (m[y][x - 1] == -1) {
m[y][x - 1] = m[y][x] + 1;
q[end] = y * 52 + x - 1;
end++;
}
if (m[y][x + 1] == -1) {
m[y][x + 1] = m[y][x] + 1;
q[end] = y * 52 + x + 1;
end++;
}
if (m[y - 1][x] == -1) {
m[y - 1][x] = m[y][x] + 1;
q[end] = (y - 1) * 52 + x;
end++;
}
if (m[y + 1][x] == -1) {
m[y + 1][x] = m[y][x] + 1;
q[end] = (y + 1) * 52 + x;
end++;
}
cur++;
}
return -1;
}