Fork me on GitHub

Day 21 - Solutions

norman06:12:40 When part 2 came up, I wrote the code to generate an expression as a string. For the sample input, I was able to give that expression to wolfram alpha to solve, which it did. The full input was too long for wolfram. I was tempted to find something else that would solve it for kicks, but in the end i just wrote the code. The solver wasn't too hard, but it took at least an hour to figure out the cases correctly, which seems quite excessive...

Callum Oakley11:12:46 I did the symbolic manipulation... sort of. let human input be h, then I kept track of the pair [a b] (represents ah + b) and then optimistically assumed that we'd never have to deal with an h^2 or h^-1 term... which turned out to be true 😅

👍 1

I’m not sure my solution works for all datasets 🙈 Instead of replacing the root operator with = I replaced it with compare and used it to recursively narrow down to the right number. I created the expression as a list first and then created a function simplify that postwalks up the expression and evaluates all lists that contain just an operator and a number.


Macro for part-1 (still working on part-2):

(defn parse [line] (split-line line #":\s|\s"))

(def data (map parse (read-data 2022 21)))

(defmacro build-oparations
  `(do ~@(for [[f a op b] data
               :let [f (symbol f)]]
           (do (println f a op b)
               (if-not op
                 `(def ~f (constantly ~(parse-long a)))
                 (let [[a op b] (map symbol [a op b])]
                   `(do (declare ~a) (declare ~b)
                        (defn ~f [] (~op (~a) (~b))))))))))

;; => 83056452926300

Callum Oakley12:12:09

totally changed my approach since someone pointed out that the graph is a tree (should have been obvious given the "root" hint :face_with_rolling_eyes:). since it's a tree the resulting function is guaranteed to be linear in h, so you can take the value at two points and extrapolate

🤯 3
bellissimo 1

@U01HL2S0X71 brilliant, just came to the same

😎 1
Alex Alemi14:12:36

I enjoyed today's puzzle. For the first part, I implemented a memoized recursive evaluator because I feared he would be unkind and have us recompute lots of things lots of times, but that turned out to be overkill. For part 2 I looked at the data and saw it was tree-like, so I wrote a solver but it simply 'unwinds' the equality at each stage. i.e. if we are sitting on a = x + b at the top, where a and b are numbers, we know that x = a - b. You can iterate this until you find the number.


Wow, yeah, it is linear. You can just search for it. (or compute it)


Using promises & futures. (I recycled my code with very few changes from 2015 day 7.) These are the only 2 where I keep state, but I like how this reads:

(defn run-prog! [memory prog]
  (reset! memory {})
  (alloc-registers! memory prog)
  (doseq [inst prog]
    (exec-inst! memory inst)))


;; p1
(let [parse (fn [line]
              (let [[id x op y] (map read-string (str/split line #":?\s"))]
                [id (if (number? x) x (list op x y))]))
      db    (->> input (str/split-lines) (map parse) (into {}))]
  (->> 'root db
    (clojure.walk/prewalk-replace db)
"Elapsed time: 30.751088 msecs"
=> 353837700405464

😆 1
clojure-spin 2

part 1 using promises. let me see if I can do the same for part 2


part 2 “Elapsed time: 61.375238 msecs”


this is a problem made for lispers


Day 21: This was the funnest one for me. I did the symbolic algebra.


geez I made the mistake of reading the other solutions… great job! not as much fun as symbolic solver 😉 but I wished I’d thought of the fact that it was a linear function. Would have definitely would have saved some time.


@U1Z392WMQ I thought I was being original with the promises and futures 😞


managed to solve part 2 through... visual inspection!


Showing my symbolic manipulation output:

(- (/ (+ 4 (* 2 (- humn 3))) 4) 150)
[+ -150 [* 1/4 (+ 4 (* 2 [+ -3 humn]))]]
[+ -301/2 [* 1/2 humn]]
This is where ‘= is replaced with ‘- effectively setting the equation equal to 0. The normalizing and simplifying code is pretty tidy thanks to core.match
(defn norm [[op exp1 exp2 :as all]]
  (condp = op
    '- (if (number? exp2)
         ['+ (* -1 exp2) exp1]
         ['+ exp1 ['* -1 exp2]])
    '/ (if (number? exp2)
         ['* (/ 1 exp2) exp1]
    (if (number? exp2) [op exp2 exp1] all)))

(defn simplify-exp [[op x exp2 :as arg]]
  (match [op (if (sequential? exp2) (vec exp2) [])]
         ['+ ['+ y other]] ['+ (+ x y) other]
         ['* ['* y other]] ['* (* x y) other]
         ['* ['+ y other]] ['+ (* x y) ['* x other]]
         :else arg))

(def normalize (partial postwalk #(cond-> % (sequential? %) norm)))
(def simplifier (partial postwalk #(cond-> % (sequential? %) simplify-exp)))


My solution for part2: 1. adds to the data set y=x*z and z=y/x when x=y/z is seen. 2. replaces root=x ops y with x=y+0 and y=x+0


learned the first thing about core.logic it was expecially satisfying that part 2 executed instantly

nice 1
📚 1
clj 1
bellissimo 1

@U02CV2P4J6S that is absolutely awesome!


Oh, I’d forgotten that core logic was a thing. Nice work!


Day 21 - Can your solution solve this

root: pppw + sjmn
pppw: 3 + humn
sjmn: 5 - humn


Is that your input? Or just a case that you accounted for?


I am just wondering. The puzzle doesn't exclude this kind of input, right?


with * and / in the mix this could be a problem of solving an equation.


i think i can still manage if there's only + and -


The puzzle does exclude this


I can tell you more if you want


I just finished


Oh that's good. So two lines join at the root pretty much

Miķelis Vindavs21:12:45

@U064J0EFR I re-read the problem statement but didn’t find anything that said that each value is used only once

Miķelis Vindavs21:12:24

I did my initial p2 solution using z3, because i was worried the equality could be really complex and nonlinear, but ended up making a really simple “reverse application” solution instead

Miķelis Vindavs21:12:38

but it assumes that humn is only referenced in one branch, and only once


in my problem the humn value has a direct line to the root

Miķelis Vindavs21:12:08

right, sure, but i mean the problem statement says nothing about this


that’s true

Callum Oakley21:12:36

properties of the input that aren't stated in the puzzle text have to be considered "part of the puzzle" imo or some previous days are borderline impossible


yeah there is definitely a stage of doing data analysis on the input for a few of these

Callum Oakley21:12:26

e.g. 2019 day 16 for a particularly infamous example 😅


This is one of the things that has always frustrated me about aoc - the input isn't input to your problem, it IS the problem to solve. The text along side is not a problem spec, it's just some text to help you understand the puzzle/problem you are given. I've come to peace with it over the years of aoc and don't treat it like I would other kinds of programming challenges. I also, always, look at my input and the question asked before I even read the text.

💯 1

Part1 my future/promise solution doesn’t care about special input structure, except that it’s solvable. Part2 I definitely looked at the behavior (linear) to simplify.