day 19, update README

codeforkjeff · codeforkjeff · commit bf4b86667bed · 2024-12-19T23:28:33.000-08:00
diff --git a/README.md b/README.md
@@ -98,3 +98,14 @@ went with the right solution from the start.
 The biggest stumbling block was adapting the well-known algorithm (I won't give it away here,
 it's in the code) to handle the direction of the reindeer in the maze, and accounting for that
 in the cost of the weighted edges of the graph.
+
+### 12/19/2024
+
+Day 17 part 2 was... oof. I skipped it immediately, since I didn't want to get stuck 
+on how to "reverse" those operations, which I think is how I should approach it. It'll require
+a longer block of time on another day.
+
+Considering how hard the problems are getting, I solved days 18 and 19 pretty damn quickly. 
+Both of those were the ideal programming puzzles, in my view. Apply the right algorithms for
+both parts and you're done. No tricks in the input data, no having to be clever about what 
+the rules imply and calculating a "shortcut" solution. Just nice efficient coding.
diff --git a/src/main/java/com/codefork/aoc2024/day19/Onsen.java b/src/main/java/com/codefork/aoc2024/day19/Onsen.java
@@ -0,0 +1,96 @@
+package com.codefork.aoc2024.day19;
+
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
+
+import static com.codefork.aoc2024.util.FoldLeft.foldLeft;
+
+public record Onsen(Set<String> towels, Set<String> designs) {
+
+    public static Onsen create(Stream<String> data) {
+        return data.collect(foldLeft(
+                () -> new Onsen(new HashSet<>(), new HashSet<>()),
+                (acc, line) -> {
+                    if (line.contains(",")) {
+                        var parts = Arrays.stream(line.split(","))
+                                .map(String::strip)
+                                .collect(Collectors.toSet());
+                        return new Onsen(parts, acc.designs());
+                    } else if (!line.isEmpty()) {
+                        acc.designs().add(line);
+                        return acc;
+                    } else {
+                        return acc;
+                    }
+                })
+        );
+    }
+
+    /**
+     * this part 1 solution could be rewritten to use part 2's countTowelCombinations()
+     * to unify the code, but it's nice to see how I approached it differently for the
+     * two parts
+     */
+    public boolean isDesignPossible(String design) {
+        if (design.isEmpty()) {
+            return true;
+        }
+        var towelMatches = towels.stream()
+                .filter(design::startsWith)
+                .toList();
+        return towelMatches.stream().anyMatch(towel ->
+                isDesignPossible(design.substring(towel.length()))
+        );
+    }
+
+    /**
+     * returns the number of designs that are actually viable (that
+     * can be achieved with some combination of towels)
+     */
+    public int countViableDesigns() {
+        return (int) designs().stream()
+                .filter(this::isDesignPossible)
+                .count();
+    }
+
+    /**
+     * count the number of towel combinations that exist for a design
+     */
+    public long countTowelCombinations(String design, Map<String, Long> cache) {
+        if(cache.containsKey(design)) {
+            return cache.get(design);
+        }
+        if (design.isEmpty()) {
+            return 1;
+        }
+        var towelMatches = towels.stream()
+                .filter(design::startsWith)
+                .toList();
+        return towelMatches.stream().reduce(0L,
+                (acc, towel) -> {
+                    var designRemainder = design.substring(towel.length());
+                    // a lot of these calls will be repeats for the same designRemainder,
+                    // so cache and re-use that count. without caching, this algorithm won't
+                    // finish, there's too many combinations to actually compute
+                    var count = countTowelCombinations(designRemainder, cache);
+                    cache.put(designRemainder, count);
+                    return acc + count;
+                },
+                Long::sum);
+    }
+
+    public long countTowelCombinationsForAllDesigns() {
+        return designs().stream()
+                .reduce(
+                        0L,
+                        (acc, design) ->
+                                acc + countTowelCombinations(design, new HashMap<>()),
+                        Long::sum);
+    }
+
+}
diff --git a/src/main/java/com/codefork/aoc2024/day19/Part01.java b/src/main/java/com/codefork/aoc2024/day19/Part01.java
@@ -0,0 +1,24 @@
+package com.codefork.aoc2024.day19;
+
+import com.codefork.aoc2024.Problem;
+import com.codefork.aoc2024.util.Assert;
+
+import java.util.stream.Stream;
+
+public class Part01 extends Problem {
+
+    public String solve(Stream<String> data) {
+        var onsen = Onsen.create(data);
+        return String.valueOf(onsen.countViableDesigns());
+    }
+
+    @Override
+    public String solve() {
+        Assert.assertEquals("6", solve(getSampleInput()));
+        return solve(getInput());
+    }
+
+    public static void main(String[] args) {
+        new Part01().run();
+    }
+}
diff --git a/src/main/java/com/codefork/aoc2024/day19/Part02.java b/src/main/java/com/codefork/aoc2024/day19/Part02.java
@@ -0,0 +1,24 @@
+package com.codefork.aoc2024.day19;
+
+import com.codefork.aoc2024.Problem;
+import com.codefork.aoc2024.util.Assert;
+
+import java.util.stream.Stream;
+
+public class Part02 extends Problem {
+
+    public String solve(Stream<String> data) {
+        var onsen = Onsen.create(data);
+        return String.valueOf(onsen.countTowelCombinationsForAllDesigns());
+    }
+
+    @Override
+    public String solve() {
+        Assert.assertEquals("16", solve(getSampleInput()));
+        return solve(getInput());
+    }
+
+    public static void main(String[] args) {
+        new Part02().run();
+    }
+}
diff --git a/src/main/java/com/codefork/aoc2024/day20/Part01.java b/src/main/java/com/codefork/aoc2024/day20/Part01.java
@@ -0,0 +1,4 @@
+package com.codefork.aoc2024.day20;
+
+public class Part01 {
+}
diff --git a/src/main/java/com/codefork/aoc2024/util/Grid.java b/src/main/java/com/codefork/aoc2024/util/Grid.java
@@ -0,0 +1,37 @@
+package com.codefork.aoc2024.util;
+
+import com.codefork.aoc2024.day20.Part01;
+
+import java.util.HashSet;
+import java.util.function.BiFunction;
+import java.util.function.Supplier;
+import java.util.stream.Stream;
+
+import static com.codefork.aoc2024.util.FoldLeft.foldLeft;
+
+public class Grid {
+
+    public static <T> T parse(
+            Stream<String> data,
+            Supplier<T> accInitializer,
+            BiFunction<T, String, T> reducer) {
+        return data
+                .map(WithIndex.indexed())
+                .filter(lineWithIndex -> !lineWithIndex.value().isEmpty())
+                .collect(foldLeft(
+                        () -> accInitializer.get(),
+                        (acc, lineWithIndex) -> {
+                            var y = lineWithIndex.index();
+                            var line = lineWithIndex.value();
+
+                            return line.chars()
+                                    .boxed()
+                                    .map(ch -> String.valueOf((char) ch.intValue()))
+                                    .collect(foldLeft(
+                                            () -> acc,
+                                            (acc2, ch) -> reducer.apply(acc2, ch)
+                                    ));
+                        })
+                );
+    }
+}
diff --git a/src/main/resources/day19/input b/src/main/resources/day19/input
diff --git a/src/main/resources/day19/sample b/src/main/resources/day19/sample
diff --git a/src/main/resources/day20/sample b/src/main/resources/day20/sample

-Original file line number
+Diff line change
@@ @@ -0,0 +1,4 @@ @@
 +package com.codefork.aoc2024.day20;
++
 +public class Part01 {
 +}