Clojurians Log v2

what was the prompt?

It is pretty long and consists of many details 🤩

https://www.twitch.tv/timpote

Im so far behind, just getting to day5 now. I had solved part1's test data using a topological sort of the rules as a DAG, and got the right answer…but when I plumb in the real inputs, it appears that the rules arent actually a DAG (at least according to ubergraph). Am I missing something?

I cant see that the problem is solvable if its not, but clearly lots of people got through it so I feel like I am misunderstanding something

It is not a dag. If you look at your file more closely, it's a loop.

You're being too smart for your own good ^^'

Ah, ok…let me re-study the problem then. Ty!

@malaingreclement finally got it, thanks for the tip https://github.com/ghaskins/adventofcode/blob/main/src/aoc/2024/day5.clj

Turned out, I was generally on the right track, but the problem as you pointed out is that the overall rules are not guaranteed to be a DAG…however, if you only consider the rules relevant to a given update, they must be.

so a slight adjustment, and now it works

One thing I dont like is I compute the DAG twice for each entry in part2…not super efficient, but its also fast enough for the problem that it doesnt matter

My solution with comparator: https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2024/day05.clj

topological ordering on day 5 feels hard too me https://github.com/nbardiuk/adventofcode/blob/master/2024/src/day05.clj

Part 2 with topological sort by way of DFS

@nbardiuk I don't think we're expected to remember the algorithm, I just went to wikipedia and applied it directly

yes, me too, I'm just thinking about beginners who don't even know the algorithm exists. I've originally solved part 1 without topo ordering, but for part 2 I would need some help.

Others just passed a custom comparator to sort which is a nicer solution tbh

I bruteforced part 2 because not enough coffee: https://codeberg.org/nathell/aoc2024/src/branch/main/src/aoc2024/day5.clj

when in doubt - loop it out

via sort:

