commit b4586e83a0e12f8a320c8625eff2288860a36618
parent d12876e85c885c2f3e6e00241272241689e33960
Author: Martin Ashby <martin@ashbysoft.com>
Date: Sat, 4 Jan 2025 16:31:00 +0000
Day 15 Pt2
Diffstat:
1 file changed, 365 insertions(+), 0 deletions(-)
diff --git a/src/main/java/day15_pt2.java b/src/main/java/day15_pt2.java
@@ -0,0 +1,365 @@
+import java.nio.file.Files;
+import java.nio.file.Path;
+import java.io.IOException;
+import java.util.*;
+import java.util.stream.*;
+import java.util.regex.*;
+
+
+class day15_pt2 {
+
+ record Point(int x, int y) implements Comparable<Point> {
+ Point add(Vec v) {
+ return new Point(this.x + v.x, this.y + v.y);
+ }
+ @Override
+ public int compareTo(Point other) {
+ var res = Integer.valueOf(this.x).compareTo(Integer.valueOf(other.x));
+ if (res != 0) return res;
+ return Integer.valueOf(this.y).compareTo(Integer.valueOf(other.y));
+ }
+ }
+ record Vec(int x, int y) {}
+ record Box(int label) {}
+ enum Direction{
+ North('^'),East('>'),South('v'),West('<');
+ final char c;
+ Direction(char c) { this.c = c; }
+
+ Vec unitVec() {
+ return switch (this) {
+ case North -> new Vec(0, -1);
+ case East -> new Vec(1, 0) ;
+ case South -> new Vec(0, 1);
+ case West -> new Vec(-1, 0);
+ };
+ }
+ static Direction from(char c) {
+ for (var d: Direction.values()) {
+ if (d.c == c) return d;
+ }
+ throw new IllegalArgumentException("unrecognised direction %c".formatted(c));
+ }
+ }
+ public static void main(String[] args) throws IOException {
+ var input = Files.readAllLines(Path.of(args[0]));
+ var spl = input.indexOf("");
+ var grid = input.subList(0, spl);
+
+ for (var y=0;y<grid.size();y++) {
+ var line = grid.get(y);
+ var sb = new StringBuilder();
+ for (var ch : line.chars().toArray()) {
+ switch (ch) {
+ case '@':
+ sb.append("@.");
+ break;
+ case '#':
+ sb.append("##");
+ break;
+ //tehsoieshfeishfe
+ case 'O':
+ sb.append("[]");
+ break;
+ case '.':
+ sb.append("..");
+ break;
+ }
+ }
+ grid.set(y, sb.toString());
+ }
+
+ // for (var line : grid) {
+ // System.out.println(line);
+ // }
+
+ var inst = input.subList(spl+1, input.size()).stream().collect(Collectors.joining(""));
+ var height = grid.size();
+ var width = grid.get(0).length();
+ Point robotPos = null;
+ var boxes = new MSet<Box>();
+ var boxLabel = 0;
+ var boxPositions = new BMap<Point,Box>();
+ var walls = new MSet<Point>();
+ for (var y=0;y<height;y++) {
+ for (var x=0;x<width;x++) {
+ var p = new Point(x, y);
+ var val = gv(grid, p);
+ if (val == '@') {
+ robotPos = p;
+ } else if (val == '[') {
+ var box = new Box(boxLabel++);
+ boxes.add(box);
+ boxPositions.put(p, box);
+ boxPositions.put(p.add(Direction.East.unitVec()), box);
+ } else if (val == '#') {
+ walls.add(p);
+ }
+ }
+ }
+ //System.out.printf("RobotPos: %s\n", robotPos);
+ for (var ch : inst.chars().toArray()) {
+ var d = Direction.from((char)ch);
+ var np = robotPos.add(d.unitVec());
+ if (walls.contains(np)) {
+ // do nothing
+ } else if (boxPositions.containsKey(np)) {
+ var box = boxPositions.get(np);
+ var newBoxPositions = moveBox(box, d, boxPositions, walls);
+ if (newBoxPositions.isEmpty()) {
+ // do nothing
+ } else {
+ // Replace the moved boxes in the boxPositions map
+ var vals = newBoxPositions.get().values();
+ vals.forEach(boxPositions::reverseRemove);
+ boxPositions.putAll(newBoxPositions.get());
+ robotPos = np;
+ }
+ } else {
+ robotPos = np;
+ }
+ // Debugging...
+ // System.out.printf("instruction: %c\n", ch);
+ // for (var y=0;y<height;y++) {
+ // for (var x=0;x<width;x++) {
+ // var p = new Point(x, y);
+ // if (walls.contains(p)) {
+ // System.out.print('#');
+ // } else if (boxPositions.containsKey(p)) {
+ // System.out.print("[]");
+ // x++; // skip te next we know what it is
+ // } else if (p.equals(robotPos)) {
+ // System.out.print('@');
+ // } else {
+ // System.out.print('.');
+ // }
+ // }
+ // System.out.print('\n');
+ // }
+ // System.out.print('\n');
+ }
+ var score = boxes.stream()
+ .map(boxPositions::reverseGet)
+ .map(pts -> {
+ var al = new ArrayList<>(pts);
+ Collections.sort(al);
+ return al.get(0);
+ })
+ .mapToLong(pt -> pt.x + 100 * pt.y)
+ .sum();
+ System.out.printf("Day 15 pt2: %d\n", score);
+ }
+ // Returns map of _new_ box positions of any boxes that moved...
+ static Optional<BMap<Point,Box>> moveBox(Box box,
+ Direction d,
+ BMap<Point, Box> boxPositions,
+ MSet<Point> walls) {
+ //System.out.printf("trying to move box %s\n", box);
+ var bPos = boxPositions.reverseGet(box);
+ var bNP = bPos.stream().map(p -> p.add(d.unitVec())).collect(Collectors.toSet());
+ if (walls.containsAny(bNP)) {
+ return Optional.empty();
+ } else {
+ var collidingBoxes = boxPositions.getMulti(bNP).stream()
+ .filter(b2 -> !b2.equals(box))
+ .collect(Collectors.toSet());
+ if (collidingBoxes.isEmpty()) {
+ var newPositions = new BMap<Point, Box>();
+ bNP.forEach(pp -> newPositions.put(pp, box));
+ return Optional.of(newPositions);
+ } else {
+ return collidingBoxes.stream().map(b2 -> moveBox(b2, d, boxPositions, walls))
+ .reduce((m1, m2) -> {
+ if (m1.isEmpty() || m2.isEmpty()) return Optional.empty();
+ var res = new BMap<Point,Box>();
+ res.putAll(m1.get());
+ res.putAll(m2.get());
+ return Optional.of(res);
+ }).get()
+ .map(newPositions -> {
+ bNP.forEach(pp -> newPositions.put(pp, box));
+ return newPositions;
+ });
+ }
+ }
+ }
+
+ static int gv(List<String> grid, Point p) {
+ var height = grid.size();
+ if (p.y < 0 || p.y >= height) return '#'; // treat out of bounds as a wall
+ var width = grid.get(0).length();
+ if (p.x < 0 || p.x >= width) return '#';
+ return grid.get(p.y).charAt(p.x);
+ }
+}
+
+class BMap<K, V> implements Map<K, V> {
+ final Map<K, V> forward;
+ final Map<V, Set<K>> backward;
+
+ public BMap() {
+ this.forward = new HashMap<>();
+ this.backward = new HashMap<>();
+ }
+
+ @Override
+ public int size() {
+ return forward.size();
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return forward.isEmpty();
+ }
+
+ @Override
+ public boolean containsKey(Object key) {
+ return forward.containsKey(key);
+ }
+
+ public boolean containsAnyKey(Collection<K> keys) {
+ return keys.stream().anyMatch(this::containsKey);
+ }
+
+ @Override
+ public boolean containsValue(Object value) {
+ return backward.containsKey(value);
+ }
+
+ @Override
+ public V get(Object key) {
+ return forward.get(key);
+ }
+
+ public Set<V> getMulti(Collection<K> keys) {
+ return keys.stream().map(this::get).filter(Objects::nonNull).collect(Collectors.toSet());
+ }
+
+ @Override
+ public V put(K key, V value) {
+ var res = forward.put(key, value);
+ backward.computeIfAbsent(value, k -> new HashSet<>()).add(key);
+ return res;
+ }
+
+ @Override
+ public V remove(Object key) {
+ var res = forward.remove(key);
+ backward.computeIfAbsent(res, k -> new HashSet<>()).remove(key);
+ return res;
+ }
+
+ @Override
+ public void putAll(Map<? extends K, ? extends V> m) {
+ m.forEach(this::put);
+ }
+
+ @Override
+ public void clear() {
+ forward.clear();
+ backward.clear();
+ }
+
+ @Override
+ public Set<K> keySet() {
+ return forward.keySet();
+ }
+
+ @Override
+ public Collection<V> values() {
+ return forward.values();
+ }
+
+ @Override
+ public Set<Entry<K, V>> entrySet() {
+ return forward.entrySet();
+ }
+
+ public Set<K> reverseGet(V value) {
+ return backward.get(value);
+ }
+
+ public void reverseRemove(V value) {
+ var vals = backward.remove(value);
+ if (vals != null) {
+ vals.stream().forEach(forward::remove);
+ }
+ }
+}
+
+class MSet<K> implements Set<K> {
+ private final Set<K> internal;
+
+ public MSet() {
+ internal = new HashSet<>();
+ }
+
+ @Override
+ public int size() {
+ return internal.size();
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return internal.isEmpty();
+ }
+
+ @Override
+ public boolean contains(Object o) {
+ return internal.contains(o);
+ }
+
+ @Override
+ public Iterator<K> iterator() {
+ return internal.iterator();
+ }
+
+ @Override
+ public Object[] toArray() {
+ return internal.toArray();
+ }
+
+ @Override
+ public <T> T[] toArray(T[] a) {
+ return internal.toArray(a);
+ }
+
+ @Override
+ public boolean add(K k) {
+ return internal.add(k);
+ }
+
+ @Override
+ public boolean remove(Object o) {
+ return internal.remove(o);
+ }
+
+ @Override
+ public boolean containsAll(Collection<?> c) {
+ return internal.containsAll(c);
+ }
+
+ public boolean containsAny(Collection<? extends K> c) {
+ return c.stream().anyMatch(internal::contains);
+ }
+
+ @Override
+ public boolean addAll(Collection<? extends K> c) {
+ return internal.addAll(c);
+ }
+
+ @Override
+ public boolean retainAll(Collection<?> c) {
+ return internal.retainAll(c);
+ }
+
+ @Override
+ public boolean removeAll(Collection<?> c) {
+ return internal.removeAll(c);
+ }
+
+ @Override
+ public void clear() {
+ internal.clear();
+ }
+}
