Well. Looks like I made the right choice using and learning Instaparse for yesterday. That is the first time I’ve ever solved both puzzles in under an hour.

(defn advent-19
  [input]
  (let [[grammar input] (input->groups input)
        grammar (->> (str/split grammar #"\n")
                     (sort-by #(Integer/parseInt (first (str/split % #":"))))
                     (str/join "\n"))
        parser (insta/parser grammar)]
    (->> (str/split input #"\n")
         (map #(insta/parses parser %))
         (remove insta/failure?)
         count)))

(`input->groups` is a utility function I’ve used a few times to split puzzle input on a blank line.)

Got my best finish-placement yet. And learned about Instaparse! https://github.com/rjray/advent-2020-clojure/blob/master/src/advent_of_code/day19.clj

TIL a few needed instaparse functions from @U01GXCWSRMW

@U01GXCWSRMW Is that really necessary to sort the rules?

OOOOHHHH I found my bug !

I should parse from rule 0

Problem solved 🙂

https://github.com/green-coder/advent-of-code-2020/blob/master/src/aoc/day_19.clj

I solved it with regexs 😂

the second part was hard, because Java’s regexs don’t support recursion.

https://github.com/rjray/advent-2020-clojure/blob/master/src/advent_of_code/day19.clj#L29 @UEF091BP0 you could have just

(reduce-kv str/replace input
  {"8: 42"     "8: 42 | 42 8"
   "11: 42 31" "11: 42 31 | 42 11 31"})

(-> input
  (str/replace "8: 42" "8: 42 | 42 8")
  (str/replace "11: 42 31" "11: 42 31 | 42 11 31")))

(defn to-grammar [rules]
  (str "S = 0\n" (str/replace rules #":" "=")))

(defn solve [input]
  (let [[rules messages] (str/split input #"\n\n")
        grammar (to-grammar rules)
        parser  (insta/parser grammar)]
     (->> messages
       (str/split-lines)
       (map #(insta/parse parser %))
       (remove insta/failure?)
       (count))))

😁

I wonder anyone else solved it without instaparse?

My solution with regexs https://github.com/zelark/AoC-2020/blob/master/src/zelark/aoc_2020/day_19.clj

I did part 1 with recursion and re-pattern, bailed on it as soon as read p2

today was brutal for me... satisfying too, in the end! https://github.com/euccastro/advent-of-code-2020/blob/master/src/advent/day19.clj

@U067R559Q I eventually solved it without regexes or instaparse. I tried regexes, and even found a clever way to do recursive regexes in Java, but my first attempts didn't work and I decided that regexes were not the most fun thing to debug and moved on 🙂

https://github.com/RedPenguin101/aoc2020/blob/main/day19.clj - Instaparse feels like cheating here, but the thought of building it myself filled me with horror.

without instaparse it is slow and hacky https://github.com/nbardiuk/adventofcode/blob/master/2020/src/day19.clj

mine runs in ~300msecs

btw by "found" I mean I looked it up, not that I discovered it myself: https://stackoverflow.com/a/3644267

a^n b^n is the pattern in 11. the pattern in 8 is just (42-pattern)+

my regex-ish version runs in 13.371895 msecs!

instaparsed https://github.com/transducer/adventofcode/blob/master/src/adventofcode/2020/day19.clj

I'm all for transforming inputs into some known problem and letting a lib do all the work (like creating a graph problem from the inputs and feeding it to loom for example) but this time I literally didn't have to change anything about the format. https://github.com/Dexterminator/advent-of-code-2020/tree/main/src/day19

The actual file: https://github.com/Dexterminator/advent-of-code-2020/blob/main/src/day19/core.clj

Wow. I hadn’t realized that the format was usable as-is. I really can’t wait until I can go back and clean up my code!

Manual glueing regex as my third attempt... it's fast and dirty and eventually works... https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2020/day19.clj

.. because I am using it for another project, so I may learn something.

namely, I am parsing Tailwinds’s grammar using instaparse.

I hope to open source the project this weekend. Anyone who want to join the effort is welcome, I will make this project “community-built”.

WTF… trying to checkout instaparse myself, and lein repl keeps erroring out on the :require…

Push your code, I can take a look if you need.

(ns advent-of-code.day19
  (:require [clojure.string :as str]
            [instaparse.code :as insta]))

.core

> _<

Dammit

Moving too fast.

(= 'too-fast 'slow)

Yep 🙂.

I am learning the transform function.

Which instaparse function to use for checking if a string matches a parser?

I couldn’t find one! If it matches, you get a vector, if it doesn’t you get a map. So I test with sequential?.

Just made 793 on the second star’s leaderboard. w00t!

wow

If you hadn’t of mentioned Instaparse, I’d still be trying to hand-code a parser-generator!

There’s no parsable? or similar, but if you call parses it should prove useful.

I wrote a function to transform the input into an instaparse grammar, but I have a bug somewhere.

Here’s my code: https://github.com/rjray/advent-2020-clojure/blob/master/src/advent_of_code/day19.clj

It’s hacky. I plan to clean up the parts that transform the input into an Instaparse grammar tomorrow.

Here is mine. If you can spot the bug, that would be nice.

(def input-parser (insta/parser "
  <input> = rules <#'\\R\\R'> messages
  rules = rule+
  messages = message+
  rule = rule-ref <':'> disjunction
  disjunction = (conjunction (<'|'> conjunction)*)
  conjunction = rule-ref+ | text-literal
  rule-ref = #'\\d+'
  text-literal = <'\"'> #'[a-z]+' <'\"'>
  <message> = #'.+'
" :auto-whitespace :standard))

(let [[rules messages] (->> (input-parser input-str)
                            (insta-tf/transform {:rules (fn [& rules] (vec rules))
                                                 :messages (fn [& messages] (vec messages))
                                                 :rule (fn [rule-id rule-definition]
                                                         (str rule-id " = " rule-definition "\n"))
                                                 :rule-ref (fn [rule-id]
                                                             (str "rule" rule-id))
                                                 :disjunction (fn [& args]
                                                                (let [s (str/join " | " args)]
                                                                  (if (> (count args) 1)
                                                                    (str "(" s ")")
                                                                    s)))
                                                 :conjunction (fn [& args]
                                                                (str/join " " args))
                                                 :text-literal (fn [text-literal]
                                                                 (str "'" text-literal "'"))}))
      new-grammar (reduce str rules)
      new-parser (insta/parser new-grammar)]
  (->> messages
       (map new-parser)
       (filter sequential?)
       count))

I am not running for the leaderboard anymore.

Huh. My transformation of the rules was dead-simple.

For each line, change “:” to ” = “. Change every number to “R<num>“. Then preface it all with “S = R0\n”.

I wanted to learn instaparse, so I chose what you see above 😛

That’s a valid point. I come from a Perl background, so I tend to see regexp transformations as the solution to everything 🙂.

oh, I know … (a b | c d) should be (a b) | (c d)

Oh yeah, That’s going to make a huge diff. I didn’t see that when I looked at the code before.

I am not sure how instaparse does its grouping

It still does not work

TIL that Instaparse places a precedence on the concatenation compared to the ‘|' operator.

@UEF091BP0: I feel like an impostor, having used instaparse for part 2.

> Tailwinds’s grammar using instaparse tell me more!

(ns girouette.grammar.css-class
  (:require [instaparse.core :as insta]))

;; Use case 1: "css class name -> corresponding css"
;; - parse a class name,
;; - find its matching rule and its variable bindings,
;; - call the css generator with the bindings,
;; - get the css corresponding to the class name.

;; Use case 2: "generate css for given combinations of rules and bindings"
;; - given a rule, some bindings between variables and a collection of values,
;; - generate the corresponding css, aggregated in order.

;; Note: the generated css could be either a string or garden format.
;; Beware: the order of the css statements matter, it should be the same as Tailwind.

(def css-class-grammar "
  rule =
     (* Layout Section *)
     container | box-sizing | display | floats | clear |
     object-fit | object-position | overflow | overscroll |
     position | positioning | visibility | z-index |

     (* Flexbox Section *)
     flex-direction | flex-wrap | flex | order |

     (* Grid Section *)
     grid-template-columns | grid-column-start-end |
     grid-template-rows | grid-row-start-end |
     grid-auto-flow | grid-auto-columns | grid-auto-rows | gap |


     padding | margin


  container = <'container'>

  box-sizing = 'box-border' | 'box-content'

  display = 'block' | 'inline-block' | 'inline' | 'flex' | 'inline-flex' |
     'table' | 'table-caption' | 'table-cell' | 'table-column' | 'table-column-group' |
     'table-footer-group' | 'table-header-group' | 'table-row-group' | 'table-row' |
     'flow-root' | 'grid' |'inline-grid' | 'contents' | 'hidden'

  floats = <'float-'> ('left' | 'right' | 'none')

  clear = <'clear-'> ('left' | 'right' | 'both' | 'none')

  object-fit = <'object-'> ('contain' | 'cover' | 'fill' | 'none' | 'scale-down')

  object-position = <'object-'> object-position-side
  <object-position-side> = 'left' | 'left-bottom' | 'left-top' |
                           'right' | 'right-bottom' | 'right-top' |
                           'center' | 'bottom' | 'top'

  overflow = <'overflow-'> (axis <'-'>)? overflow-mode
  overflow-mode = 'auto' | 'hidden' | 'visible' | 'scroll'

  overscroll = <'overscroll-'> (axis <'-'>)? overscroll-mode
  overscroll-mode = 'auto' | 'contain' | 'none'

  position = 'static' | 'fixed' | 'absolute' | 'relative' | 'sticky'

  positioning = signus? positioning-mode <'-'> positioning-size
  positioning-mode = 'top' | 'right' | 'bottom' | 'left' | 'inset'
  positioning-size = size unit? | unit | fraction | 'auto'

  visibility = 'visible' | 'invisible'

  z-index = signus? <'z-'> (#'\\d+' | 'auto')

  flex-direction = <'flex-'> ('row' | 'row-reverse' | 'col' | 'col-reverse')

  flex-wrap = <'flex-'> ('wrap' | 'wrap-reverse' | 'nowrap')

  flex = <'flex-'> (flex-shorthand | (flex-grow-value (<'-'> flex-shrink-value)? <'-'> flex-basis-value))
  flex-grow = <'flex-grow'> (<'-'> flex-grow-value)?
  flex-shrink = <'flex-shrink'> (<'-'> flex-shrink-value)?

  flex-shorthand = '1' | 'auto' | 'initial' | 'none'
  flex-grow-value = int-number
  flex-shrink-value = int-number
  flex-basis-value = size unit? | unit | fraction | 'auto'

  order = signus? <'order-'> int-number | 'first' | 'last' | 'none'


  grid-template-columns = <'grid-cols-'> (int-number | 'none')
  grid-column-start-end =
     <'col-'> ('auto' |
               ('span-' (int-number | 'full')) |
               ('start' (int-number | 'auto')) |
               ('end' (int-number | 'auto')))

  grid-template-rows = <'grid-rows-'> (int-number | 'none')
  grid-row-start-end =
     <'row-'> ('auto' |
               ('span-' (int-number | 'full')) |
               ('start' (int-number | 'auto')) |
               ('end' (int-number | 'auto')))

  grid-auto-flow = <'grid-flow-'> ('row' | 'col') (<'-'> 'dense')?
  grid-auto-columns = <'auto-cols-'> ('auto' | 'min' | 'max' | (int-number? 'fr'))
  grid-auto-rows = <'auto-rows-'> ('auto' | 'min' | 'max' | (int-number? 'fr'))
  gap = <'gap-'> (axis <'-'>)? (size unit? | unit)


  padding = signus? <'p'> (direction | axis)? <'-'> (size unit? | unit)
  margin = signus? <'m'> (direction | axis)? <'-'> (size unit? | unit)

  signus = '-' | '+'
  direction = 't' | 'r' | 'b' | 'l'
  axis = 'x' | 'y'
  size = float-number
  <int-number> = #'\\d+'
  <float-number> = #'\\d+(_\\d+)?'
  fraction = #'\\d+' '/' #'\\d+' | 'full'
  unit = 'px' | 'em' | 'rem'
  ")

(def css-class-parser
  (insta/parser css-class-grammar))

(comment
  (css-class-parser "gap-x-37_5px")
  (css-class-parser "z-7")
  (css-class-parser "-order-37")
  (css-class-parser "flex-0-1-auto")
  (css-class-parser "overflow-x-auto")
  (css-class-parser "-inset-2/3")
  (css-class-parser "container")
  (css-class-parser "-mx-30_5px")
  (css-class-parser "pt-2px")
  (css-class-parser "pt-5")
  (css-class-parser "p-5"))

that’s my POC

where do you use it for?

at work we use tailwind

makes css fun

i mean: where do you use that parser for?

Short answer: Where you can.

Long answer: Where you can.

note that you only needed to sort the numbers for instaparse in this question

it was already a valid grammar

I did without sorting, by adding a new root at the top.

I suspect that instaparse has an option to define which rule to use as the root.

you can use = : := and ::= to define rules

ah yes maybe

Yes, I know … I just wanted to play with the transformer.

I wanted to learn something.

🙂

As "everyone", I used Instaparse. Discovered afterwards that you can just prepend "valid : 0\n" to the rules, instead of "sorting" rules so 0 is the first one.

(defn sort-rules [rules] (str "valid : 0\n" rules))

(defn solve-part-1 [input]
  (let [[rules messages] (str/split input #"\R\R")
        parse (insta/parser (sort-rules rules))
        valid? (comp not insta/failure? parse)]
    (count (filter valid? (str/split-lines messages)))))

aaaah

haha

This one was painful. A solution without instaparse: https://github.com/benfle/advent-of-code-2020/blob/main/day19.clj

How did you handle the infinite loops ?

It works for part2 with the recursive rules because concat is lazy 🙂

ah, I see … breadth search?

or just luck of being in the right order?

I basically generate all possible paths through the grammar until I find one that matches, yes.

Today’s puzzle reminded me a lot of my library Minimallist where I did the exact same parsing.

@U963A21SL Does it still work if you reverse the order of the alt in the data?

(assoc-in [:rules 8] [:non-terminal '((42 8) (42))])

(assoc-in [:rules 8] [:non-terminal '((42 8) (42))]) ?

yes

impressive

Actually it doesn't need to be lazy 🙂 I'm not generating the strings, I'm matching against the messages so it will stop in the success case as well.

Start matching with this evil rule, does it still work? 666: 666 | 0

That's where you need the laziness, yes 🙂

It stack overflows when I doall the concat but works otherwise.

Nevermind I didn't test properly.

It overflows, yes.

Anyway, congratz on finishing it the hard way.

I would be curious to know the solution that takes advantage of the hint in part2. I still don't understand what they meant by this hint.

What hint?

This small change has a big impact: now, the rules do contain loops, and the list of messages they could hypothetically match is infinite. You'll need to determine how these changes affect which messages are valid.

Fortunately, many of the rules are unaffected by this change; it might help to start by looking at which rules always match the same set of values and how those rules (especially rules 42 and 31) are used by the new versions of rules 8 and 11.

Maybe it's for people who did Part1 by generating all possible strings in the language?

For part1 I had a much simpler solution where I consumed the message while traversing the grammar.

Unfortunately this didn't work for Part2 because of the recursions. I was taking just one path in the grammar. That's when I had the idea to return a seq of matches instead of the first one,

You could have reuse your part 1 and push down the recursion a set of visited [rule matching-index] and fail a match if you are asked to match something you visited before (to detect a loop).

I don’t understand the hint, it sounds more complicated to do something custom than doing it for the general case.

Why would you fail if you detect a cycle?

Some of the messages are only valid in part2 because those cycles are visited a few times.

the matching index is to be part of the state, not just the rule alone.

But my problem with part1 was not that it was looping but that it was stopping too early with unconsumed input

Because it was not greedy and repeating the cycles. That's where I got the idea to just generate all matches until I find one that return an empty string.

sleeping time here, see you tomorrow~

:thumbsup:

I solved part 1 by generating a regular expression, then rewrote my solution to solve both part 1 and 2 using a handwritten parser. It came out quite https://github.com/ocisly/advent2020/blob/674ec473fe599cc081a07a7d676502138cfbc672/day-19.clj#L26-L32!

Looks great 👍

here's mine (I don't have one for part 2 though)

#"^(a((b(b(a(baa|(ba|a(b|a))b)|b(bba|abb))|a(b(aba|baa)|a((aa|(b|a)b)b|(ba|(b|a)b)a)))|a(a((b(b|a)|aa)(b|a)b|((aa|(b|a)b)b|(ba|(b|a)b)a)a)|b(((aa|(b|a)b)b|(ba|a(b|a))a)b|(baa|(b(b|a)|aa)b)a)))a|((a((b|a)(aa|bb)a|(ba|a(b|a))(b|a)b)|b(((ba|a(b|a))b|(ab|aa)a)b|a(aa|(b|a)b)a))b|(((b(ab|ba)|a(aa|bb))a|(baa|(ba|a(b|a))b)b)a|(((aa|ba)b|aaa)b|((ba|a(b|a))b|aaa)a)b)a)b)|b(b((b(b(baa|(ba|a(b|a))b)|a(bbb|bba))|a(a(a(aa|ba)|b(ba|a(b|a)))|ba(aa|(b|a)b)))a|(((b(ba|(b|a)b)|a(ba|a(b|a)))b|(a(aa|bb)|b(bb|ba))a)a|(babb|a(bbb|abb))b)b)|a(((b((ab|ba)b|aaa)|a(b|a)(ba|a(b|a)))a|((baa|(b(b|a)|aa)b)a|(bb|ba)bb)b)b|(((b|a)(ba|(b|a)b)a|bbab)a|(a((ab|ba)b|(ba|a(b|a))a)|b((ab|ba)b|(b(b|a)|aa)a))b)a)))(a((b(b(a(baa|(ba|a(b|a))b)|b(bba|abb))|a(b(aba|baa)|a((aa|(b|a)b)b|(ba|(b|a)b)a)))|a(a((b(b|a)|aa)(b|a)b|((aa|(b|a)b)b|(ba|(b|a)b)a)a)|b(((aa|(b|a)b)b|(ba|a(b|a))a)b|(baa|(b(b|a)|aa)b)a)))a|((a((b|a)(aa|bb)a|(ba|a(b|a))(b|a)b)|b(((ba|a(b|a))b|(ab|aa)a)b|a(aa|(b|a)b)a))b|(((b(ab|ba)|a(aa|bb))a|(baa|(ba|a(b|a))b)b)a|(((aa|ba)b|aaa)b|((ba|a(b|a))b|aaa)a)b)a)b)|b(b((b(b(baa|(ba|a(b|a))b)|a(bbb|bba))|a(a(a(aa|ba)|b(ba|a(b|a)))|ba(aa|(b|a)b)))a|(((b(ba|(b|a)b)|a(ba|a(b|a)))b|(a(aa|bb)|b(bb|ba))a)a|(babb|a(bbb|abb))b)b)|a(((b((ab|ba)b|aaa)|a(b|a)(ba|a(b|a)))a|((baa|(b(b|a)|aa)b)a|(bb|ba)bb)b)b|(((b|a)(ba|(b|a)b)a|bbab)a|(a((ab|ba)b|(ba|a(b|a))a)|b((ab|ba)b|(b(b|a)|aa)a))b)a)))(b(((b(b((b|a)(b|a)a|(b(b|a)|aa)b)|a(b|a)(ba|a(b|a)))|a((bba|a(b(b|a)|aa))a|((b|a)(b|a)a|(ab|aa)b)b))b|(b(b(aab|(ab|aa)a)|a((ab|ba)a|bbb))|a(a(bbb|abb)|b((aa|bb)b|(ba|(b|a)b)a)))a)b|((b(b((ab|aa)a|(aa|bb)b)|a(a(aa|(b|a)b)|b(bb|ba)))|a((b|a)(aa|bb)b|(abb|bab)a))b|(b(((ab|ba)b|(bb|ba)a)a|(a(bb|ba)|b(b(b|a)|aa))b)|a(a(aaa|(b|a)(b|a)b)|b((aa|(b|a)b)b|aaa)))a)a)|a(a(b((a(a(aa|ba)|b(ba|a(b|a)))|b(bba|(aa|(b|a)b)b))b|((bba|bab)b|(bba|a(b(b|a)|aa))a)a)|a((a(bb|ba)b|(aaa|bab)a)a|(aba|baa)(b|a)b))|b(((((bb|ba)a|bbb)b|(aba|b(b|a)(b|a))a)b|(b(b(b|a)(b|a)|a(ba|(b|a)b))|aa(aa|(b|a)b))a)b|((((ba|(b|a)b)b|aba)b|(a(ba|(b|a)b)|b(bb|ba))a)b|((b(b(b|a)|aa)|a(aa|ba))a|((ab|ba)b|(bb|ba)a)b)a)a)))$"

so did yours work without anchoring?

aaaand yes, I guess I should make my groups non-capturing 🙂

how did you create that visualization?

I don't think it's possible to create a regular expression to solve part 2, because the rule:

11: 42 31 | 42 11 31

@U067R559Q did you generate that regex??

> how did you create that visualization? @U65FN6WL9 https://regexper.com/

@U2PGHFU5U hahaha, did it by hands https://media.giphy.com/media/lCbSAbRrFEfkY/giphy.gif

@U01GG79SA00 you’re right, it’s not possible at least in Clojure/Java. But there is a trick I used. You aren’t asked to solve general problem, what they ask is to solve a given input. In the end, I generated a regex for the part 2, which searches only five levels down.

I'd be interested in peoples thoughts. I found the results not as elegant as some of the solutions here.

He's definitely not doing the most elegant, fancy, super smart solution and you can tell he Clojure isn't his strongest language, but he does go through most of his process step by step in a pretty entertaining way, so I definitely like seeing how he thinks through stuff.

9/10 recommendation because of the didactic part for more people that are newer to clojure

Yeah, Martin has a long history of OO and Java. I think his move to clojure is relatively recent. But he’s made some quite strong statements about its good qualities.