Серия «Advent of Code 2022»

Снова мартышки — те, да не те. Эти позадорней, поживей, поактивней 🙂 Но решение чем-то схожее — соседи, операции, кидают банан чиселку, занимаются эквилибристикой. Для этой загадки обвязка получилась потолще, конечно.

Мартышкины ужимки

enum Action {
ADD('+', Long::sum),
SUBTRACT('-', (op1, op2) -> op1 - op2),
DIVIDE('/', (op1, op2) -> op1 / op2),
MULTIPLY('*', (op1, op2) -> op1 * op2);
final char code;
final BiFunction<Long, Long, Long> func;
static final Map<Character, Action> OPS = Arrays.stream(Action.values())
.collect(Collectors.toUnmodifiableMap(it -> it.code, it -> it));
Action(char code, BiFunction<Long, Long, Long> func) {
this.code = code;
this.func = func;
}
BiFunction<Long, Long, Long> invert(boolean isPrev) {
switch (this) {
case ADD: return (op1, op2) -> op2 - op1;
case MULTIPLY: return (op1, op2) -> op2 / op1;
case SUBTRACT: return isPrev ? ADD.func : this.func;
case DIVIDE: return isPrev ? MULTIPLY.func : this.func;
default: return null;
}
}
}

Macaca sylvanus

static class Monkey {
String name, prevName, nextName;
Action action;
Monkey parent, prev, next;
Long number;
public Monkey(String inLine) {
name = inLine.substring(0, 4);
if (inLine.length() == 17) {
action = Action.OPS.get(inLine.charAt(11));
prevName = inLine.substring(6, 10);
nextName = inLine.substring(13);
} else {
number = Long.valueOf(inLine.substring(6));
}
}
public long calcNum() {
return number != null ? number : action.func.apply(prev.calcNum(), next.calcNum());
}
public void setPrevNext(Map<String, Monkey> monkeys) {
if ((prev = monkeys.get(prevName)) != null) {
prev.parent = this;
}
if ((next = monkeys.get(nextName)) != null) {
next.parent = this;
}
}
long calcEquilibrium() {
return "root".equals(parent.name) ? parent.getJoined(this).calcNum()
: parent.action.invert(isPrev()).apply(parent.getJoined(this).calcNum(), parent.calcEquilibrium());
}
boolean isPrev() {
return parent.prev == this;
}
Monkey getJoined(Monkey monkey) {
return monkey == prev ? next : prev;
}
}

Але-ап!
Благодаря высокому интеллекту мартышек (весь фокус они проделывают самостоятельно) — решение получилось коротеньким.

static void day21(String puzzleInputUri) throws IOException, InterruptedException {
var monkeys = client.send(request.uri((URI.create(puzzleInputUri))).build(), BodyHandlers.ofLines())
.body()
.map(Monkey::new)
.collect(Collectors.toMap(m -> m.name, m -> m));
monkeys.forEach((name, monkey) -> monkey.setPrevNext(monkeys));
System.out.println("Answer 1: " + monkeys.get("root").calcNum());
System.out.println("Answer 2: " + monkeys.get("humn").calcEquilibrium());
}

Advent of Code 2022: Day 19

Тяжело дались мне эти игры в Factorio. Хотя, вроде бы, с виду и похожи на слоновьи пляски на вентилях.
В этой задачке тоже пришлось погуглить подсказки, когда нашел варианты отсечек для рекурсии — дело пошло значительно веселее!

