Fork me on GitHub
#adventofcode
<
2022-12-12
>
norman05:12:33

Day 12 - Solutions

wevrem07:12:09

Had one of those “aha!” thoughts as I was just about to head to bed, and totally revamped my approach for part II. Okay, maybe not so much “aha!” as “duh!”

alekszelark07:12:49

@UTFAPNRPT like your comments (thoughts) in the code

Callum Oakley09:12:37

https://github.com/callum-oakley/advent-of-code/blob/main/src/aoc/2022/12.clj always happy to have an opportunity to use my search functions. used the same trick as @UTFAPNRPT. searching in reverse 😌

Casey10:12:33

Today was fun! I leaned on loom rather than come up with my own bfs alg. https://github.com/Ramblurr/advent-of-code/blob/main/src/aoc/2022/day12.clj

alekszelark10:12:09

@U01HL2S0X71 how does it work for part 2 if you don’t change the climbing condition?

Callum Oakley10:12:55

I’m doing part 1 in reverse as well 🙂

alekszelark10:12:32

Ohh, I missed that 🙃

alekszelark12:12:59

Found out that my lowest destination on the way is just -2 from the current. Seems like nobody would break their legs.

😌 1
tschady13:12:52

Re-used my grid library, leveraged ubergraph algorithm, Terra Incognita has infinite height. https://github.com/tschady/advent-of-code/blob/main/src/aoc/2022/d12.clj

👍 1
leinfink15:12:12

I didn't keep track of particular paths, just spread out from the starting point with a counter for each step, using sets to avoid double checks. This worked flawlessly for multiple starting points (and goals also, I guess), so I think this was my luckiest part 2 so far. https://github.com/leinfink/aoc-2022-clj/blob/main/src/aoc22/day12.clj

nice 2
bhauman17:12:16

I’m high I’m low and I’m high again. Fun stuff!

🥴 1
bhauman17:12:08

one of my problems is I’m using the graph library loom b/c I be darned if I implement dikstras, but now I don’t have insight into why its choosing a least optimal path, other than I’m creating the graph wrong.

bhauman18:12:42

LGTM

👏 1
🗻 2
👍 1
bhauman18:12:23

yeah I guess there is an off by one error somewhere but looking at the output it really seems like the minimal path so I’m going to let it go for now, and come back to it this evening

Casey18:12:02

Consider that in the example explanation for Day12 they are counting steps, not the number of nodes visited

Casey18:12:15

That could be causing an off by 1

Casey18:12:23

(I also used loom 😊)

bhauman18:12:33

Thanks! That’s good advice. But … that’s already been accounted for as I dec the result.

bhauman18:12:45

awesome, loom users unite!

alekszelark18:12:37

@U064J0EFR Could you miss out this statement “This also means that the elevation of the destination square can be much lower than the elevation of your current square”?

bhauman18:12:45

thanks, yeah thats in there to and my path has to allow for that as it goes [ab … nopnopqr …]

1
genmeblog22:12:14

When your paths end nowhere, read this sentence after a couple of hours of debugging :/ > (This also means that the elevation of the destination square can be much lower than the elevation of your current square.)

chucklehead23:12:57

Came here to say basically the same thing

🙂 1
chucklehead00:12:15

Couldn’t figure out why my bfs worked on the sample but not the full

bhauman05:12:00

I did figure out my problem from earlier, I was setting start to 0 and end to 27 thinking that I was being clever. Still not sure why that added 4 steps to the result but … I’ll look into it more tomorrow

Apple06:12:43

y25 cannot get to E27

bhauman15:12:56

@UP82LQR9N my coding was 1-26 and I was using 0 for start and 27 for end. I was a real puzzler for me…

Apple15:12:44

1 for start and 26 for end then

Apple15:12:45

i use 0 and 25 for the 0-25 range

Apple15:12:27

doesn't matter really as long as the start and end falls in the range

bhauman17:12:45

