≡ Day 19 of Advent of Code in q

Author - Rory Kemp

Original Problem Statement

--- Day 19: Linen Layout ---

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.

Could this finally be your chance to visit the onsen next door? Only one way to find out.

After a brief conversation with the reception staff at the onsen front desk, you discover that you don't have the right kind of money to pay the admission fee. However, before you can leave, the staff get your attention. Apparently, they've heard about how you helped at the hot springs, and they're willing to make a deal: if you can simply help them arrange their towels, they'll let you in for free!

Every towel at this onsen is marked with a pattern of colored stripes. There are only a few patterns, but for any particular pattern, the staff can get you as many towels with that pattern as you need. Each stripe can be white (w), blue (u), black (b), red (r), or green (g). So, a towel with the pattern ggr would have a green stripe, a green stripe, and then a red stripe, in that order. (You can't reverse a pattern by flipping a towel upside-down, as that would cause the onsen logo to face the wrong way.)

The Official Onsen Branding Expert has produced a list of designs - each a long sequence of stripe colors - that they would like to be able to display. You can use any towels you want, but all of the towels' stripes must exactly match the desired design. So, to display the design rgrgr, you could use two rg towels and then an r towel, an rgr towel and then a gr towel, or even a single massive rgrgr towel (assuming such towel patterns were actually available).

To start, collect together all of the available towel patterns and the list of desired designs (your puzzle input). For example:

r, wr, b, g, bwu, rb, gb, br

brwrr
bggr
gbbr
rrbgbr
ubwu
bwurrg
brgr
bbrgwb

The first line indicates the available towel patterns; in this example, the onsen has unlimited towels with a single red stripe (r), unlimited towels with a white stripe and then a red stripe (wr), and so on.

After the blank line, the remaining lines each describe a design the onsen would like to be able to display. In this example, the first design (brwrr) indicates that the onsen would like to be able to display a black stripe, a red stripe, a white stripe, and then two red stripes, in that order.

Not all designs will be possible with the available towels. In the above example, the designs are possible or impossible as follows:

In this example, 6 of the eight designs are possible with the available towel patterns.

To get into the onsen as soon as possible, consult your list of towel patterns and desired designs carefully. How many designs are possible?

First, read the input. We mark t as unique to increase lookup speed.

show (t;d):(", ";".")vs'".."vs "." sv read0 `19.txt; t:`u#t
,"r"    "wr"   ,"b"   ,"g"     "bwu"  "rb"     "gb"   "br"    
"brwrr" "bggr" "gbbr" "rrbgbr" "ubwu" "bwurrg" "brgr" "bbrgwb"

We need to find which designs are possible to make from the available towels.

To do this, for each design we create an adjacency matrix, representing where is "reachable" from every position.

The first step is to create the relevant "slices" from the original design.

{i{z _y#x}[x]\:/:i:til 1+count x} "brwrr"
"" ,"b" "br" "brw" "brwr" "brwrr"
"" ""   ,"r" "rw"  "rwr"  "rwrr" 
"" ""   ""   ,"w"  "wr"   "wrr"  
"" ""   ""   ""    ,"r"   "rr"   
"" ""   ""   ""    ""     ,"r"   
"" ""   ""   ""    ""     ""

Now, we check which are valid towels.

{in[;t]i{z _y#x}[x]\:/:i:til 1+count x} "brwrr"
011000b
001000b
000010b
000010b
000001b
000000b

Define this as a function.

adj: {in[;t]i{z _y#x}[x]\:/:i:til 1+count x}

Now, we use matrix multiplication, but replacing the plus with or and the multiplication by and. This represents finding the transitive closure of the matrix.

M: adj first d; (M(any@&)\:)scan M
011000b 001000b 000010b 000010b 000001b 000000b
001010b 000010b 000001b 000001b 000000b 000000b
000011b 000001b 000000b 000000b 000000b 000000b
000001b 000000b 000000b 000000b 000000b 000000b
000000b 000000b 000000b 000000b 000000b 000000b

We can see each "step" of the iteration, and the top right value being 1, representing there being a path from the start to the end.

Wrapping this in a function:

valid:{M:adj x; last first any (M(any@&)\:)scan M}

Now count how many designs are valid.

sum valid each d

Part 2:

Part 2 Original Description:

--- Part Two ---

The staff don't really like some of the towel arrangements you came up with. To avoid an endless cycle of towel rearrangement, maybe you should just give them every possible option.

Here are all of the different ways the above example's designs can be made:

brwrr can be made in two different ways: b, r, wr, r or br, wr, r.

bggr can only be made with b, g, g, and r.

gbbr can be made 4 different ways:

rrbgbr can be made 6 different ways:

bwurrg can only be made with bwu, r, r, and g.

brgr can be made in two different ways: b, r, g, r or br, g, r.

ubwu and bbrgwb are still impossible.

Adding up all of the ways the towels in this example could be arranged into the desired designs yields 16 (2 + 1 + 4 + 6 + 1 + 2).

They'll let you into the onsen as soon as you have the list. What do you get if you add up the number of different ways you could make each design?

Now we want the count, not just the number. Luckily, this corresponds to using regular matrix multiplication.

We adjust the valid function to a new one that counts the different possibilities. 

ways: {M:0+adj x; last first sum (M(sum@*)\:)scan M}

And part 2 then becomes:

sum ways each d
16

Now, this works, but it isn't very efficient. A faster method is to recognise we are essentially finding a matrix inverse, which can be done in many ways, either using inv, or a faster method like the Jacobi method.

We can implement the new method as follows:

ways:{M:0+adj x; b: (count[x]#0),1; first (b+M(sum@*)\:)over 0}

This is significantly faster, as it avoids having to do whole matrix multiplications.

For the full solution, we can also reuse this calculation for part 1.

Recap:

The full solution is this. 
(t;d):(", ";".")vs'".."vs "." sv read0 `:i/19t.txt; t:`u#t
adj:{in[;t]i{z _y#x}[x]\:/:i:til 1+count x}
ways:{M:0+adj x; b: (count[x]#0),1; first (b+M(sum@*)\:)over 0}
sum 0<c: ways each d
sum c