Clojurians Log v2

This is very useful to know in general, thanks. But out of interest what's the motivation for encrypting the input for AOC puzzles? Is it sensitive?

> Don’t make your inputs public! > > Plea from creator of AOC: > If you’re posting a code repository somewhere, please don’t include parts of Advent of Code like the puzzle text or your inputs. > — Eric Wastl

Ah, didn't know that, thanks

I developed a library that https://github.com/souenzzo/maoc/blob/main/projects/aoc/src/aoc/io.clj the input So it is pretty easy to use it from REPL, without commit the file: https://github.com/souenzzo/maoc/blob/main/projects/aoc2024/src/aoc2024/main.clj#L98

how does crypt apply to history commits?

Perhaps a folk of AoC like AoC-gen to come up with solutions that generate the appropriate input.

@zengxh it doesn’t… only files going forward. That’s why there’s the second part to burn your history.

I thought I was smarty smart by just rotating the grid counter clockwise for turning right, but I can’t even solve part 1 lol. Value is too high, test input works 🤷

> Story of our lives indeed

Why would you rotate the grid? What’s the benefit of that compared to keeping a variable to denote direction of movement?

It’s certainly much slower and more complex implementation-wise

Ha: I just wanted to do something else I guess

And yes to the implementation being more complex. How I ended up implementing this bright idea. 1. “Move” the guard up to the first obstacle and mark all stepped fields with “X” 2. Now that I have implemented this for up direction I could just rotate the grid and repeat that until I have the guard standing at an edge. 3. sunk cost fallacy combined with false pride

Then I wanted to try a (take-while guard-at-edge (iterate make-move start-grid)) , which also doesn’t make sense at all to call last on that one

(and it was a bug: take-until would be correct. I ended up looping)

I have (iterate make-move start-grid) and when it goes off the end it starts returning nil

so then it’s just (take-while some? …

that gives you whole path

Oh, that makes sense!

fairly easy to do since get-in 2-d vector on a coordinate that doesn’t exist will give you nil

Yes, already liked that in the XMAS trial

As for movement, a lot of people tried writing code that always moves the guard by 1 position. That is a bitch to write, since you can get into a situation where guard has an obstacle ahead and to the right so you need to do 2 rotations to make one step (back the way you came).

Instead I wrote code that either moves the guard 1 square OR rotates the guard’s direction once

far easier to write and all the difference is that you can be at same position multiple consecutive steps while rotating each step

which doesn’t affect solution

Here’s my crap https://gist.github.com/RokLenarcic/87898a07717498f5bc86f3d6f96eca26

Yeah skimming the thread here I thought maybe my solution has the same problem, but I think it’s something else 🤔 Thanks for the solution, will check it out later! Groceries first, my one productive activity on this nice Saturday 😄

Did anyone here get an answer that was too high? Any advice?

It might be an off-by-one error.

good idea, but nope 😕

How do you detect a cycle?

I think there might be an edge case in my input that's not there for other people. tried inputting the answer I got from some reddit solutions and I still get wrong answer. hmm

> You could be placing an obstacle in the path of the patrol from a point you will never reach normally had that obstacle been there from the start oh wow, maybe that's it?

No that’s nonsense

nonsense eh?

Guard goes along a non-circular path. You can only interrupt that path by a single new obstacle. That’s it

that note was from my optimizations not for an original impl 🙂

as long as you are starting your detection from the starting point it the above note doesn’t apply

that insight lowered my answer and it now matches the reddit output, but that's still wrong? 🤔

It’s really not that complicated. Do part1. Now, for part 2, try placing an obstacle in each position from part 1 and run the guard from the start for each placement, check if he starts looping. That’s it. Count the loop runs.

yep, that's what I'm doing.

not complicated but tempermental

This is extremely complicated, you probably have a bug with detecting loops. Just keep a set of visited position+direction pairs.

Having a result too high is likely if you detect loops by just looking for repeated position instead of repeated position + direction

oh my god it was an off by one error

was getting 1704 and 1703 worked

lol

> This is extremely complicated, you probably have a bug with detecting loops. Just keep a set of visited position+direction pairs. That's exactly what I do... > Having a result too high is likely if you detect loops by just looking for repeated position instead of repeated position + direction I had that for a minute but that caused the 10x10 example to produce 8 instead of 6 > oh my god it was an off by one error did you find the cause?

I'm going to print loops and look for oddities

@felipecortezfi so I read all the loop code for nothing?? 🙂

@felipecortezfi I think your error was you were adding the position and the direction to loops

its each unique position that can cause a loop

not position and direction

hmm, but I do save the position that caused the loop, no the direction

(swap! loops conj (mapv + position (direction->delta direction)))

oh yep

sorry

got my hopes up

It’s really not that complicated. Do part1. Now, for part 2, try placing an obstacle in each position from part 1 and run the guard from the start for each placement, check if he starts looping. That’s it. Count the loop runs.That's what I do. BTW my (too high) result is 2078. Did anyone who got it right get higher than that?

No I get 1482

@ingy you mean lower, right? you don’t want something that’s even farther away from the result :)

