Fork me on GitHub
#adventofcode
<
2020-12-09
>
Vincent Cantin03:12:25

Polling for yesterday's solution: PC people bmo vs. IP people bananadance

bmo 15
bananadance 12
djblue05:12:04

I'm going to rename my repo to advent-of-for 馃槅

馃槀 18
alekszelark05:12:11

Day 9 Answers Thread - Post your answers here

alekszelark05:12:02

Just solved today鈥檚 puzzle, but it鈥檚 a bit dirty, so I鈥檓 going to refactor it before publishing ^_^

rjray06:12:25

Grrr. Got my first wrong submission this time, on part 1. Last year I reached day 12 before I made a wrong submission. Ah well. clojure.math.combinatorics helps again... https://github.com/rjray/advent-2020-clojure/blob/master/src/advent_of_code/day09.clj

mchampine06:12:46

Mine鈥檚 quick-n-dirty also, but whatever.. [edit] Cleaned up a bit.

(def input
  (map #(BigInteger. %)
       (str/split-lines (slurp "resources/day09.data"))))

;; part 1 (refactored for to set/when/not-any via nbardiuk)
(defn none-valid? [blk]
  (let [ps (set (butlast blk))
        n (last blk)]
    (when (not-any? #(ps (- n %)) ps) n)))

@(def sol-p1 (some none-valid? (partition 26 1 input)))
;; => 400480901

;; part 2
(defn findn [n] (filter #(= sol-p1 (apply + %)) (partition n 1 input)))

(->> (ffirst (remove empty? (map findn (iterate inc 2))))
     (#(+ (apply max %) (apply min %))))
;; => 67587168N

馃憤 3
fingertoe06:12:26

Using reductions + as a set has to be a terrible idea, but it worked.. https://github.com/jreighley/aoc2020/blob/master/src/day9.clj

nbardiuk07:12:20

https://github.com/nbardiuk/adventofcode/blob/master/2020/src/day09.clj today I've used partition juxt reductions it was fun

馃憦 15
馃挴 3
pez10:12:55

Not cleaned up at all.

(defn parse [input]
  (->> input
       (re-seq #"\d+")
       (map #(Integer/parseInt %))))

(comment
  (def input (util/fetch-input 9))
  ; step 1
  (->> input
       (parse)
       (partition 26 1)
       (keep #(apply (fn [& nums]
                       (let [code     (butlast nums)
                             checksum (last nums)
                             sums (for [a (butlast code)
                                        b (rest code)
                                        :let [sum (+ a b)]]
                                    sum)]
                         (when-not ((set sums) checksum)
                           checksum))) %))

       (first))

  ; step 2
  (def weakness 127)
  (def weakness 36845998)
  (->> input
       (parse)
       ((fn dig [weakness data]
          (loop [remaining data]
            (let [nums (reduce (fn [acc num]
                                 (let [new-acc (conj acc num)
                                       sum (apply + new-acc)]
                                   (cond
                                     (= sum weakness) (reduced new-acc)
                                     (> sum weakness) (reduced nil)
                                     :else new-acc)))
                               []
                               remaining)]

              (if nums
                nums
                (recur (rest remaining)))))) weakness)
       ((fn [nums] [(apply min nums) (apply max nums)]))
       (apply +)))

motform12:12:03

It seems like brute-force was the name of the game. Missed an opportunity to juxt though! https://github.com/motform/advent-of-clojure/blob/master/src/advent-of-clojure/2020/nine.clj

st3fan12:12:59

Yup brute force

st3fan12:12:41

Oh! recur without a loop is allowed?

alekszelark12:12:57

@U4T7GE7PE Yes it works with functions as well.

motform12:12:49

It goes to the latest fn-def, which can be #(), letfn, loop, defn or fn (afaik those are the main ones). I always thought of loop as a nicer proxy for a nested recur-fn a scheme

Bj枚rn Ebbinghaus12:12:13

How long does your solutions take? I need 1,3s and it really bugs me, that I don鈥檛 know why it takes so long..

Vincent Cantin12:12:47

What is the algorithmic complexity of your code? Mine is O(n^2) and it is faster than your. O(n) might be possible also.

Joe12:12:09

Mine is 150ms for part 1, 35ms for part 2. Only using time though, so might be inaccurate. That's also with the input already loaded into memory.

nbardiuk13:12:44

10ms and 35ms when the input string is already in the memory using time

Vincent Cantin13:12:53

For part2, if all the numbers are positive, it might be possible to solve it by doing one pass over the collection, adding in front when the sum is less, and removing from behind when the sum is greater.

馃憤 12
pez14:12:34

I think that means that all numbers in my input are positive. 馃槂

Vincent Cantin15:12:45

Yes, that's what I meant.

Vincent Cantin15:12:27

The sum could be a rolling sum ... you add in front and substract in the back.

tws16:12:48

yes, i know i鈥檓 resumming too much, that鈥檚 for a phantom refactor that may never happen 馃檪

alekszelark17:12:22

@U076FM90B, you solution is awesome! But I noticed that has-sum should be called has-not-sum 馃檪

nbardiuk17:12:25

That is right! I have renamed it couple times and never noticed the missing negation

alekszelark18:12:20

Also (apply max-key count) could be just first 馃

R.A. Porter18:12:53

Definitely needs some cleanup: https://github.com/coyotesqrl/advent2020/blob/master/src/coyotesqrl/advent2020.clj#L464 but I was not completely disgusted by what I wrote.

markw19:12:18

Not the most efficient, but I think it鈥檚 reasonably clean: https://github.com/Solaxun/aoc2020_clj/blob/main/src/aoc2020_clj/day9.clj

plexus07:12:54

Recording for day 9 https://youtu.be/7gp4MZdCDQc used a nested loop/recur for part 2, I may try to clean that up a bit later today 馃檪

馃憤 3
Vincent Cantin07:12:20

After some heavy cleanup, I made a version which is using only the for loop. https://github.com/green-coder/advent-of-code-2020/blob/master/src/aoc/day_9.clj#L19-L48 Edit: not totally, there is still a reduce inside.

Vincent Cantin08:12:57

I decided to write some functions with the purpose of saving time of some commonly used operations. Here is my new group-by. Feedback welcome:

(defn group-by
  "Same as clojure.core/group-by, but with some handy new arities which apply
   custom map & reduce operations to the elements grouped together under the same key."
  ([kf coll]
   (group-by kf identity conj [] coll))
  ([kf vf coll]
   (group-by kf vf conj [] coll))
  ([kf vf rf coll]
   (group-by kf vf rf (rf) coll))
  ([kf vf rf init coll]
   (persistent!
    (reduce
     (fn [ret x]
       (let [k (kf x)
             v (vf x)]
         (assoc! ret k (rf (get ret k init) v))))
     (transient {}) coll))))

Vincent Cantin08:12:28

Testing expressions:

(group-by first [[:a 1] [:a 2] [:b 3] [:a 4] [:b 5]])
(group-by first second [[:a 1] [:a 2] [:b 3] [:a 4] [:b 5]])
(group-by first second + [[:a 1] [:a 2] [:b 3] [:a 4] [:b 5]])
(group-by first second + 10 [[:a 1] [:a 2] [:b 3] [:a 4] [:b 5]])

=> {:a [[:a 1] [:a 2] [:a 4]], :b [[:b 3] [:b 5]]}
=> {:a [1 2 4], :b [3 5]}
=> {:a 7, :b 8}
=> {:a 17, :b 18}

Vincent Cantin09:12:01

I made this group-by because usually the part which is in the val after the group-by is often the target of further computation.

Vincent Cantin09:12:02

Another problem I want to address is comp on functions. The way I think about the operations to apply is the reverse of what I need to write.

(defn comp-> [& args]
  (apply comp (reverse args)))

#_ ((comp str inc) 17) ; => "18"
#_ ((comp-> inc str) 17) ; => "18"
Feedback welcome.

metal 3
imre09:12:43

@vincent.cantin I recommend taking a look at https://github.com/cgrand/xforms - there are lots of goodies in there that help build stuff like this but it's all transducer-based

馃憤 3
imre09:12:37

I used it in a lot of places in my solutions so far https://github.com/imrekoszo/advent-2020/

馃憤 3
Vincent Cantin09:12:44

It is a good library. With this tree-seq transducer, you may have used it at one more place too. https://github.com/cgrand/xforms/issues/20

imre09:12:18

Nice one, that 馃檪

Vincent Cantin09:12:48

on the shiny bag day

imre09:12:40

I don't think I got that far just yet

imre09:12:47

I'm 3 days behind rn

Vincent Cantin09:12:49

Side note: The functions I past in the channel are targeted at saving typing time. They are not necessarily the right choice for quality code.

Vincent Cantin09:12:24

Until now, performance was not the issue in all the puzzles, so lazy collections are still in the game.

imre09:12:58

I prefer using transducers even then. Easy to go back to lazyland from there

Vincent Cantin09:12:19

One last function: the equivalent of partition, but with vector input and a sequence of subvec as output.

(defn partitionv
  ([n vec-coll]
   (partitionv n n vec-coll))
  ([n step vec-coll]
   (for [i (range n (inc (count vec-coll)) step)]
     (subvec vec-coll (- i n) i))))

#_ (partitionv 3 (vec (range 10)))
#_ (partitionv 3 1 (vec (range 10)))
The idea is to keep collections which are indexable (i.e. vectors) while having the benefits of partition

Vincent Cantin10:12:15

@plexus you may like that one

plexus10:12:04

oh yeah that's nice

erwinrooijakkers10:12:08

maybe more logical to return a vec of subvecs?

Vincent Cantin11:12:49

the lazyness on the outter sequence could be useful, I want to keep it.

馃憤 3
Vincent Cantin11:12:39

I will also make a variation partition-indexes which returns the indexes of the possible sub-vectors.

nbardiuk12:12:10

I've build similar function, which returns sequence of vectors, but does not require input to be a vector https://gist.github.com/nbardiuk/ec16046263734c795a82d33dcf83fb81#file-moving-avarage-clj-L4-L8 but in my case it would be probably simpler to just use partition (I didn't know it has step argument)

alekszelark18:12:58

Day 10 Answers Thread - Post your answers here

bubblebobble 3
mchampine06:12:17

Updated w/ part 2. Note: I found an interesting pattern. Looking a the diffs pattern (first and last value with moving window of 3) you can simply count the number of runs of 2's. Runs of 3 = 7, runs of 2 = 4, runs of 1 = 2, then take the product.

;; part 1
(let [jolts (sort (concat input [0 (+ 3 (apply max input))]))
      diffs (map (fn [[a b]] (- b a)) (partition 2 1 jolts))]
  (apply * (vals (select-keys (frequencies diffs) [1 3]))))
;; => 1690

;; part 2
(defn adapter-combos [inp]
  (->> (sort (concat inp [0 (+ 3 (apply max inp))]))
       (partition 3 1)
       (map (fn [[a _ c]] (- c a)))
       (partition-by identity)
       (keep {'(2 2 2) 7 '(2 2) 4 '(2) 2})
       (reduce *)))

(adapter-combos input)
;; => 5289227976704

pez07:12:40

No real idea about how to think about step 2. Step1 seemed like this to me:

(->> input
       (parse)
       (sort)
       (cons 0)
       (#(concat % [(+ 3 (last %))]))
       (partition 2 1)
       (map #(- (second %) (first %)))
       (frequencies)
       (vals)
       (apply *))

馃憤 3
Dosbol08:12:39

{0 1}
{1 1}
{4 1}
{5 1, 6 1, 7 1}
{6 1, 7 2, 10 1}
{7 1, 10 2, 11 1, 12 1}
{10 1, 11 2, 12 3, 15 1}
{11 1, 12 3, 15 3, 16 1}
{12 1, 15 3, 16 3, 19 1}
{15 1, 16 3, 19 4}
{16 1, 19 7}
{19 8}

  (defn next-numbers [x]
    (remove nil? [(when (some #{(+ x 1)} data) (+ x 1))
                  (when (some #{(+ x 2)} data) (+ x 2))
                  (when (some #{(+ x 3)} data) (+ x 3))]))

  (defn next-ways [m]
    (reduce-kv
     (fn [m k v]
       (-> (reduce (fn [m key] (update m key (fnil + 0) v))
                   m
                   (next-numbers k))
           (update k - v)
           (->> (filter (fn [[_ y]] (not= y 0)))
                (into {}))))
     m
     (dissoc m maximum)))

  (loop [ways {0 1}]
    (if (= (keys ways) (list maximum))
      (ways maximum)
      (recur (next-ways ways))))

鉂わ笍 6
pez09:12:00

Trying to not look at your solutions just yet, but seems best to ask this here. Part 2 seems like a math problem to me. When there is a string of distances 1, I can remove some subsets of them and still have a 鈥渂ridge鈥. Does that make sense to you people?

oxalorg (Mitesh)09:12:37

My day 10 solution, but I ported my python solution as-is. I am not satisfied with this though and maybe there's a more "clojurey" / "functional" way to do this. I'll go through some of the above solution to check alterntative methods: https://github.com/oxalorg/aoc/blob/main/src/day10.clj

oxalorg (Mitesh)09:12:01

@pez I can probably give you a small hint: It's not a math problem, it's a memory problem. Can you find out a way to mix and match such that you reduce unnecessary computations.

erwinrooijakkers09:12:11

I calculated in three parts using brute force https://github.com/transducer/adventofcode/blob/master/src/adventofcode/2020/day10.clj Cut the coll in three parts (finding snips where I could cut the adapters, if there鈥檚 a gap of 2 in between you don鈥檛 miss any) then multiplying the separate answers Not proud of this using an atom to count. But it works. Will try to improve if I have more time. Also wanting to fully automate.

erwinrooijakkers09:12:30

I read btw that the creator of AoC is not a fan of checking in your inputs, he prefers not making them public

馃憤 3
erwinrooijakkers09:12:36

@U013MQC5YKD a you can also brute force using memoize?

erwinrooijakkers09:12:43

Cutting of parts you already did?

pez09:12:48

Part of it can be seen as a math problem, it seems, @U013MQC5YKD. Here鈥檚 a 鈥渟olution鈥:

(->> input
       (parse)
       (sort)
       (cons 0)
       (#(concat % [(+ 3 (last %))]))
       (partition 2 1)
       (map #(- (second %) (first %)))
       (partition-by identity)
       (keep #(seq (filter #{1} %)))
       (map count)
       (map {1 1
             2 2
             3 4
             4 7})
       (apply *))

馃檹 3
馃憦 3
pez09:12:08

Using the longer example in the calendar, after the keep there I have this: ((1 1 1 1) (1 1 1 1) (1 1 1) (1 1) (1 1 1 1) (1) (1 1 1 1)) which is the strings of 1 distances I was thinking about. So after mapping count over them I have (4 4 3 2 4 1 4). I then map those over the 鈥渕agic鈥 function that tells me how many combinations each string contributes with. Then multiplying all those.

pez09:12:50

I have yet to figure out the 鈥渕agic鈥 function, but don鈥檛 expect a blocker there.

oxalorg (Mitesh)09:12:36

@U2PGHFU5U That is a very nice solution! If you can try and generalize your part cutting solution in a way where you don't have to cut, rather just progressively find solutions to larger subsets then you will have discovered Dynamic programming!

oxalorg (Mitesh)10:12:47

@pez That is an interesting take on this, I'll have to dig deeper to understand it haha

erwinrooijakkers10:12:27

haha funny you say that talked about dynamic programming last night with a friend and realized i did not know what it was and that i would find out more today

parrot 6
pez10:12:19

I will have to check that out too! 馃槂

erwinrooijakkers10:12:27

so you start in the small, then go up to a larger problem, adding the sub amounts?

erwinrooijakkers10:12:35

like the opposite of memoization

erwinrooijakkers10:12:30

with memoization you start in the large and memoize subparts, with dynamic programming you start in the small and go to the large, i have to find out more after work 馃檪

馃憤 3
erwinrooijakkers10:12:36

@U013MQC5YKD the problem with the cutting is that for just bare multiplication the subparts needs to be separated on the three jumps. e.g., From the example:

(count-paths [1 4 5 6 7 10 11 12 15 16 19])
;; => 8
and when cutting on a three jump (from 7 to 10) you can just multiply solutions to both parts:
(* (count-paths [1 4 5 6 7])
   (count-paths [10 11 12 15 16 19]))
;; => 8
But when cutting between 10 and 11, you miss a few solutions:
(* (count-paths [1 4 5 6 7 10])
   (count-paths [11 12 15 16 19]))
;; => 4
So not sure how I can prevent this cutting part or maybe if there鈥檚 some logic to the type of cutting and the factor of paths you miss

oxalorg (Mitesh)10:12:48

Don't think about cutting the input randomly. Put a bit more stress on the problem and figure out a pattern in which dividing the problem into smaller parts gives you something concrete (the ability to avoid future computations)

馃憤 3
nbardiuk10:12:28

I've cut input by difference of 3, then counted connections inside each group. Since 3 is the longest possible link, only one item from group can reach next group

馃挴 3
pez12:12:18

So the 鈥渕agic鈥 function/map in my step 2 鈥渟olution鈥 above was really just the needed 2-combinations + 1. So then this is my real solution:

(defn ! [n]
  (reduce *' (range 1 (inc n))))

(defn combinations [n r]
  (if (= 1 n)
    0
    (let [n! (! n)
          r! (! r)
          r-n! (! (- n r))]
      (/ n! (* r! r-n!)))))

(->> parsed-input
     (sort)
     (cons 0)
     (#(concat % [(+ 3 (last %))]))
     (partition 2 1)
     (map #(- (second %) (first %)))
     (partition-by identity)
     (keep #(seq (filter #{1} %)))
     (map count)
     (map #(inc (combinations % 2)))
     (apply *))

馃帀 9
馃く 12
pez12:12:23

Given parsed input it runs in just above 1ms on my machine fed my input data. I guess that decent. Anyone see any speed gains I could collect? @U051HUZLD, maybe?

oxalorg (Mitesh)12:12:52

This is beautiful @pez ! So basically you're finding out how many ways can we arrange consecutive adapters until we have a jump which is a 3 volt difference. Since a 3 volt difference can't be reached by any adapter in the previous consecutive list (except for the last one) so that won't affect the number of arrangements.

馃憤 3
oxalorg (Mitesh)12:12:37

You definitely did it the math way 馃槃

pez13:12:46

Thanks! Yes, like that. When solving step 1, I had stuff like this before I applied frequencies:

(1 1 1 1 3 1 1 1 1 3 3 1 1 1 3 1 1 3 3 1 1 1 1 3 1 3 3 1 1 1 1 3)
And those strings of 1s looked like bridges to me.

馃憦 3
pez13:12:57

But then I needed to ask my daughter for help with figuring out the pattern. Then wikipedia helped me with the math. 馃槂

馃槆 3
oxalorg (Mitesh)13:12:12

That was great thinking, not going to lie I don't think I would've noticed this! 馃檲

pez13:12:57

I think it was because I think so literally about the problem as it is stated. It made me miss those binary numbers when finding a seat on that plane, but spot this bridging thing instead. Haha.

馃槅 3
馃挴 3
oxalorg (Mitesh)13:12:05

One catch in this solution would be if the requirement of using all adapters were loosened and the AOC input had something like this: [2 4 7] So there would be two ways to arrange this: [2 4 7] and [2 7] Maybe something can be done with the bridges to divide them even further? Or just count the number of 2 and multiply the result by n^2 as every 2 would lead to two possible solutions

nbardiuk13:12:12

oh, I didn't notice that there are only differences in 1 and 3, I assumed that there should be 2s somewhere 馃槷

oxalorg (Mitesh)13:12:02

@U076FM90B Yes I didn't realise that either, just went back and checked they've said "need to use all adapters" and they've conveniently left input which can lead to a difference of 2

馃憤 3
oxalorg (Mitesh)13:12:19

Awesome solution by @pez in case people missed this thread!

鉂わ笍 3
benoit13:12:57

path-count(n) = path-count(n+1) + path-count(n+2) + path-count(n+3)

misha14:12:58

@pez I don't think 1ms needs any speeding up. I have a similar solution wrt splitting by "magic" [3 3] pattern, but my "combinations" function is a dirty loop, I have left over from the morning

misha14:12:05

(def minus (fnil - ##Inf ##Inf))

(defn split [xs]
  (let [threes (fn [[a b c]] (= 3 (minus a b) (minus b c)))]
    (->> xs
      (partition-all 3 1)
      (partition-by threes)
      (map (partial map first))
      (partition-all 2)
      (map (partial apply concat)))))

(->> xs split (map p1) (reduce *))

pez15:12:47

It鈥檚 wonderful!

Ben List15:12:18

struggled with part 2 for a little bit, but memoization saved the day. Pretty happy with my end result https://github.com/listba/advent-of-code-2020/blob/master/clojure/src/aoc_2020/days/10.clj

馃憤 3
rjray17:12:01

This took me over 2 1/2 hours. I basically had part 2 correct, but I had the memoize at the wrong lexical level and I wasn鈥檛 getting any benefit from it. Looking at @vincent.cantin鈥檚 solution showed me what I had wrong. At least I can take some solace in knowing I was about 96% there鈥 https://github.com/rjray/advent-2020-clojure/blob/master/src/advent_of_code/day10bis.clj

tws18:12:31

Not as clean as the awesome O(n) above, but this was my first idea - to isolate the areas of multiple paths (runs of 1), compute the ways through them (kind of like a change making algo), then multiply those together. https://github.com/tschady/advent-of-code/blob/master/src/aoc/2020/d10.clj

mchampine18:12:12

I found an interesting pattern for part 2. I haven鈥檛 waded through all the other solutions to see if someone discovered this, but: Looking at the diffs pattern (first and last value with moving window of 3) you can simply count the number of runs of 2's.聽Runs of 3 = 7, runs of 2 = 4, runs of 1 = 2, then take the product. [edit]. Just discovered @UGFL22X0Q posted a question on the main thread earlier that references the prime factorization. So, yeah, some others were onto this idea also.. Maybe there are more. Note: runs in 鈥淓lapsed time: 0.5174 msecs鈥

;; part 2
(defn adapter-combos [inp]
  (->> (sort (concat inp [0 (+ 3 (apply max inp))]))
       (partition 3 1)
       (map (fn [[a _ c]] (- c a)))
       (partition-by identity)
       (keep {'(2 2 2) 7 '(2 2) 4 '(2) 2})
       (reduce *)))
(adapter-combos input)
;; => 5289227976704

Joe18:12:08

Dang, tough part 2, spent a good half-hour with pen and paper before I touched the keyboard. https://github.com/RedPenguin101/aoc2020/blob/main/day10.clj- but it is fast, < 2ms.

R.A. Porter19:12:05

I鈥檓 not going to say how long part 2 took me. And it鈥檚 not like it鈥檚 the prettiest of solutions鈥ould be really short if I鈥檇 found a graphing library to count all paths in a DAG for me. https://github.com/coyotesqrl/advent2020/blob/master/src/coyotesqrl/advent2020.clj#L550

馃憦 3
Joe19:12:21

https://redpenguin101.github.io/posts/2020_12_10_aoc2020_day10.html. Looking forward to going through other peoples solutions for this one!

metal 3
pez20:12:23

I got very different results from time so tried criterium quick-bench which reports:

Evaluation count : 4350 in 6 samples of 725 calls.
             Execution time mean : 137,221776 碌s
    Execution time std-deviation : 3,615336 碌s
   Execution time lower quantile : 134,692566 碌s ( 2,5%)
   Execution time upper quantile : 143,297341 碌s (97,5%)
                   Overhead used : 6,391737 ns

Found 1 outliers in 6 samples (16,6667 %)
	low-severe	 1 (16,6667 %)
 Variance from outliers : 13,8889 % Variance is moderately inflated by outliers

pez20:12:15

I get 18 碌s for the smallest sample input and 43 碌s for the larger.

curlyfry23:12:21

(ns day10.core
  (:require [clojure.string :as str]))

(def input (slurp "src/day10/input.txt"))

(defn add-device [coll]
  (cons (+ 3 (apply max coll)) coll))

(def adapters (->> input
                   (str/split-lines)
                   (map #(Long. %))
                   (add-device)
                   (cons 0)
                   (sort)))

;; Part 1
(defn part1 []
  (let [freqs (->> adapters
                   (partition 2 1)
                   (map (fn [[x y]] (- y x)))
                   (frequencies))]
    (* (get freqs 1) (get freqs 3))))

;; Part 2
(defn part2 []
  (let [graph (->> adapters
                   (partition-all 4 1)
                   (map (fn [[x & xs]] [x (vec (remove #(< 3 (- % x)) xs))]))
                   (into {}))
        vs (reverse adapters)
        goal (first vs)]
    (loop [[v & vs] (rest vs)
           v->count {goal 1}]
      (let [n (apply + (map v->count (get graph v)))]
        (if (seq vs)
          (recur vs (assoc v->count v n))
          n)))))
(time (part2)) "Elapsed time: 0.496946 msecs" For part 2, I made the numbers into a DAG (where the neighbours of a number are the numbers with a diff of 3 or smaller). Did a little bit of googling for efficient graph algorithms and found out that a property of a topologically sorted graph (which is what you get when you sort the input numbers) is that you can find the number of paths really efficiently using dynamic programming. Basically I keep a map (`v->count`) of the number of paths from which you can reach the goal from the given vertex. The number of paths to reach the goal from the goal is 1. Then I go to the next vertex in the topological sorting and look at its neighbours (only the goal in this case), and store the number of paths in the map. I then keep doing this until I reach the start. Since we're going backwards, the map will already contain the number of paths for all the neighbours we're checking, and the last neighbour sum (the neighbours of the start vertex) is the answer!

鉂わ笍 3
馃憤 3
bellissimo 3
Stuart02:12:59

day 10 part 2, dirty solution

(as-> (slurp "puzzle-inputs/2020/day10") o
        (str/split-lines o)
        (map #(Integer/parseInt %) o)
        (sort o)
        (concat [0] o)
        (map - (rest o) o)
        (partition-by identity o)
        (filter #(some #{1} %) o)
        (map #(case (count %) 1 1 2 2 3 4 4 7) o)
        (reduce * 1 o))

markw04:12:10

Late to the party - didn鈥檛 find the math trick, went with memoization:

(defn adapter-fits? [current-adapter other-adapter]
  (< current-adapter other-adapter (+ 4 current-adapter)))

(defn possible-arrangements [root adapters]
  (if-let [choices (seq (filter #(adapter-fits? root %) adapters))]
    (reduce + (map #(possible-arrangements % adapters) choices))
    1))

(def possible-arrangements (memoize possible-arrangements))

andrea.crotti20:12:29

what's the best way to do a cartesian product but without the order?

markw20:12:21

what do you mean by without the order?

misha20:12:40

(for [x (range 3) y (range 3)] [x y])
=> ([0 0] [0 1] [0 2] [1 0] [1 1] [1 2] [2 0] [2 1] [2 2])

andrea.crotti21:12:42

yeah I mean having [0 1] but not [1 0] for example

andrea.crotti21:12:07

so imagining a square, taking the diagonal and the lower or upper half

tws21:12:08

combination instead of permutation?

imre21:12:19

ha. Is this for day 1?

imre21:12:18

Cause that did bug me with day 1 where you kinda need elements taken for the combinations of indices. Not being able to find an existing implementation, I wrote a transducer for it but its performance is shite when compared to the for-based approach: https://github.com/imrekoszo/advent-2020/blob/master/src/imrekoszo/advent2020/day1_alternatives.clj#L102

Lars Nilsson21:12:01

I used (for [i (range size) j (range i size)] ...) to get a triangle of indices (where size if the count of the collection)

markw21:12:06

@andrea.crotti There is more than one way to do it, but as mentioned above that鈥檚 combinations vs permutations. Another way is in the for macro to make sure that one index is > than another, e.g. 1(for [i xs j xs :when (> j i))1

markw21:12:04

basically you want your inner loop to always start at 1 + the outer loop var

raicotop21:12:28

as @markw mentions:

(for [x (range 5)
      y (range 5)
      :when (< x y)]
  [x y])
;; => ([0 1] [0 2] [0 3] [0 4] [1 2] [1 3] [1 4] [2 3] [2 4] [3 4])

markw21:12:47

Yep - I think @plexus mentioned this in the most recent video

raicotop21:12:52

That's where I saw it too I guess. Came in handy for day 9.

misha21:12:18

lacks diagonal: [0 0] 鈥 [4 4]

markw21:12:50

if you need diagonals you can just add a condition to the :when

markw21:12:23

:when (or ( = x y) (< x y))

Lars Nilsson21:12:28

Or change < to <=, I would imagine...

Lars Nilsson21:12:26

Using the when clause will make the for comprehension iterate over all 5*5 indices though (perhaps a small cost compared to the work overall...)

markw21:12:08

if you want efficient generation i would use combinatorics and tack on the diagonals explicitly

Lars Nilsson21:12:09

It just won't generate an entry for the failing conditions.

Lars Nilsson21:12:50

As I mentioned above, I did it using the two argument version of range to get the triangular shape of indices.

馃憤 3
markw21:12:57

Missed the fact that you started the second loop at i rather than i+1 which would have made it effectively the same as combinations

Lars Nilsson21:12:29

In my actual for sequence I do have :let and :when for other purposes, just not the range/index checking.

Lars Nilsson21:12:42

I feel somewhat stupid about my day 1, part 2 implementation where I just added another index instead of doing something else.

misha21:12:14

(time (do (doall (for [x (range 1000) y (range 1000) :when (<= x y)] [x y])) nil))
"Elapsed time: 40.609524 msecs"
=> nil
(time (do (doall (for [x (range 1000) y (range x 1000)] [x y])) nil))
"Elapsed time: 27.957203 msecs"

markw21:12:20

oh yeah i brute forced that one O^N(3)

markw21:12:30

i鈥檓 not going to be clever on day 1 馃槢

misha21:12:55

Depends on what your goals are for this puzzle thing. And there are a bunch of conflicting ones there.

Lars Nilsson21:12:01

(time (do (doall (for [x (range 1000) y (range 1000) :when (<= x y)] [x y])) nil))
"Elapsed time: 65.1356 msecs"
(time (do (doall (for [x (range 1000) y (range x 1000)] [x y])) nil))
"Elapsed time: 53.8159 msecs"

Lars Nilsson21:12:33

Never mind my duplicate experiment. I misread yours completely and thought it did not include the x offset for y... Time to fetch my glasses.

andrea.crotti21:12:27

I'm using loom for problem 7 https://github.com/aysylu/loom and it worked out nicely for the first part of the problem

andrea.crotti21:12:56

I also added the number of bags contained as the weight of each edge, so I thought it would be easy to do part b of the exercise

andrea.crotti21:12:15

but I can't find anything useful to do that

misha21:12:37

> it worked out nicely for the first part of the problem famous last words鈩

Lars Nilsson21:12:16

Thanks for the heads-up on loom.. I might need to look at that for some non-aoc stuff.

andrea.crotti21:12:17

in theory I just want to be able to sum all the paths that I generate with a DFS search for example (multiplying the weights)

misha21:12:17

someone shared loom solution here

andrea.crotti21:12:03

it's pretty much just

(->> "shiny gold"
       (la/bf-traverse (get-graph))
       count
       ;; removing the node itself
       dec)
once you have the graph

andrea.crotti21:12:14

but yeah getting the actual weights to do something seems to be another matter

misha21:12:16

> Aysylu Greenberg - Loom and Graphs in Clojure

andrea.crotti21:12:17

yeah I think I saw that some time ago, but well I kind of know how I could do it I guess. I need to find in the whole dfs which are the terminal nodes, for them generate all the paths, then get the weights, multiply them and sum it all together

andrea.crotti21:12:32

would be nice if there was an easier way though

misha21:12:17

sounds like one ugly loop would do just fine here kappa

andrea.crotti21:12:26

hehe yeah that would work I guess

andrea.crotti21:12:34

was trying to avoid that since that's all I'm doing apparently

misha21:12:02

yeah, story of my aoc life for 5 years

Lars Nilsson21:12:08

Day 7 was some ugly for comprehension over recursive calls for me.

misha21:12:22

but yeah, downloading a bunch of ugly loop s from clojars might seem more idiomatic :)

andrea.crotti22:12:44

mm dammit I think I'm close

(defn n-bags-inside [gr starting]
  (let [edges (lg/out-edges gr starting)]
    (if (empty? edges)
      1
      (apply +
             (for [e edges]
               (* (lg/weight gr e)
                  (n-bags-inside gr (second e))))))))
at least it works for this simple graph
;; desired = 16
(def sample-g
  (lg/weighted-digraph
   [:a :b 2]
   [:a :d 10]
   [:b :c 3]))

andrea.crotti22:12:30

but aoc doesn't agree with me

andrea.crotti22:12:59

mm weird my result is exactly (actual-result / 2 + 1) using the example from the instructions

andrea.crotti22:12:21

but of course if I (dec (* 2 current)) it still doesn't work 馃槃

andrea.crotti22:12:29

so probably just a coincidence

andrea.crotti22:12:18

I think the problem is maybe the graph generated because the algorithm I think it's correct, bah I'll see tomorrow

andrea.crotti22:12:50

that's quite neat thanks

markw22:12:04

I have been revisiting some prior years problems I gave up on鈥 https://adventofcode.com/2018/day/20 is really stumping me. Is it possible to parse something like ENWWW(NEEE|SSE(EE|N)) using recursive descent into the following paths? Basically each | is an optional fork in the path, which starts from the point in each prior group formed by (. The instructions give some more detail, but the above should yield these three paths: 鈥 ENWWWNEEE 鈥 ENWWWSSEEE 鈥 ENWWWSSEN I feel like this should be simple yet I鈥檝e been stuck on it for an embarrassingly long amount of time. I recently abandoned the recursive approach dealing with each symbol in-turn for a token-by-token approach, which is getting be closer but bleh.

Lars Nilsson22:12:15

Cheating to use instaparse?

markw23:12:51

that鈥檚 next, first i want to understand how to do it though

st3fan23:12:07

Did a bunch of reading on graphs and depth first search and I think I finally have all the pieces I need to solve day 7

st3fan23:12:26

Totally out of my comfort zone, but it is a good learning exercise

鉂わ笍 6
馃憤 6
st3fan23:12:48

Got some code snippets in a file that need to work together and then 鈥

oxalorg (Mitesh)13:12:19

Awesome solution by @pez in case people missed this thread!

鉂わ笍 3