Clojurians Log v2

compare with last year

Today's a struggle 🤣

is the leaderboard still full of LLMs?

But this is not a particularly hard problem

why would it fall to half? LLMs cannot handle it?

I'm quite stuck on part 2. Part 1 was easy, and my solution works for the test input on part 2. I have no idea why its wrong for part 2 on the real input

My part 2 is reasonable performance wise as well, if the damn thing was correct 😄

I did part 1 in a super complicated way that was basically same as part 2 lol except in one way.

I think I have an issue with creating blocks bigger than the initial block if the numbers overlap e.g.

1..2.....2222
would becomes
1..22222.....

What do you mean? Part2 you’re only moving whole block with a specific ID. There’s never two separate places with same IDs

Part 2 feels awkward with immutable data structures. I’m waiting to solve it before seeing everyone’s solution but I have a feeling I’ll learn a ton once I do haha

but the ids are each just 1 digit, right ?

No

like its 0-9 repeat and reused ?

oh ffs!

My solution is nowhere close then 😄

The digit in the input in the size of the block

So input only has 0-9

but IDs are sequential and go up to 10k

In solutions thread you can see 2 solutions from me. A normal one and a solution with regexes because I am a wicked wicked man.

And your regex solution "only" takes 25 seconds on my input! I was truly expecting something akin to 5 minutes, I went and made myself coffee expecting it to be way longer.

So in the example

00...111...2...333.44.5555.6666.777.888899

00...111...2...333.44.5555.6666.777.888899.00

So, it's not a really convenient way to represent it like this.

No that’s just a representation

He manufactured an example with 9 files so he could render it like this

10 files rather

so you might look at it like this:

[0 0 nil nil nil 1 1 1 ..... 9 9 nil 10 10]

How did you solve part1 without sorting this out, might I ask?

With a parsing that puts things in a vector and use numbers, it would look like this: [0 0 nil nil nil 1 1 1 nil nil nil 2 nil nil nil 3 3 3 nil 4 4 nil 5 5 5 5 nil 6 6 6 6 nil 7 7 7 nil 8 8 8 8 9 9 nil 10 10]

Ah damn. @roklenarcic is too fast for me.

I have no idea, my part 1 just worked 😐 I'm thinking maybe by fluke...

Yeah and for my regex solution I figured: hey, I can go up to 65k on each character with UTF-16, so I can fit each ID in one character.

@qmstuart Can you post your code for part 1 ? This is fascinating.

@roklenarcic I thought about it too, but it's a little crazy

Basically you need about 10k different characters

10, 50, 5k, 10k? what’s the difference? I just generated \u0xxx on the fly

Yep! I'll start at 11:00 CST.

https://www.twitch.tv/timpote

@erdos's day 7 is 🔥 tho

Given memory

[0, 0, nil, 1, 1, 1, 1, nil, nil, 2, 2, 2, 2]

So memory would be [0, 0, nil, 1, 1, 1, 1, 2, 2, 2, 2, nil, nil] In this case.

No, I think the puzzle is specifically asking for 4 empty blocks to put the memory into

I just can’t let this go. Here’s a tree solution that doesn’t use clojure.zip. It uses straightforward recursion with no micro optimizations and it runs in ~620ms on my old machine. https://github.com/bhauman/adv2024/blob/main/src/adv2024/day09/soltreesimple.clj

I tried to solve part 1 by taking an id and length pair and then pasting it over 1..n empty space sections, with 0..1 leftover section from empty section. Really horrible stuff to do in Clojure, looping through things, holding an element, that is updated and mutating another vector. Easily added 25 minutes to my time there, when it wasn’t needed at all.

I solved it but not happy with my code at all. Part 2 takes about 3.5-4 seconds

Heh mine takes 11

Pfiou. My code is horrible. But it runs in 280 ms. I'll clean up a bit and post it. Not proud that it took me four hours x)

🙈🙈🙈 https://github.com/zelark/AoC/blob/master/src/zelark/aoc_2024/day_09.clj

https://github.com/Maravedis/advent_code/blob/master/src/advent_of_code/2024/09.clj I used sorted maps, which are a huge boon performance wise for part 2.

what did you use sorted maps for?

I’ve bruteforced part 2 (gotta get to work) but quite like my custom transducer that solves part 1 in ~0.2ms 🙂 https://codeberg.org/nathell/aoc2024/src/branch/main/src/aoc2024/day9.clj

