Linen Layout

Part 1

The staff at the onsen will let us in for free if we can arrange their towels. Not a bad deal; let’s see how well we can do.

Before we start, we need to know what towels we’re working with, and what designs we’re allowed to make with them. The input is in the form of two “blocks” separated by two newlines, and they’re easy to parse into a list of towels and a list of designs.

class Solution(StrSplitSolution):
    separator = "\n\n"

    def part_1(self) -> int:
        raw_towels, raw_designs = self.input
        towels = raw_towels.split(", ")
        designs = raw_designs.splitlines()
        ...

Now, which of these designs can we make with our towels? Instead of using some sort of brute-force method, let’s see if we can think about this recursively. (To show what I mean, I’ll be using the towels from the sample input: r, wr, b, g, bwu, rb, gb, and br.)

For our recursive case, we can start by thinking about which of our towels could go first in our arrangement — i.e. which of our towels’ stripe patterns the design starts with. If we couldn’t put any of our towels first, the design is not possible; otherwise, we’ll want to check whether or not the rest of the design is possible. So for example:

• If the design is brwrr:
  • We could start with a b towel, and check whether rwrr is possible.
  • We could start with a br towel, and check whether wrr is possible.
• If the design is bggr:
  • We could start with a b towel, and check whether ggr is possible.
• If the design is gbbr:
  • We could start with a g towel, and check whether bbr is possible.
  • We could start with a gb towel, and check whether br is possible.
• If the design is rrbgbr:
  • We could start with a r towel, and check whether rbgbr is possible.
• If the design is ubwu:
  • This design is impossible; none of the towels we have available could go first in our arrangement.
• If the design is bwurrg:
  • We could start with a b towel, and check whether wurrg is possible.
  • We could start with a bwu towel, and check whether rrg is possible.
• If the design is brgr:
  • We could start with a b towel, and check whether rgr is possible.
  • We could start with a br towel, and check whether gr is possible.
• If the design is bbrgwb:
  • We could start with a b towel, and check whether brgwb is possible.¹

We also need to figure out a base case, which will answer the simplest possible version of our question. In this case, the simplest possible case I can imagine is the case of an empty design — a design with no stripes — which we will say is possible.

Now that we have our recursive case and base case, we can easily implement a function to validate each design — returning True if the design is valid, and False otherwise. And thanks to the fact that bools act like ints when you add them together, we can simply add up our True/False results directly with sum to count how many designs are possible.

from functools import cache

class Solution(StrSplitSolution):
    separator = "\n\n"

    def part_1(self) -> int:
        raw_towels, raw_designs = self.input
        towels = raw_towels.split(", ")
        designs = raw_designs.splitlines()

        @cache
        def validate_design(design: str) -> bool:
            # An empty design (with no stripes) is possible
            if not design:
                return True
            # For each towel that could go first, check the validity of
            # the rest of the design
            return any(
                validate_design(design.removeprefix(towel))
                for towel in towels
                if design.startswith(towel)
            )

        return sum(validate_design(design) for design in designs)

Part 2

Looks like the onsen staff don’t know good towel arrangements when they see them. So at this point, let’s do the lowest-effort thing possible, and write some code to find all possible towel arrangements; the designs will be their responsibility from now on.

Believe it or not, we don’t have to change very much from our Part 1 solution. The same recursive algorithm that checks the existence of valid towel arrangements can also be used to count those arrangements, with two tweaks:

• Instead of return True in our base case, we’ll return 1 to signify that we can make the design using a single towel arrangement.
• Instead of any in our recursive case, we’ll use sum to add up the towel arrangement counts for each possible starting towel.

from functools import cache

class Solution(StrSplitSolution):
    separator = "\n\n"

    def part_2(self) -> int:
        raw_towels, raw_designs = self.input
        towels = raw_towels.split(", ")
        designs = raw_designs.splitlines()

        @cache
        def validate_design(design: str) -> int:
        def count_arrangements(design: str) -> int:
            # An empty design (with no stripes) can be made in one way
            # (by using no towels)
            if not design:
                return True
                return 1
            # For each towel that could go first, count the possible
            # towel arrangements for the rest of the design
            return any(
            return sum(
                validate_design(design.removeprefix(towel))
                count_arrangements(design.removeprefix(towel))
                for towel in towels
                if design.startswith(towel)
            )

        return sum(validate_design(design) for design in designs)
        return sum(count_arrangements(design) for design in designs)

In fact, we can turn this into a unified solve function by making a useful observation: a design is valid if and only if the number of towel arrangements that can make it is nonzero. This means that, if we have our Part 1 answer count the number of nonzero results of count_arrangements, we could get rid of the validate_design function entirely.

My unified function first calculates the number of towel arrangements for each design, and stores these counts in a list called arrangements. The answers for both parts are the result of two simple sum() expressions:

1. For Part 1, first I use map(bool, arrangements) to convert the arrangement counts to bools; this makes the nonzero values True and the zero values False. Then, I can pass these bools to sum() to count the valid designs.
2. For Part 2, I can just pass arrangements to sum() directly to count the valid arrangements.

from functools import cache

class Solution(StrSplitSolution):
    separator = "\n\n"

    def solve(self) -> tuple[int, int]:
        raw_towels, raw_designs = self.input
        towels = raw_towels.split(", ")
        designs = raw_designs.splitlines()

        @cache
        def count_arrangements(design: str) -> int:
            # An empty design (with no stripes) can be made in one way
            # (by using no towels)
            if not design:
                return 1
            # For each towel that could go first, count the possible
            # towel arrangements for the rest of the design
            return sum(
                count_arrangements(design.removeprefix(towel))
                for towel in towels
                if design.startswith(towel)
            )

        arrangements = [count_arrangements(design) for design in designs]
        # Part 1 counts designs with a nonzero number of arrangements;
        # Part 2 counts all arrangements for all designs
        return sum(map(bool, arrangements)), sum(arrangements)

Excellent towel-arranging work, if I do say so myself. We deserve that free entry into the onsen.