aoc2024

Advent of Code 2024
Log | Files | Refs | README

day15_pt2.java (9536B)

      1 import java.nio.file.Files;
      2 import java.nio.file.Path;
      3 import java.io.IOException;
      4 import java.util.*;
      5 import java.util.stream.*;
      6 import java.util.regex.*;
      7 
      8 
      9 class day15_pt2 {
     10   
     11   record Point(int x, int y) implements Comparable<Point> {
     12     Point add(Vec v) {
     13       return new Point(this.x + v.x, this.y + v.y);
     14     }
     15     @Override
     16     public int compareTo(Point other) {
     17       var res = Integer.valueOf(this.x).compareTo(Integer.valueOf(other.x));
     18       if (res != 0) return res;
     19       return Integer.valueOf(this.y).compareTo(Integer.valueOf(other.y));
     20     }
     21   }
     22   record Vec(int x, int y) {}
     23   record Box(int label) {}
     24   enum Direction{
     25     North('^'),East('>'),South('v'),West('<');
     26     final char c;
     27     Direction(char c) { this.c = c; }
     28     
     29     Vec unitVec() {
     30       return switch (this) {
     31         case North -> new Vec(0, -1);
     32         case East -> new Vec(1, 0)  ;
     33         case South -> new Vec(0, 1);
     34         case West -> new Vec(-1, 0);
     35       };
     36     }
     37     static Direction from(char c) {
     38       for (var d: Direction.values()) {
     39         if (d.c == c) return d;
     40       }
     41       throw new IllegalArgumentException("unrecognised direction %c".formatted(c));
     42     }
     43   }
     44   public static void main(String[] args) throws IOException {
     45     var input = Files.readAllLines(Path.of(args[0]));
     46     var spl = input.indexOf("");
     47     var grid = input.subList(0, spl);
     48 
     49     for (var y=0;y<grid.size();y++) {
     50       var line = grid.get(y);
     51       var sb = new StringBuilder();
     52       for (var ch : line.chars().toArray()) {
     53         switch (ch) {
     54           case '@': 
     55             sb.append("@.");
     56             break;
     57           case '#':
     58             sb.append("##");
     59             break;
     60             //tehsoieshfeishfe
     61           case 'O':
     62             sb.append("[]");
     63             break;
     64           case '.':
     65             sb.append("..");
     66             break;
     67         }
     68       }
     69       grid.set(y, sb.toString());
     70     }
     71     
     72     // for (var line : grid) {
     73     //   System.out.println(line);
     74     // }
     75     
     76     var inst = input.subList(spl+1, input.size()).stream().collect(Collectors.joining(""));
     77     var height = grid.size();
     78     var width = grid.get(0).length();
     79     Point robotPos = null;
     80     var boxes = new MSet<Box>();
     81     var boxLabel = 0;
     82     var boxPositions = new BMap<Point,Box>();
     83     var walls = new MSet<Point>();
     84     for (var y=0;y<height;y++) {
     85       for (var x=0;x<width;x++) {
     86         var p = new Point(x, y);
     87         var val = gv(grid, p);
     88         if (val == '@') {
     89           robotPos = p; 
     90         } else if (val == '[') {
     91           var box = new Box(boxLabel++);
     92           boxes.add(box);
     93           boxPositions.put(p, box);
     94           boxPositions.put(p.add(Direction.East.unitVec()), box);
     95         } else if (val == '#') {
     96           walls.add(p);
     97         }
     98       }
     99     }
    100     //System.out.printf("RobotPos: %s\n", robotPos);
    101     for (var ch : inst.chars().toArray()) {
    102       var d = Direction.from((char)ch);
    103       var np = robotPos.add(d.unitVec());
    104       if (walls.contains(np)) {
    105         // do nothing
    106       } else if (boxPositions.containsKey(np)) {
    107         var box = boxPositions.get(np);
    108         var newBoxPositions = moveBox(box, d, boxPositions, walls);
    109         if (newBoxPositions.isEmpty()) {
    110           // do nothing
    111         } else {
    112           // Replace the moved boxes in the boxPositions map
    113           var vals = newBoxPositions.get().values();
    114           vals.forEach(boxPositions::reverseRemove);
    115           boxPositions.putAll(newBoxPositions.get());
    116           robotPos = np;
    117         }
    118       } else {
    119         robotPos = np;
    120       }
    121       // Debugging...
    122        // System.out.printf("instruction: %c\n", ch);
    123        // for (var y=0;y<height;y++) {
    124        //   for (var x=0;x<width;x++) {
    125        //     var p = new Point(x, y);
    126        //     if (walls.contains(p)) {
    127        //       System.out.print('#');
    128        //     } else if (boxPositions.containsKey(p)) {
    129        //       System.out.print("[]");
    130        //       x++; // skip te next we know what it is
    131        //     } else if (p.equals(robotPos)) {
    132        //       System.out.print('@');
    133        //     } else {
    134        //       System.out.print('.');
    135        //     }
    136        //   }
    137        //   System.out.print('\n');
    138        // }
    139        // System.out.print('\n');
    140     }
    141     var score = boxes.stream()
    142       .map(boxPositions::reverseGet)
    143       .map(pts -> {
    144         var al = new ArrayList<>(pts);
    145         Collections.sort(al);
    146         return al.get(0);
    147       })
    148       .mapToLong(pt -> pt.x + 100 * pt.y)
    149       .sum();
    150     System.out.printf("Day 15 pt2: %d\n", score);
    151   }
    152   // Returns map of _new_ box positions of any boxes that moved...
    153   static Optional<BMap<Point,Box>> moveBox(Box box,
    154                                            Direction d,
    155                                            BMap<Point, Box> boxPositions,
    156                                            MSet<Point> walls) {
    157     //System.out.printf("trying to move box %s\n", box);
    158     var bPos = boxPositions.reverseGet(box);
    159     var bNP = bPos.stream().map(p -> p.add(d.unitVec())).collect(Collectors.toSet());
    160     if (walls.containsAny(bNP)) {
    161       return Optional.empty();
    162     } else {
    163       var collidingBoxes = boxPositions.getMulti(bNP).stream()
    164               .filter(b2 -> !b2.equals(box))
    165               .collect(Collectors.toSet());
    166       if (collidingBoxes.isEmpty()) {
    167         var newPositions = new BMap<Point, Box>();
    168         bNP.forEach(pp -> newPositions.put(pp, box));
    169         return Optional.of(newPositions);
    170       } else {
    171         return collidingBoxes.stream().map(b2 -> moveBox(b2, d, boxPositions, walls))
    172                 .reduce((m1, m2) -> {
    173                   if (m1.isEmpty() || m2.isEmpty()) return Optional.empty();
    174                   var res = new BMap<Point,Box>();
    175                   res.putAll(m1.get());
    176                   res.putAll(m2.get());
    177                   return Optional.of(res);
    178                 }).get()
    179                 .map(newPositions -> {
    180                   bNP.forEach(pp -> newPositions.put(pp, box));
    181                   return newPositions;
    182                 });
    183       }
    184     }
    185   }
    186 
    187   static int gv(List<String> grid, Point p) {
    188     var height = grid.size();
    189     if (p.y < 0 || p.y >= height) return '#'; // treat out of bounds as a wall
    190     var width = grid.get(0).length();
    191     if (p.x < 0 || p.x >= width) return '#';
    192     return grid.get(p.y).charAt(p.x);
    193   }
    194 }
    195 
    196 class BMap<K, V> implements Map<K, V> {
    197   final Map<K, V> forward;
    198   final Map<V, Set<K>> backward;
    199 
    200   public BMap() {
    201     this.forward = new HashMap<>();
    202     this.backward = new HashMap<>();
    203   }
    204 
    205   @Override
    206   public int size() {
    207     return forward.size();
    208   }
    209 
    210   @Override
    211   public boolean isEmpty() {
    212     return forward.isEmpty();
    213   }
    214 
    215   @Override
    216   public boolean containsKey(Object key) {
    217     return forward.containsKey(key);
    218   }
    219 
    220   public boolean containsAnyKey(Collection<K> keys) {
    221     return keys.stream().anyMatch(this::containsKey);
    222   }
    223 
    224   @Override
    225   public boolean containsValue(Object value) {
    226     return backward.containsKey(value);
    227   }
    228 
    229   @Override
    230   public V get(Object key) {
    231     return forward.get(key);
    232   }
    233 
    234   public Set<V> getMulti(Collection<K> keys) {
    235     return keys.stream().map(this::get).filter(Objects::nonNull).collect(Collectors.toSet());
    236   }
    237 
    238   @Override
    239   public V put(K key, V value) {
    240     var res = forward.put(key, value);
    241     backward.computeIfAbsent(value, k -> new HashSet<>()).add(key);
    242     return res;
    243   }
    244 
    245   @Override
    246   public V remove(Object key) {
    247     var res = forward.remove(key);
    248     backward.computeIfAbsent(res, k -> new HashSet<>()).remove(key);
    249     return res;
    250   }
    251 
    252   @Override
    253   public void putAll(Map<? extends K, ? extends V> m) {
    254     m.forEach(this::put);
    255   }
    256 
    257   @Override
    258   public void clear() {
    259     forward.clear();
    260     backward.clear();
    261   }
    262 
    263   @Override
    264   public Set<K> keySet() {
    265     return forward.keySet();
    266   }
    267 
    268   @Override
    269   public Collection<V> values() {
    270     return forward.values();
    271   }
    272 
    273   @Override
    274   public Set<Entry<K, V>> entrySet() {
    275     return forward.entrySet();
    276   }
    277 
    278   public Set<K> reverseGet(V value) {
    279     return backward.get(value);
    280   }
    281 
    282   public void reverseRemove(V value) {
    283     var vals = backward.remove(value);
    284     if (vals != null) {
    285       vals.stream().forEach(forward::remove);
    286     }
    287   }
    288 }
    289 
    290 class MSet<K> implements Set<K> {
    291   private final Set<K> internal;
    292 
    293   public MSet() {
    294     internal = new HashSet<>();
    295   }
    296 
    297   @Override
    298   public int size() {
    299     return internal.size();
    300   }
    301 
    302   @Override
    303   public boolean isEmpty() {
    304     return internal.isEmpty();
    305   }
    306 
    307   @Override
    308   public boolean contains(Object o) {
    309     return internal.contains(o);
    310   }
    311 
    312   @Override
    313   public Iterator<K> iterator() {
    314     return internal.iterator();
    315   }
    316 
    317   @Override
    318   public Object[] toArray() {
    319     return internal.toArray();
    320   }
    321 
    322   @Override
    323   public <T> T[] toArray(T[] a) {
    324     return internal.toArray(a);
    325   }
    326 
    327   @Override
    328   public boolean add(K k) {
    329     return internal.add(k);
    330   }
    331 
    332   @Override
    333   public boolean remove(Object o) {
    334     return internal.remove(o);
    335   }
    336 
    337   @Override
    338   public boolean containsAll(Collection<?> c) {
    339     return internal.containsAll(c);
    340   }
    341 
    342   public boolean containsAny(Collection<? extends K> c) {
    343     return c.stream().anyMatch(internal::contains);
    344   }
    345 
    346   @Override
    347   public boolean addAll(Collection<? extends K> c) {
    348     return internal.addAll(c);
    349   }
    350 
    351   @Override
    352   public boolean retainAll(Collection<?> c) {
    353     return internal.retainAll(c);
    354   }
    355 
    356   @Override
    357   public boolean removeAll(Collection<?> c) {
    358     return internal.removeAll(c);
    359   }
    360 
    361   @Override
    362   public void clear() {
    363     internal.clear();
    364   }
    365 }