@roklenarcic keeping the idxes nice and sorted to find the next empty block, and being able to compare the keys (that are indexes in the original memories) to not overshoot.

It works really well.

I’ve rewritten part2 to use regexes and str/replace https://gist.github.com/RokLenarcic/54b0ed20885ce6739bd39e100adc9249

blek, first one this year that required a "slog". I ended up keeping the expanded vector approach for part 2. https://github.com/tildedave/advent-of-code/blob/main/src/advent2024/day9.clj one of those problems where I think it would have been easier with a mutable linked list with a bunch of pointers keeping track of the "next block of size", AoC seems to have a few of these every year...

Did anybody encounter stack overflow exceptions when trying to "expand" the disk layout?

yes, I got this from vec on a giant list, switched to reduce into [] l

(defn unpack-disk [layout]
  (let [[r]
        (reduce (fn [[res type file] digit]
                  (condp = type
                    1 [(concat res (repeat (parse-long (str digit)) file)) 0 (inc file)]
                    0 [(concat res (repeat (parse-long (str digit)) \.)) 1 file])) [[] 1 0] layout)]
    r))

I am using this function to unpack, but apparently I get a stackoverflow when using on the real input

Precisely at iteration 9999 😐

looks like it could be this https://stackoverflow.com/questions/24958907/why-does-reduce-give-a-stackoverflowerror-in-clojure

Ah ok

So I might need to loop and recur instead

Updated my regex solution to be simpler and faster.

Well, I'm still stuck on part 2. Part 1 was poorly implemented, so much so that I had to increase the JVM stack-size to get it to run at all. And the way it represented the data made part 2 essentially impossible. So I'm going to totally re-do how I represent the files and gaps, and see if I can get part 2 done. Then I'll see if I can back-port any of that to part 1 so as to remove the JVM hack.

(By "poorly implemented", I mean my part 1 solution. The puzzle itself is, of course, just fine.)

Part 1 is fairly straightforward. You go forward from the front and backwards from the back, throwing anything you find into the holes in the front. Single pass, O(n/2)

Part 2 got me

I'm still somewhat of a beginner with clojure. That being said, clojure felt really akward for this. Did anyone else have a similar experience?

Yes

A lot of these can be most elegantly solved by sticking some sort of helper mutable datastructure into global scope and then nest a couple of loops and mutate and calculate things as you go. Especially when you have to modify 2 things at once, e.g. update some data and also update some sort of accumulator. Clojure is all about returning sequences and stuff. So you usually have to write reduce calls and have complex arguments so they can hold 2 values that you need to write to. And you have to return these always. Also most C-style languages have much neater syntax when you need to fiddle with indexes.

And all that destructuring and restructuring of pairs or 2-3 key hashmaps ain’t cheap, it’s runs slow.

oh yeah i should try using a transient vector here

(gotta go fast)

Finally got part 2 done: https://github.com/rjray/advent-2024-clojure/blob/master/src/advent_of_code/day09.clj I borrowed the representation of the uncompressed data from @zelark, and cleaned a couple of things based on comparing my code to his. My part 1, however, is atrocious. Takes 65-70s to run and requires boosting the JVM's stack-size to keep from overflowing. I'll rewrite part 1 later, to use the lessons learned in part 2.

My solution is relatively bad, but at least I came with it by myself in limited time. I am unable to work on this during the weekends so I had to catch up on day 7 and 8 - and do day 9 then

It’s kinda embarrassing TBH

I do not know why I am unable to upload code snippets

unreadable. did not enjoy. refuse to refactor. https://github.com/tschady/advent-of-code/blob/main/src/aoc/2024/d09.clj

well, it was annoying more than anything else. chose to wrangle with flattened vec of repeated ids over mapcatting or rrbv/subvec and fighting ints "Elapsed time: 4160.339875 msecs"

I did not enjoy todays puzzle. I managed to get it working, but it was not a great fit for Clojure. I used a vector of (id,file-size,free-size) which was convenient to work with, but kind of slow (3-4 secs) as operations on both ends are needed, though i am sure faster approaches exist. I also ran in to stackoverflows when using normal recursion, so i had to refactor to use loop..recur https://github.com/ChrisBlom/advent-of-code/blob/master/src/adventofcode/2024/day09.clj#L175

