Clojurians Log v2

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

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

Day 9 Answers Thread - Post your answers here

Just solved today’s puzzle, but it’s a bit dirty, so I’m going to refactor it before publishing ^_^

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

Mine’s 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

bruted it with code I’m not too proud of 🤕

I’m officially a day behind now and late to the party https://gist.github.com/KennyMonster/9b9db6daa056e41413112d0fb31a5e47

feels like part 2 could be way nice even brute forcing it… but I dunno how

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

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

I think you can get some reuse by keeping the program state up until the point where you hit the changed instruction, and reusing that. Still, not sure if it would really be worth it.

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 🙂

https://github.com/lambdaisland/aoc_2020/blob/main/src/lambdaisland/aoc_2020/puzzle09.clj

My solution, after a lot of clean up. https://github.com/green-coder/advent-of-code-2020/blob/master/src/aoc/day_9.clj#L19-L48 I made a first-for macro.

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.

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

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

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}

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.

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"

@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

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

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

Nice one, that 🙂

on the shiny bag day

I don't think I got that far just yet

I'm 3 days behind rn

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.

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

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

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

@plexus you may like that one

oh yeah that's nice

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

ah nice

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

perhaps nice addition to medley: https://github.com/weavejester/medley/blob/master/src/medley/core.cljc

maybe more logical to return a vec of subvecs?

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

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

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

Gold fever is bad for your soul. 😃

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

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)

that is what Andrea suggested in other thread and I think it would definitely help in "feel good by not brute forcing it 100%" and I like the idea 😄

but I was thinking more in the vein that because the every jump is not conditional you could use that as an advantage

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.

hehe well the problem is that that there is a new problem every day

can't really spend too much time on smart solutions if I want to keep up to date 😄

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

Day 10 Answers Thread - Post your answers here

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

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

what do you mean by without the order?

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

or https://github.com/clojure/math.combinatorics/blob/master/src/main/clojure/clojure/math/combinatorics.cljc#L232-L249

VS Code + Calva Paredit.

Unfortunately I haven’t had the focused time I need to make Paredit multi cursor. I miss it every day.

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

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

combination instead of permutation?

ha. Is this for day 1?

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

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

@andrea.crotti There is more than one way to do it, but as mentioned above that’s 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

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

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

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

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

lacks diagonal: [0 0] – [4 4]

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

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

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

oh yeah

<=? :kappa:

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

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

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

cool nice

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

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

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

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

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

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

i’m not going to be clever on day 1 😛

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

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

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.

A reason part 2 took me so long is that I was looking at it as a tree problem. So I was able to build a structure something like so (simplyfied):

[[nop jmp]
 [acc]
 [acc]
 [jmp nop]
 [acc]]

[[nop acc acc jmp acc]
 [jmp acc acc jmp acc]
 [nop acc acc nop acc]
 [jmp acc acc nop acc]]

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

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

but I can't find anything useful to do that

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

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

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)

someone shared loom solution here

it's pretty much just

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

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

there is a loom conj presentation https://www.youtube.com/watch?v=wEEutxTYQQU

> Aysylu Greenberg - Loom and Graphs in Clojure

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

would be nice if there was an easier way though

sounds like one ugly loop would do just fine here :kappa:

hehe yeah that would work I guess

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

yeah, story of my aoc life for 5 years

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

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

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

;; desired = 16
(def sample-g
  (lg/weighted-digraph
   [:a :b 2]
   [:a :d 10]
   [:b :c 3]))

but aoc doesn't agree with me

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

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

so probably just a coincidence

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

@andrea.crotti tws used https://github.com/tschady/advent-of-code/blob/master/src/aoc/2020/d07.clj if you want to peek. Mine is in the related https://github.com/RedPenguin101/aoc2020/blob/main/day7.clj

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

that's quite neat thanks

Cheating to use instaparse?

that’s next, first i want to understand how to do it though

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

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

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