Clojurians Log v2

https://gitlab.com/maximoburrito/advent2022/-/blob/main/src/day12/main.clj Finally a nice fun search...

https://github.com/wevre/advent-of-code/blob/master/src/advent_of_code/2022/day_12_elevations.clj Used a Dijkstra datatype I put in place for prior years.

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!”

@michaeljweaver like your comments (thoughts) in the code

https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2022/day12.clj

refactored a bit https://github.com/leinfink/aoc-2022-clj/blob/main/src/aoc22/day12.clj

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

1 for start and 26 for end then

i use 0 and 25 for the 0-25 range

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

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

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

I think?

y25 cannot get to E27

yeah thats right

so you can skip the last z

I just didn’t think that was correct

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

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

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.

pretty straightforward …

ugh

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

OMG

yep there are the extra steps

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

old good bfs without any tricks https://github.com/zelark/AoC-2022/blob/master/src/zelark/aoc_2022/day_12.clj

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 @michaeljweaver. searching in reverse 😌

https://github.com/akovantsev/adventofcode/blob/master/src/adventofcode/y2022/day12.clj

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

Ok, I refactored it and use the same trick for part 2. Thanks @michaeljweaver https://github.com/zelark/AoC-2022/blob/master/src/zelark/aoc_2022/day_12.clj

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

I’m doing part 1 in reverse as well 🙂

Ohh, I missed that 🙃

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

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

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

https://github.com/axelarge/advent-of-code/blob/master/src/advent_of_code/y2022/day12.clj

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

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.

LGTM

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

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

That could be causing an off by 1

(I also used loom 😊)

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

awesome, loom users unite!

@bhauman 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”?

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

https://github.com/volesen/aoc2022/blob/main/day12/day12.clj

ugly as hell dijkstra code, but it gets the job done https://github.com/FelipeCortez/advent-of-code/blob/master/2022/12.clj

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

Came here to say basically the same thing

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

Running, jumping, climbing trees... • https://github.com/abyala/advent-2022-clojure/blob/main/docs/day12.md • https://github.com/abyala/advent-2022-clojure/blob/main/src/advent_2022_clojure/day12.clj

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

y25 cannot get to E27

@leinfink apparently your algo has a name: https://en.wikipedia.org/wiki/Lee_algorithm

@mikelis.vindavs 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

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

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

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

breadth-first search

you could google Dijkstra’s algorithm

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

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)

a handy helper for PersistentQueue

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

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

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)

I have used PriorityQueue

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

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

@c.oakley108 that’s a very nice support lib!

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 

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