This page is not created by, affiliated with, or supported by Slack Technologies, Inc.
2022-12-12
Channels
- # adventofcode (80)
- # announcements (11)
- # babashka-sci-dev (6)
- # beginners (52)
- # calva (144)
- # clj-kondo (28)
- # cljdoc (2)
- # cljs-dev (7)
- # clojure (120)
- # clojure-dev (28)
- # clojure-europe (36)
- # clojure-nl (1)
- # clojure-norway (16)
- # clojure-uk (3)
- # clojurescript (1)
- # cursive (4)
- # datomic (14)
- # figwheel-main (5)
- # fulcro (23)
- # hoplon (2)
- # hyperfiddle (46)
- # improve-getting-started (10)
- # jobs (1)
- # joyride (1)
- # leiningen (10)
- # malli (5)
- # nbb (5)
- # off-topic (21)
- # polylith (7)
- # portal (15)
- # practicalli (1)
- # rdf (18)
- # re-frame (3)
- # releases (2)
- # remote-jobs (5)
- # shadow-cljs (25)
- # spacemacs (4)
- # tools-deps (16)
- # tree-sitter (1)
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!”
@UTFAPNRPT like your comments (thoughts) in the code
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 @UTFAPNRPT. 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 @UTFAPNRPT https://github.com/zelark/AoC-2022/blob/master/src/zelark/aoc_2022/day_12.clj
@U01HL2S0X71 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
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.
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
Thanks! That’s good advice. But … that’s already been accounted for as I dec
the result.
@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”?
thanks, yeah thats in there to and my path has to allow for that as it goes [ab … nopnopqr …]
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.)
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
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
@UP82LQR9N my coding was 1-26 and I was using 0 for start and 27 for end. I was a real puzzler for me…
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 ….
In fact you can skip all of the last z’s theoretically I just didn’t think the problem implied that at all
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.
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
@U04BA34MCDN apparently your algo has a name: https://en.wikipedia.org/wiki/Lee_algorithm
@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
ohh and i like the idea of propagating waves from source and target at the same time
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))
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)
oh nice i didn’t know clojure.data.priority-map
existed
i guess you could also build it using a sorted-map
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.
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?