static int mostGeodes(int ore, int clay, int obsidian, int geode, int oreBot, int clayBot,
int obsidianBot, int geodeBot, int time, int maxTime, int[] botsCost) {
if (time == maxTime) {
return geode;
}
int oreTotal = ore + oreBot;
int clayTotal = clay + clayBot;
int obsidianTotal = obsidian + obsidianBot;
int geodeTotal = geode + geodeBot;

if (ore >= botsCost[4] && obsidian >= botsCost[5]) {
return mostGeodes(oreTotal - botsCost[4], clayTotal, obsidianTotal - botsCost[5],
geodeTotal, oreBot, clayBot, obsidianBot, geodeBot + 1, time + 1, maxTime, botsCost);
}
if (clayBot >= botsCost[3] && obsidianBot < botsCost[5] && ore >= botsCost[2] && clay >= botsCost[3]) {
return mostGeodes(oreTotal - botsCost[2], clayTotal - botsCost[3], obsidianTotal, geodeTotal,
oreBot, clayBot, obsidianBot + 1, geodeBot, time + 1, maxTime, botsCost);
}

int best = 0;
if (obsidianBot < botsCost[5] && ore >= botsCost[2] && clay >= botsCost[3]) {
best = Math.max(best, mostGeodes(oreTotal - botsCost[2], clayTotal - botsCost[3], obsidianTotal,
geodeTotal, oreBot, clayBot, obsidianBot + 1, geodeBot, time + 1, maxTime, botsCost));
}
if (clayBot < botsCost[3] && ore >= botsCost[1]) {
best = Math.max(best, mostGeodes(oreTotal - botsCost[1], clayTotal, obsidianTotal, geodeTotal, oreBot,
clayBot + 1, obsidianBot, geodeBot, time + 1, maxTime, botsCost));
}
if (oreBot < 4 && ore >= botsCost[0]) {
best = Math.max(best, mostGeodes(oreTotal - botsCost[0], clayTotal, obsidianTotal, geodeTotal,
oreBot + 1, clayBot, obsidianBot, geodeBot, time + 1, maxTime, botsCost));
}
if (ore <= 4) {
best = Math.max(best, mostGeodes(oreTotal, clayTotal, obsidianTotal, geodeTotal, oreBot, clayBot, obsidianBot,
geodeBot, time + 1, maxTime, botsCost));
}
return best;
}

static void day19(String puzzleInputUri) throws IOException, InterruptedException {
var blueprints = client.send(request.uri((URI.create(puzzleInputUri))).build(), BodyHandlers.ofLines())
.body()
.map(blueprint -> Arrays.stream(blueprint.split("[^0-9]+")).skip(1).mapToInt(Integer::parseInt).toArray())
.collect(Collectors.toList());

int answer1 = 0;
int answer2 = 1;
for (int i = 0; i < blueprints.size(); i++) {
int[] cost = blueprints.get(i);
answer1 += cost[0] * mostGeodes(0, 0, 0, 0, 1, 0, 0, 0, 0, 24, Arrays.copyOfRange(cost, 1, cost.length));
if (i < 3) {
answer2 *= mostGeodes(0, 0, 0, 0, 1, 0, 0, 0, 0, 32, Arrays.copyOfRange(cost, 1, cost.length));
}
}
System.out.printf("Answer 1: %d %nAnswer 2: %d", answer1, answer2);
}

Загадка восемнадцатого дня, на мой вкус, могла бы служить образцом для многих предыдущих загадок.
Минимум возни с парсингом ввода и кодированием очередных обходов графа. Максимум размышлений над поисками решения.
В то же время, само решение — не переусложнённое. Похожей по соотношению интерес/сложность для меня была задачка с обработкой сигналов.

