aoc2024

commit e1652e565d5220b01a736e8722b3b5e8d8ba342c
parent edf606b9ef2669d72a7005c064489222248d4653
Author: Martin Ashby <martin@ashbysoft.com>
Date:   Thu,  2 Jan 2025 08:49:50 +0000

Day 12, pt2

Diffstat:
A
src/main/java/day12_pt2.java
 | 
111
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 111 insertions(+), 0 deletions(-)
diff --git a/src/main/java/day12_pt2.java b/src/main/java/day12_pt2.java
@@ -0,0 +1,111 @@
+import java.nio.file.Files;
+import java.nio.file.Path;
+import java.io.IOException;
+import java.util.*;
+import java.util.stream.*;
+
+class day12_pt2 {
+  record Point(int x, int y) {
+    Point add(Vec v) {
+      return new Point(this.x + v.x, this.y + v.y);
+    }
+  }
+  record Vec(int x, int y) {}
+  static Vec[] DIRS = new Vec[]{
+    new Vec(0, 1),
+    new Vec(1, 0),
+    new Vec(0, -1),
+    new Vec(-1, 0)
+  };
+  static Vec[][] DIRPAIRS = new Vec[][]{
+    new Vec[]{new Vec(0, 1),  new Vec(1, 0)},
+    new Vec[]{new Vec(1, 0),  new Vec(0, -1)},
+    new Vec[]{new Vec(0, -1), new Vec(-1, 0)},
+    new Vec[]{new Vec(-1, 0), new Vec(0, 1)},
+  };
+  public static void main(String[] args) throws IOException {
+    var grid = Files.readAllLines(Path.of(args[0]));
+    // iterate the grid. Recursively find regions and their perimeters.
+    var pts = new HashSet<Point>();
+    var nRegions = 0;
+    var regions = new HashMap<Integer, HashSet<Point>>();
+    int height = grid.size();
+    int width = grid.get(0).length();
+    for (int y=0; y<height; y++) {
+      for (int x=0; x<width; x++) {
+        var pt = new Point(x, y);
+        if (pts.contains(pt)) continue;
+        var region = expandRegion(grid, pt);
+        regions.put(nRegions++, region);
+        pts.addAll(region);
+      }
+    }
+    
+    var res = regions.entrySet().stream().mapToLong(e -> {
+      var region = e.getValue();
+      var ss = sides(grid, region);
+      System.out.printf("Region %d: size: %d sides: %d\n", e.getKey(), e.getValue().size(), ss);
+      return ss * region.size();
+    })
+    .sum();
+    System.out.printf("Day 12, pt1: %d\n", res);
+  }
+
+  static long sides(List<String> grid, HashSet<Point> region) {
+    return region.stream()
+      .mapToLong(p -> {
+        var v = gv(grid, p);
+        // consider pairs of cardinal directions, e.g. N+E. Look at the squares in these directions
+        // if both are not the same as us; then that's definitely a corner. +1;
+        // if one's the same and one's not, we're not a corner
+        // if both are the smae as us, look at the diagnoal. 
+        //   if it's the same, not a corner
+        //   if it's different, we're an inside corner.
+
+        // Oo = 0 corner  Ox = 1 corner  Ox = 1 corner  Ox = 1 corner Oo = 0 corner
+        // oo             oo             xo             xx            xx
+        return Arrays.stream(DIRPAIRS).mapToLong(dp -> {
+          var p1 = p.add(dp[0]);
+          var p2 = p.add(dp[1]);
+          var v1_m = gv(grid, p1) == v; 
+          var v2_m = gv(grid, p2) == v;
+          if (!v1_m && !v2_m) {
+            return 1l;
+          } else if (v1_m && v2_m){
+            var p3 = p2.add(dp[0]);
+            var v3_m = gv(grid, p3) == v;
+            if (v3_m) {
+              return 0l;
+            } else {
+              return 1l;
+            }
+          } else {
+            return 0l;
+          }
+        }).sum();
+      })
+      .sum();
+  }
+  static HashSet<Point> expandRegion(List<String> grid, Point p) {
+    var res = new HashSet<Point>();
+    expandRegionInternal(grid, p, gv(grid, p), res);
+    return res;
+  }
+  static void expandRegionInternal(List<String> grid, Point p, int val, HashSet<Point> region) {
+    if (region.contains(p)) return;
+    region.add(p);
+    Arrays.stream(DIRS).forEach(d -> {
+      var pp = p.add(d);
+      if (gv(grid, pp) == val) {
+        expandRegionInternal(grid, pp, val, region);
+      }
+    });
+  }
+  static int gv(List<String> grid, Point p) {
+    var height = grid.size();
+    if (p.y < 0 || p.y >= height) return -1;
+    var width = grid.get(0).length();
+    if (p.x < 0 || p.x >= width) return -1;
+    return grid.get(p.y).charAt(p.x);
+  }
+}