It took something like 10 minutes for my Part 2 to run. Yikes!

If a position is occupied by B then that position doesn't count for part1, correct? How about the position of S?

I think just the B’s have to be removed.

I used pmap and got my part 2 runtime down to about 2.5 minutes. Still seems slow. https://github.com/wevre/advent-of-code/blob/master/src/advent_of_code/2022/day_15_beacons.clj

https://gitlab.com/maximoburrito/advent2022/-/blob/main/src/day15/main.clj Not proud in any way of this code. Sad to say I spend OVER 30 minutes debugging part1 only to realize I was checking y=10 from the sample input and not the y for the real input... UGGH... I had to write a couple version of part2 before I got it right. I didn't reuse much code between part1 and part2. "Elapsed time: 31199.856226 msecs"

optimizing this problem is hard, I've reordered points and suddenly it solves in 4 seconds - just because my answer is close to edge and with the new order it needs to brute force through less data

part 2 takes some 30 seconds but hey, it works! my previous record was completing day 14 so I'm happy that's as far as I ever got 🎉 https://github.com/FelipeCortez/advent-of-code/blob/master/2022/15.clj

(defn merge-intervals [intervals]
  (get
   (reduce (fn [[nb-open last retval] [x dir]]
             (if (= -1 dir)
               [(inc nb-open) (if (zero? nb-open) x last) retval]
               [(dec nb-open) last (if (= 1 nb-open) (conj retval [last x]) retval)]))
           [0 nil []]
           (->>
            (concat (map #(list (first %) -1) intervals)
                    (map #(list (second %) 1) intervals))
            (sort-by second)
            (sort-by first))) 2))

(defn part1 [rowy inputs]
  (let [intervals (keep (fn [[x1 y1 x2 y2]]
                          (let [dist (+ (abs (- x2 x1)) (abs (- y2 y1)))
                                dist-at-row (- dist (abs (- rowy y1)))]
                            (when (>= dist-at-row 0)
                              [(- x1 dist-at-row) (+ x1 dist-at-row)])))
                        inputs)]
    (merge-intervals intervals)))

(defn part2 [inputs]
  (doall
   (for [y (range 4000000)]
     (let [intervals (part1 y inputs)]
       (when (> (count intervals) 1)
         (println y intervals)))))
  nil)

(->> (slurp "day15.txt")
     (str/split-lines)
     (map (fn [line]
            (map parse-long (str/split line #" "))))
     (part1 2000000))

(->> (slurp "day15.txt")
     (str/split-lines)
     (map (fn [line]
            (map parse-long (str/split line #" "))))
     (part2))

finding slopes, their intersections, and the only one outside all sensors - 10ms

(spoilers) of course https://www.reddit.com/r/adventofcode/comments/zmfwg1/2022_day_15_part_2_seekin_for_the_beacon/. how did I not think of that

https://github.com/bhauman/advent-of-code-2022/blob/main/src/adv2022/day15/sol.clj

Wrong parsing killed me today... https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2022/day15.clj

I tried out my idea that I was pondering last night, and Part 2 runs in 41 msecs. Yahoo!

Reading above, it looks like my approach must be similar to @U051HUZLD ’s

I'm just flailing on this day, for some reason. My first submission for part 1 was too low. Every change/adjustment I've made to the code since then keeps returning the exact same answer.

It was my case too... I had a bug in parsing, there are negative numbers.

What happens on example data?

Example data runs fine. And I am accounting for negative numbers, yeah.

What is weirding me, is that every change yields the same answer. If there were something wrong with the algorithm I would expect SOME variation...

Today's case is really hard to debug imho. I was reading squares manually to be sure I'm right (or wrong).

You can take a look at my input and compare results.

https://github.com/genmeblog/advent-of-code/blob/master/resources/advent_of_code_2022/day15.txt

yields 4737443

Which value for y?

2000000

@UEF091BP0 not sure what you’re using, but sometimes when I get crazy results like that, it’s because I have some old function compile in my cache. restarting takes care of it.

@UEF091BP0 how are you handling becons in the row?

Sadly, when I run for the actual answer I use a lein run process to make sure it's a clean VM.

And I got the right answer for genme's input. Yay.

I don't count beacons in the row... should I be? The example specifically doesn't count the one beacon in its row.

yeah that’s the way, just checking

Hey, even I'm not sure at this point 😛.

hmmm and your are incrementing the difference between the start and end locations?

Not sure what you mean?

I had exactly the same, other imput was correct, mine not. Maybe verify parsing again?

Hmmm... can't hurt. Let me check.

So the abs difference between -2 and 24 is 26. But its inclusive so its actually 27 entries minus the beacon.

^^^ exactly

Also, I think I’ve mentioned before about how edn/read-string is a great way to parse …. :face_with_hand_over_mouth:

yeah that was obnoxious

Parsing checks out. What I am doing is running along the given y from (min-x, max-x). For each (x,y) pair, I look to see if it isn't a beacon, and if it is in range of at least one sensor. This gave me the correct answer for the other input data, just not for mine.

then I’d suspect the bounds maybe min-x and max-x are wrong

Possible. They are calculated by finding the min-X from the sensors, then subtracting it's beacon distance from it. Do the same with max-X and +.

I can tell you a number that your max shouldn’t be below if you want. It’s something you learn in from the second part.

but that sounds like a great way to get the min and max

@UEF091BP0 hmmm actually your bounds algorithm sounds wrong

anyone got more than one beacon on the same row?

@UEF091BP0 because the (min-x sensor + beacon dist) might not be the the absolute min-x

Oh $^!%. I think it might actually be freakin' typo. Just found something sus when verifying my bounds code.

@UEF091BP0 did you see my messages above?

Yes, I did. It's (min-x sensor minus beacon dist), then (max-x sensor plus beacon dist).

yeah that’s the problem, I had a typo

@UEF091BP0 (min-x sensor minus beacon dist) isn’t nessearily the min-x

@UEF091BP0 because the middle-x sensor may have a huge beacon dist

Argh. And I must have just been lucky on genme's input, then.

Whee. Part 1 done. How hard can part 2 be? Right?

good luck!

Yeah, that was sarcasm 🙂. Even before reading part 2, I knew the gist of it. Not even sure where to start...

Finished writing a lot of notes to explain my approach. I’m quite pleased with it. https://github.com/wevre/advent-of-code/blob/master/src/advent_of_code/2022/day_15_beacons.clj I need to go back and adapt part 1 to use it, I think I have a way to do it.

a pretty naive approach, checking each row for spans covered and merging those. pt2 runs in ~36 seconds edit: a bit of hacking away with some threads to use all my cores and I can get pt2 down to about 6.5s

Had no time yesterday.. playing catch up now. I came upon the same insight that was linked earlier on reddit.. checking one space beyond the perimeter of each range diamond. It's dog slow.. even using pmap . I also used the for some geometry functions. https://github.com/Ramblurr/advent-of-code/blob/main/src/aoc/2022/day15.clj My part 2 solution has a bug somewhere, because it returns multiple points for the sample.. but I lucked out I guess with my input because after 11 minutes running it spat out a single (correct) answer

I'm not really sure why it is so slow.. if anyone is interested, I'd be curious to get some tips on why it's slow.

@U70QFSCG2 you don’t need to check every point outside a diamond (I think that is what you are doing) you can limit your search to intersections. In other words, expand the lines that make up each diamond by one point outward, then search the intersections of all those lines.

Just to be precise I need a couple of sensors with the result for any y

All of my input is in github

ok, I'll try this, thanks

https://github.com/bhauman/advent-of-code-2022/blob/main/src/adv2022/day15/input.txt

and my results are in my code

https://github.com/bhauman/advent-of-code-2022/blob/main/src/adv2022/day15/sol.clj#L78

https://github.com/bhauman/advent-of-code-2022/blob/main/src/adv2022/day15/sol.clj#L117

Thanks! Funny (or not), the result from my code is the same... :/

been there for sure

geez... the bug is in parsing...

I missed the negative - sign... which caused the error with my data.

But not with yours.

Anyway, thanks for assisting me 🙂

It was nothing! Glad you got it sorted. 🙂