static void day18(String puzzleInputUri) throws IOException, InterruptedException {
List<Point> points = client.send(request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines())
.body()
.map(line -> line.split(","))
.map(xyz -> new Point(Integer.parseInt(xyz[0]), Integer.parseInt(xyz[1]), Integer.parseInt(xyz[2])))
.collect(Collectors.toUnmodifiableList());
long area1 = area(points);
System.out.println("Answer 1: " + area1);
List<Point> voids = findVoids(new Point(0, 0, 0), makeCube(points));
System.out.println("Answer 2: " + (area1 - area(voids)));
}
enum Matter {
AIR, STEAM, LAVA
}
static class Point {
public final int x, y, z;
private final Set<BiFunction<Point, Integer, Point>> makeNeighbor = Set.of(
(p, add) -> new Point(p.x + add, p.y, p.z),
(p, add) -> new Point(p.x, p.y + add, p.z),
(p, add) -> new Point(p.x, p.y, p.z + add)
);
public Point(int x, int y, int z) {
this.x = x;
this.y = y;
this.z = z;
}
public boolean isNeighbor(Point c) {
return Math.abs(this.x - c.x) + Math.abs(this.y - c.y)
+ Math.abs(this.z - c.z) == 1;
}
public List<Point> makeNeighbours() {
return makeNeighbor.stream()
.flatMap(f -> IntStream.of(-1, 1).mapToObj(i -> f.apply(this, i)))
.collect(Collectors.toList());
}
}
static List<Point> findVoids(Point start, int[][][] cube) {
Deque<Point> stack = new ArrayDeque<>();
Set<Point> visited = new HashSet<>();
stack.push(start);
while (!stack.isEmpty()) {
Point cur = stack.pop();
visited.add(cur);
if (cube[cur.x][cur.y][cur.z] == Matter.AIR.ordinal()) {
cube[cur.x][cur.y][cur.z] = Matter.STEAM.ordinal();
for (Point neighbour : cur.makeNeighbours()) {
if (!visited.contains(neighbour) && isBelongCube(neighbour, cube)) {
stack.push(neighbour);
}
}
}
}
return IntStream.range(0, cube.length)
.mapToObj(x -> IntStream.range(0, cube[x].length)
.mapToObj(y -> IntStream.range(0, cube[x][y].length)
.mapToObj(z -> new Point(x, y, z))
)
)
.flatMap(it -> it.flatMap(Function.identity()))
.filter(p -> cube[p.x][p.y][p.z] == Matter.AIR.ordinal())
.collect(Collectors.toList());
}
static boolean isBelongCube(Point p, final int[][][] cube) {
return (p.x >= 0 && p.y >= 0 && p.z >= 0)
&& (p.x < cube.length && p.y < cube[0].length && p.z < cube[0][0].length);
}
static int[][][] makeCube(List<Point> points) {
int maxCoord = points.stream()
.flatMapToInt(p -> IntStream.of(p.x, p.y, p.z))
.summaryStatistics().getMax();
int[][][] cube = new int[maxCoord + 1][maxCoord + 1][maxCoord + 1];
points.forEach(p -> cube[p.x][p.y][p.z] = Matter.LAVA.ordinal());
return cube;
}
static long area(List<Point> points) {
return (points.size() * 6L) - IntStream.range(0, points.size())
.mapToObj(i -> IntStream.range(i, points.size())
.mapToObj(j -> points.get(i).isNeighbor(points.get(j)))
)
.flatMap(b -> b)
.filter(Boolean.TRUE::equals)
.count() * 2;
}

Возможно, для постоянно имеющих дело играми/графикой (и подобным), эта задачка будет выглядеть скучной. Мне же она понравилась (и с капелькой стримоза!).

--- Ссылка на запись ---
https://dimio.org/advent-of-code-2022-day-18.html

Тетрис, больше тетриса! Этот тетрис оказался поголоволомней прошлого. Общая идея была понятна сразу, но «на местности» постоянно вылезали какие-то подводные камешки

Сначала думал пойти через 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);

}

Ну и прочитанное когда-то интервью с создателем оригинального «Тетриса» тоже помогло — там он как раз описывал, почему в игре «сгорают» ряды.

А впереди — день восемнадцатый!

Advent of Code 2022: Day 16

