Fork me on GitHub
#adventofcode
<
2023-12-06
>
rjray05:12:31

Holy crap. For once, I was the first-to-finish on our leaderboard!

👍 5
norman05:12:30

Day 6 - Solutions

norman05:12:54

https://gitlab.com/maximoburrito/advent2023/-/blob/main/src/day06/main.clj I made one assumption that I don't have any basis for, but I've learned to accept that in aoc your input is the puzzle, not the problem statement. Solve your input, not the general problem, because often times that's the only way.

rjray05:12:22

https://github.com/rjray/advent-2023-clojure/blob/master/src/advent_of_code/day06.clj A silly mistake on part 1 lead to ~5 minutes of debugging. Part 2 took 3 minutes, total. Regexp for the win 🙂.

norman05:12:31

Wait - did you just use the brute force solution? And it was fast enough?

norman06:12:26

Wow - it is! Nicely done @UEF091BP0

Brute Force:   "Elapsed time: 9315.748712 msecs"
Binary Search: "Elapsed time: 2.786305 msecs"

😁 2
Andrew Belo06:12:47

Hi, everybody I am a bit of a novice in Clojure (completed a few days from last year's AOC) Just joined your private leaderboard https://github.com/andrewbelo/aoc2023/blob/master/src/day_6_wait_for_it.clj

jake07:12:18

No regex for me today, I hand wrote my input in - felt good

1
oyakushev09:12:18

Very easy today, just a simple quadratic equation https://gist.github.com/alexander-yakushev/6ad2ec7bfc16fd9d68c3d133636c59bc "Elapsed time: 0.126625 msecs"

🙌 1
1
Casey09:12:48

Maybe i had a lucky input? but the brute force worked well for me https://github.com/Ramblurr/advent-of-code/blob/main/src/aoc/2023/day06.clj#L10-L15

genmeblog09:12:17

Quadratic solver works. I was afraid of floating point accuracy for such big numbers but looks like it's not a case here (my zeros are at: [7711542.749144189, 3.827683025085581E7])

oyakushev09:12:52

@U1EP3BZ3Q IEEE754 has 52 bits for the fraction, input numbers are not that big:)

genmeblog10:12:35

True, but in reality fractional part in floating point number depends on the exponent. Here we have E7 but for 5.0E15 the next possible number is one larger, ie: (m/ulp 5.0E15) ;; => 1.0

genmeblog10:12:27

So, above 1.0e16 you have no fractional part at all.

genmeblog10:12:23

Sometimes AoC tasks go beyond this value.

Sam Ferrell10:12:13

https://github.com/samcf/advent-of-code/blob/main/2023-06-wait.clj Not as brute force as (range 1 n) but not as fast as binary search or math

oyakushev10:12:57

@U1EP3BZ3Q What's m/ulp? I'm not sure what are you saying with your example.

user=> (long 5.0E15)
5000000000000000
user=> (long 5.0E16)
50000000000000000
user=> (long 5.1E17)
510000000000000000

oyakushev10:12:57

I think I got it.

(long (double (inc (long 5.0e16)))) => 50000000000000000

👍 1
genmeblog10:12:51

https://en.wikipedia.org/wiki/Unit_in_the_last_place is Unit in the last place. It's a measure of a precision of the floating point number. Meaning: what is the difference between next possible double and given double.

(== 1.0e16 (+ 1.0e16 0.5))
;; => true
(== 1.0e16 (+ 1.0e16 1.0))
;; => true
(== 1.0e16 (+ 1.0e16 1.5))
;; => false

👍 1
1
oyakushev10:12:11

I think it is consistent with my point.

user=> (count (Long/toBinaryString 50000000000000000))
56

oyakushev10:12:50

So as long as the non-fractional part fits into 52 bits, you should be safe.

genmeblog10:12:37

Yes. But as I mentioned, sometimes you deal with numbers around 1.0e15 and higher in AoC and operations can lead to losing the precision. Race task is not a case fortunately.

