Fork me on GitHub
<
2022-12-21
>
norman06:12:28

Day 21 - Solutions

norman06:12:40

https://gitlab.com/maximoburrito/advent2022/-/blob/main/src/day21/main.clj 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

https://github.com/callum-oakley/advent-of-code/blob/main/src/aoc/2022/21.clj 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
oddsor11:12:05

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. https://github.com/Oddsor/advent-of-code-clj/blob/master/src/y2022/d21.clj

genmeblog11:12:39

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

(build-oparations)
(root)
;; => 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 https://github.com/callum-oakley/advent-of-code/blob/main/src/aoc/2022/21.clj#L20-L24

🤯 3
1
1
alekszelark12:12:07

@U01HL2S0X71 brilliant, just came to the same

😎 1
Alex Alemi14:12:36

I enjoyed today's puzzle. https://github.com/alexalemi/advent/blob/main/2022/clojure/p21.clj 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.

norman15:12:31

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

misha17:12:15

``````;; 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)
(eval)
(time)))
"Elapsed time: 30.751088 msecs"
=> 353837700405464``````

😆 1
2
Felipe20:12:29

part 1 using promises. let me see if I can do the same for part 2 https://github.com/FelipeCortez/advent-of-code/blob/master/2022/21.clj

bhauman21:12:56

part 2 “Elapsed time: 61.375238 msecs”

bhauman21:12:26

this is a problem made for lispers

bhauman21:12:54

Day 21: This was the funnest one for me. I did the symbolic algebra. https://github.com/bhauman/advent-of-code-2022/blob/main/src/adv2022/day21/sol.clj

bhauman21:12:48

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.

Felipe02:12:47

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

Felipe02:12:58

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

bhauman03:12:14

Showing my symbolic manipulation output:

``````(- (/ (+ 4 (* 2 (- humn 3))) 4) 150)
(normalize)
[+ -150 [* 1/4 (+ 4 (* 2 [+ -3 humn]))]]
(simplifier)
[+ -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]
all)
(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)))``````

Apple06:12:32

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`

Benjamin12:12:29

learned the first thing about core.logic https://github.com/benjamin-asdf/advent-of-code/blob/master/src/Y2022/day21_logic.clj it was expecially satisfying that part 2 executed instantly

1
📚 1
1
1
bhauman12:12:31

@U02CV2P4J6S that is absolutely awesome!

1
stephenmhopper16:12:16

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

Apple21:12:32

Day 21 - Can your solution solve this

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

bhauman21:12:17

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

Apple21:12:48

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

Apple21:12:04

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

Apple21:12:41

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

bhauman21:12:27

The puzzle does exclude this

bhauman21:12:40

I can tell you more if you want

bhauman21:12:47

I just finished

Apple21:12:19

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

bhauman21:12:47

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

Miķelis Vindavs21:12:08

bhauman21:12:45

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

bhauman21:12:17

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 😅

norman22:12:38

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