import { inputDay } from "./lib/utilities.js"

const parser = inp => {
  const [patterns, displays] = inp.trim().split("\n\n")
  return [patterns.replaceAll(" ", "").split(",").sort(), displays.split("\n")]
}
const test = parser(`r, wr, b, g, bwu, rb, gb, br

brwrr
bggr
gbbr
rrbgbr
ubwu
bwurrg
brgr
bbrgwb
`)
display(test)

const input = await inputDay(19, { parser })

part 1

Let's start with a function that finds all the patterns that match a given display. Since we've sorted our pattern list, we can exit out if the pattern is lexically greater than the display we want to match.

We could use a prefix tree for greater efficiency if we wanted, but the pattern list is small enough that it's unlikely we'd get a big win out of it.

function matches(patterns, display) {
  const matches = []
  for (const pat of patterns) {
    if (display.startsWith(pat)) matches.push(pat)
    if (pat > display) return matches
  }
  return matches
}

display(matches(test[0], test[1][0]))

now let's write a function to search for a match

function search(patterns, display) {
  let frontier = new Set([display])
  let seen = new Set([])
  while (frontier.size > 0) {
    const newf = new Set()
    for (const f of frontier) {
      if (seen.has(f)) continue
      seen.add(f)
      for (const pat of matches(patterns, f)) {
        if (f.length == pat.length) return true
        newf.add(f.slice(pat.length))
      }
    }
    frontier = newf
  }
  return false
}

display(search(test[0], "brwrr"))

display(test[1].map(d => search(test[0], d)).reduce((a, b) => a + b, 0))
display(input[1].map(d => search(input[0], d)).reduce((a, b) => a + b, 0))

part 2

To solve part 2, we're going to rub some dynamic programming on it.

First, a function that recursively searches the breaks and remembers results as it goes. This is important because there will be many duplicate branches of the tree.

function searchr(patterns, display, memo) {
  if (memo.has(display)) return memo.get(display)
  let n = matches(patterns, display)
    .map(m =>
      m.length === display.length
        ? 1
        : searchr(patterns, display.slice(m.length), memo),
    )
    .reduce((a, b) => a + b, 0)
  memo.set(display, n)
  return n
}
display(searchr(test[0], "rrbgbr", new Map())) // 6

Then we can write a function that keeps the memo table between displays (because the sub-problem answers won't have changed), searches each display for the number of results it has, and sums them up

function search2(patterns, displays) {
  const displaymemo = new Map()
  return displays
    .map(d => searchr(patterns, d, displaymemo))
    .reduce((a, b) => a + b)
}

display(search2(...test)) // 16
const t = new Date()
display(search2(...input))
const t2 = new Date()
display(`part 2 took ${t2 - t}ms`)

Day 19

prelude

part 1

part 2