solved part 2 in a non-optimal way (https://github.com/lawreka/aoc24/blob/master/src/aoc24/5.clj) > I'm just thinking about beginners who don't even know the algorithm exists this is why I love these threads, definitely going to spend some time looking at https://en.wikipedia.org/wiki/Topological_sorting today 🌞

after p2, rewrote p1 to use valid? when the list is the same as the sorted list.

Fun! (Though I really do need to start getting up earlier... 😅) https://github.com/CarnunMP/Advent-of-Code/blob/master/src/y2024/d5.clj

It seems like I might have come out with a solution that's different from the people here, at least for day 1 The general idea - though probably not so efficient, is to find out the positions of the two elements in a rule and make sure the order is correct

(defn is-valid-line [line [first second]]
  (let [pos-first (count (take-while #(not= % first) line))
        pos-second (count (take-while #(not= % second) line))
        line-count (count line)]
    (or
     (= pos-first line-count)
     (= pos-second line-count)
     (>= pos-second pos-first))))

(def sol1 (->> (for [update updates
                     :let [lines-validation (map #(is-valid-line update %) pages-order)
                           middle (nth update (quot (count update) 2))]
                     :when (every? true? lines-validation)]
                 middle) 
               (apply +)))

Today's was fun: https://gitlab.com/jake-jake-jake/aoc-2024/-/blob/main/src/aoc_2024/day_5.clj?ref_type=heads

(require '[clojure.string :as string])

(defn process-input [st]
  (second
   (reduce
    (fn [[process acc] line]
      (if (string/blank? line)
        [:print acc]
        (case process
          ;; split rule "X|Y" into [X Y]
          :rule
          [:rule (let [[k v] (string/split line #"\|")]
                   (-> acc
                       ;; "less rules" set of all Ys that are lesser than X
                       (update-in [:l-rules k] (fnil conj #{}) v)
                       ;; "great rules" set of all Xs that are greater than Y
                       (update-in [:g-rules v] (fnil conj #{}) k)))]

          ;; collection of preprocessed "prints"
          ;; "x,y,z" -> [x y z]
          :print
          [:print (update acc :prints (fnil conj [])
                          (string/split line #","))])))
    [:rule {}]
    (string/split-lines st))))

(defn custom-comparator [l-rules g-rules]
  (fn [a b]
    (cond
      (= a b) 0
      (contains? (get l-rules a) b) -1
      (contains? (get g-rules a) b) 1)))

(defn solve [input sorted?]
  (let [{:keys [l-rules g-rules prints]} (process-input input)
        compare (custom-comparator l-rules g-rules)
        pred (if sorted? #'= #'not=)
        result (if sorted? :before :after)]
    (transduce
     (comp (map (fn [print]
                  {:before print
                   :after (sort compare print)}))
           (filter #(pred (:before %) (:after %)))
           (map result)
           (map #(nth % (quot (count %) 2)))
           (map parse-long))
     +
     prints)))

;; part 1
(solve (slurp "input") true)

;; part 2
(solve (slurp "input") false)

curious to see everyone's solutions today. I spent a long time thinking there was a global ordering from the input rules, which is the case for the sample input but not for the real one. the idea was to use the rules to find out what is the page without successors, remove the rules where that is a successor, and repeat until you've find the ordering. turns out there's no page without successors if you look at all rules, but it's always the case for the rule subsets.

Well here’s todays: https://github.com/bhauman/adv2024/blob/main/src/adv2024/day05/sol.clj

#yamlscript part1

!yamlscript/v0

defn main(data): !:say
  rules updates =: data:slurp.split("\n\n")
  rules =: rules:lines.zipmap(repeat(1))
  updates =: updates:lines.map(\(_.split(',')))
  defn valid(update):
    loop update update:
      num1 num2 =: update.take(2)
      cond:
        rules.get("$num2|$num1"): false
        update:rest.!: true
        else: recur(update:rest)
  defn middle(_): _.nth(_.#.quot(2)):N
  sum: updates.filter(valid).map(middle)

#yamlscript part2

!yamlscript/v0

defn main(data): !:say
  rules updates =: data:slurp.split("\n\n")
  rules =: rules:lines.zipmap(repeat(1))
  updates =: updates:lines.map(\(_.split(',')))
  defn fixed(update):
    fixed =:
      loop update update, new []:
        n1 n2 =: update.take(2)
        cond:
          update:rest.!: new.conj(n1)
          rules.get("$n2|$n1"):
            recur _ []:
              new + [n2 n1] + update.drop(2):V
          else: recur(update:rest new.conj(n1))
    when fixed != update: fixed
  defn middle(_): _.nth(_.#.quot(2)):N
  sum: updates.keep(fixed).map(middle)

(ns stuartstein777.2024.day5
  (:require [clojure.string :as str]))

(defn parse-input []
  (let [[ordering-rules update-page-numbers]
        (-> "puzzle-inputs/2024/day5"
            (slurp)
            (str/split #"\n\n"))]
    {:ordering-rules (->> (str/split ordering-rules #"\n")
                          (mapv (fn [r] (->> (str/split r #"\|")
                                             (mapv parse-long)))))
     :update-page-numbers (->> (str/split update-page-numbers #"\n")
                               (mapv (fn [x] (->> (str/split x #",")
                                                  (mapv parse-long)
                                                  (partition 2 1)))))}))

(defn reducer [rules [before after]]
  (if (rules before)
    (update rules before conj after)
    (assoc rules before #{after})))

(defn build-ordering-rules-map [ordering-rules]
  (reduce reducer {} ordering-rules))

(defn get-middle [xs]
  (nth xs (/ (count xs) 2)))

(defn valid? [rules page-numbers]
  (reduce (fn [_ [before after]]
            (if (and (rules before) ((rules before) after))
              true
              (reduced false))) true page-numbers))

(defn part-one []
  (let [input (parse-input)
        page-numbers (:update-page-numbers input)
        rules (build-ordering-rules-map (:ordering-rules input))]
    (->> (filter (partial valid? rules) page-numbers)
         (mapv (fn [xs] (conj (mapv first xs) (last (last xs)))))
         (map get-middle)
         (reduce +))))

(part-one) ;; 5762

(defn insert-at [xs i n]
  (vec (concat (subvec xs 0 i) [n] (subvec xs i))))

;; for each number n
;;      cur-idx: 0
;;      x: res[cur-idx]
;;      check map for x
;;         does it contain n ?
;;             yes: at end of list?
;;                 yes: add n to end
;;                 no: increment cur-idx
;;             no: check map for n, does it contain x
;;                  yes: add n at cur-idx
;;                  no: increment cur-idx
(defn repair-reducer [rules acc n]
  (let [cnt (count acc)]
    (loop [idx 0]
      (if (= idx cnt)
        (conj acc n)
        (let [x (nth acc idx)]
          (if (and (rules x) ((rules x) n))
            (if (= idx cnt)
              (conj acc n)          ;; at end of list
              (recur (inc idx)))    ;; not at end of list, but doesnt go here.
            (if (and (rules n) ((rules n) x))
              (insert-at acc idx n) ;; found where it should be, insert it.
              (recur (inc idx))))))))) ;; not at end of list, but doesnt go here.

(defn repair [rules page-numbers]
  (reduce (partial repair-reducer rules) [(first page-numbers)] (rest page-numbers)))

(defn part-two []
  (let [input (parse-input)
        page-numbers (:update-page-numbers input)
        rules (build-ordering-rules-map (:ordering-rules input))]
    (->> (remove (partial valid? rules) page-numbers)
         (mapv (fn [xs] (conj (mapv first xs) (last (last xs)))))
         (mapv (partial repair rules))
         (map get-middle)
         (reduce +))))

(part-two) ;; 4130

ys->clj 🙂

$ ys -c part1.ys | zprint
(defn main
  [data]
  (say (let [[rules updates] (split (slurp data) "\n\n")
             rules (zipmap (lines rules) (repeat 1))
             updates (+map (lines updates) (fn [& [_1]] (split _1 ",")))]
         (defn valid
           [update]
           (loop [update update]
             (let [[num1 num2] (+take update 2)]
               (cond (get rules (str num2 "|" num1)) false
                     (ys.std/falsey? (rest update)) true
                     :else (recur (rest update))))))
         (defn middle [_] (N (+nth _ (quot (clojure.core/count _) 2))))
         (sum (+map (+filter updates valid) middle)))))
(apply main ARGS)

$ ys -c part2.ys | zprint
(defn main
  [data]
  (say
    (let [[rules updates] (split (slurp data) "\n\n")
          rules (zipmap (lines rules) (repeat 1))
          updates (+map (lines updates) (fn [& [_1]] (split _1 ",")))]
      (defn fixed
        [update]
        (let [fixed (loop [update update
                           new []]
                      (let [[n1 n2] (+take update 2)]
                        (cond (ys.std/falsey? (rest update)) (conj new n1)
                              (get rules (str n2 "|" n1))
                                (recur (add+ new [n2 n1] (V (+drop update 2)))
                                       [])
                              :else (recur (rest update) (conj new n1)))))]
          (when (not= fixed update) fixed)))
      (defn middle [_] (N (+nth _ (quot (clojure.core/count _) 2))))
      (sum (+map (+keep updates fixed) middle)))))
(apply main ARGS)

@malaingreclement - thanks for the kind words! That's really motivating to read. 🙂 I just implemented another solution that uses the comparator to reorder all inputs in a single go so there's common logic for parts 1 and 2. It wasn't necessary, but I felt like it anyway. • Updated blog: https://github.com/abyala/advent-2024-clojure/blob/main/docs/day05.md • Compact solution: https://github.com/abyala/advent-2024-clojure/blob/main/src/advent_2024_clojure/day05_compact.clj

Would have been interesting if the rules weren't complete for the input. e.g. having the 2 rules A|B and B|C implies A|C but this never came up. I'm surprised all the rules we had were enough.

my initial scan had me thinking that was a possibility, but I made myself read (and trust) the example again

I visualised the example and actual input with graphviz and deemed them „transitively closed by visual inspection”

Found a very interesting article in the solution megathread on reddit, about an algorithm to find the median without sorting the list, in O(n) complexity (instead of the O(n log n) of quicksort): https://rcoh.me/posts/linear-time-median-finding/

@qmstuart If you look a bit more, you'll see that the ordering is actually not a DAG but a loop. It's not a true ordering. Which is why a topo sort can get finnicky.

Lots of meme about that on the subreddit x)

if it weren't a true ordering there wouldn't be a One True Middle for problem 2

There is because the input is built in a way that the looping thing doesn't come up.

People discussing it here : https://www.reddit.com/r/adventofcode/comments/1h73c98/2024_day_5_rules_are_not_a_dag/

I'm pretty happy with this one:

(defn solve [s]
  (let [[ORD PAG] (map s->ints (split s #"\n\n"))
        RUL (reduce (fn [m [a b]] (update m a (fnil conj #{}) b)) {} ORD)
        COM (comparator (fn [a b] (not (contains? (RUL b) a))))]
    (->> PAG
         (map #(as-> (vec (sort COM %)) sx, [(= sx %) (sx (quot (count sx) 2))]))
         (reduce (fn [acc [ok n]] (update acc (if ok :part1 :part2) (fnil + 0) n)) {}))))

Initially i planned to use topological sorting, but i noticed the ordering has cycles. Then i found a nice use for comparator: https://github.com/ChrisBlom/advent-of-code/blob/master/src/adventofcode/2024/day05.clj

https://github.com/dvliman/advent-of-code/blob/master/src/dvliman/2024/day05.clj

I had decided on the way I'd go about this one pretty soon after reading the task, but I still hit some roadblocks due to my relative unfamiliarity with clojure... (including stuff like trying to index get an item out of (what along the way became) a sequence...

Got the chance to learn some cider debugging features at least.

Got tripped up because I thought there was a one true order to rule them all! But alas my precious order was no more https://github.com/oxalorg/aoc/blob/main/src/2024/day5.clj

(def input (into [0] (map #(slurp (format "resources/2024/%02d" %)) (range 1 25))))

(defn func1 [s] (->> (re-seq #"\d+" s) (mapv parse-long)))

(let [rules (->> (input 5) (re-seq #"\d+\|\d+") (map func1))
      updates (->> (input 5) (re-seq #"\d+,.*") (map func1))
      rules-map (-> (group-by first rules) (update-vals #(set (map second %))))
      validate-pair1 (fn [[a b]] ((rules-map a) b))
      validate-pair2 (fn [a b] (if ((rules-map a) b) 1 -1))
      combinations-2 (fn [xs]
                       (for [x (range (count xs))
                             y (range (inc x) (count xs))]
                         (map #(nth xs %) [x y])))]
  (->> (for [u updates]
         (if (every? validate-pair1 (combinations-2 u))
           [(nth u (quot (count u) 2)) 0]
           [0 (nth (sort validate-pair2 u) (quot (count u) 2))]))
       (apply map +)))

https://github.com/Lambdaphile/aoc/blob/main/2024/clojure/src/aoc/days/05/core.clj

https://gitlab.com/maximoburrito/advent2024/-/blob/main/src/day05/main.clj

Gonna spend some time cleaning this up laughcry https://gist.github.com/samcf/ee2ace7c6ed1422b5f97b4f3c8209e42

Needs some DRY-ing, but otherwise really easy day

DRY-ed version: https://github.com/Maravedis/advent_code/blob/master/src/advent_of_code/2024/05.clj

sort to the rescue https://github.com/zelark/AoC/blob/master/src/zelark/aoc_2024/day_05.clj

#todo add snippet

Would you mind putting the code in a snippet ? That way we get syntax highlighting and collapse ? The thread gets really hard to read after a couple of long blocks of code 😅 (ctrl+shift+enter to make a snippet by default)

Cleaned up a little, noticed from other solutions I could simplify things a lot with the rules map

My solution. I really wanted to find a way to take all the rules and create a manual that definitively said where each page would have to go, but there weren't enough rules to give a perfect ordering. So I just did the standard comparator that most folks here seem to have done. • Blog: https://github.com/abyala/advent-2024-clojure/blob/main/docs/day05.md • Source: https://github.com/abyala/advent-2024-clojure/blob/main/src/advent_2024_clojure/day05.clj

I remember last year being considerably more difficult, I'm not sure I solved the second part of day 5 in 2023

The beginning of last year was tough, yeah, and it got more in-line with 2022 afterward.

@abyala I've really been enjoying your breakdowns (and I've been steadily stealing your utils functions). Thanks for your work 🙌

https://github.com/benjamin-asdf/advent-of-code/blob/master/src/Y2024/day5.clj

https://github.com/gtoast/Advent-of-Code-2024/tree/master/day05