adventofcode 2023-12-12 | Slack Archive

Day 12 - Solutions 🤯

https://github.com/erdos/advent-of-code/blob/master/2023/day12.clj memoize can help speed up the recursive calls. This seems to be a dynamic programming problem, where we can quickly match the prefix of a pattern, and then recursively process all the possible suffixes of the remaining pattern as well.

👏 2

roklenarcic07:12:10

yeah this one was easy just wrap the whole thing in memoize

roklenarcic08:12:02

Sidenote, no idea why it takes 26ms to fetch a memoized solution…

(time (p2 input))
"Elapsed time: 26.741197 msecs"

borkdude10:12:02

when objects are not identical, you have to determine value equality. for big objects this can entail walking the entire object graph. not sure if that is into play here but could be

borkdude14:12:08

@U2E1D7WUB’s solution in https://squint-cljs.github.io/cherry/?boilerplate=https%3A%2F%2Fgist.githubusercontent.com%2Fborkdude%2Fcf94b492d948f7f418aa81ba54f428ff%2Fraw%2Fa6e9992b079e20e21d753e8c75a7353c5908b225%2Faoc_ui.cljs&repl=true&src=OzsgSGVscGVyIGZ1bmN0aW9uczoKOzsgKGZldGNoLWlucHV0IHllYXIgZGF5KSAtIGdldCBBT0MgaW5wdXQKOzsgKGFwcGVuZCBzdHIpIC0gYXBwZW5kIHN0ciB0byBET00KOzsgKHNweSB4KSAtIGxvZyB4IHRvIGNvbnNvbGUgYW5kIHJldHVybiB4Cgo7OyBSZW1lbWJlciB0byB1cGRhdGUgdGhlIHllYXIgYW5kIGRheSBpbiB0aGUgZmV0Y2gtaW5wdXQgY2FsbC4KKGRlZiBsaW5lcyAoLT4%2BIChqcy1hd2FpdCAoZmV0Y2gtaW5wdXQgMjAyMyAxMikpCiAgICAgICAgICAgICBzdHIvc3BsaXQtbGluZXMpKQoKKGRlZm4gcGFyc2UtbGluZSBbbGluZV0KICAobGV0IFtbcm93IG5yc10gKC5zcGxpdCBsaW5lICIgIildCiAgICBbKHN0ciAoLnJlcGxhY2VBbGwgcm93ICJcXC5cXC4rIiAiLiIpKQogICAgIChtYXAgcGFyc2UtbG9uZyAoLnNwbGl0IG5ycyAiLCIpKV0pKQoKKGRlZm4gdmFsaWQtc3VmZml4ZXMgW3JvdyBudW1iZXJdCiAgKGZvciBbaSAocmFuZ2UgKGluYyAoLSAoY291bnQgcm93KSBudW1iZXIpKSkKICAgICAgICA6d2hpbGUgKGV2ZXJ5PyAje1wuIFw%2FfSAodGFrZSBpIHJvdykpCiAgICAgICAgOndoZW4gKGV2ZXJ5PyAje1wjIFw%2FfSAodGFrZSBudW1iZXIgKGRyb3AgaSByb3cpKSkKICAgICAgICA6d2hlbiAoI3tcLiBcP30gKG50aCByb3cgKCsgaSBudW1iZXIpIFwuKSldCiAgICAoZHJvcCAoKyBpIG51bWJlciAxKSByb3cpKSkKCihkZWZuIGFjcyBbcm93IG51bWJlcnNdCiAgKGlmLWxldCBbW24gJiBucnNdIChzZXEgbnVtYmVycyldCiAgICAocmVkdWNlICsgKGZvciBbcyAodmFsaWQtc3VmZml4ZXMgcm93IG4pXSAoYWNzIHMgbnJzKSkpCiAgICAoaWYgKGV2ZXJ5PyAje1wuIFw%2FfSByb3cpIDEgMCkpKQoKKGRlZiBhY3MgKG1lbW9pemUgYWNzKSkKCjs7IHBhcnQgMQooY29tbWVudAogICgtPj4gbGluZXMKICAgIChtYXAgcGFyc2UtbGluZSkKICAgIChtYXAgKHBhcnRpYWwgYXBwbHkgYWNzKSkKICAgIChyZWR1Y2UgKykKICAgICh0aW1lKSkpCgooZGVmbiAqNSBbW2xpbmUgcnVsZV1dCiAgWyhzdHIvam9pbiAiPyIgKHJlcGVhdCA1IGxpbmUpKQogICAoYXBwbHkgY29uY2F0IChyZXBlYXQgNSBydWxlKSldKQoKOzsgcGFydCAyCihjb21tZW50CiAgKGFzLT4gbGluZXMgJAogICAgKG1hcCBwYXJzZS1saW5lICQpCiAgICAobWFwICo1ICQpCiAgICAobWFwIChwYXJ0aWFsIGFwcGx5IGFjcykgJCkKICAgIChyZWR1Y2UgKyAkKQogICAgKGpzLWF3YWl0ICQpCiAgICAodGltZSAkKSkp

