Fork me on GitHub
#adventofcode
<
2021-12-16
>
lread00:12:40

This is the first one I will not be able to finish by the end of the day. Perhaps a sign just to take the rest of the challenges at a non-daily pace for me.

alekszelark04:12:02

🧵Day 16 answers thread: post your answers here

AC07:12:18

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

👍 1
alekszelark09:12:14

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

genmeblog11:12:05

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

norman14:12:01

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.

👍 1
Antonio Bibiano14:12:39

I have to say, mutual recursion is thrilling :D

Björn Ebbinghaus14:12:06

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

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

👏 2
Antonio Bibiano14:12:42

well that's pretty cool

tschady14:12:40

i hated this problem, such tedious reading

🤯 2
Antonio Bibiano14:12:57

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

alekszelark15:12:28

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

euccastro16:12:54

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

AC18:12:51

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

tschady19:12:47

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

👏 1
Sam Adams19:12:27

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

AC19:12:00

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.

tschady19:12:49

if you liked this problem then we are enemies

😢 1
😆 1
Antonio Bibiano19:12:48

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

1
tschady19:12:47

like being released from prison

😆 1
Antonio Bibiano19:12:51

ahahhaha right 😄

kevinc03:12:29

This was like a vacation compared to yesterday. I really liked the exercise. https://github.com/kconner/advent-of-code/blob/master/2021/16a.cljhttps://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.

karol00:12:24

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

genmeblog16:12:00

@sebastian I've started to use it for the other project (for a documentation). What cases you want to see?

sebastian18:12:11

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.

genmeblog18:12:55

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

genmeblog18:12:05

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

genmeblog18:12:39

Generated by quil or clojure2d for example

genmeblog18:12:58

It can be done via direct html embedding

R.A. Porter00:12:15

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.

ivangalbans22:12:07

🧵 Day 16 -

ivangalbans22:12:40

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 ?

ivangalbans22:12:50

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

genmeblog22:12:38

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

👌 1
lread23:12:21

I found day 16 much easier than day 15. Still not finished day 15!

lread03:12:22

Ugh! Finally finished day 15!