Advent of Code 2022: Day 17
Тетрис, больше тетриса! Этот тетрис оказался поголоволомней прошлого. Общая идея была понятна сразу, но «на местности» постоянно вылезали какие-то подводные камешки
Сначала думал пойти через byte[][], выставляя нужные биты в единицу (на что намекала ширина поля), но закопался в сдвигах (жаль, что ввод не оказался набором сдвиговых операций, или я не разгадал его).
Ну, хотя бы с идеей движения «окном» не промахнулся — во второй части она пригодилась.
Подготовительная работа
enum Move {
LEFT,
RIGHT;
private static final Map<Character, Move> cache = Map.of('<', LEFT, '>', RIGHT);
static Move of(char code) {
return cache.get(code);
}
}
class Triple {
public int left;
public int middle;
public List<Integer> right;
public Triple(int left, int middle, List<Integer> right) {
this.left = left;
this.middle = middle;
this.right = right;
}
public boolean equals(Object obj) {
if (obj == this) {
return true;
} else if (!(obj instanceof Triple)) {
return false;
} else {
Triple other = (Triple) obj;
return Objects.equals(left, other.left)
&& Objects.equals(middle, other.middle)
&& Objects.equals(right, other.right);
}
}
public int hashCode() {
return Objects.hashCode(left) ^ Objects.hashCode(middle)
^ Objects.hashCode(right);
}
}
static boolean hasMove(boolean[][] shape, int x, int y, Map<Integer, boolean[]> rows) {
for (int yIdx = 0; yIdx < shape.length; yIdx++) {
int currentY = y + (shape.length - yIdx);
if (rows.containsKey(currentY)) {
boolean[] shapeRow = shape[yIdx];
boolean[] fieldRow = rows.get(currentY);
for (int xIdx = 0; xIdx < shapeRow.length; xIdx++) {
if (fieldRow[x + xIdx] && shapeRow[xIdx]) return false;
}
}
}
return true;
}
Triple позаимствовал в Apache Commons, чтобы не изгаляться с импортом в консольный скрипт.
Время собирать камни
static void day17(String puzzleInputUri) throws IOException, InterruptedException {
boolean[][][] shapes = new boolean[][][] {
{ {true, true, true, true} }, // ___
{ {false, true, false}, {true, true, true}, {false, true, false} }, // +
{ {false, false, true}, {false, false, true}, {true, true, true} }, // _|
{ {true}, {true}, {true}, {true} }, // |
{ {true, true}, {true, true} } // #
};
List<Move> moves = client.send(request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines())
.body()
.map(String::toCharArray)
.flatMap(chars -> CharBuffer.wrap(chars).chars().mapToObj(i -> (char) i))
.map(Move::of)
.collect(Collectors.toList());
int level = 0;
int ins = 0;
Map<Integer, boolean[]> rows = new HashMap<>();
Map<Triple, Map.Entry<Long, Integer>> visited = new HashMap<>();
long additionalLevel = 0;
// long totalRocks = 2022L;
long totalRocks = 1_000_000_000_000L;
for (long rock = 0; rock < totalRocks; rock++) {
int currentShapeIdx = (int) (rock % shapes.length);
boolean[][] shape = shapes[currentShapeIdx];
int x = 2;
int y = level + 3;
while (true) {
Move direction = moves.get(ins++ % moves.size());
if ((Move.LEFT == direction && x > 0) && hasMove(shape, x - 1, y, rows)) {
x--;
} else if ((Move.RIGHT == direction && x < 7 - shape[0].length)
&& hasMove(shape, x + 1, y, rows)) {
x++;
}
if (hasMove(shape, x, y - 1, rows) && y > 0) {
y--;
} else {
for (int yIdx = 0; yIdx < shape.length; yIdx++) {
int currentY = y + (shape.length - yIdx);
boolean[] shapeRow = shape[yIdx];
boolean[] fieldRow = rows.computeIfAbsent(currentY, it -> new boolean[7]);
for (int xIdx = 0; xIdx < shapeRow.length; xIdx++) {
fieldRow[x + xIdx] |= shapeRow[xIdx];
}
}
break;
}
}
var levels = rows.keySet().stream().mapToInt(Integer::intValue).sorted().toArray();
level = levels[levels.length - 1];
List<Integer> window = new ArrayList<>(Collections.nCopies(7, -1));
for (int i = 0; i < 7; i++) {
for (int j = levels.length - 1; j >= 0; j--) {
if (rows.get(levels[j])[i]) {
window.add(i, level - levels[j]);
break;
}
}
}
var visitedRow = new Triple((ins - 1) % moves.size(), currentShapeIdx, window);
if (visited.containsKey(visitedRow)) {
var previous = visited.get(visitedRow);
long repeat = (totalRocks - rock) / (rock - previous.getKey());
rock += (rock - previous.getKey()) * repeat;
additionalLevel += repeat * (level - previous.getValue());
}
visited.put(visitedRow, Map.entry(rock, level));
}
System.out.println(level + additionalLevel);
}
Ну и прочитанное когда-то интервью с создателем оригинального «Тетриса» тоже помогло — там он как раз описывал, почему в игре «сгорают» ряды.
А впереди — день восемнадцатый!