https://gitlab.com/maximoburrito/advent2021/-/blob/main/src/day16/main.clj good enough for aoc.. ship it

part 1 did a good job of hinting what part 2 would want, so I spent most of my time on it and then part 2 took just a few minutes. I wonder if we are going to see future days expand on this..

Today was the most tedious task so far https://github.com/nbardiuk/adventofcode/blob/master/2021/src/day16.clj

@U076FM90B totally agree, and I spent lots of time to find an annoying bug in my code

ugh... the same here... one bug ~2h to find if-not instead of if 😕

https://github.com/jacoelho/advent-of-code-clj/blob/main/src/aoc/2021/day16.clj

https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2021/day16.clj

Strange. I thought it was a fun problem. A parser and an expression evaluator. 95% of my time was on the parser, and that was mostly in trying to find a way to do this with clojure. Immutable parsers are hard. I did a pretty poor job with my attempt, but it was a fun thought process trying to figure out how to do it with those constraints. There was definitely more "reading and understanding" on this problem than others, but at no point was I finding it tedious.

I have to say, mutual recursion is thrilling :D

My solution for part 2 involves generating Clojure Code from this BITS code.

(macroexpand-1 '(BITS "C200B40A82"))
=> (clojure.core/reduce clojure.core/+ [1 2])

well that's pretty cool

i hated this problem, such tedious reading

Yeah took me a long time to wrap my head around it, after that I was afraid I would have to use trampoline to get the mutual recursion working, luckily it was fine

Didn’t refactor it, I probably won’t https://github.com/zelark/AoC-2021/blob/main/src/zelark/aoc_2021/day_16.clj

second part just builds a big clojure expression, and evals it

nothing fancy here; I build some kind of AST which is not a clojure expression, then walk it in a different way for each part: https://github.com/euccastro/advent-of-code-2021/blob/main/day16.clj

very clean!

I’m not happy with all the “take” and “drop” operations that I have to keep in sync, but I do like using lazy-cat to create a stream of binary digits from the input. Since there’s no need for backtracking, a destructive read from the bit-stream would be cleaner. I originally did a bunch of bit manipulations to create the bit-stream but then replaced it with a lookup table.

(ns aoc21.day16
  (:require [ :as io]))

;; part 1

(defn input-data [filename]
  (slurp (io/resource filename)))

(def hex->bin
  {\0 [0 0 0 0]
   \1 [0 0 0 1]
   \2 [0 0 1 0]
   \3 [0 0 1 1]
   \4 [0 1 0 0]
   \5 [0 1 0 1]
   \6 [0 1 1 0]
   \7 [0 1 1 1]
   \8 [1 0 0 0]
   \9 [1 0 0 1]
   \A [1 0 1 0]
   \B [1 0 1 1]
   \C [1 1 0 0]
   \D [1 1 0 1]
   \E [1 1 1 0]
   \F [1 1 1 1]})

(defn bit-stream [[hexchar & hexstr]]
  (if (nil? hexchar)
    nil
    (lazy-cat (hex->bin hexchar) (bit-stream hexstr))))

(defn bin->dec [bits]
  (reduce #(bit-or (bit-shift-left %1 1) %2) bits))

(defn packet-version [bits]
  (bin->dec (take 3 bits)))

(defn packet-type [bits]
  (case (bin->dec (take 3 bits))
    4 :literal
    :operator))

(defn decode-literal [version bits]
  (loop [[bit & bits] bits
         acc []]
    (case bit
      1 (recur (drop 4 bits) (concat acc (take 4 bits)))
      0 [{:version version
          :type :literal
          :value (bin->dec (concat acc (take 4 bits)))}
         (drop 4 bits)])))

(declare decode-packet)

(defn decode-operator [version bits]
  (let [optype (bin->dec (take 3 bits))
        ltype (take 1 (drop 3 bits))
        bits (drop 4 bits)]
    (case (bin->dec ltype)
      0 (let [len (bin->dec (take 15 bits))]
          (loop [spbits (take len (drop 15 bits))
                 acc []]
            (if (seq spbits)
              (let [[packet spbits] (decode-packet spbits)]
                (recur spbits (conj acc packet)))
              [{:version version
                :type :operator
                :op optype
                :children acc}
               (drop (+ len 15) bits)])))
      1 (let [cnt (bin->dec (take 11 bits))]
          (loop [i cnt
                 bits (drop 11 bits)
                 acc []]
            (if (> i 0)
              (let [[packet bits] (decode-packet bits)]
                (recur (dec i) bits (conj acc packet)))
              [{:version version
                :type :operator
                :op optype
                :children acc}
               bits]))))))

(defn decode-packet [bits]
  (let [version (packet-version bits)]
    (case (packet-type (drop 3 bits))
      :literal (decode-literal version (drop 6 bits))
      :operator (decode-operator version (drop 3 bits)))))

(defn sum-version [{version :version type :type children :children}]
  (case type
    :literal version
    (+ version (reduce #(+ %1 (sum-version %2)) 0 children))))

(defn soln-1 [filename]
  (sum-version (first (decode-packet (bit-stream (input-data filename))))))

;; part 2

(def optable
  {0 +
   1 *
   2 min
   3 max
   5 #(if (> %1 %2) 1 0)
   6 #(if (< %1 %2) 1 0)
   7 #(if (= %1 %2) 1 0)})

(defn solve-tree [{type :type value :value op :op children :children}]
  (if (= type :literal)
    value
    (apply (optable op) (map solve-tree children))))

(defn soln-2 [filename]
  (solve-tree (first (decode-packet (bit-stream (input-data filename))))))

i don’t like my code. There’s only 2 things I liked, cl-format and medley.core/take-upto:

(defn hex->bits [hex]
  (cl-format nil "~{~4,'0B~}" (map #(Character/digit % 16) hex)))

(defn slice-literal [stream]
  (let [val-part (->> stream
                      (partition 5)
                      (take-upto #(= \0 (first %))))
        stream   (drop (count (flatten val-part)) stream)
        value    (->> val-part
                      (map (partial drop 1))
                      flatten
                      (s->int 2))]
    [value stream]))

I find these problems somehow both tedious and satisfying… too much reading for midnight, though. https://samadams.dev/2021/12/16/advent-of-code-day-16.html

yeah.. when I saw the wall of text, I debated waiting until the morning. I did waste a fair amount of time because I read “bits at the end are extra due to the hexadecimal representation and should be ignored” as meaning that we had to handle the padding ourselves on every packet. I was throwing out bits that didn’t cause problems until later examples with sub-packets.

if you liked this problem then we are enemies

I dreaded it until I got the main pieces down, then actually running and see the codes get parsed gave me a rush 😄

like being released from prison

ahahhaha right 😄

This was like a vacation compared to yesterday. I really liked the exercise. https://github.com/kconner/advent-of-code/blob/master/2021/16a.clj, https://github.com/kconner/advent-of-code/blob/master/2021/16b.clj. Now I'm trying to find ways to shorten it; I think the state monad is relevant.

https://github.com/kfirmanty/advent-of-code-2021/blob/main/src/day16.clj as most of the people also enjoyed this over the day15, part 2 went rather quickly as I was converting stuff to proper representation as I went through the packets And when parsing I went probably with easiest solution: always return: [left-to-parse parsed-element] data structure

for example how to visualize some AOC solutions like 2d grids or things like that. what would be a good format to be easily visualized. Things like that.

as far as I know, vega light and plotly are supported, that means that you should generate spec for that

also I know that currently support for images (generated or external) are not easily supported as it's in nextjournal. But it's comming.

Generated by quil or clojure2d for example

It can be done via direct html embedding

If you don't need more from the grid other than on/off, there's also the brute-force way they use in their own Rule-30 example. I updated my day 13 solution (messily) to use that. The code's so-so, but it does lead to old-school calculator looking output.

You can embed image as described here: https://github.com/nextjournal/clerk/issues/37

when the length type id is 0, how do you know the number of bits in each packet? for example here, why not 12 + 15 = 27 ?

they are always chosen from 11 to 11 and they end up with one that is a power of 2 ?

You don't know the number of bits in each packet and you don't know the number of packets (which is the case for ID 1). You know total number of bits, you know that this number is valid and should contain complete subpacket (which can contain much more subpackets etc).

Ugh! Finally finished day 15!