But the interesting question is why would [start = 0, a = 1 … z=26, end = 27] provide a different result ing edge length of 444 in this case (both in loom and my custom bfs), and when I changed the mapping to [start = 1, a = 1 … z=26, end = 26] I got the correct solution of 440 . The traversal rules work the same for both? hmmmm ….

leinfink17:12:52

You can go from Y (25) to Z (26), but not to 27

💯 1
Apple17:12:07

y25 cannot get to E27

bhauman17:12:07

yeah thats right

bhauman17:12:34

so you can skip the last z

bhauman17:12:09

I just didn’t think that was correct

bhauman17:12:50

In fact you can skip all of the last z’s theoretically I just didn’t think the problem implied that at all

bhauman17:12:04

I’m rereading the problem for the qoute I missed now

bhauman17:12:23

Also included on the heightmap are marks for your current position (S) and the location that should get the best signal (E). Your current position (S) has elevation a, and the location that should get the best signal (E) has elevation z.

bhauman17:12:38

pretty straightforward …

leinfink17:12:40

if you got lucky and had my input instead, i think your mistake wouldn't have mattered and your day would have been much more relaxing haha

bhauman17:12:30

yep there are the extra steps

leinfink17:12:18

ah I had that start too, so it still would have mattered

leinfink09:12:40

@U89SBUQ4T oh, interesting. I wonder if the fact that I didn't need to do the backtrace part mitigates some of that slowness / memory usage? but i guess thats negligible

leinfink09:12:26

ohh and i like the idea of propagating waves from source and target at the same time

1
leinfink12:12:39

welp, tried it, didn't give any noticeable performance benefit tho

Benjamin15:12:52

tips for day 12?

Benjamin15:12:27

I have a function that finds all possible paths but the time complexity doesn't work for the input

alekszelark15:12:51

breadth-first search

Miķelis Vindavs15:12:45

you could google Dijkstra’s algorithm

Miķelis Vindavs15:12:04

also, clojure has a somewhat hidden datastructure called PersistentQueue It is fast to add to the back and remove from the end Create an empty one with clojure.lang.PersistentQueue/EMPTY (no parens needed) Add to the end (right) with conj Look at the first element (left) with peek Return a new queue without the first element with pop

Callum Oakley15:12:43

hard to say without seeing what you’ve already got, but given you say you already have a function to find all possible paths I have a hunch you’ll already be doing BFS (or something equivalent) and the time complexity issue will be because of double counting. make sure you’re not finding multiple paths to the same place! (you only care about the shortest one)

💯 3
👀 1
alekszelark15:12:30

a handy helper for PersistentQueue

(defn queue [& args]
  (into PersistentQueue/EMPTY args))

1
Miķelis Vindavs15:12:04

That’s exactly the one I have in my support namespace as well 😄

1
Callum Oakley15:12:51

while we’re sharing convenient type wrappers for search, here’s my https://github.com/callum-oakley/advent-of-code/blob/main/src/aoc/search.clj#L8-L13 based on clojure.data.priority-map (useful for Dijkstra)

👍 1
1
J15:12:04

I have used PriorityQueue

Miķelis Vindavs16:12:05

oh nice i didn’t know clojure.data.priority-map existed

Miķelis Vindavs16:12:20

i guess you could also build it using a sorted-map

Miķelis Vindavs16:12:30

@U01HL2S0X71 that’s a very nice support lib!

😁 1
Stuart20:12:18

I'm a ways behind, just catchup up with day 10 now. I have a question about part 2. Question in thread to avoid spoilers.

Stuart20:12:12

I'm not sure what's asking me to do. I dont see the relevance of what I did in part 1. I have all the values for x at each cycle (240 of them). So essentially in pseudo code is it asking

for n = 1 to 240:
   if x-values[n] is within +/- 1 of n (mod 40):
      draw dark pixel
      draw light pixel 
Is that right?

Stuart20:12:26

Argh, I had (<= 1 ,,, ), where I should have had (<= ,,, 1) Solved now