This page is not created by, affiliated with, or supported by Slack Technologies, Inc.
2020-12-09
Channels
- # adventofcode (197)
- # announcements (25)
- # aws (1)
- # babashka (21)
- # beginners (138)
- # calva (21)
- # cider (5)
- # clara (1)
- # clj-kondo (35)
- # clojure (97)
- # clojure-australia (4)
- # clojure-dev (37)
- # clojure-europe (100)
- # clojure-nl (2)
- # clojure-spec (7)
- # clojure-uk (36)
- # clojurescript (11)
- # conjure (15)
- # cursive (20)
- # datomic (12)
- # emacs (10)
- # events (2)
- # fulcro (83)
- # graalvm (14)
- # jobs (1)
- # jobs-discuss (27)
- # kaocha (75)
- # lambdaisland (21)
- # off-topic (27)
- # pedestal (5)
- # reitit (2)
- # reveal (20)
- # rewrite-clj (24)
- # sql (9)
- # tools-deps (37)
- # xtdb (93)
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
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
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.
https://github.com/transducer/adventofcode/blob/master/src/adventofcode/2020/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
@U4T7GE7PE 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.
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.
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 🙂
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
@U076FM90B, 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
@U1Z392WMQ 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
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 🙂
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.
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}
ah nice
perhaps nice addition to medley: https://github.com/weavejester/medley/blob/master/src/medley/core.cljc
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"
Feedback welcome.@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
on the shiny bag day
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.
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
@plexus you may like that one
maybe more logical to return a vec of subvecs?
I will also make a variation partition-indexes
which returns the indexes of the possible sub-vectors.
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)
My solutions for today https://github.com/green-coder/advent-of-code-2020/blob/master/src/aoc/day_10.clj
And mine, definitely wanna clean up it https://github.com/zelark/AoC-2020/blob/master/src/zelark/aoc_2020/day_10.clj
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
Refactored version https://github.com/zelark/AoC-2020/blob/master/src/zelark/aoc_2020/day_10.clj
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 *))
{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))))
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
@U013MQC5YKD 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, @U013MQC5YKD. 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.
@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!
@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
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 🙂
@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’s some logic to the type of cutting and the factor of paths you missDon'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? @U051HUZLD, 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)
And those strings of 1s looked like bridges to me.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 😮
@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
A solution to Day 10. https://github.com/benfle/advent-of-code-2020/blob/main/day10.clj
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
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 @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 “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
@U06B54Y95 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
(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!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))
what's the best way to do a cartesian product but 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])
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
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
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])
Or change <
to <=
, I would imagine...
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"
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.
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
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)
it's pretty much just
(->> "shiny gold"
(la/bf-traverse (get-graph))
count
;; removing the node itself
dec)
once you have the graphbut 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
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
hehe yeah that would work I guess
was trying to avoid that since that's all I'm doing apparently
Day 7 was some ugly for comprehension over recursive calls for me.
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]))
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
that's quite neat thanks
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.
Cheating to use instaparse?
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
Awesome solution by @pez in case people missed this thread!