brute force dead end

SimonBaars · SimonBaars · commit 370224e73bf1 · 2022-12-16T06:49:00.000+01:00
diff --git a/src/main/java/com/sbaars/adventofcode/year22/days/Day16.java b/src/main/java/com/sbaars/adventofcode/year22/days/Day16.java
@@ -14,6 +14,15 @@ public class Day16 extends Day2022 {
 
   public Day16() {
     super(16);
+    this.example = 1;
+    this.in = dayStream().map(s -> {
+      try {
+        return readString(s, "Valve %s has flow rate=%n; tunnels lead to valves %s", Valve.class);
+      } catch (IllegalStateException e) {
+        return readString(s, "Valve %s has flow rate=%n; tunnel leads to valve %s", Valve.class);
+      }
+    }).toList();
+    this.indices = IntStream.range(0, in.size()).boxed().collect(Collectors.toMap(i -> this.in.get(i).name, i -> i));
   }
 
   public static void main(String[] args) {
@@ -26,24 +35,24 @@ public static void main(String[] args) {
 //    d.submitPart2();
   }
 
+  private final List<Valve> in;
+  private final Map<String, Integer> indices;
+
   public record Valve(String name, long flow, String others) {}
-  public record State(Map<String, Long> open, List<String> path, int index) {}
+  public record State(Map<String, Long> open, int mins, int index) {}
 
   @Override
   public Object part1() {
-    List<Valve> in = dayStream().map(s -> {
-      try {
-        return readString(s, "Valve %s has flow rate=%n; tunnels lead to valves %s", Valve.class);
-      } catch (IllegalStateException e) {
-        return readString(s, "Valve %s has flow rate=%n; tunnel leads to valve %s", Valve.class);
-      }
-    }).toList();
-    Map<String, Integer> indices = IntStream.range(0, in.size()).boxed().collect(Collectors.toMap(i -> this.in.get(i).name, i -> i));
-    List<State> states = new ArrayList<>();
-    return walk(0, 0, new HashMap<>(), new HashSet<>());
+    return walk(0, 0, new HashMap<>(), new HashMap<>());
   }
 
-  private long walk(int mins, int index, Map<String, Long> open, Set<String> visited) {
+  Map<State, Long> visited = new HashMap<>();
+
+  private long walk(int mins, int index, Map<String, Long> open, Map<State, Long> visited) {
+    State st = new State(open, mins, index);
+    if(visited.containsKey(st)){
+      return visited.get(st);
+    }
     long flow = open.values().stream().mapToLong(e -> e).sum();
     if(mins == 30){
 //      System.out.println(Arrays.toString(open.keySet().toArray()));
@@ -54,9 +63,11 @@ private long walk(int mins, int index, Map<String, Long> open, Set<String> visit
     List<Long> options = new ArrayList<>();
     if(v.flow > 0 && !open.containsKey(v.name)) {
       open.put(v.name, v.flow);
-      options.add(walk(mins + 1, index, new HashMap<>(open), new HashSet<>(visited)));
+      options.add(walk(mins + 1, index, new HashMap<>(open), new HashMap<>(visited)));
     }
-    return flow + LongStream.concat(options.stream().mapToLong(e -> e), Arrays.stream(v.others.split(", ")).mapToLong(s -> walk(mins + 1, indices.get(s), new HashMap<>(open), new HashSet<>(visited)))).max().orElse(0);
+    long res = flow + LongStream.concat(options.stream().mapToLong(e -> e), Arrays.stream(v.others.split(", ")).mapToLong(s -> walk(mins + 1, indices.get(s), new HashMap<>(open), new HashMap<>(visited)))).max().orElse(0);
+    visited.put(st, res);
+    return res;
   }
 
   @Override
