Fork me on GitHub

Day 17 - Solutions

norman07:12:40 Part 1 was very fun, though it took much longer than I thought. Part 2 was really tough, but we've had cycle detection problems before so it seemed relatively clear what generally needed to be done. Part2 here is kind of ugly. I dumped my height differences into emacs and played with the buffer a bit to confirm there were cycles and what size they were to write a more targeted solution. It's not my finest clojure, but it works...

Miķelis Vindavs16:12:20

@U076FM90B what a beautiful solution — very readable & expressive! I like the use of reductions and cycle , and the reusing of dh in part 2

Miķelis Vindavs16:12:31

I wasn’t able to get my clj solution for today to run faster than 3 or so seconds. Whereas my simpler python solution runs in 70ms 😕

Miķelis Vindavs16:12:53

then again in py i used a bitmask to represent each line of the stack


yes, my solution is slow. Also I track which point belongs to which original shape for colorful rendering

bellissimo 1
Miķelis Vindavs16:12:52

my comment about the slowness wasn’t directed at you, it was about my own clojure solution 😅 sorry if it sounded that way yes, i noticed that you assoc the keyword for each shape into the map. What are you using to generate that image?


I didn't took it personally, I meant my code is ALSO slow 🙂 I use clojure2d, the file with sketch is not that readable

Miķelis Vindavs16:12:53

nice, i didn’t know about clojure2d


it's great - runs on latest jvm (while quil doesn't) and has documentation site with examples

gratitude-thank-you 2
Miķelis Vindavs17:12:13

i also find it surprising that you can find the cycle just by looking at the height differences, that’s so much simpler than what i did — make a “fingerprint” of the last 10 rows, basically the relative max height of each x coordinate

Miķelis Vindavs17:12:48

i don’t think either solution would work correctly for all possible inputs though e.g. mine definitely wouldn’t work if there were “caves” under an overhang

Miķelis Vindavs17:12:05

or a super tall empty gap on one side which then later gets filled by dropping an I shape down more than 10 rows


yes, last 10 rows are not stable because peaces can fall between cracks. Also heights can repeat while the shape does not.


@U89SBUQ4T “to run faster than 3 or so seconds” Is it for part 1 or part 2?

Miķelis Vindavs17:12:19

I store the occupied slots as a set of x,y tuples This means that collision tests, but especially fingerprinting (which has to do at least 1 linear search over the entire set to find the max Y coordinate), get slower as the stack gets filled up. What’s interesting is that i tried pruning down the set of coordinates every once in a while, but that only made the whole thing even slower


Interesting, pruning down the set was my first thought when I saw part 2 question.

Miķelis Vindavs17:12:50

the cycle occurs pretty fast so it doesn’t get that huge- it always stays below 10k elements

Miķelis Vindavs17:12:20

i just realized i can pass in the “max y” from outside, now it all takes 100ms

🔥 1
Miķelis Vindavs17:12:09

that’s kind of funny


I ended with this, works relatively fast

(defn reify-rock [state]
  (let [{:keys [rock chamber position height]} state
        [cx cy] position
        [chamber' height'] (reduce (fn [[m h] [x y]]
                                     (let [x' (+ x cx)
                                           y' (+ y cy)]
                                       [(assoc m [x' y'] \#) (max h y')]))
                                   [chamber height]
    (assoc state
           :chamber chamber'
           :height height')))

Miķelis Vindavs17:12:42

what’s position, is it the bottom left corner of the rock?

Miķelis Vindavs17:12:07

and how do you detect cycles for p2?


For part 2 I did it manually with a notepad 🙃

😅 1
📝 1
Miķelis Vindavs17:12:33

btw, another finding that was surprising to me

;;(def intersects? (comp seq set/intersection))

(defn intersects? [a b]
  (if (< (count a) (count b))
    (some b a)
    (some a b)))
Doing this (avoiding construction of the overlapping set, instead breaking early if anything overlaps) didn’t change the run time much

Miķelis Vindavs17:12:58

in general, i keep getting surprised by how ok it is to generate lots of garbage