Fork me on GitHub
#adventofcode
<
2021-12-15
>
alekszelark04:12:36

🧵Day 0xF answers thread: post your answers here

AC06:12:05

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

alekszelark07:12:19

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

peterc07:12:11

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

alekszelark07:12:01

Oh, thank you, I see

alekszelark09:12:06

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

alekszelark09:12:20

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

erwinrooijakkers10:12:34

Wat does (Character/digit n 10) do?

mikelis10:12:13

parses a char into an integer

mikelis10:12:08

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

tschady12:12:24

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.

cyppan13:12:01

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)

👍 1
euccastro17:12:18

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

👍 1
euccastro17:12:17

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

euccastro17:12:47

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

euccastro17:12:04

so it runs in <4s

Callum Oakley17:12:01

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

👍 1
Antonio Bibiano20:12:52

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

sarcilav21:12:58

@U01HY37QQUA? how? maybe wrong data structure implementation?

AC21:12:40

@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

thumbnail21:12:01

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.

thumbnail21:12:12

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

sarcilav22:12:41

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: https://samadams.dev/2021/12/15/advent-of-code-day-15.html

kevinc00:12:55

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

kevinc01:12:01

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.

lread03:12:41

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!

kingcode02:01:35

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.

lread19:01:51

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

kingcode03:01:21

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?

Stuart17:12:03

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

Stuart17:12:49

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?

Stuart17:12:13

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.

Stuart17:12:59

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

Stuart17:12:31

thanks, that helps

genmeblog19:12:17

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?

euccastro17:12:23

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

AC17:12:25

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…?

AC19:12:41

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…

AC19:12:03

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!

genmeblog19:12:17

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

🙌 1
samedhi03:12:11

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.

samedhi04:12:44

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

Stuart19:12:41

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!

genmeblog19:12:05

how do you count character count?

genmeblog19:12:03

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

Stuart19:12:05

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.

genmeblog19:12:15

what is the result after, say 20 cycles?

Stuart19:12:15

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

genmeblog19:12:38

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

Stuart19:12:55

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

genmeblog19:12:14

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

Stuart19:12:33

is that for the test data ?

Stuart19:12:12

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

Stuart19:12:52

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

genmeblog19:12:52

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

genmeblog19:12:49

check also "NO" count

genmeblog19:12:34

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

Stuart19:12:33

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

genmeblog19:12:54

it looks valid at the first glance...

genmeblog19:12:14

shit... sorry

Stuart19:12:27

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}

genmeblog19:12:38

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

genmeblog19:12:57

The result on test data is 1961318

genmeblog19:12:16

{[\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}

genmeblog19:12:31

sorry for confusion, my fault

Stuart19:12:00

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

genmeblog19:12:25

for 10 I got 2194

genmeblog19:12:59

for 40: 2360298895777

Stuart19:12:29

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

Stuart20:12:47

Is this a valid way of doing 10 cycles

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

genmeblog20:12:23

it's better to use iterate

genmeblog20:12:07

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

👍 1
genmeblog20:12:24

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

tschady20:12:33

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

Stuart20:12:42

yes please

tschady20:12:02

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

Stuart20:12:03

is it that you can get duplicate results from the pairs

Stuart20:12:27

thanks for confirming that

tschady20:12:03

that one bit a friend

Stuart22:12:11

got it! Thanks for the help guys 😄

bananadance 2
sebastian22:12:20

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

lread23:12:55

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

Stuart23:12:25

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