Is that really the case, or are we just bad at Clojure?

99.9% of the times I feel like this, it’s because I do not know the core library enough

i'm sure there are better ways to solve it, but my solution required changes to both the start and end of a collection + inserts, which are not fast when using lists or vectors. a immutable deque with fast inserts would help a lot

hmm, profiling shows me slowest bit in my solution is searching for which block to move, that could probably be sped up with something clever

You can also speed up the arbitrary-position updates in a vector with transient.

transient didn't save any time for me, probably just not enough updates

I'm quite happy with my solution. 500ms for part 2 (no transient, assoc on vectors, boxed math). I used two separate vectors, one for files and second for gaps (both keeping position and size) which made things quite easy (4 cases for part 1, 2 cases for part 2). https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2024/day09.clj UPDATE: without boxed math part 2 is around 250ms

Here’s todays: https://github.com/bhauman/adv2024/blob/main/src/adv2024/day09/sol.clj The solution is nothing special really. 25s for part 2. I’d love to revisit it.

the way I’d like to do this is to have a simple tree structure that would represent fungible blocks

[[[1 1 1] [:E :E]] [[2 2 2 2] [:E :E]] [[3 3] [:e]]]

meh, something wrong with my part 2. works for the example input, maybe doesn't move some files in the real input because checksum is too high compared to other solutions 😕

(def areas (str/trim (slurp "2024/09.sample.in")))
(defn char->num [c] (- (int c) (int \0)))

(def files+spaces
  (loop [areas areas
         types (cycle [:file :space])
         file-number 0
         idx 0
         output {:files [], :spaces []}]
    (if areas
      (let [[area] areas, [area-type] types]
        (recur (next areas)
               (next types)
               (if (= :file area-type) (inc file-number) file-number)
               (+ idx (char->num area))
               (if (= :file area-type)
                 (update output :files  conj [file-number idx (char->num area)])
                 (update output :spaces conj [idx (char->num area)]))))
      output)))

(defn checksum [files]
  (reduce + (map (fn [[number idx area]]
                   (* number (/ area 2) (+ (* idx 2)
                                           (dec area))))
                 files)))

(defn leftmost-that-fits [spaces f-area]
  (when f-area
    (some->> spaces
             (filter (fn [[_s-idx s-area]] (<= f-area s-area)))
             (seq)
             (apply min-key first))))

(let [files+spaces' (update files+spaces :spaces (partial into (sorted-map)))]
  (loop [files+spaces files+spaces', new-files []]
    (let [[f-number _f-idx f-area :as file] (peek (:files files+spaces))
          [s-idx s-area :as space] (leftmost-that-fits (:spaces files+spaces) f-area)]
      (if (seq (:files files+spaces))
        (cond
          (not space)
          (recur (update files+spaces :files pop)
                 (conj new-files file))

          (> s-area f-area)
          (recur (-> files+spaces
                     (update :files pop)
                     (update :spaces dissoc s-idx)
                     (assoc-in [:spaces (+ s-idx f-area)] (- s-area f-area)))
                 (conj new-files [f-number s-idx f-area]))

          (= s-area f-area)
          (recur (-> files+spaces
                     (update :files pop)
                     (update :spaces dissoc s-idx))
                 (conj new-files [f-number s-idx s-area])))
        (+ (checksum (:files files+spaces))
           (checksum new-files))))))

wait, maybe I'm moving stuff to the right?

that was it!

#yamlscript Part 1

What I actually used: https://gist.github.com/RokLenarcic/6567a9a5fd7505268b98fee7d3ba9e6d Here’s after washing it, to make it less horrifying: https://gist.github.com/RokLenarcic/4e15a89d053928130c6ee2036b2e00ee

I promised myself I wasn't going to stay up late on these longer ones.... But I kept thinking I had the right optimization "this time". An hour of optimizing later... https://gitlab.com/maximoburrito/advent2024/-/blob/main/src/day09/main.clj Looking back, linked lists would be the way to go I think...

your input parsing is very complex for what it is

#yamlscript Part 2

OK I made a tree structure and used zippers for navigation and modification and got 1.3s for part2. https://github.com/bhauman/adv2024/blob/main/src/adv2024/day09/soltree.clj

Is that pushed?

it’s pushed now

I’ve not used clojure.zip before so don’t take this as idiomatic