Fork me on GitHub

🧵Day 0xF answers thread: post your answers here


I have a lot of code clean-up and optimization to do.. 17s for part 2.


> However, risk levels above `9` wrap back around to `1`. @U0954HGDQ why do you wrap it back when n is equal to 9, not above? (if (= n 9) 1 (inc n)))


I think its because the function is increasing n (`n` hasn't been increased yet)


Oh, thank you, I see


The same result could be gotten with #(inc (mod % 9))


I slept not much today, so my brain’s working badly 🤯


Wat does (Character/digit n 10) do?

Miķelis Vindavs10:12:13

parses a char into an integer

Miķelis Vindavs10:12:08

user=> (Character/digit \9 10)
user=> (type \9)
user=> (type (Character/digit \9 10))


280ms / 9s, used ubergraph doc: code: I did Djikstra once, ain’t nobody got time to type that out all day. I also assume input is a square, easy enough to change for rects.


Djikstra indeed! I’ve used which is a pretty nice way of using a priority queue in Clojure (~ 100ms / 2500ms)

👍 1

I no longer have the time to try and factor nicely across parts, so ugly redefs will have to do:

👍 1

... but it actually implements it in the code, instead of using it from a library (nothing wrong with that, I just felt like using the opportunity to have a refresher)


and this also allowed me not to compute the paths, just the cost of the result


so it runs in <4s

Callum Oakley17:12:01

had a dijkstra function ready to go from previous years. 72ms/1.7s there goes my sub 1s total runtume (for the year) 😞 was fun while it lasted. 2.5s total now, 740ms before today

👍 1
Antonio Bibiano20:12:52

Wow my dijkstra takes 98 seconds on the second grid :(


@U01HY37QQUA? how? maybe wrong data structure implementation?


@U01HY37QQUA are you keeping track of all the paths you’re trying? I did that to help with debugging, but then ripped it out. Mine sped up from 17s to 4s.

Antonio Bibiano21:12:19

Mhh maybe my implementation is very inefficient, it takes about 1 second on part 1

Antonio Bibiano21:12:40

I'll try to clean it up and post it in a bit


I used A* (which isn't the best pick for topleft to bottom right, but okay), but it runs in ~1.2S for part1 and doesn't finish for part 2 :') 102ms for part 1 and <4s for part 2. That wraps it up 😬

Callum Oakley21:12:48

@U01HY37QQUA if I had to guess… are you considering positions more than once? If you return to a position you’ve already seen, then you’re necessarily returning to it via a longer path than the first time, so you can ignore it.


I sped up my algorithm by a factor of 10 by just using a proper priority map 😅

💯 1
Antonio Bibiano21:12:16

this is my implementation

Antonio Bibiano21:12:57

my first guess would be that sorting becomes expensive as tds becomes bigger and bigger

Antonio Bibiano22:12:04

i changed (first (sort-by val tds)) to (apply min-key val tds) and got down to 15 s


ah yeah, that helps, sort is O(n log n) and min is O(n)

💪 1
Sam Adams23:12:11

I spent way too long trying to invent an algorithm for this… thanks to @U0124C56J5R for pointing me to Dijkstra’s. Toxic code:


Brute force, and probably not doing lazy sequences right because I can't fit part 2 in a heapsize under 50MB… 0.2s and 1.0s though!


No, I have to take that back. I spaced on checking my second answer after I got the correct answer for the sample input. There are paths I don't consider at all.


Blech! Finally finished day 15 using dijkstra alg. My code is a mess, but I’m not gonna clean this one up anytime soon! Clever fellow that dijkstra!


I implemented Dijkstra first the naive way (no priority queue, 41+ secs on real input for part 1, no part2 result); then used (370 msecs for part1), then used a Fibonacci Heap (252 msecs for part1, 10+ secs for part2). I kept track of all the paths throughout.


I kept track of paths too so that I could easily print out a visualization.


As an aside, I couldn’t find a Clojure implementation of a Fibonacci Heap, so I fetched a (mutable) Java impl. and hacked a wrapper around it. Does anyone know of a Clojure and/or persistent FibHeap impl?


Can someone who has solved Day 14 help me debug an issue, issue in thread


Using the test data "NNCB" After 10 cycles of reactions, I get

{"CH" 21, "HH" 32, "BH" 81, "BN" 735, "NH" 27, "NB" 796, "HB" 26, "BC" 120, "CN" 102, "CC" 60, "BB" 812, "CB" 115, "HN" 27, "HC" 76, "NC" 42}
Can someone who has solved it tell me what the pair counts are after 10 iterations?


When I try to solve, I'm counting the number of character and halving it. BUt I'm off by one on some

R.A. Porter17:12:59

The last character in the template string.


oh yeah, its the first and last char that is off by one


thanks, that helps


You have to add first and last characters too before dividing by 2.

Sam Adams17:12:42

SPOILER ALERT — day 15 hint request 🪡🙏

Sam Adams17:12:28

Maybe just a sanity check: contrary to the examples, the min-risk path CAN include leftward and upward movements, right?


theoretically yes, I haven't checked whether they happen in my real input


yes. people were posting example grids in the reddit thread that break the assumption that it’s only down and to the right. for example: <tel:1911191111|1911191111> <tel:1119111991|1119111991> <tel:9999999111|9999999111> <tel:9999911199|9999911199> <tel:9999119999|9999119999> <tel:9999199999|9999199999> <tel:9111199999|9111199999> <tel:9199999111|9199999111> <tel:9111911191|9111911191> <tel:9991119991|9991119991>

Sam Adams17:12:08

Gahh, okay, thanks!

Sam Adams18:12:16

I’m stumped… were people able to write recursive memoized solutions? Or is a stateful cache necessary…?


my main logic is a loop and a priority-map. have you gotten any hints/spoilers about what algorithm others are using? (I don’t want to give too many hints unless you want them)

Sam Adams19:12:11

Have had no hints yet, but I’d appreciate any that come to mind 🙂 (at this point just hoping to avoid punting or reading the solution thread)

Sam Adams19:12:08

“priority-map” confuses me so I suspect my basically brute-force approach (to which I’m trying to add memoization and pruning) is very wrong…


most people are using Dijkstra’s algorithm (or A* though it didn’t help speed mine up at all)

🙌 1
Sam Adams19:12:29

That’s a very helpful hint and just what I was after, thanks!


my two hints for dijkstra: you don't need to track a path and you should stop after reaching the end

🙌 1

Wow, finally Took me a long time to reason that I could use a sorted map as a heapq like thing.


I would love to see other peoples solution to this day.


Day 14 is annoying me majorly. It works for the test data, gets the correct answer of 1588 after 10 cycles Wrong answer for real data. I re-write with a different approach. It works for the test data, gets the correct answer of 1588 after 10 cycles. Exactly the same wrong answer for the real data! Argh!


how do you count character count?


my string has the same character at the beginning and the end and it broke my first attempt


I end up with two chars that have an odd number of counts. One char is the same as the first char in the string, so I add 1 to that. Same with the last char in the string. THen I find the max and min, do max-min, and half that result.


what is the result after, say 20 cycles?


My algo is, I only keep track of the number of each pairs, then on each react cycle I swap out the key with that pair (repeated n times, where n is the original keys value).


I remove everything before next cycle. I mean I build counts from the scratch every time.


Yeah, that's waht I'm doing too. My react method

(defn react [reactions v]
  (reduce (fn [acc [k v]]
            (let [freq (frequencies (flatten (repeat v (reactions k))))]
              (merge-with + acc freq)))
where reactions is a map of reactions
{"CH" ["CB" "BH"], "HH" ["HN" "NH"], "BH" ["BH" "HH"] ...}
And v is a map of the current pair counts
{"NN" 1
 "NC" 1
 "CB" 1}


to verify: after 20 cycles my result is: 2264701 and for example [\N \O] is 77113


is that for the test data ?


oooh, for the test data I get 1961318 after 20 cycles.


so there is something that happens after 10 cycles, that doesnt happen in the first 10 cycles for me!


yep, sometimes some bug appears later than sooner (was there 🙂 )


check also "NO" count


if it's the same it could mean that your final counting is wrong not pair counting


It's my react function, I guess as I don't end up with any "NO" key at all after 20


it looks valid at the first glance...


shit... sorry


After 20 my map looks like

{"CH" 10614, "HH" 10002, "BH" 20606, "BN" 965778, "NH" 6775, "NB" 983801, "HB" 13841, "BC" 36044, "CN" 31220, "CC" 18022, "BB" 986886, "CB" 24787, "HN" 6775, "HC" 17379, "NC" 13198}


sorry, I have the same result as you... I used the same var for my data and test data and acciedentally shadow one by another


The result on test data is 1961318


{[\C \H] 10614, [\H \C] 17379, [\N \C] 13198, [\N \H] 6775, [\C \N] 31220, [\N \B] 983801, [\B \C] 36044, [\B \B] 986886, [\B \H] 20606, [\C \C] 18022, [\H \N] 6775, [\C \B] 24787, [\H \B] 13841, [\B \N] 965778, [\H \H] 10002}


sorry for confusion, my fault


so my problem is, something happens in real data that doesnt happen in test data!


for 10 I got 2194


for 40: 2360298895777


oh, thats helpful, i deffo have a problem as after 10 I'm getting 4151/2


Is this a valid way of doing 10 cycles

(->> (partial react reactions)
     (repeat 10)
     (apply comp))
Then just call that with my starting map ?


it's better to use iterate


(nth (iterate (partial react reactions)) 10)

👍 1

however comp of 10 the same functions should be ok as well


there is a key difference between real and test data, want a hint?


yes please


teh example data only has at most 1 of each pair. real data has multiple.


is it that you can get duplicate results from the pairs


thanks for confirming that


that one bit a friend


got it! Thanks for the help guys 😄

bananadance 2

General question: has anyone tried used Clerk to do some visualizations on their AoC problems? I would like to see some use-cases.


Someone said it starts to get harder on day 15. Well, I think I see watcha meant there!


i'm trying to wrangle my existing clojure maze solver into a solution for this, but i dont think i can use it