aoc2024

Advent of Code 2024
Log | Files | Refs | README

day16_pt1.java (4124B)

      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 class day16_pt1 {
      9   enum Dir{
     10     North,
     11     East,
     12     South,
     13     West;
     14 
     15     Vec unitVec() {
     16       return switch (this) {
     17         case North -> new Vec(0, -1);
     18         case East -> new Vec(1, 0);
     19         case South -> new Vec(0, 1);
     20         case West -> new Vec(-1, 0);
     21       };
     22     }
     23     Dir opp() {
     24       return switch(this) {
     25         case North -> South;
     26         case East -> West;
     27         case South -> North;
     28         case West -> East;
     29       };
     30     }
     31     // there's a better way with matrix multiplication 
     32     // but I'm not going to write it r.n.
     33     int nr(Dir other) {  
     34       return switch (this) {
     35         case North -> switch (other) {
     36           case North -> 0;
     37           case East -> 1;
     38           case South -> 2;
     39           case West -> 1;
     40         };
     41         case East -> switch (other) {
     42           case North -> 1;
     43           case East -> 0;
     44           case South -> 1;
     45           case West -> 2;
     46         };
     47         case South -> switch (other) {
     48           case North -> 2;
     49           case East -> 1;
     50           case South -> 0;
     51           case West -> 1;
     52         };
     53         case West -> switch (other) {
     54           case North -> 1;
     55           case East -> 2;
     56           case South -> 1;
     57           case West -> 0;
     58         };
     59       };
     60     }
     61   }
     62   record Point(int x, int y) {
     63     Point add(Vec v){
     64       return new Point(this.x + v.x, this.y + v.y);
     65     }
     66   }
     67   record Vec(int x, int y){}
     68   public static void main(String[] args) throws IOException {
     69     var grid = Files.readAllLines(Path.of(args[0]));
     70     var height = grid.size();
     71     var width = grid.get(0).length();
     72     var scores = new int[height][width];
     73     Point start = null;
     74     Point end = null;
     75     for (var y=0; y<height; y++) {
     76       for (var x=0; x<width; x++) {
     77         scores[y][x] = Integer.MAX_VALUE;
     78         var p = new Point(x, y);
     79         var ch = gv(grid, p);
     80         switch (ch) {
     81           case 'S':
     82             start = p;
     83             break;
     84           case 'E':
     85             scores[y][x] = 0;
     86             end = p;
     87             break;
     88         }
     89       }
     90     }
     91         
     92     // From the start, recurse backwards over the whole grid
     93     // to find hte scores to each point
     94     var dirOut = new Dir[]{null}; // surely there's a neater way
     95     for (var dir : Dir.values()) {
     96       var pp = end.add(dir.unitVec());
     97       scores[pp.y][pp.x] = 1;
     98       markScores(grid, pp, dir.opp(), scores, dirOut);
     99     }
    100     
    101     // debug
    102     // for (int y=0;y<height;y++) {
    103     //   for (int x=0;x<width;x++) {
    104     //     var ss = scores[y][x];
    105     //     if (ss < Integer.MAX_VALUE) {
    106     //       System.out.printf("|%05d", ss);
    107     //     } else {
    108     //       System.out.printf("|     ", ss);
    109     //     }
    110         
    111     //   }
    112     //   System.out.print('\n');
    113     // }
    114     // Now simply read the score from the start point 
    115     var res = scores[start.y][start.x];
    116     // and twiddle for any 
    117     // initial rotation we had to do
    118     var dd = dirOut[0];
    119     res += 1000 * dd.nr(Dir.East);
    120     System.out.printf("Day 16, pt1: %d\n", res);
    121   }
    122 
    123   static void markScores(List<String> grid, Point cur, Dir curDir, int[][] scores, Dir[] dirOut) {
    124     var curScore = scores[cur.y][cur.x];
    125     for (var dir : Dir.values()) {
    126       var pp = cur.add(dir.unitVec());
    127       var ch = gv(grid, pp);
    128       switch (ch) {
    129         case '#': break; // Wall, do nothing.
    130         case 'S': 
    131         case '.': 
    132           int add = 1 + dir.opp().nr(curDir) * 1000;
    133           var s = curScore + add;
    134           var ss = scores[pp.y][pp.x];
    135           if (s < ss) {
    136               if (ch == 'S')
    137                 dirOut[0] = dir.opp(); 
    138               scores[pp.y][pp.x] = s;
    139               markScores(grid, pp, dir.opp(), scores, dirOut);
    140           }
    141           break;
    142       }
    143     }
    144   }
    145   
    146   static int gv(List<String> grid, Point p) {
    147     var height = grid.size();
    148     if (p.y < 0 || p.y >= height) return -1;
    149     var width = grid.get(0).length();
    150     if (p.x < 0 || p.x >= width) return -1;
    151     return grid.get(p.y).charAt(p.x);
    152   }
    153 }