Clojurians Log v2

Day 19 answers thread - Post your answers here

I am going to take the slow path and do something with instaparse.

.. 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 🙂.

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.)

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.

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

I am not sure how instaparse does its grouping

It still does not work

TIL a few needed instaparse functions from @coyotesqrl

@coyotesqrl 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

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

> “I am a good library, AoC had me tested!” > > — Instaparse

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

Haha instaparse, really the tip of the day 😄

I solved it with regexs 😂

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

read part2 description and *insta*ntly replaced page of spaghetti embarrassment with instaparse :kappa:

me and my regular expression for part 1

〜(＞＜)〜

"(?:(?:(?:b(?:b(?:(?:b(?:(?:(?:ab|aa)b|(?:ab|bb)a)b|(?:(?:ba|bb)b|(?:ab|bb)a)a)|a(?:(?:a(?:ab)|b(?:ba|bb))b|(?:b(?:ab|aa)|a(?:aa|b(?:b|a)))a))a|(?:b(?:a(?:(?:b|a)(?:(?:b|a)b|aa))|b(?:a(?:ab|bb)|b(?:aa|b(?:b|a))))|a(?:(?:(?:ab|aa)(?:b|a))a|(?:(?:aa)b|(?:ab|aa)a)b))b)|a(?:(?:b(?:(?:(?:ba|bb)b|(?:ab|bb)a)b|(?:a(?:(?:b|a)b|aa)|b(?:ab|ba))a)|a(?:a(?:(?:ab|bb)a|(?:(?:b|a)(?:b|a))b)|b(?:(?:ab|aa)(?:b|a))))b|(?:b(?:(?:(?:(?:b|a)(?:b|a))a|(?:bb)b)b|(?:(?:ab)a|(?:ab)b)a)|a(?:a(?:(?:ab|aa)a)|b(?:b(?:(?:b|a)(?:b|a))|a(?:bb))))a))|a(?:(?:a(?:(?:(?:a(?:ab|aa)|b(?:ab|(?:b|a)a))a|(?:b(?:ab)|a(?:ab|ba))b)b|(?:(?:(?:bb|aa)a)a|(?:(?:b|a)(?:ab|(?:b|a)a))b)a)|b(?:b(?:(?:a(?:ab))b|(?:b(?:(?:b|a)b|aa)|a(?:bb|aa))a)|a(?:b(?:b(?:bb|aa)|a(?:ba|bb))|a(?:(?:aa)a|(?:bb)b))))a|(?:(?:b(?:a(?:(?:ab)a|(?:aa|b(?:b|a))b)|b(?:b(?:(?:b|a)(?:b|a))|a(?:bb)))|a(?:(?:b(?:ba|bb)|a(?:bb))b|(?:(?:(?:b|a)b|aa)a)a))b|(?:(?:a(?:(?:ab|(?:b|a)a)b|(?:ab|ba)a)|b(?:(?:(?:b|a)(?:b|a))a|(?:ab|aa)b))a|(?:a(?:a(?:ab)|b(?:(?:b|a)b|aa))|b(?:b(?:ba|bb)|a(?:bb)))b)a)b)))(?:(?:b(?:b(?:(?:b(?:(?:(?:ab|aa)b|(?:ab|bb)a)b|(?:(?:ba|bb)b|(?:ab|bb)a)a)|a(?:(?:a(?:ab)|b(?:ba|bb))b|(?:b(?:ab|aa)|a(?:aa|b(?:b|a)))a))a|(?:b(?:a(?:(?:b|a)(?:(?:b|a)b|aa))|b(?:a(?:ab|bb)|b(?:aa|b(?:b|a))))|a(?:(?:(?:ab|aa)(?:b|a))a|(?:(?:aa)b|(?:ab|aa)a)b))b)|a(?:(?:b(?:(?:(?:ba|bb)b|(?:ab|bb)a)b|(?:a(?:(?:b|a)b|aa)|b(?:ab|ba))a)|a(?:a(?:(?:ab|bb)a|(?:(?:b|a)(?:b|a))b)|b(?:(?:ab|aa)(?:b|a))))b|(?:b(?:(?:(?:(?:b|a)(?:b|a))a|(?:bb)b)b|(?:(?:ab)a|(?:ab)b)a)|a(?:a(?:(?:ab|aa)a)|b(?:b(?:(?:b|a)(?:b|a))|a(?:bb))))a))|a(?:(?:a(?:(?:(?:a(?:ab|aa)|b(?:ab|(?:b|a)a))a|(?:b(?:ab)|a(?:ab|ba))b)b|(?:(?:(?:bb|aa)a)a|(?:(?:b|a)(?:ab|(?:b|a)a))b)a)|b(?:b(?:(?:a(?:ab))b|(?:b(?:(?:b|a)b|aa)|a(?:bb|aa))a)|a(?:b(?:b(?:bb|aa)|a(?:ba|bb))|a(?:(?:aa)a|(?:bb)b))))a|(?:(?:b(?:a(?:(?:ab)a|(?:aa|b(?:b|a))b)|b(?:b(?:(?:b|a)(?:b|a))|a(?:bb)))|a(?:(?:b(?:ba|bb)|a(?:bb))b|(?:(?:(?:b|a)b|aa)a)a))b|(?:(?:a(?:(?:ab|(?:b|a)a)b|(?:ab|ba)a)|b(?:(?:(?:b|a)(?:b|a))a|(?:ab|aa)b))a|(?:a(?:a(?:ab)|b(?:(?:b|a)b|aa))|b(?:b(?:ba|bb)|a(?:bb)))b)a)b))(?:a(?:a(?:(?:b(?:b(?:b(?:ab|aa)|a(?:ba|aa))|a(?:(?:b|a)(?:ab|bb)))|a(?:(?:b(?:ab|bb)|a(?:ab|aa))a|(?:(?:ab|bb)a|(?:ab|(?:b|a)a)b)b))b|(?:a(?:b(?:a(?:ab|aa)|b(?:(?:b|a)(?:b|a)))|a(?:a(?:bb)|b(?:aa)))|b(?:a(?:b(?:aa)|a(?:bb|aa))|b(?:b(?:(?:b|a)(?:b|a))|a(?:bb))))a)|b(?:a(?:a(?:(?:a(?:ba|(?:b|a)b)|b(?:ab|(?:b|a)a))a|(?:a(?:ab|ba)|b(?:ba|bb))b)|b(?:(?:b(?:ab)|a(?:ab|ba))b|(?:b(?:ab|ba)|a(?:ab|aa))a))|b(?:b(?:b(?:(?:(?:b|a)b|aa)a|(?:aa)b)|a(?:(?:ab|bb)a))|a(?:(?:(?:aa|b(?:b|a))b|(?:ab|ba)a)a|(?:a(?:ba|(?:b|a)b)|b(?:ab|(?:b|a)a))b))))|b(?:(?:(?:(?:(?:a(?:ab|aa)|b(?:(?:b|a)(?:b|a)))a|(?:a(?:aa)|b(?:aa))b)a|(?:b(?:a(?:ab|ba)|b(?:ba|bb))|a(?:a(?:ab|aa)|b(?:ab|(?:b|a)a)))b)b|(?:(?:b(?:(?:ab|ba)b|(?:ba|aa)a)|a(?:a(?:ab|ba)|b(?:aa|b(?:b|a))))b|(?:a(?:a(?:ab|ba)|b(?:aa|b(?:b|a)))|b(?:(?:ba|bb)a|(?:ab)b))a)a)a|(?:(?:(?:(?:(?:ba|bb)b|(?:bb)a)a|(?:b(?:ab|ba)|a(?:ab|bb))b)b|(?:a(?:a(?:(?:b|a)b|aa)|b(?:ab|ba))|b(?:(?:ab|bb)a|(?:ab)b))a)a|(?:(?:a(?:(?:ba|bb)a|(?:ab)b)|b(?:b(?:bb)|a(?:ba|bb)))a|(?:(?:b(?:ab)|a(?:ba))a|(?:(?:ab|ba)a|(?:ba|aa)b)b)b)b)b))))"

you got to do what you got to do©

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 🙂

Instaparse can start at any rule, there is an option for that.

(insta/parser new-grammar :start :rule0)

Yeah, I’ve now learned that I didn’t need to do any of the pre-processing to the rules. I wonder if Wastl knew about Clojure+Instaparse 🙂.

Instaparse was so so helpful when I built this old thing (about four years ago 😮) https://www.imperimetric.com/ I felt pretty dumb when I didn't use it for day 18 when I had used it so much before

The grammars: https://github.com/Dexterminator/imperimetric/tree/master/src/clj/imperimetric/grammars

I did (str "S = 0\n" input)

btw: https://akovantsev.github.io/corpus/clojure-slack/instaparse#t1582822396013800

http://instaparse-live.matt.is/

Has anyone else seen https://www.youtube.com/watch?v=Ren_QQHM3iI Livecoding Clojure AOC?

Oohh that's real nice

how did you create that visualization?

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

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