Пропустил пятнадцатый день. Не осилил… Пока что! Что ж, настало время дня шестнадцатого.
Правда, здесь тоже не обошлось без «помощи зала» — часть решения пришлось подсмотреть в интернете. Иначе упорно не желала разгадываться вторая половина загадки.
В целом — задачи становятся интересней (и парсинг ввода не причиняет неудобств, как бывало). Но и времени занимают ощутимо больше, чем первая десятка.
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 void day16(String puzzleInputUri) throws IOException, InterruptedException {
final Pattern vName = Pattern.compile("([A-Z]{2})");
final Pattern vFlow = Pattern.compile("\\d+");

var valves = client.send(request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines()).body()
.map(line -> {
List<String> linkedValves = new ArrayList<>();
var nameMatcher = vName.matcher(line);
nameMatcher.find();
String name = nameMatcher.group();
while (nameMatcher.find()) {
linkedValves.add(nameMatcher.group());
}
var flowMatcher = vFlow.matcher(line);
flowMatcher.find();
int flow = Integer.parseInt(flowMatcher.group());
return new Valve(name, flow, linkedValves);
})
.collect(Collectors.toMap(v -> v.name(), v -> v));

// Part 1
Set<State> states = new HashSet<>();
states.add(new State(new HashMap<>(), valves.get("AA"), null, 0));
for (int minutes = 0; minutes < 30; minutes++) {
Set<State> newStates = new HashSet<>();
for(State s : states) {
long flow = s.openValves().values().stream().mapToLong(f -> f).sum() + s.totalFlow();
if(s.player().flow() > 0 && !s.openValves().containsKey(s.player().name())) {
Map<String, Long> newOpen = new HashMap<>(s.openValves());
newOpen.put(s.player().name(), s.player().flow());
newStates.add(new State(newOpen, s.player(), null, flow));
}
s.player().linked().forEach(name -> newStates.add(new State(s.openValves(), valves.get(name), null, flow)));
}
states = newStates;
}
var answer1 = states.stream().mapToLong(State::totalFlow).max().orElseThrow();
System.out.println("Answer 1: " + answer1);
}

#adventofcode #adventofcode_2022 #программирование

--- Ссылка на запись ---
https://dimio.org/advent-of-code-2022-day-16.html

Advent of Code 2022: Day 14

Да, «тетрис» был определённо приятней вчерашних «скобочек». И концептуально, и в реализации. Старые-добрые циклы-в-циклах — что может быть лучше!? 🙂
Только циклы, приправленные щепоткой стримов, конечно! Впрочем, попытки решить вторую часть через стрим — не увенчались успехом, увы. Приступ стримоза отступил и циклы вошли в свои права.
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;
}

static void day14(String puzzleInputUri) throws IOException, InterruptedException {
boolean[][] gameField = new boolean[1000][1000];
var maxY = client.send(request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines())
.body()
.mapToInt(scanLine -> drawRock(scanLine, gameField))
.max().orElse(0);

int answer = 0;
drawRock( "0," + (maxY + 2) + " -> " + (gameField[0].length - 1) + "," + (maxY + 2), gameField);
while (pourSand(maxY, gameField)) {
answer++;
}
System.out.println(answer);
}

Капля стримоза
Первая часть загадки через стрим решилась без особых проблем, и даже выглядела не слишком страшно:
var sandCnt = client.send(request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines())
.body()
.mapToInt(scanLine -> drawRock(scanLine, gameField))
.max()
.stream().mapToObj(mY ->
IntStream.rangeClosed(0, gameField.length)
.mapToObj(i -> pourSand(mY, gameField))
.takeWhile(Boolean.TRUE::equals)
.count()
)
.findAny()
.orElseThrow();
System.out.println(sandCnt);
А вот со второй — возникли проблемы. Попытки подсунуть в стрим «пол пещеры» в таком виде:
.peek(maxY -> drawRock( "0," + (maxY + 2) + " -> " + (gameField[0].length - 1) + "," + (maxY + 2), gameField))
не приводили к успеху — ответ никак не сходился. Пришлось вернуться к циклам.

#adventofcode #adventofcode_2022 #программирование

--- Ссылка на запись ---
https://dimio.org/advent-of-code-2022-day-14.html