2023-12-12 adventofcode | Clojure Slack Archive

adventofcode

danielneal 2023-12-12T15:38:16.010759Z

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.

thomas 2023-12-13T10:03:00.211549Z

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

danielneal 2023-12-13T10:06:42.227239Z

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

thomas 2023-12-13T10:08:19.273579Z

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

Aleks 2023-12-12T06:13:06.048409Z

Day 12 - Solutions 🤯

roklenarcic 2023-12-13T20:38:23.359869Z

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

➕ 1

alpox 2023-12-22T10:16:36.808019Z

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

👍 1

roklenarcic 2023-12-12T08:00:02.499969Z

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

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

borkdude 2023-12-12T10:16:02.872119Z

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

borkdude 2023-12-12T14:31:08.597509Z

@erdos’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

borkdude 2023-12-12T14:31:31.974419Z

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

oyakushev 2023-12-12T16:01:56.855159Z

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))))

borkdude 2023-12-12T18:44:26.692779Z

borkdude 2023-12-12T18:55:16.120419Z

roklenarcic 2023-12-12T19:05:39.966709Z

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

roklenarcic 2023-12-12T19:05:55.145119Z

takes about 1.5 sec

roklenarcic 2023-12-12T19:11:28.764439Z

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.

roklenarcic 2023-12-12T19:13:35.406359Z

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

rjray 2023-12-12T19:17:26.255689Z

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...

borkdude 2023-12-12T19:48:46.718229Z

genmeblog 2023-12-12T19:52:12.554119Z

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

borkdude 2023-12-12T19:55:35.471179Z

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

❤️ 2

oyakushev 2023-12-12T19:56:06.614709Z

Let me edit my comment

oyakushev 2023-12-12T19:59:18.172819Z

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

⚡ 1

borkdude 2023-12-12T20:03:24.321189Z

🔥 1

borkdude 2023-12-12T20:06:51.349319Z

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

oyakushev 2023-12-12T20:08:46.668199Z

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

oyakushev 2023-12-12T20:08:51.691699Z

Couldn't help refactoring a bit

borkdude 2023-12-12T20:09:05.263919Z

no worries, porting was minor

roklenarcic 2023-12-12T20:56:27.226219Z

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

👍 1

roklenarcic 2023-12-12T21:10:03.880359Z

but the code is way uglier

roklenarcic 2023-12-12T21:15:34.563369Z

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

Ivana 2023-12-13T00:59:24.386849Z

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 +))

wevrem 2023-12-13T04:25:34.930709Z

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.

bhauman 2023-12-14T18:35:09.575399Z

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

alpox 2023-12-21T13:57:47.764599Z

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.

genmeblog 2023-12-21T14:01:50.279169Z

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

alpox 2023-12-21T14:06:25.157649Z

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

genmeblog 2023-12-21T14:10:48.880659Z

Ah sorry for spoiling a little bit...

alpox 2023-12-21T14:17:18.059379Z

This is basically a spoil-channel so no worries 😉

erdos 2023-12-12T06:37:49.471619Z

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

👏🏻 1

roklenarcic 2023-12-12T07:59:10.821759Z

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

Clojurians Log v2

adventofcode