Fork me on GitHub

Day 19 answers thread - Post your answers here

R.A. Porter05:12:22

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
  (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?)

👏 6
☝️ 6
bananadance 6
bellissimo 9
🍻 6
sheepy 6
🎉 12
😍 6
R.A. Porter05:12:10

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

👍 3

Got my best finish-placement yet. And learned about Instaparse!

🎉 6
Vincent Cantin06:12:37

TIL a few needed instaparse functions from @U01GXCWSRMW

👍 3
Vincent Cantin06:12:55

@U01GXCWSRMW Is that really necessary to sort the rules?

Vincent Cantin06:12:53

OOOOHHHH I found my bug !

Vincent Cantin06:12:08

I should parse from rule 0

Vincent Cantin06:12:29

Problem solved 🙂


I solved it with regexs 😂


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

misha08:12:50 @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"})
or if you don't mind repetition
(-> 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
       (map #(insta/parse parser %))
       (remove insta/failure?)


I wonder anyone else solved it without instaparse?

👍 3

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


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

Joe11:12:39 - Instaparse feels like cheating here, but the thought of building it myself filled me with horror.

👍 9

mine runs in ~300msecs


btw by "found" I mean I looked it up, not that I discovered it myself:

✔️ 3

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!

😮 3
🏎️ 6

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.

👍 6

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

👍 3
Vincent Cantin05:12:17

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

Vincent Cantin05:12:32

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

Vincent Cantin05:12:02

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

👍 6
Vincent Cantin05:12:42

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

👍 6

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

Vincent Cantin05:12:20

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


Moving too fast.

Vincent Cantin05:12:38

(= 'too-fast 'slow)


Yep 🙂.

Vincent Cantin05:12:36

I am learning the transform function.

Vincent Cantin06:12:55

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!

🎉 6

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

😄 3
R.A. Porter06:12:02

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

☝️ 3
Vincent Cantin06:12:38

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


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

Vincent Cantin06:12:25

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 ")")
                                                 :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?)

Vincent Cantin06:12:48

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

Vincent Cantin06:12:14

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

Vincent Cantin06:12:07

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.

Vincent Cantin06:12:43

I am not sure how instaparse does its grouping

Vincent Cantin06:12:29

It still does not work

Vincent Cantin07:12:39

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

Vincent Cantin07:12:52

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


> Tailwinds’s grammar using instaparse tell me more!

Vincent Cantin15:12:53

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

  (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"))

Vincent Cantin15:12:09

that’s my POC


where do you use it for?


at work we use tailwind


i mean: where do you use that parser for?

Vincent Cantin15:12:06

Short answer: Where you can.

Vincent Cantin15:12:13

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

Vincent Cantin15:12:46

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

Vincent Cantin15:12:08

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


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

Vincent Cantin15:12:30

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

Vincent Cantin15:12:39

I wanted to learn something.

Charles Fourdrignier15:12:10

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

💯 3

This one was painful. A solution without instaparse:

🎉 3
❤️ 3
👍 3
Vincent Cantin16:12:17

How did you handle the infinite loops ?


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

Vincent Cantin16:12:51

ah, I see … breadth search?

Vincent Cantin16:12:28

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.

👍 3
Vincent Cantin16:12:48

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

Vincent Cantin16:12:21

@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))]) ?


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.

Vincent Cantin17:12:01

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

😈 3

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.

😈 3
Vincent Cantin17:12:24

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.


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,

Vincent Cantin17:12:51

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

Vincent Cantin17:12:33

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.

Vincent Cantin17:12:03

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.

Vincent Cantin17:12:18

sleeping time here, see you tomorrow~




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!

👍 3

Looks great 👍

Vincent Cantin07:12:43

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

😂 9

Haha instaparse, really the tip of the day 😄


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


me and my regular expression for part 1



d 3
😱 9
😬 6
😭 3
party-corgi 9
🙈 3

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



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
requires matching n times whatever rule 42 matches followed by n times whatever rule 31 matches. If n is not known, then the language described by this rule is not regular, as it would require a "memory" (i.e. a stack) to keep track of how many instances of rule 42 have already been observed. (Your input may differ, but if you have a rule of the same "shape" the same logic applies)


@U067R559Q did you generate that regex??


> how did you create that visualization? @U65FN6WL9


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


you got to do what you got to do©

Vincent Cantin16:12:22

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

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

👍 21

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 😮) I felt pretty dumb when I didn't use it for day 18 when I had used it so much before


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

🤯 3

Has anyone else seen Livecoding Clojure AOC?

👀 6

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.


Oohh that's real nice