Today, The Historians take you up to the hot springs on Gear Island! Very suspiciously, absolutely nothing goes wrong as they begin their careful search of the vast field of helixes.
Solution in Java
Full source can be found: in GitHub
Part 1
The solution for part 1 today can be resolved by creating a regular expression of all allowed rugs (line 16) and then checking each line in the input to see if it matches.
1public void part1() {
2 var inputLines = new ArrayList<>(Arrays.asList(inputLoader.split("\n")));
3
4 var pattern = buildRegex(inputLines.removeFirst());
5 inputLines.removeFirst();
6
7 var matchingLines = inputLines.stream()
8 .filter(line -> pattern.matcher(line).matches())
9 .count();
10
11 validator.part1(matchingLines);
12}
13
14private Pattern buildRegex(String line) {
15 var patternOptions = String.join("|", line.split(", "));
16 return Pattern.compile("(" + patternOptions + ")+");
17}
Part 2
For the second part of today I opted for a solution where we first extract all allowed towels in a list. Then using that list we remove any matching rug from the beginning of the input string. The remainder of the input string gets recursively passed into the same extraction logic.
To make sure that we don’t hit to big performance hits a cache is also build using the resulting count and input string. This way if any (partial) input string matches we can short-circuit out of the method.
1public void part2() {
2 var inputLines = new ArrayList<>(Arrays.asList(inputLoader.split("\n")));
3
4 var towels = Arrays.asList(inputLines.removeFirst().split(", "));
5 inputLines.removeFirst();
6
7 var answer = inputLines.stream()
8 .mapToLong(line -> countPossibilities(line, towels, new HashMap<>()))
9 .sum();
10
11 validator.part2(answer);
12}
13
14private long countPossibilities(String line, List<String> towels, HashMap<String, Long> memo) {
15 if (memo.containsKey(line)) {
16 return memo.get(line);
17 }
18
19 var count = 0L;
20 for (var towel : towels) {
21 if (line.startsWith(towel)) {
22 var remaining = line.substring(towel.length());
23 if (remaining.isEmpty()) {
24 count++;
25 } else {
26 count += countPossibilities(remaining, towels, memo);
27 }
28 }
29 }
30
31 memo.put(line, count);
32 return count;
33}