Clojurians Log v2

this case it would be (partial = 2020) I think

It’s this recommendation from the style guide https://github.com/bbatsov/clojure-style-guide#set-as-predicate

;; good
(remove #{1} [0 1 2 3 4 5])

;; bad
(remove #(= % 1) [0 1 2 3 4 5])

;; good
(count (filter #{\a \e \i \o \u} "mary had a little lamb"))

;; bad
(count (filter #(or (= % \a)
                    (= % \e)
                    (= % \i)
                    (= % \o)
                    (= % \u))
               "mary had a little lamb"))

Curious: why use set membership rather than `(= 2020 ...)

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

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

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

(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"

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

Why the while?

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 .

ah I see smart 🙂

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

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

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

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

@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”

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

@mroerni my definition of functional programming is “pure functions (that always return same output with same input) and no use of mutable variables”. By that definition the solution was already functional. Perhaps you mean something different, like using higher order functions with well known names (see below)? @juniusfree indeed map and filter are implemented using recursion. I think it’s instructive to look at and they have similar patterns to your solution, the gist of it (clojure.core one also uses lazy-seq to delay evaluation of recursive call making them lazy, and chunked sequences to increase performance):

(defn map* [f coll]
  (when (seq coll)
    (cons (f (first coll)) (map* f (rest coll)))))

(map* inc [1 2 3])
;; => (2 3 4)

@erwinrooijakkers Correct. There are a lot of built-in functions in Clojure that I still have to explore!

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