ah, or you mean globally?

It’s not position that you need to check for the loop, it’s position and direction @bhauman

I did not find the cause. only thing I can think of is the initial position restriction, but I check for that

Consider this:

....#....
.....#...
.........
.........
....^....

up then down

> you mean lower, right? you don’t want something that’s even farther away from the result I meant is 2078 near the median? I made a change that lowered it to 2032. Might be off by one, but now I have to wait 5 minutes because it was my 4th time. > The new obstruction can't be placed at the guard's starting position Failure to honor that could cause off by one

yep, that was it. wtf

(not= position initial-position) ;; nope (not= front initial-position) ;; yep!

@felipecortezfi So I’m running your code and it isn’t working for the test case, as it’s returning 5 instead of 6

@bhauman it now works for the test case if you make the change I just said

OK good!

it is weird though. I thought you couldn't put the obstruction at her line of sight / immediately-in-front position, but you can't place the obstruction where she is

I think I know what I'm doing wrong. I'm following my part1 path and testing by putting an obstacle in the next position. but I don't keep track of where I've already tried. So counting way too much.

derp

so I’m not seeing your code but I would put an obstacle in each unique position of the originial path and start from the beginning

not in front

yep

You are adding obstacles as you go along?

and when I say start from the beginning I mean start path tracing at the beginning

