Fork me on GitHub
#adventofcode
<
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

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.

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

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

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

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