Hi! Does anyone knows if day 16 (packet decoder) is solvable by something like Kern? https://github.com/blancas/kern

I thought it could be a good opportunity to learn some interesting parsing techniques (like parser combinators) but I’m not sure if the structure of the program is amenable to such a solution

(https://github.com/Engelberg/instaparse also looks like an interesting parsing library, so same question :-))

Note: I am not a ParseMaster. I’m more familiar with Instaparse, zero with kern. I don’t think you can do it with a pure CFG, because there would be ambiguity in level of subgroup, and that matters for part2. You need to recurse to either n subgroups or m bit length of subgroups. I think you can get the groupings right, but not the levels. I thought about hardcoding the n with PEG lookaheads and BNF, like just handling 1-9, but I don’t know a way to handle the m case. Which means you have to write code, so at that point I just did it with plain old . Kern’s state tracking is promising though, I hadn’t seen that before. Looks easy to handle n , and after a quick source browse, you may be able to get m through get-position . That seems to be the crux, figuring out how to consider the next m bits for parsing. I’m very interested if you crack it.

I think I’m making progress, but it’s a bit hacky, I think - would really appreciate your feedback @tws! I am just learning Clojure, so this is probably very non-idiomatic. My idea was to programmatically generate the appropriate parser:

(def base-parser-rules
  "packet = literal_packet | op_0_packet | op_1_packet
   literal_packet = version lit_val_type lit_val
   op_0_packet = version op_type '0' rest15 op_rest
   op_1_packet = version op_type '1' rest11 op_rest
   version = #'\\d{3}'
   rest11 = #'\\d{11}'
   rest15 = #'\\d{15}'
   lit_val_5 = #'\\d{5}'
   lit_val_4 = #'\\d{4}'
   lit_val_1 = #'\\d{1}'
   lit_val_2 = #'\\d{2}'
   lit_val_3 = #'\\d{3}'
   lit_val_type = '100'
   op_type = '000' | '001' | '010' | '011' | '101' | '110' | '111' 
   lit_val = lit_val_5+ (lit_val_1 | lit_val_2 | lit_val_3 | lit_val_4)?
   op_rest = #'\\d+'")

(def base-parser (insta/parser (str/join " \n " (list "S = packet" base-parser-rules))))
(defn parser-n-packets [n]
  (insta/parser 
   (str/join " \n " 
             (list 
              (str/join " = " (list "S" (str/join " " (reverse (conj (repeat n "packet") "op_rest"))))) 
              base-parser-rules))))

I think it’s starting to do what I want it to do… I’m having a really hard time with the tree structure returned by insta/parser; I’m sure there are nice ways to traverse/process it, I just haven’t found them 🙂

transform is the function to use to shape the tree output. I dunno, I think you’ve hit the wall. You’d have analyze rest11 and rest15 outside this grammar AFAICT, which is doable but I need one BNF grammar to make it appealing for me.

Got it. I thought this was doable with parser combinators (eval rest11/rest15 and proceed parsing accordingly), but I guess it’s not (or just significantly harder than I thought)… thanks anyway!

don’t let my relative ignorance talk you out of it. the extent of my instaparse knowledge is from past advent of code years