Advent of Code Day 19 was quite an easy puzzle. Let’s figure it out!

---

The below is a guest post by the amazing Shraddha Agrawal.

---

Part 1

We are given a list of towel patterns available. We have unlimited supply of each of these patterns. Each letter in the pattern describes the colour of stripe, which can be: white (w), blue (u), black (b), red (r), or green (g). The order of these colour stripes can not be changed or reversed.

We are also given a list of towel designs. These towel designs need to be created using the unlimited supply of towel patterns given above.

For part 1, we need to determine how many towel designs are possible to create using the towel patterns.

Solution

Main crux of the problem is figuring out how to determine if creating a towel design witht eh given pattern is possible or not. This calls for a recursive dynamic programming solution. Some important points:

For any given design, we iterate over the available patterns:

1. Base success case: if the towel design has the current pattern as a prefix and the length of the towel design is equal to the current pattern, we have found a way to create the towel with the available patterns. We can exit early.
2. Recursive Case: if the towel design has the current pattern as a prefix and the length of the towel design if greater than the current pattern, we can call the same function again for the rest of the design yet to be matched to a pattern.
3. Exit case: If all available pattern are longer / do not match the beginning of the input towel design, there is no match available and the towel design is not possible.

Since the subsections of a towel design can overlap, it would be wise to make use of memoisation (ie caching) so we are not doing the same calculation again and again. So for each call to the recursive function whenever we encounter a base success case or an exit case, we can store this result in a possible map.

Implementing this is straightforward now:

func isTowelPossible(towelDesign string, towelPatterns []string, possible map[string]bool) bool {
	if val, ok := possible[towelDesign]; ok {
		return val
	}

	for _, t := range towelPatterns {

		if len(t) > len(towelDesign) {
			continue
		}

		if strings.HasPrefix(towelDesign, t) {
			if len(t) == len(towelDesign) {
				return true
			}
			if isTowelPossible(towelDesign[len(t):], towelPatterns, possible) {
				possible[towelDesign] = true
				return true
			}
		}
	}

	possible[towelDesign] = false
	return false
}

The above function can be called for each input towel and the total count of towel designs that are possible can be summed.

func getPossibleCount(towelPatterns []string, designs []string) int {
	count := 0
	possible := make(map[string]bool)
	for _, d := range designs {
		if isTowelPossible(d, towelPatterns, possible) {
			count += 1
		}
	}
	return count
}

This gets us the answer for part 1!

Part 2

Now, we need to find the number of ways each towel design can be created with the given towel patterns. Final answer should be the sum of count of ways each towel design can be created.

Solution

With the way I implemented part 1, this was quite trivial to implement. In our recursive solution, we just need to make a few modifications:

1. Memoisation: Instead of using a map with value of type bool, now we need to keep a count so we will change the value to int.
2. Base Success Case: In part 1, as soon as we find a way to create the design, we would exit early. Now as we want to find all ways to create the design, so instead of exiting when finding the design, we would increment the count in the cache map.

Just by making these two changes, we can find the answer to part 2. Implementing the changes, our function changes to:

func isTowelPossible(towelDesign string, towelPatterns []string, possible map[string]int) int {
	if val, ok := possible[towelDesign]; ok {
		return val
	}

	isPossibleCount := 0

	for _, t := range towelPatterns {
		if len(t) > len(towelDesign) {
			continue
		}

		if strings.HasPrefix(towelDesign, t) {
			if len(t) == len(towelDesign) {
				isPossibleCount++
				continue
			}
			isPossibleCount += isTowelPossible(towelDesign[len(t):], towelPatterns, possible)
		}
	}
	possible[towelDesign] = isPossibleCount
	return isPossibleCount
}

And thats it! You can find my final code here.

This was quite an easy day so late into the challenge but I appreciate the dynamic programming practice! I actually misread part 1 and solved part 2 before part 1 yet again. Some folks also solved this using regex entirely, both part 1 and part 2 which is quite cool!

How did you solve Day 19? I would love to compare notes and checkout your solution. Reach out to me on Twitter, Bluesky or on e-mail at contact[at]shraddhaag[dot]dev.