um. yeah. I as I go along (the original path), (say I'm in position "pos") I put an obstacle in position "next" and then starting walking from position "pos" (immediately turning of course). Then I detect if I loop.

that’s the hardest way to do it and it causes answers that are way too high

you can get the correct answer by starting the guard sweep at start position with an empty visited set

the problems come from 1. placing a obstacle that on a path for a second time

bc now you are in a state that is not actually reachable, had the obstacle been on the path originally

Right but if you take visited positions from part1 those would have to be deduplicated already

also you need to construct the correct visited set for loop detection

Got it. 1812. Did exact same thing but didn't try same spot more than once.

12secs 😕 but... it's day 7!

#yamlscript Part 2

I noped out when reading part2 last night and went to sleep, now catching up. This was really hacky, I kept increasing the threshold to get the right answer on the real dataset 😄, as I'm just looking at consecutive already visited points as the test. (in the end that doesn't really slow it down anyway, it's around 8.7 seconds regardless how safe I play it there)

Supremely stuck on part 2, not sure why. Getting around 2,000 obstacles. Any hints? Edit: Solved!

Nothing special today, as usual you might use pmap to boost your solution, my part 2 runs ~6 secs https://github.com/zelark/AoC/blob/master/src/zelark/aoc_2024/day_06.clj UPD: optimized my solution for part 2, now it takes less than a sec

@mail191 I think you're detecting loops as you're moving? Thing is, you could potentially let the loop "behind you", as in you are past the point when you would enter the loop. You need to place the obstacle THEN move the guard. I think. Your approach is hard to read for me.

Don't have time for p2 yet, but enjoy my brutalist p1

@malaingreclement Thanks for the help! I retooled my solution to filter all the visited nodes by nodes that would result in loops (like your part 2) and that did the trick... answer was about 50 off 😕 but everything takes about 4s

Bruteforcing my way through Day 6 https://github.com/skazhy/advent/blob/master/src/advent/2024/day6.clj

35ms fot part 1 but 39 secs for part 2 😅 https://github.com/jramosg/advent-of-code/blob/master/src/advent_of_code/year_2024/day06.clj

(ns advent-of-code.year-2024.day06
  (:require
   [advent-of-code.util :as util]
   [clojure.set :as set]))

(def obstruction \#)

(def ->new-direction {[-1 0] [0 1]
                      [0 1] [1 0]
                      [1 0] [0 -1]
                      [0 -1] [-1 0]})

(defn- get-pos0 [input-coords]
  ((set/map-invert input-coords) \^))

(defn- input-by-coords []
  (reduce-kv
   (fn [acc row-index row]
     (reduce
      (fn [acc-map [col-index cell]]
        (assoc acc-map [row-index col-index] cell))
      acc
      (map-indexed vector row)))
   {} (util/read-input "2024" "06")))

(defn move-guard [pos0 input-coords]
  (loop [direction [-1 0]
         current-pos pos0
         visited {pos0 #{direction}}]
    (let [new-coords (mapv + current-pos direction)
          in-coord (input-coords new-coords)]
      (cond
        ;;
        (= in-coord obstruction)
        (recur (->new-direction direction)
               current-pos 
               visited)
        ;;
        (not in-coord) (keys visited)
        ;;
        (get-in visited [new-coords direction])
        ::looping
        ;;
        :else
        (recur direction
               new-coords
               (update visited new-coords (fnil conj #{}) direction))))))

(defn part1 []
  (let [input-coords (input-by-coords)
        pos0 (get-pos0 input-coords)]
    (count (move-guard pos0 input-coords))))

(defn part2 []
  (let [input-coords (input-by-coords)
        pos0 (get-pos0 input-coords)]
    (->> (move-guard pos0 input-coords)
         (filter
          (fn [coord]
            (and (not= coord pos0)
                 (= ::looping (move-guard pos0 (assoc input-coords coord obstruction))))))
         count)))

(comment
  (part1)
  ;; => 5162
  (time (part2))
  ;; => 1909
  )

just realized that my "optimization" in s2 doesn't happen at all lol, no wonder it took two minutes. E: and good thing it didn't, it was a bad idea anyway

I added a few optimizations to my solution: ;; 16071.819368 msecs (my original solution without pmap) ;; 4646.135041 msecs (cut guard's path) ;; 1954.627387 msecs (take big steps) ;; 927.825388 msecs (with pmap) Need some time to clean it up and push

It's becoming an Advent of Brute Force for me this year 😄 https://codeberg.org/nathell/aoc2024/src/branch/main/src/aoc2024/day6.clj (I might revisit this later in the day... or not)

Pushed the update

(ns day6
  (:require [clojure.string :as str]))

(defn indexed [items]
  (map-indexed vector items))

(def input
  (into {}
        (for [[y line] (indexed (str/split-lines (slurp "src/input/6.txt")))
              [x c]    (indexed line)]
          [[x y] c])))

(def next-dir
  {\^ [0 -1]
   \> [1 0]
   \< [-1 0]
   \v [0 1]})

(def rotate 
    {\^ \>
    \> \v
    \< \^
    \v \<})

; start dir [4 6]

(def sol1
  (loop [grid input
         [x y] [42 83]
         cnt 0]
    (let [guardian (grid [x y])
          [dx dy] (next-dir guardian)
          next-point [(+ x dx) (+ y dy)]
          next-slot (grid next-point -1)]
      (condp = next-slot
        -1  (inc cnt)
        \. (recur (assoc grid next-point guardian [x y] \X) next-point (inc cnt))
        \X (recur (assoc grid next-point guardian [x y] \X)  next-point cnt)
        \# (recur (assoc grid [x y] (rotate guardian)) [x y] cnt)))))

I am not too sure what is the best way to look for a place to put a new obstacle. Any tip, without me looking at other people's source code?

It seems like I could collect all the obstacles positions somehow and from there see if I can come up with a "square" of obstacles somehow

Even if you could, you'd have to then find out if the guard reaches your square, which is really hard imho.

So just brute force it and try with a wall on whatever place the guard walks in?

That seems to be the most common approach, yeah. Although I'm not saying yours cannot work, I'm just saying it doesn't sound easy.

Advent of Bruteforce is in full swing this year.

@vincenz.chianese One of the optimizations I did is i cut the guard's path placing the guard in front of the obstacle, it helped a lot.

All right, thanks everybody. Brute force it is I guess

4s unoptimized. lots of duplicate steps on sep guard runs.

random insights that only occurred to me now: • new obstacles only matter when added on the original path of the guard (truly groundbreaking I know...) • we could compute a "minefield" of all possible loop states by placing the guard in each state right after a collision (there are four per obstacle) and tracing its path for the next four "bumps"; of course this needn't happen in an eager fashion. • Assuming that relatively few loop paths are invalidated when only a single obstacle is added, perhaps there are gains that could be made there.

> next four "bumps" are you assuming loop is always rectangle? it is not

Hmmmm part 2 is stumping me I’m doing straight forward loop detection and I tried 2 different implementations and get the same result. https://github.com/bhauman/adv2024/blob/main/src/adv2024/day06/sol.clj They keep saying my part 2 answer is too low. Anyone available for a sanity check here?

#yamlscript Part 1:

My final solution for both

@bhauman I"m checking it out. Gives a too low answer for my input as well. Although I don't know why yet.

Thanks, that’s super helpful, at least I know the code is wrong for sure

Something in your mover function, the fact that when you're in front of a crate, you don't keep [pos new-dir], but only [new-pos new-dir] kinds of tickles me the wrong way, but it shouldn't change anything.

so part 1 works

it would be hard for part 1 to work if the mover function didn’t work

I know.

part 1 works for you as well right?

Yup.

Lmao.

I was right

what!!

(let [new-dir (turn-right dir)]
          [new-p new-dir])

; Replace by 
[p (turn-right dir)]

; in mover function

And it runs faster too.

I should listen when something tickles me the wrong way.

I was so confused

Tbh, I'm not sure why... It just was the only difference I could spot between your code and everyone else's.

If you find out why I'd be delighted to know.

Because you should just be detecting loops one step later. I'm really confused too tbh x)

I know why because I could easily step onto a wall and skip its detection

ugh

I have to just turn and not turn and move

I think I’ve made this same mistake before on AOC

don’t AOC when you’re under the weather

Oh yeah.. ANything like this

...#.
....#

I suppose the parts where it happened werent reached before you add the crate.

yeah it makes sense that that would have to occur when you are adding crates and very easy for it not to be there in the original

@malaingreclement thanks that saved me some cycles. My assumption that the move function worked really got me.

My pleasure 🙂

well I did just think of an algorithmic optimization. Because we are only using on-path position-directions, you can move your start position to just before the obstacle, and you can initialize your seen with the path up to that point. Also pmap cut my execution time by 75%

pmap and brute force on originally visited gives around 6 seconds https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2024/day06.clj

Got down to 2 seconds with very ugly code.

Optimized with @bhauman idea of placing the guard just before the obstacle and having the previous path in seen . Don't judge me on readability

I'd appreciate some spoiler free pointers for part 2 My logic was writing the same traversal, but at each point along my path, check if getting blocked will make me close a loop. I recognize a closed loop by visiting the same location in the same direction.

Also I prefer clojure.core.reducer/fold to pmap , although I can't explain why. I remember reading somewhere it was better-suited to parallelization. Does anyone know if that claim holds any water?

@ben.sless I’ll take a look

@ben.sless it looks good

@ben.sless did you reset your repl bc I got symbol reference error for out-of-bounds?

actually all kinds of symbol references are missing mainly having to do with '

actually check that out and then repost the code and I’ll run it against my data

@bhauman out-of-bounds'? and out-of-bounds? ended up having the same impl

same for blocked?

you omitted visit and find-start.

(defn visit
  [visited x y]
  (let [v (get visited x #{})]
    (assoc visited x (conj v y))))
(defn find-start
  [lines]
  (->> lines
       (map-indexed (fn [i ^String s]
                      (let [j (.indexOf s "^")]
                        (when (nat-int? j)
                          [i j]))))
       (some identity)))

Here's a thought... Detecting loops by placing obstacles while also figuring out where the patrol goes doesn't work

Why?

At each point along the patrol's path, I can ask the question - will placing a block in front of it induce a loop

You could be placing an obstacle in the path of the patrol from a point you will never reach normally had that obstacle been there from the start

With added visualization, my solution looks like it works

I see, so I would in theory need to check I'm not placing the obstacle on a place the patrol had gone through

is that sufficient?

Maybe... 🤣 All I know is that I tried solving it the same way the first time and it was broken

gotcha 😉

Okay, adding the check

can-place? (not (-> visited (get xb) (get yb)))
looping? (and can-place? (will-close-loop? x y dx dy visited lines render))

What worked for me was collecting the normal patrol first and then filtering the visited set by those that cause a loop were they turned into obstacles, restarting the patrol from the start each time

#... ...# ^... ..#. Does this case take 0 for part 2?

@zengxh is this a general question or addressed to me?

general question

Checked with my code and it would seem that yes.

Thx

My solution: https://github.com/ChrisBlom/advent-of-code/blob/master/src/adventofcode/2024/day06.clj#L85-L108 Initially with a naive approach (count all positions on the walked path were placing # results in a loop) this ran in 17 seconds. Then i figured i could reuse the state from the initial walk to speed it up to 3.5s Forking state is where immutability and structural sharing shines!

Man, my friend did it in Rust and it’s about a 100 times faster. The most disappointing thing is parallelization, it only makes it 2-3 times as fast in Clojure, but in Rust it makes it 10 times as fast. When doing these AoC problems I can never seem to squeeze more than 2-3x speedup by doing things in parallel.

Rust is really fast to begin with. I remember seeing 100x speedups when using opt-level = 3`` when i used it for AoC. I found rust a great language for AoC type problems, but i recall parsing the inputs with it was a bit tedious

I tried to do part 2 two ways, a brute force and a smarter approach. Both work for the test input, both fail for the real input 😞

Story of our lives

Still trying 😕

Given this test map, would you expect it to find a potential obstacle at [1 5]

0123456789
0 ....#.....
1 ..........
2 ..........
3 .#........
4 ........#.
5 ..........
6 ....^.....
7 #.........
8 ....#..#..
9 ..........

0123456789
0 ....#.....
1 ....│#....
2 ....│.....
3 .#..│.....
4 .┌──┼──┐#.
5 .│..│..│..
6 .│..^..│..
7 #└──┘──┘..
8 ....#..#..
9 ..........

Finally, yep that was my issue above. I wasn't handling that case. I was rotating right and advancing in one step, so when I was placing potential obstacles in the example above I wouldn't consider [1 5], as when I was on [1 4] I was moving north, never east...

[1 5] is valid

@qmstuart I had the same problem

adding the algorithmic optimization of starting from just before the introduced obstacle and using the path up to that point as the seen, I got part 2 down to 2.7 seconds on my 10yr old MBP, it’s tricky though, you shouldn’t try evaluate the same position again later in the path as an obstacle https://github.com/bhauman/adv2024/blob/main/src/adv2024/day06/sol.clj

https://gitlab.com/maximoburrito/advent2024/-/blob/main/src/day06/main.clj I misunderstood part1 and wrote the cycle detection first assuming that was required. However, I misunderstood that the guard could leave the map and just had the guard turn right at the edge. I spent about 10-15 minutes debugging that. So part2 was pretty trivial after that, though on the first pass I checked every single point for a cycle. After seeing that was slow, I only checked points that were visited by the guard in part1

For me, cycle detection was just checking if path is long enough. After a given length, it either goes outside of the area or is in a loop. Part 2 is quite slow though :F (30s) https://github.com/erdos/advent-of-code/blob/master/2024/day06.clj

I used an infinite list for directions. Just look at the first one to get the current direction and drop it when you want the next 😄

Damn my part2 is so slow x) 24s. Imma try to clean this up.

All done, and I got my running time for part 2 down from a minute to 13 seconds, which is good enough for me! • Blog: https://github.com/abyala/advent-2024-clojure/blob/main/docs/day06.md • Source: https://github.com/abyala/advent-2024-clojure/blob/main/src/advent_2024_clojure/day06.clj

Got it down to 8 seconds with reducers. Not my cleanest code ever.

Around 6 seconds for part 2: https://github.com/hansbugge/aoc/blob/main/src/hansbugge/year2024/day6.clj Edit: Around 3.6s with some parallelisation.

https://github.com/ghaskins/adventofcode/blob/main/src/aoc/2024/day6.clj

(time (part1))
"Elapsed time: 4.444375 msecs"
=> 4982
(time (part2))
"Elapsed time: 446.586625 msecs"
=> 1663