Advent of Code 2022: Day 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 + '}';
}
}
static Vertex findEndPoint(Vertex from, char[][] map) {
Set<Vertex> visited = new HashSet<>();
char endMark = 'E';
char nextTraversableMarkAfter_z = '{';
int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int mapHeight = map.length;
int mapWidth = map[0].length;
Vertex start = new Vertex(from.x, from.y, from.dist, from.height);
Queue<Vertex> queue = new ArrayDeque<>();
queue.add(start);
visited.add(start);
while (!queue.isEmpty()) {
Vertex current = queue.poll();
for (int[] direction : directions) {
int nextX = Math.max(current.x + direction[1], 0);
int nextY = Math.max(current.y + direction[0], 0);
if (nextX < mapWidth && nextY < mapHeight) {
Vertex next = new Vertex(nextX, nextY, current.dist + 1, map[nextY][nextX]);
if (!visited.contains(next) && (next.height - current.height <= 1 || current.height == 'S')) {
if (next.height == endMark) {
map[next.y][next.x] = nextTraversableMarkAfter_z;
continue;
}
if (next.height == nextTraversableMarkAfter_z) {
map[next.y][next.x] = endMark;
return next;
}
queue.add(next);
visited.add(next);
}
}
}
}
return new Vertex(from.x, from.y, from.dist, '#');
}
static void day12(String puzzleInputUri) throws IOException, InterruptedException {
char[][] mapArray = client.send(request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines())
.body()
.map(String::toCharArray)
.toArray(char[][]::new);
System.out.println("Answer 1: " + findEndPoint(new Vertex(0,20,0, 'S'), mapArray));
Vertex answer2 = IntStream.range(0, mapArray.length)
.mapToObj(y -> Map.entry(y, mapArray[y]))
.flatMap(row -> IntStream.range(0, row.getValue().length)
.mapToObj(x -> Stream.of(new Vertex(x, row.getKey(), 0, row.getValue()[x])))
)
.flatMap(Function.identity())
.filter(vertex ->
Set.of('a', 'S').contains(vertex.height)
&& (
(vertex.x == 0 || vertex.x == mapArray[0].length - 1)
|| (vertex.y == 0 || vertex.y == mapArray.length - 1)
)
)
.map(entrance -> findEndPoint(entrance, mapArray))
.filter(v -> v.height != '#')
.min(Comparator.comparingInt(v -> v.dist))
.orElseThrow();
System.out.println("Answer 2: " + answer2);
}
Для решения второй части — была мысль пойти от E в направлении ближайших a, но всё равно пришлось бы перебрать их все, чтобы сравнить длину пройденного пути.
Начать дискуссию