This page is not created by, affiliated with, or supported by Slack Technologies, Inc.
2020-12-10
Channels
- # adventofcode (174)
- # announcements (5)
- # aws (9)
- # babashka (17)
- # beginners (259)
- # boot-dev (1)
- # calva (6)
- # cider (19)
- # circleci (7)
- # clj-kondo (9)
- # cljfx (51)
- # cljs-dev (4)
- # clojure (83)
- # clojure-australia (2)
- # clojure-dev (9)
- # clojure-europe (78)
- # clojure-nl (3)
- # clojure-spec (4)
- # clojure-switzerland (1)
- # clojure-uk (18)
- # clojurescript (22)
- # conjure (17)
- # cursive (17)
- # data-science (1)
- # datomic (15)
- # defnpodcast (1)
- # events (2)
- # fulcro (39)
- # graalvm (16)
- # graphql (1)
- # kaocha (5)
- # lambdaisland (11)
- # malli (6)
- # meander (1)
- # off-topic (26)
- # pathom (10)
- # re-frame (10)
- # reitit (6)
- # rewrite-clj (7)
- # sci (3)
- # shadow-cljs (28)
- # sql (12)
- # test-check (10)
- # tools-deps (31)
I am sure people will start to be VERY DYNAMIC very soon. … or never (<- hidden joke there)
I had to google "dynamic programming", seems this is basically just divide and conquer algorithms? it's not confusing at all that this has nothing to do with dynamic programming languages or dynamic bindings
It is a "divide and reuse" way of doing. I guess the "dynamic" part is the non-constant cost of calculating things when memoized.
Crap... almost 2 1/2 hours and I can't get a solution for part 2 that takes less than forever...
Spent about an hour on this one, and same deal. The second demo input takes ~25ms for part2, but no end in sight with the real input. Might have to crack out visualvm and do some profiling.
Don’t forget your old friend memoize
. That takes the naive approach straight to O(n).
I don't see how my solution benefits from memoize, it's not doing anything multiple times
It's that time of the year where I'm starting to wonder why I'm wasting my time on this...
Oh wow didn't know you could check the stats! Thanks, it took me 26 minutes 🙈
btw during reclojure I saw someone fire up a nice graph genreated from the profiler output
anyone knows how it can be done? I used to love to generate these graphs with Python and https://github.com/gak/pycallgraph
something like https://github.com/jstepien/flames maybe but I think it was a different one
@andrea.crotti probably this one: https://github.com/clojure-goes-fast/clj-async-profiler
The best solution I’ve seen today. Only one thing I could add to it is simplifying of the part 1 by reverting map’s arguments. [Spoiler inside]
I'm having trouble wrapping my head around this solution for part 2. Anyone care to explain the logic behind it?
@UE8PRHLTY The key here is a reverse order of adapters.
We start with a map with just the end adapter, which means there is only one way to reach the end. Then, on each iteration we count ways for the next adapter based on cnts map and previous calculations. And so on, until we reach opposite end of reverse sequence of adapters. At the end, we get a result hold under 0
key.
Actually, the idea is pretty simple and elegant.
p2:
"Elapsed time: 0.39624 msecs"
=> 19208 (test input)
"Elapsed time: 9.720333 msecs"
=> 96717311574016
Was trying to come up with some clever solution, but in the end gave up and memoized results.
Side-effect of my accomplishment is code that hurts my eyes.
Is that why I'm looking at completing a backlog of AoC years?
Forgot about aoc this year. Just remembered yesterday. Finally caught up !
I found an odd… pattern? in the results of day 10 part 2 . The results will only have prime factors of 2 and 7… I’ve been trying to figure out why.. and if I could leverage that into a different solution.
Check out https://www.reddit.com/r/adventofcode/comments/ka9pc3/2020_day_10_part_2_suspicious_factorisation/ post in reddit, unless you don't want any spilers
@UGFL22X0Q it’s because a run of 4 ones has 7 combos, a run of 3 ones has 4 combos, and a run of 2 ones has 2 combos.
Yep, it depends upon the length of runs, but I think is not that simple to get the exponents anyway
Kind of, I guess. But in this case there is an O(n) solution, so clearly not the general one
My thinking is, but I'm having trouble implementing it.. Spoiliers ahead if this works* Find partitions where smallest number in partition is within 3 of biggest. either the partition will have 4 numbers in it, or the partition will have 3 numbers in it (or less) Partitions with 4 will have 4 combos. Partitions with 3 will have 2 combos. Multiply all theses partitions combo counts together. It works for the smaller test but not the bigger one. Or my code is guff. 😕 Am I on the right track or should I give up with this line of thinking?
I dunno how to explain it, because I don’t really understand it, but I did make it work by checking the number of consecutive 1 jumps and mapping:
{:dual-consecutive-1s 2
:trip-consecutive-1s 4
:quad-consecutive-1s 7}
and so in the beginning if you omit the 0 to 1 jump you’re missing a consecutive 1 from the beginning. I suppose the 3 jump at the end can be ignored
spoiler, but my solution goes along these lines: https://github.com/tschady/advent-of-code/blob/master/src/aoc/2020/d10.clj
relevant bit:
(defn permuted-partition-count
"Returns the number of different ways a sequence can be carved up
into segments of length 1,2, or 3"
[xs]
(->> (combo/partitions xs :min 1 :max 3)
(map (comp count combo/permutations))
(reduce +)))
Ah, I discovered the powers of 7, 4 and 2 pattern independently and used it for my part 2: 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
here is my (probably not too Clojurey) version, but hopefully with clear enough comments to explain the logic. https://github.com/jeff303/advent-of-code-2020/blob/master/src/advent_of_code/day10.clj#L41-L73
jeez it's getting hard even to understand the assignment
depends what you mean by easily
if you have never done clojure it might take a while but the algoriths to use are quite simple
There is a couple guys who recorded videos. You can learn from them a lot.
yeah but you should try by yourself first maybe
I like his man : https://www.reddit.com/r/Clojure/comments/k9cg8l/a_teacher_looks_at_advent_of_code_2020_days_07/
A lot of the very early problems rely on using things like regular expressions, generating sequences using for and range, map and filter or sequences. Having a handle on things like that will take you past several problems.
(slurp filename), or (line-seq (reader filename)) is fairly suitable. The first gets the whole content into a string, the second generates a sequence of lines (using reader from the http://clojure.java.io namespace).
(map #(Long/parseLong %) (line-seq (reader filename)))
would be a common way of getting a sequence of integers out of lines of integers in a file.
> I see , I think first learn more and get more familiar with clojure Doing AoC was for me, a good way to learn a language (in my case was Prolog)
part 2… it’s definitely not easy, I’d guess because the puzzle doesn’t hint at the solution so directly?
I saw part 2 and was like.. oh that’s easy, i’ll just generate permutations for everything +3 from current, drop the count of that from the remaining sequence, and concat all the results to what i’ve found so far and recurse
then I thought.. oh that’s easy, I’ll just do a depth first search and track the paths.
I also tried working out all the paths, and went to buy bread (I do these in the morning). When I got back, it (obviously) had not finished, and just then I came up with the good one 🙂
I guess my first indication should have been when using the second test input took like 5 seconds to count the valid paths
My clue was the word "trillions".
hmm actually, if you assume an upper bound for the branching factor of 3 (can be 1, 2, or 3 higher), then wouldn’t the possible paths be count of input ^ 3?
Wouldn't it be 3^input?
3^100 is a big number..
even being generous and assuming a branching factor of 2, that’s 2.1 billion paths for the second test input
Is there any goo way to work a clojure file without creating a whole project? This year I'm doing days in different languages. And I don't want to create a whole project for single days
also, as far as I know, you can just create a .clj
file, im not aware of any need to create a whole project for it
Yup you can. But working with it gets kind of awkward. For example, I work with emacs-cider, and refuses to cider-jack-in
(run the repl) correctly
ah yeah, in that case try with a deps.edn
file, i have a project with that and cider-jack-in
seems to work fine
Anything special in deps.edn
? Mine still fails
touch hw.clj
echo "(println \"Hello world\")" > hw.clj
clj hw.clj
WARNING: When invoking clojure.main, use -M
Hello world
I think you might just need {:deps}
? heres the documentation https://clojure.org/guides/deps_and_cli
at least you have to have {:paths [“src”]}, that’s enough to start
I (like a lot of people, I imagine) have a project for all the days, and one file per day with a different namespace ( (ns aoc2020.day01)
for example)
I must be missing something obvious but why are the intervals between any 2 adapters today either 1 or 3. Why not 2?
That’s just the way the Institute of Elvish Electrical Engineers spec’d them, I guess.
Not sure, but I “misunderstood” the description such that this was the case and based my solution on it. 😃
yeah, i just realised i think my solution totally breaks if any 2 adapters were seperated by 2 (and not 1 or 3)
Mine certainly will produce the wrong answer then. But I think it is quite small adaption needed,
How do they fail? Are working with prime factorization? Or am I missing something?
I look for partitions that are like [4 5 6 7], and then find the ways through those partitions find the product of those, plus the count of the partitions that dont result in a branching.
so if in the 1st test input if the adapters were 1 4 5 6 8 10, my code would split it into [4 5 6] and I'd lose a branching multiplier
what woul return to [1 3 5]?
The input being [1 4 5 6 8 10]? Because we were supposed to add 0 ourselves right?
Mhh, yes I think I understand what the problem is
yeah right
Mine I think it works with differences of two
But I'm not so sure anymore haha
My solution does not split or anything like that. Instead it finds sprees of distances 1, calculates (inc (combinations n 2))
on the length of these sprees and then multiplies them. This only works if there are no distances 2. But I think that I could adapt it for those as well.
Could you elaborate? I thought there was no close formula (even under the assumption that the there are no differences of 2)
I used this: https://www.calculatorsoup.com/calculators/discretemathematics/combinations.php
Translated that into:
(def !
(memoize (fn [n]
(reduce *' (range 1 (inc n))))))
(def combinations
(memoize (fn [n r]
(if (= 1 n)
0
(let [n! (! n)
r! (! r)
r-n! (! (- n r))]
(/ n! (* r! r-n!)))))))
Thanks, I'll have a look at it. Though combinations of two can be calculated with n(n-1)/2, since r is constant in your application you don't need that complicated algorithm
Oh, I struggled hard to see that connection. Very nice! I’ll throw criterium on this simpler one and see it gains me execution time as well.
I really don't understand why your solution works 😂 But nicely done. Can you prove that it does what it should?
Ore give me an insight?
So, about the same performance, but I take the simplification! 😃
Evaluation count : 4242 in 6 samples of 707 calls.
Execution time mean : 145,779817 µs
Execution time std-deviation : 4,846516 µs
Execution time lower quantile : 141,316390 µs ( 2,5%)
Execution time upper quantile : 152,683197 µs (97,5%)
Overhead used : 6,391737 ns
If you check, the lengths of runs of 1
s are alel numbers between 1 and 20 (at least in my input) so yeah, not gonna change performance.
And I think I'm understanding why it works now Thanks!
Let’s look at my part 1 solution:
(->> input
(parse)
(sort)
(cons 0)
(#(concat % [(+ 3 (last %))]))
(partition 2 1)
(map (fn [[a b]] (- b a)))
(frequencies)
(vals)
(apply *))
For the larger input example, after the (map (fn [[a b]] (- b a)))
step I have:
(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)
So, to me those strings of 1
s looked like “bidges”. For the shorter sprees it was easy to reason “I can remove none of them, this one, this one, those two…” and so on. There was a pattern to it and my daughter helped me see what the pattern was about. Then I googled it a bit and it seemed like the 2-combinations + 1 was the answer. I tried it and, boom.Pasting my part 2 here as well, for comleteness:
(->> input
parse
(sort)
(cons 0)
(#(concat % [(+ 3 (last %))]))
(partition 2 1)
(map (fn [[a b]] (- b a)))
(partition-by identity)
(keep #(seq (filter #{1} %)))
(map count)
(map #(inc (combinations % 2)))
(apply *)))
I think your solution does not always work. Even if there are no differences of two: Try it on [1,2,3,4,5,8,9] for example. I think you are going to get 11
. Where the real aswwer should be 13
Not that if you get to 4 or 5, you only have one way to proceed. Since 4 must go to 5. And 5 must go to 8 which must go to 9. So we can count 4 and 5 as leaves. And you get a tree with 13 leaves:
I thought so. But, my input has runs of 7 and it works on my input. So I'm not completely aware of whats going on
This that the last 1 near a 3 couldn’t be removed was a thing that I and my daughter saw when we were looking at it. We didn’t draw a tree of it (thankfully, maybe) but we reasoned our way towards that, like you did there before you drew the tree.
just {1,2,4,7}
No no, I lied sorry
It does have runs of at most 4, there it is. I was looking at the wrong output
haha. yes with runs of <= 4 it works as you found the formula so it fitted that pattern
So then there might be a formula that works past 4, I guess. I just fitted 2-combinations + 1
onto the table we plotted, my daughter and I.
Don’t know if you saw this https://clojurians.slack.com/archives/C0GLTDB2T/p1607593968030300?thread_ts=1607538538.458400&cid=C0GLTDB2T 😃
Yup. That would be my guess too. About another formula I'm not too sure. That's why was suspicious in the first place. A lot of this combinatorial problems have no, or very hard to find closed formula
hahaha, yup.
You can still try to find one! I don't know if definitively does not exist. But yeah, probably not gonna be easy.
On reddit I saw solutions using "Tribonacci" numbers. Which are a generalization of fibonacci numbers. And fibonacci numbers have closed formulas (although using irrationals). So there might be one, but again, probably involving irrationals
Interesting. My daughter and I was “seeing” fibbonacci sequences a while, but then when we blinked they were gone. 😃
I have this feeling that some day soon the AoC challenge will involve runs > 4 and that I was supposed to walk into that trap.
Yup, that must be it
(defn tribonacci [a b c]
(lazy-seq (cons a (tribonacci b c (+' a b c)))))
According to stackoverflow.That would make a solution I am still unable to prove to be:
(defn tribonacci [a b c]
(lazy-seq (cons a (tribonacci b c (+' a b c)))))
(def run-lenght->paths
(memoize (fn [n]
(nth (tribonacci 1 2 4) (dec n)))))
(quick-bench
(->> parsed-input
(sort)
(cons 0)
(#(concat % [(+ 3 (last %))]))
(partition 2 1)
(map (fn [[a b]] (- b a)))
(partition-by identity)
(keep #(seq (filter #{1} %)))
(map count)
(map run-lenght->paths)
(apply *)) ; => 24179327893504
)
; Evaluation count : 3990 in 6 samples of 665 calls.
; Execution time mean : 150,040247 µs
; Execution time std-deviation : 5,732067 µs
; Execution time lower quantile : 143,768069 µs ( 2,5%)
; Execution time upper quantile : 157,965810 µs (97,5%)
; Overhead used : 6,391737 ns
Gonna take a closer look to it, but probably tomorrow
Nice pictures
I read on the subreddit that it’s indeed a tribonacci sequence, but not sure what that means for the solution
It is not hard actually. So suppose values for t(1),t(2), and t(3) are correct. And you wanna know how many ways are there to get to the fourth place in a run of ones, then since the fourth must be preceded by one of the previous three, there must be t(1) + t(2) + t(3) options. And so on an so on
I think that what it means for the solution is about what I have there. Of course, it's solving the special case where there are no gaps off 2 in the input.
Part 2 feels like it requires some knowledge of mathematics which I do not have. Presumably some aspect of combinatorics.
@rob156 It might seem like that. And it helped me gather my shiny gold stars thinking it did. But I’ve just learnt (the thread above your post) that I had the math wrong. Haha.
is there a typo on day 10, part 2, the longer sample input? here: https://adventofcode.com/2020/day/10
“In this larger example, in a chain that uses all of the adapters, there are `22` differences of 1 jolt and `10` differences of 3 jolts.”
I think there are actually 9
differences of 3 jolts. I counted by hand (and also my code came up with that, which of course may not be bug free)
Maybe you are not counting the max element + 3 you must add