Clojurians Log v2

the AOC server is struggling tonight

Yeah, I was getting alternating 502/503 errors within the first minute or so.

Per reddit thread (https://www.reddit.com/r/adventofcode/comments/k4ejjz/2020_day_1_unlock_crash_postmortem/), the downtime was due to overloading their configured AWS instances. They'll be canceling leaderboard points for the first day.

Got day 1 done.. My question 2 answer came up too easily.. I might have to mix up my data to make it work on more universal data..

Day 1 with math.combinatorics https://github.com/transducer/adventofcode/blob/master/src/adventofcode/2020/day1.clj

oh, cool TIL about math.combinatorics I had to roll my own inefficient combinations function https://github.com/nbardiuk/adventofcode/blob/0955796f728c9d73376ba480003994db902c6b21/2020/src/day01.clj

but I guess @nbardiuk that might be a good exercise haha. I did

(require '[clojure.math.combinatorics :as combo])

(->> (combo/combinations data 2)
     (filter #(= (apply + %) 2020))
     (apply reduce *))

Maybe I should create a repo for advent of code hmmmm

no deps, little waste, part 2 "Elapsed time: 2.362157 msecs"

(time
  (let [xs   (->> input (str/split-lines) (map read-string) (sort <))
        vecs (for [x xs
                   y xs
                   :while (< (+ x y) 2020)
                   z xs
                   :let   [s (+ y x z)]
                   :while (<= s 2020)
                   :when  (= s 2020)]
               [x y z])]
    (some->> vecs first (apply *))))

"Elapsed time: 2.362157 msecs"

@zackteo your example gives me "Elapsed time: 1095.922251 msecs" for part2

@misha right >< yeah was thinking it isn't optimal but at least is a start hahaha 🙂 I usually don't get these challenges done

so the first while is a pre-filtering. And xs is the sequential list of numbers?

(for [x [1 2 3]
      y [1 2 3]]
  {:x x :y y})
=>
({:x 1, :y 1}
 {:x 1, :y 2}
 {:x 1, :y 3}
 {:x 2, :y 1}
 {:x 2, :y 2}
 ,,,

(for [x [1 2 3]
      :when (< x 2)
      y [1 2 3]]
  {:x x :y y})
=>
({:x 1, :y 1}
 {:x 1, :y 2}
 {:x 1, :y 3})

xs is parsed puzzle input, seq of ints, yes

(defn find-first [p xs]
  (->> xs (filter p) first))

(some pred xs)

that is interesting

(defn find-first [p xs]
  (some #(when (p %) %) xs))

Yes, the combinatorics namespace has been very valuable for many AoC Puzzles in the past.

ah, yes, should have mentioned: you'd have to change predicate too.

I used a different apporach to solve this problem here: https://nextjournal.com/oxalorg/advent-of-clojure-01 The runtime complexity here is O(n) for part1 and O(n^2) for part 2

I made use of some in combination with set lookup. I find it quite simple. Task 1: ~ 0.25 msecs Task 2: ~30 msecs When executed with babashka https://github.com/MrEbbinghaus/advent-of-code/blob/master/2020/day01.clj

in the worst case filter walks extra 31 element after first is ready to go:

(->> (range 100) 
  (filter #(do (println %) (even? %)))
  (first))

0
1
,,,
30
31
=> 0

oh, that is valid point, it is dangerous in case of side effects inside filter

I am still curious why in my case some was not visibly faster, maybe it is related with chunking?

(chunked-seq? (range 100)) ; true
(chunked-seq? (combinations 2 [1 2 3])) ; false

When I use a sorted-set as input I go down to 0.08ms and 0.09ms. But I think my input list favors this heavily as just 7 numbers are smaller than 2020 / 2 ..

Why the while?

👋Newbie coder. Trying my first AoC. Any helpful feedback is welcome! https://twitter.com/juniusfree/status/1333727767658053632 https://github.com/juniusfree/advent-code-2020/tree/master/day01

notice, input ints are sorted ascending. while makes sure for does not iterate over combinations which are already known to be useless. even though xs are sorted, combinations of [x y z] - are not, and as soon as y or z becomes large enough to disqualify [x y z] - while makes for abandon iteration over the rest of y or z , and takes next x (or y respectively) instead

if all combinations would be sorted by sum , you'd be able to just (->> combos (drop-while <2020) first). but combinations are not sorted, so need to terminate "branch" early another way: while .

Have look at recur for tail-recursion. https://clojuredocs.org/clojure.core/recur https://clojure.org/about/functional_programming#_recursive_looping Check this out

(defn check-second
  [fst rst]
  (cond
    (nil? (first rst))            nil
    (= 2020 (+ fst (first rst)))  (* fst (first rst))
    :else                         (recur fst (rest rst))))

I think so, yes:

(defn- -unchunk [sek]
  (when sek
    (lazy-seq
      (cons (first sek)
        (-unchunk (next sek))))))

(defn unchunked-seq
  "converts coll into seq which will be realized 1 element at a time,
   and not in chunks, like e.g. 32 for (range 40)."
  [coll]
  (let [xs (seq coll)]
    (if (chunked-seq? xs)
      (-unchunk xs)
      xs)))

(->> (range 100)
  (unchunked-seq)
  (filter #(do (println %) (even? %)))
  (first))

0
=> 0

@mroerni Thanks for checking. loe just means list of expenses. I'll definitely look into recur

And it looks like you are still in the “thinking in loops”-phase (every functional programming beginner starts there when they come from python, java, … whatever In functional programming you would not “iterate” over things.. You apply functions to collections. Like so:

(defn check-second [fst rst]
  (when-let [snd (some (fn [possible-snd] (when (= 2020 (+ fst possible-snd)) possible-snd)) rst)]
    (* fst snd)))

Or maybe easier to understand:

(when-let [snd (first (filter #(= 2020 (+ fst %)) rst))]
  (* fst snd))

@mroerni You're right. I haven't develop the intuition yet on the application of functions on collections. Any tips or resources for that? And thanks for providing the revised code. I'll definitely study this.

(cond (seq x) (blabla)
      :else 0)

;; is the same as:

(if (seq x)
  (blabla)
  0)

and you can use some sequential destructuring (https://clojure.org/guides/destructuring#_sequential_destructuring) instead of doing first and rest amybe

(defn report-repair
  [loe]
  (cond
    (empty? loe) 0
    :else (or
            (check-second (first loe) (rest loe))
            (report-repair (rest loe)))))

=

(defn report-repair
  [[x & xs :as expenses]]
  (cond
    (empty? expenses) 0
    :else (or
            (check-second x xs)
            (report-repair xs))))

=

(defn report-repair [[x & xs :as expenses]]
  (if (seq expenses)
    (or (check-second x xs)
        (report-repair xs))
    0))

@juniusfree Maybe have a look at Clojure for the Brave and True https://www.braveclojure.com/clojure-for-the-brave-and-true/ But what I told you makes the difference between “Learning the clojure syntax” and “Learning functional programming”

right! I also have noticed that sorting input improves almost any solution I've tried

ah I see smart 🙂

https://github.com/jreighley/aoc2020/blob/master/src/prb1.clj

(time (reduce * (find-pair data 2020))) “Elapsed time: 0.646178 msecs” => 786811 (time (reduce * (find-triple data 2020))) “Elapsed time: 1.553634 msecs”

That doesn’t count the slurp or sort though.. using sorted data made my first answer right.

@mroerni in my eyes it’s quite a functional solution already because of the use of recursion. But yes there are possibly functions that encapsulate these recursive patterns in names (like map, filter, reduce and for-comprehension). I 100% agree with not using abbreviations.

I updated to similar to you 🙂 https://github.com/transducer/adventofcode/blob/master/src/adventofcode/2020/day1.clj

25ms then

Did not look for edge cases (like adding same number) and was not necessary for my input

Ah your while is one step earlier

Then 3ms

(def inp (map #(Integer/parseInt %) (str/split-lines (slurp "day1.data"))))
(first (for [a inp b inp :when (= 2020 (+ a b))] (* a b))) ;; part 1
(first (for [a inp b inp c inp :when (= 2020 (+ a b c))] (* a b c))) ;; part 2

I think this use of recursion is symptom of this “loop” thinking. And not an “apply function to collection” mindset. Recursion doesn’t make it functional. You can think of it that way: Does the decision whether a value in the input has a partner to sum to 2020 or not depend on prior values in the input? Does the order matter? No. So why a recursion? In a recursion you do one thing after another.

@mroerni @erwinrooijakkers Thanks for your feedback. I'll take some time to study these things. I have a question though. Please correct me if I'm wrong. Doesn't map,`filter`, etc. uses recursion under the hood?

Maybe, maybe not. 🙂 But this shouldn’t be your concern, it is a layer of abstraction.

@mroerni OK. 😅