oyakushev10:12:35

Fair enough. Can always switch to BigDecimal if needed.

user=> (inc 5.0e16M)
50000000000000001M

👍 1
genmeblog11:12:02

One more example and I shut up 🙂 . There is no representation in doubles for 100000000000000006 which is valid as long.

(long 1.0e17)
;; => 100000000000000000
(long (m/next-double 1.0e17))
;; => 100000000000000016
(long (double 100000000000000006))
;; => 100000000000000000

1
Arno Jacobs11:12:11

I coded brute force solutions for day 6 and I was amazed by the speed. About 2 seconds for both parts. 💪

Jakob Durstberger13:12:20

Today's puzzle was so much more enjoyable, and I am quite happy that my very simple implementation just worked. Definitely dropped my frustration level with AoC 2023 back down. https://youtu.be/8SMrDhRFr6E

👍 1
Arno Jacobs15:12:02

Great. Was able to some more on the challenge. Quadratic indeed. Now it's "Elapsed time: 0.628375 msecs"

Ivana15:12:59

Got it by simple binary-search of monotonic function root, in integers, without any quadratic equations, discriminants, square roots etc. Actually easy task, both parts can be solved with a pen & paper without computer at all.

(let [t 44707080N
        d 283113411341491N
        root (fn [t1 t2]
               (let [tc (quot (+ t1 t2) 2)
                     [d1 dc] (map #(- (* % (- t %)) d) [t1 tc])]
                 (cond (= 1 (- t2 t1)) t2
                       (>= (* d1 dc) 0) (recur tc t2)
                       :else (recur t1 tc))))]
    (- (root (quot t 2) t) (root 0 (quot t 2))))

oyakushev15:12:49

Quadratic equation is 5th grade math, you make it sound complicated:)

Ivana15:12:20

Yep, but BS allows to keep in integers, without any mistakes of floats/doubles due to accuracy etc.

oyakushev15:12:51

By multiplying two longs together you'll get an overflow before a loss of precision from doubles in this task.

oyakushev15:12:47

Or, actually, "might" get an overflow, not 100% sure

Ivana15:12:50

Actually not. Look at N s in numbers literals

oyakushev15:12:48

That's fair, but similarly BigDecimal can be used for floating-points.

Ivana15:12:29

Yep, but when you get f.e. 3.9999999999999 as a root, but you need cell + 1, so is it 3 or 4? Of course, you can check, but integer algorythms avoid of such cases

oyakushev15:12:31

floor(3.99999999) is 3. It takes a very large number so that the square root of it is a at the margin of error of an integer number. But I get your point.

bhauman04:12:41

Here’s day 6 using newtons method:

bhauman04:12:23

only five iterations to solution on my part 2

bhauman04:12:19

But I think the simplest solution is to search in steps of 5000 and when you cross over just search the 5000 entries for the cross over point.

Max14:12:31

5 minutes of simple math saves you 10 minutes of brute forcing 😆 The parsing code ended up being longer than the solution https://github.com/maxrothman/advent-of-code/blob/main/2023/clj2023/src/clj2023/day6.clj

👏 1
thomas08:12:14

still stuck on day 2.... but getting there.

metal 7
bop15:12:41

[SPOILER WARNING] Hey guys! Does anyone can give a direction on why my day 3 /part 1 solution is wrong? https://github.com/brunoti/advent-of-code/blob/main/years/y2023/day3.clj

bop15:12:39

It works with the default data. Even after spotting some possible edge cases that would cause my code to fail, I’m still very stuck!

pez15:12:51

You should post under the Day 3 solutions thread, me thinks. Or at least post your code in a thread. Anyway. I had troubles with part 1 too and that was because I failed to find the numbers when they were last on the line. Haven’t read your code super carefully, but just maybe you have the same issue?

bop15:12:56

It’s not that. Just checked. But, what you said is that should ask for help on the solutions thread?

pez15:12:18

What I mean is that we try to avoid spoilers in the main channel.

💯 1