Fork me on GitHub
<
2020-12-01
>
kenj05:12:15

the AOC server is struggling tonight

rjray05:12:01

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

rjray05:12:14

😮 3
fingertoe07:12:21

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

rmprescott15:12:10

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

erwinrooijakkers10:12:23

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

erwinrooijakkers10:12:56

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

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

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

(count (filter #(or (= % \a)
(= % \e)
(= % \i)
(= % \o)
(= % \u))

nbardiuk09:12:02

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

misha10:12:24

``````(defn find-first [p xs]
(->> xs (filter p) first))``````
there is more efficient `some` instead
``(some pred xs)``

👍 3
nbardiuk10:12:20

that is interesting

``````(defn find-first [p xs]
(some #(when (p %) %) xs))``````
some returns first truthy value, so I had to wrap it into when, and it is slightly slower now

spfeiffer10:12:18

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

misha10:12:38

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

misha11:12:24

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

nbardiuk11:12:28

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

nbardiuk11:12:31

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

misha11:12:01

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

👍 3
zackteo09:12:19

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

zackteo09:12:00

Maybe I should create a repo for advent of code hmmmm

misha09:12:03

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

👍 3
💯 3
misha09:12:25

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

zackteo09:12:32

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

misha09:12:26

``````(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})``````

misha09:12:45

`xs` is parsed puzzle input, seq of ints, yes

erwinrooijakkers11:12:26

Why the `while`?

misha11:12:26

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

misha11:12:09

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

erwinrooijakkers14:12:48

ah I see smart 🙂

erwinrooijakkers19:12:56

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

erwinrooijakkers19:12:56

Ah your while is one step earlier

misha09:12:20

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

zackteo09:12:57

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

👍 3
oxalorg (Mitesh)10:12:23

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

Björn Ebbinghaus10:12:35

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

Björn Ebbinghaus11:12:57

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

👍 3
nbardiuk12:12:53

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

Björn Ebbinghaus11:12:42

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))))``````
And: Are abbreviated parameters worth it? I have no idea what you mean with `loe`

🙏 3
juniusfree11:12:13

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

Björn Ebbinghaus12:12:48

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)))``````
(`(some pred coll)` returns the first “truthy” value when pred is applied to every element in item.)

Björn Ebbinghaus12:12:06

Or maybe easier to understand:

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

juniusfree12:12:48

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

erwinrooijakkers12:12:11

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

;; is the same as:

(if (seq x)
(blabla)
0)``````

erwinrooijakkers12:12:29

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

erwinrooijakkers12:12:50

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

erwinrooijakkers12:12:15

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

👍 3
erwinrooijakkers12:12:23

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

Björn Ebbinghaus12:12:39

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

erwinrooijakkers18:12:15

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

Björn Ebbinghaus19:12:49

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.

juniusfree21:12:42

@U4VT24ZM3 @U2PGHFU5U 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?

Björn Ebbinghaus21:12:25

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

👍 3
erwinrooijakkers12:12:26

@U4VT24ZM3 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)? @U013R0P5ZJT 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)``````
`reduce` can also be implemented recursively and you can implemented `map` and `filter` also in terms of `reduce`. Some examples are given in https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-15.html#%_sec_2.2 (`reduce` is called `accumulate` there and is used to implement other higher order functions). It states in SICP: > In effect, `map` helps establish an abstraction barrier that isolates the implementation of procedures that transform lists from the details of how the elements of the list are extracted and combined The recursive definitions you defined yourself probably already exist, or can be written in, terms of higher order functions with well known names, thus making us think differently and perhaps arguably more functionally.

juniusfree20:12:14

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

fingertoe15:12:27

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

fingertoe15:12:32

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

mchampine19:12:41

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

🔥 12