https://gitlab.com/maximoburrito/advent2021/-/blob/main/src/day15/main.clj

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

https://github.com/zelark/AoC-2021/blob/main/src/zelark/aoc_2021/day_15.clj

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?

parses a char into an integer

user=> (Character/digit \9 10)
9
user=> (type \9)
java.lang.Character
user=> (type (Character/digit \9 10))
java.lang.Integer

280ms / 9s, used ubergraph doc: https://github.com/tschady/advent-of-code/blob/main/doc/2021.adoc#aoc-2021-d15 code: https://github.com/tschady/advent-of-code/blob/main/src/aoc/2021/d15.clj 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 https://github.com/clojure/data.priority-map which is a pretty nice way of using a priority queue in Clojure (~ 100ms / 2500ms)

Dijkstra here (with slow second part, 13s)! https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2021/day15.clj

https://github.com/nbardiuk/adventofcode/blob/master/2021/src/day15.clj

I no longer have the time to try and factor nicely across parts, so ugly redefs will have to do: https://github.com/euccastro/advent-of-code-2021/blob/main/day15.clj

uses A*

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

had a dijkstra function ready to go from previous years. 72ms/1.7s https://github.com/callum-oakley/advent-of-code/blob/main/src/aoc/2021/15.clj there goes my sub 1s total runtume (for the year) 😞 was fun while it lasted. 2.5s total now, 740ms before today

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.

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

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 😬

@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 😅

this is my implementation

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

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)

I spent way too long trying to invent an algorithm for this… thanks to @U0124C56J5R for pointing me to Dijkstra’s. Toxic code: https://samadams.dev/2021/12/15/advent-of-code-day-15.html

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! https://github.com/kconner/advent-of-code/blob/master/2021/15a.clj, https://github.com/kconner/advent-of-code/blob/master/2021/15b.clj

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.

Got it: https://github.com/kconner/advent-of-code/blob/master/2021/15a.clj, https://github.com/kconner/advent-of-code/blob/master/2021/15b.clj. 115ms and 2.1s by a weighted flood fill.

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 clojure.data.priority-map (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?

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}

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

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.

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>

Gahh, okay, thanks!

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)

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)

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

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

Wow, finally https://github.com/samedhi/advent-of-code-2021/blob/main/30.clj. 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.

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)))
          {}
          v))

{"CH" ["CB" "BH"], "HH" ["HN" "NH"], "BH" ["BH" "HH"] ...}

{"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 ?

yes

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

thanks

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!

you can try on my test data: https://github.com/genmeblog/advent-of-code/blob/master/resources/advent_of_code_2021/day14.txt

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

it's better to use iterate

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

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 😄