borkdude14:12:31

I tried to use https://github.com/bruceon/jsworkers for pmap but couldn't get it to work in just the browser with dynamic import etc

oyakushev16:12:56

Caching solution, 230ms.

(ns day12
  (:require [clojure.string :as str]
            [clojure.java.io :as io]))

(def lines (line-seq (io/reader "2023/day12.txt")))

(def parsed
  (for [line lines]
    (let [[field hints] (str/split line #" ")]
      [(str "." (str/join "?" (repeat 5 field)) ".")
       (vec (apply concat (repeat 5 (map parse-long (str/split hints #",")))))]
      #_[(str "." field ".") (map parse-long (str/split hints #","))])))

(defn variants [[^String field, hints]]
  (let [cache (volatile! {})]
    (letfn [(f [i j start c]
              (let [key (+ (* 10000 i) j)]
                (or (and (nil? c) (nil? start) (@cache key))
                    (let [c (or c (when (< i (.length field))
                                    (.charAt field i)))]
                      (case c
                        nil (if (= j (count hints)) 1 0)
                        \. (if start
                             (let [len (- i start)]
                               (if (= len (nth hints j nil))
                                 (recur (inc i) (inc j) nil nil)
                                 0))
                             (recur (inc i) j nil nil))
                        \# (recur (inc i) j (or start i) nil)
                        \? (let [res (+ (f i j start \.)
                                        (f i j start \#))]
                             (when (nil? start)
                               (vswap! cache assoc key res))
                             res))))))]
      (f 0 0 nil nil))))

(defn task2 []
  (time (reduce + (map variants parsed))))

borkdude18:12:26

borkdude18:12:16

roklenarcic19:12:39

mine: https://gist.github.com/RokLenarcic/ce35afd4d5c72c825f5961442d937c70

roklenarcic19:12:55

takes about 1.5 sec

roklenarcic19:12:28

It tries to match the whole group in one step. So if you have 3 as group count it will try to remove prefix of 3 ? or # and an additional . or ?, immediately returning 0 if not able.

roklenarcic19:12:35

Probably could make it faster by accessing string characters by index, instead of using string as a seq, but the code would be way uglier

rjray19:12:26

https://github.com/rjray/advent-2023-clojure/blob/master/src/advent_of_code/day12.clj Solved part 1 with brute force, then did a little analysis on how big part 2 was. Chose to sleep. Today, due to time-constraints, I just adapted a DP solution from some Python. I knew it needed to be a DP solution with memoize, but it was this or spend hours reviewing my DP notes...

borkdude19:12:46

genmeblog19:12:12

I hate it... Three complete rewrites for part 2... https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2023/day12.clj

borkdude19:12:35

@U06PNK4HG do you have your part 1 also somewhere? I'd like to include it in the squint hall of fame solutions ;)

❤️ 2

oyakushev19:12:06

Let me edit my comment

oyakushev19:12:18

Actually, here https://gist.github.com/alexander-yakushev/7f40fbafa4fa29b93706ca823be4250a

⚡ 1

borkdude20:12:24

🔥 1

borkdude20:12:51

added it here now https://github.com/squint-cljs/squint/blob/main/examples/aoc/solutions.md

oyakushev20:12:46

Sorry, didn't mean to add extra stuff:))

oyakushev20:12:51

Couldn't help refactoring a bit

borkdude20:12:05

no worries, porting was minor

roklenarcic20:12:27

yeah I made it way faster by making the function use indexes instead of sequences (which affects memoize speed).

👍 1

roklenarcic21:12:03

but the code is way uglier

roklenarcic21:12:34

Comparison: https://gist.github.com/RokLenarcic/d39edc908f8d59146d2436fe2ede834c

Ivana00:12:24

Manual memoization with local atom, 450 msec

(defn process-row [s]
  (let [[s v] (str/split s #"\s+" 2)
        s (->> s (repeat 5) (str/join "?"))
        v (->> v (repeat 5) (str/join ","))
        v (read-string (str "[" v "]"))
        dp (atom {})
        go (fn go [si vi]
             (cond (>= vi (count v)) (if (str/index-of s \# si) 0 1)
                   (>= si (count s)) 0
                   :else (let [dp-k (+ vi (* 10000 si))]
                           (or (get @dp dp-k)
                               (let [n (get v vi)
                                     dot-i (or (str/index-of s \. si) (count s))
                                     r (+ (if (or (<= si dot-i (+ si n -1))
                                                  (= \# (get s (+ si n))))
                                            0
                                            (go (+ si n 1) (inc vi)))
                                          (if (= \# (get s si))
                                            0
                                            (go (inc si) vi)))]
                                 (swap! dp assoc dp-k r)
                                 r)))))]
    (go 0 0)))

(->> input
     str/split-lines
     (map process-row)
     (apply +))

wevrem04:12:34

My https://github.com/wevre/advent-of-code/blob/master/src/advent_of_code/2023/day_12.clj. I’m on a business trip on the east coast and, sadly, not much time to work on these.

roklenarcic20:12:23

if you care about performance, why use atom and persistent map to cache things? Why not use java.util.Hashmap?

➕ 1

bhauman18:12:09

Day 12 beat me up a bit for not thinking more about the problem first. https://github.com/bhauman/adv2023/blob/main/src/adv2023/day12/sol.clj

alpox13:12:47

Are there any weird edge cases? I am pretty sure that my solution works and it looks right in all cases I picked. But for some reason it tells me the result is too low - so I wonder if I missed something specific in the input.

genmeblog14:12:50

For part 2 i missed ? as a separator of the copies.

alpox14:12:25

Ah well i’m still at part 1 😄 thanks for the heads up though

genmeblog14:12:48

Ah sorry for spoiling a little bit...

alpox14:12:18

This is basically a spoil-channel so no worries 😉

alpox10:12:36

Update: I found the issue. A typical off-by-one error

👍 1

danielneal15:12:16

Day 1 - 10 using a lot of instaparse … https://github.com/danielneal/advent-of-code-2023/tree/main/src Not even going to look at Day 11, better quit now, as day 10 took me most of Sunday ha.

thomas10:12:00

I considered using instaparse for day 2.... but ended up with several lines of replace etc. instead.

danielneal10:12:42

I enjoyed how it reveals the structure of the input each time - I personally think you can look at it a grammar and get a feel for what the input looks like more easily than reading combinations of regexes

thomas10:12:19

yes, very true... and a couple of regex are much more error prone IMHO... just one added space or so and it can go wrong. Regexes seem to be much more tied to the exact format. but maybe that is more perception TBH.

😊 1

2023-12-12

Channels