Тетрис, больше тетриса! Этот тетрис оказался поголоволомней прошлого. Общая идея была понятна сразу, но “на местности” постоянно вылезали какие-то подводные камешки 🙂
Сначала думал пойти через 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, чтобы не изгаляться с импортом в консольный скрипт.
Пропустил пятнадцатый день. Не осилил… Пока что! Что ж, настало время дня шестнадцатого.
Правда, здесь тоже не обошлось без “помощи зала” – часть решения пришлось подсмотреть в интернете. Иначе упорно не желала разгадываться вторая половина загадки.
В целом – задачи становятся интересней (и парсинг ввода не причиняет неудобств, как бывало). Но и времени занимают ощутимо больше, чем первая десятка.
Следить за котлом!
record Valve(String name, long flow, List<String> linked) {}
record State(Map<String, Long> openValves, Valve player, Valve elephant, long totalFlow) {}
static List<State> openValve(Valve v1, Valve v2, boolean both, Map<String, Valve> valves, State s, long flow) {
if(v1.flow() > 0 && !s.openValves().containsKey(v1.name()) && (!both || (v2.flow() > 0 && !s.openValves().containsKey(v2.name())))) {
Map<String, Long> newOpen = new HashMap<>(s.openValves());
newOpen.put(v1.name(), v1.flow());
if (both) {
newOpen.put(v2.name(), v2.flow());
return List.of(new State(newOpen, v1, v2, flow));
}
return v2.linked().stream().map(name -> new State(newOpen, v1, valves.get(name), flow)).collect(Collectors.toList());
}
return List.of();
}
Да, “тетрис” был определённо приятней вчерашних “скобочек”. И концептуально, и в реализации. Старые-добрые циклы-в-циклах – что может быть лучше!? 🙂
Только циклы, приправленные щепоткой стримов, конечно! Впрочем, попытки решить вторую часть через стрим – не увенчались успехом, увы. Приступ стримоза отступил и циклы вошли в свои права.
Песок и камни, или – камни и песок
static int drawRock(String scanLine, boolean[][] gameField) {
int maxY = 0;
String[] XY = scanLine.split(" -> ");
for (int i = 0; i < XY.length - 1; i++) {
int[] rocks = IntStream.rangeClosed(i, i + 1).mapToObj(idx -> XY[idx].split(","))
.flatMap(Arrays::stream).mapToInt(Integer::parseInt).toArray();
for (int j = Math.min(rocks[0], rocks[2]); j <= Math.max(rocks[0], rocks[2]); j++) {
for (int k = Math.min(rocks[1], rocks[3]); k <= Math.max(rocks[1], rocks[3]); k++) {
gameField[j][k] = true;
}
}
maxY = Math.max(maxY, Math.max(rocks[1], rocks[3]));
}
return maxY;
}
static boolean pourSand(int maxY, boolean[][] gameField) {
if (gameField[500][0]) return false;
int x = 500;
int y = 0;
while (y <= maxY + 3) {
if (!gameField[x][y + 1]) {
y++;
continue;
} else if (!gameField[x - 1][y + 1]) {
x--;
y++;
continue;
} else if (!gameField[x + 1][y + 1]) {
x++;
y++;
continue;
}
return gameField[x][y] = true;
}
return false;
}
Зря я сетовал на загадку прошлого дня. Ох, зря! Парсинг вот этих вот дурных скобочек-в-скобочках – это было форменно издевательство, помноженное на бесконечное уныние.
Просто весь интерес убивает. После решения, вместо удовольствия – только облегчение с мыслью “Хоть бы никогда больше не встретить подобного” 🙂
Да будь там, допустим, валидный JSON – я бы, пожалуй, сдался, и подключил либу. Но костыли с JSONArray, навскидку, не выглядели проще кастомного решения. Что ж, вот оно.
По двенадцатому дню – сказать особо нечего. Если дни 7 и 10 запомнились (первый – неожиданными сложностями, второй – интересной в решении загадкой), то день 12 – совершенно безликий какой-то.
Тут изначально понятно, что именно придется делать для решения, и также понятно, что делать это будут довольно скучно.
Ну да ладно, BFS – так BFS. Разве что – не “тру-ООП” – без хранения вершиной своего состояния. Работает – и хорошо.
Что полезного отсюда вынес – обратное преобразование матрицы в стрим элементов, позволяющее отказаться от вложенных циклов.
Простая вершина для представления точки на карте
class Vertex {
public final int x;
public final int y;
public final int dist;
public final char height;
public Vertex(int x, int y, int dist, char height) {
this.x = x;
this.y = y;
this.dist = dist;
this.height = height;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Vertex that = (Vertex) o;
return x == that.x && y == that.y;
}
@Override
public int hashCode() {
return x + y;
}
@Override
public String toString() {
return "Vertex{x=" + x + ", y=" + y + ", dist=" + dist + '}';
}
}
С задачкой про Бандар-логов я познакомился (и расстался) непосредственно в день её выхода. И, к стыду своему, уже не очень помню подробности.
Под влиянием пресловутого “И так сойдёт!” – совершил ошибку с BigInteger (вероятно, ожидаемую и типовую для этой задачи). Несколько минут, потраченных на просчет первой тысячи “обезьяньих прыжков”, ясно показали – это ошибочный путь.
А, да – потом зачем-то пробовал пойти путём вычисления GCD, но вовремя присмотрелся к множителям “проверок” и заметил, что все они – простые числа. После этого поиск решения не составил труда.
Источник: Wikipedia
В формате таблицы заметить этот факт гораздо проще. Ну а “обезьян” я захардкодил, чтобы не парсить ввод. Решение этой загадки запускается на Java 17 (как и решение для Дня 7).
record Monkey(List<Long> items, Worry worry, Test test) {};
record Test(Integer divider, Map<Boolean, Integer> action) {};
record Worry(String arg1, String arg2, BiFunction<Long, Long, Long> op) {};
static BiFunction<Long, Long, Long> mult = (a, b) -> a * b;
static void day11() {
Map<Integer, Map.Entry<Monkey, AtomicLong>> bandarLogs = new TreeMap<>(Map.of(
0, Map.entry(
new Monkey(new CopyOnWriteArrayList<>(List.of(63L, 57L)), new Worry("old", "11", mult), new Test(7, Map.of(true, 6, false, 2))),
new AtomicLong(0)
),
1, Map.entry(
new Monkey(new CopyOnWriteArrayList<>(List.of(82L, 66L, 87L, 78L, 77L, 92L, 83L)), new Worry("old", "1", Long::sum), new Test(11, Map.of(true, 5, false, 0))),
new AtomicLong(0)
),
2, Map.entry(
new Monkey(new CopyOnWriteArrayList<>(List.of(97L, 53L, 53L, 85L, 58L, 54L)), new Worry("old", "7", mult), new Test(13, Map.of(true, 4, false, 3))),
new AtomicLong(0)
),
3, Map.entry(
new Monkey(new CopyOnWriteArrayList<>(List.of(50L)), new Worry("old", "3", Long::sum), new Test(3, Map.of(true, 1, false, 7))),
new AtomicLong(0)
),
4, Map.entry(
new Monkey(new CopyOnWriteArrayList<>(List.of(64L, 69L, 52L, 65L, 73L)), new Worry("old", "6", Long::sum), new Test(17, Map.of(true, 3, false, 7))),
new AtomicLong(0)
),
5, Map.entry(
new Monkey(new CopyOnWriteArrayList<>(List.of(57L, 91L, 65L)), new Worry("old", "5", Long::sum), new Test(2, Map.of(true, 0, false, 6))),
new AtomicLong(0)
),
6, Map.entry(
new Monkey(new CopyOnWriteArrayList<>(List.of(67L, 91L, 84L, 78L, 60L, 69L, 99L, 83L)), new Worry("old", "old", mult), new Test(5, Map.of(true, 2, false, 4))),
new AtomicLong(0)
),
7, Map.entry(
new Monkey(new CopyOnWriteArrayList<>(List.of(58L, 78L, 69L, 65L)), new Worry("old", "7", Long::sum), new Test(19, Map.of(true, 5, false, 1))),
new AtomicLong(0)
)
));
int divider = bandarLogs.values().stream().map(Entry::getKey).mapToInt(m -> m.test().divider()).reduce(1, (a, b) -> a * b);
// int rounds = 20;
int rounds = 10_000;
for (int i = 1; i <= rounds; i++) {
System.out.printf("Round %d\r", i);
bandarLogs.forEach((monkeyN, monkeyEntry) -> {
Monkey monkey = monkeyEntry.getKey();
monkey.items().forEach(item -> {
var a1 = "old".equals(monkey.worry().arg1()) ? item : Integer.parseInt(monkey.worry().arg1());
var a2 = "old".equals(monkey.worry().arg2()) ? item :Integer.parseInt(monkey.worry().arg2());
var newWorryLvl = monkey.worry().op().apply(a1, a2);
newWorryLvl = rounds == 20 ? newWorryLvl / 3 : newWorryLvl % divider;
int recipientMonkey = monkey.test().action().get(
newWorryLvl % monkey.test().divider() == 0
);
bandarLogs.get(recipientMonkey).getKey().items().add(newWorryLvl);
monkey.items().remove(item);
monkeyEntry.getValue().incrementAndGet();
});
});
}
System.out.println();
var result = bandarLogs.values().stream()
.map(Entry::getValue)
.map(AtomicLong::get)
.sorted(Comparator.reverseOrder())
.limit(2)
.reduce((a, b) -> a * b);
System.out.println("Monkey business = " + result);
}
Задача десятого дня далась неожиданно просто. Ну, не совсем неожиданно и не совсем просто, будем честны. Но, по сравнению с проклятым “древом седьмого дня” – это было совсем не больно 🙂
Поначалу думал, что получится всё запихать в один длинный и страшный стрим, с кучей таинственных мутаций внутри.
Как-то я делал сервис, реализующий развесистую логику подбора уже не помню чего по куче разных условий – и вот там было именно так. Мапы перетекали в мапы, всё это бесконечно упаковывалось и распаковывалось, подвергалось преобразованиям Шварца (да, корни где-то в Лиспе), и, в качестве вишенки на торте, венчалось самосборным коллектором.
В общем, для такого лучше подошел бы Perl. Или, например, JS. И уже через минуту я бы точно забыл, как это работает.
После седьмого дня – решение восьмого было, в некотором роде, отдыхом. Хотя “усладой для глаз” его точно не назовёшь – вид оно имеет весьма портяночный.
Когда-то развлекался – делал “крестики-нолики” с полем свободного размера. И для среднего уровня сложности позиция следующего хода компьютера вычислялась сканированием этого самого поля.
Не то, чтобы это всё пригодилось мне в задаче восьмого дня. Но с тех пор, помучившись с отладкой, я крепко запомнил необходимость тщательной проверки границ массивов. Благодаря чему поймал ArrayIndexOutOfBoundsException лишь единожды ¯\_(ツ)_/¯.
static void day8(String puzzleInputUri) throws IOException, InterruptedException {
int[][] forest = client.send(
request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines()
).body()
.map(line -> line.chars().map(cCode -> cCode - '0').toArray())
.toArray(int[][]::new);
int mapHeight = forest.length;
int mapWidth = forest[0].length;
AtomicInteger visibilityCount = new AtomicInteger(mapWidth * mapHeight);
TreeSet<Integer> scenicScores = new TreeSet<>();
for (int j = 1; j < mapHeight - 1; j++) { //j down
for (int i = 1; i < mapWidth - 1; i++) { //i ->
List<Boolean> visibilities = new ArrayList<>();
int scenicScore = 1;
//look left
for (int k = i - 1; k >= 0; k--) {
if (forest[j][k] >= forest[j][i]) {
visibilities.add(false);
scenicScore *= (i - k);
break;
} else if (k == 0) {
visibilities.add(true);
scenicScore *= i;
}
}
//look right
for (int k = i + 1; k < mapWidth; k++) {
if (forest[j][k] >= forest[j][i]) {
visibilities.add(false);
scenicScore *= (k - i);
break;
} else if (k == mapWidth - 1) {
visibilities.add(true);
scenicScore *= (mapWidth - 1) - i;
}
}
//look top
for (int k = j - 1; k >= 0; k--) {
if (forest[k][i] >= forest[j][i]) {
visibilities.add(false);
scenicScore *= (j - k);
break;
} else if (k == 0) {
visibilities.add(true);
scenicScore *= j;
}
}
//look bottom
for (int k = j + 1; k < mapHeight; k++) {
if (forest[k][i] >= forest[j][i]) {
visibilities.add(false);
scenicScore *= (k - j);
break;
} else if (k == (mapHeight - 1)) {
visibilities.add(true);
scenicScore *= (mapHeight - 1) - j;
}
}
visibilities.stream().reduce(Boolean::logicalOr).ifPresent(isVisible -> {
if (!isVisible) visibilityCount.decrementAndGet();
});
scenicScores.add(scenicScore);
}
}
System.out.println(visibilityCount);
System.out.println(scenicScores.last());
}
Всё началось с того, что мне совершенно не хотелось строить это дерево (забегая вперёд – всё же пришлось).
После пары неудачных попыток (о которых ниже) – решил хранить эту псевдо-ФС в избыточном виде – получились этакие “мангровые заросли”.
Директории, помимо вложенности в свои родительские каталоги, дублируются на корневом уровне. Таким образом получается без лишних усилий посчитать результат по условиям загадки.
