Clojurians Log v2

https://github.com/transducer/adventofcode/blob/master/src/adventofcode/2020/day9.clj

https://github.com/RedPenguin101/aoc2020/blob/main/day9.clj

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

https://github.com/genmeblog/advent-of-code-2020/blob/master/src/advent_of_code_2020/day09.clj

Nothing very exciting today either ... https://github.com/benfle/advent-of-code-2020/blob/main/day9.clj

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

https://github.com/st3fan/aoc/blob/master/2020/advent-of-code/src/advent_of_code/day9.clj

Yup brute force

Oh! recur without a loop is allowed?

@st3fan Yes it works with functions as well.

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

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

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.

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.

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

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.

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

meh: https://github.com/tschady/advent-of-code/blob/master/src/aoc/2020/d09.clj

Yes, that's what I meant.

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

yes, i know i’m resumming too much, that’s for a phantom refactor that may never happen 🙂

https://github.com/bradlucas/advent-of-code-2020/blob/master/src/advent/day09.clj

Here I am https://github.com/zelark/AoC-2020/blob/master/src/zelark/aoc_2020/day_09.clj

https://github.com/djblue/advent-of-code/blob/master/src/advent_of_code/core_2020.clj#L318

not my best work but gets the job done https://github.com/listba/advent-of-code-2020/blob/master/clojure/src/aoc_2020/days/09.clj

@nbardiuk, you solution is awesome! But I noticed that has-sum should be called has-not-sum 🙂

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

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

@vincent.cantin refactored to be a rolling sum: https://github.com/tschady/advent-of-code/blob/master/src/aoc/2020/d09.clj

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.

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

@tws This is my new optimized version, super fast. https://github.com/green-coder/advent-of-code-2020/blob/master/src/aoc/day_9.clj#L52-L65

For the record: https://github.com/pwojnowski/advent-of-code/blob/master/src/aoc/aoc2020.clj#L258

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

https://github.com/nbardiuk/adventofcode/blob/923232e713a34bdcbbbab7d35ee2f933209bf284/2020/src/day10.clj

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 “bridge”. Does that make sense to you people?

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

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

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’s a gap of 2 in between you don’t 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.

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

@mitesh a you can also brute force using memoize?

Cutting of parts you already did?

Part of it can be seen as a math problem, it seems, @mitesh. Here’s a “solution”:

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

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 “magic” function that tells me how many combinations each string contributes with. Then multiplying all those.

I have yet to figure out the “magic” function, but don’t expect a blocker there.

@erwinrooijakkers 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!

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

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

I will have to check that out too! 😃

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

like the opposite of memoization

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 🙂

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

(* (count-paths [1 4 5 6 7])
   (count-paths [10 11 12 15 16 19]))
;; => 8

(* (count-paths [1 4 5 6 7 10])
   (count-paths [11 12 15 16 19]))
;; => 4

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)

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

So the “magic” function/map in my step 2 “solution” 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 *))

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? @misha, maybe?

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.

You definitely did it the math way 😄

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)

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

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

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.

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

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

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

A solution to Day 10. https://github.com/benfle/advent-of-code-2020/blob/main/day10.clj

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

Brilliantly!

@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

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

so test input gets split like this: https://gist.github.com/akovantsev/782045b0f49a5d3875c0c42c11776ed4

It’s wonderful!

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

Finally! 2-3ms for part 2 with input sorted in descending order. https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2020/day10.clj#L17-L31

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’t getting any benefit from it. Looking at @vincent.cantin’s 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

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

I found an interesting pattern for part 2. I haven’t 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 @hobosarefriends 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 “Elapsed 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

@mchampine i wrote a fn to calculate those magic 7, 4, 2 https://github.com/tschady/advent-of-code/blob/master/src/aoc/2020/d10.clj#L23-L29

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.

I’m not going to say how long part 2 took me. And it’s not like it’s the prettiest of solutions…would be really short if I’d 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

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

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

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

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

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

Late to the party - didn’t 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))