Clojurians Log v2

Totally over-thinking this one

Kinda quiet in here tonight? 😉

Good morning

I am sure people will start to be VERY DYNAMIC very soon. … or never (<- hidden joke there)

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

Crap... almost 2 1/2 hours and I can't get a solution for part 2 that takes less than forever...

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

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.

It's that time of the year where I'm starting to wonder why I'm wasting my time on this...

man, top solver had solution for part 2 solved in 2:19

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

Oh wow didn't know you could check the stats! Thanks, it took me 26 minutes 🙈

@andrea.crotti probably this one: https://github.com/clojure-goes-fast/clj-async-profiler

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

well, not 100% true, but still 🙂

alright, got a solution now

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]

(->> (frequencies (map - (rest adapters) adapters)) vals (apply *))

p2:
"Elapsed time: 0.39624 msecs"
=> 19208 (test input)
 
"Elapsed time: 9.720333 msecs"
=> 96717311574016

https://twitter.com/alekszelark/status/1337047003541463040

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.

Forgot about aoc this year. Just remembered yesterday. Finally caught up !

Shiny gold stars does that to ya! 😃

Is that why I'm looking at completing a backlog of AoC years?

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.

jeez it's getting hard even to understand the assignment

I have to fire up all the neurons even to understand the instructions

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

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

my input didn’t have more than run of 4

Yep, it depends upon the length of runs, but I think is not that simple to get the exponents anyway

my solution (almost there) may show that. it’s a variant of a change-making problem

Kind of, I guess. But in this case there is an O(n) solution, so clearly not the general one

I can’t say I understand it yet, but thanks a lot for the info guys

Just learning clojure and I wonder if the first 3 days can easiliy be done in clojure

an interesting stats today

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.

https://youtu.be/9ITiZ88sljA

yeah but you should try by yourself first maybe

and https://youtu.be/Vp8RbO7l6eg

part 2… it’s definitely not easy, I’d guess because the puzzle doesn’t hint at the solution so directly?

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 like his man : https://www.reddit.com/r/Clojure/comments/k9cg8l/a_teacher_looks_at_advent_of_code_2020_days_07/

make sure you have the beginning and ending pieces there

you mean the starting (0) and ending + 3, does this makes a difference?

damn, thought i could ignore that

it does for this because you’re adding a 1 and 3 to the total

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.

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

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

yes, you are correct. The 0 at the start definitely makes a difference!

Yeah that didn’t work

then I thought.. oh that’s easy, I’ll just do a depth first search and track the paths.

That also didn’t work… I think you can see where this is going

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

well it’s only trillions if you generate all permutations up front I think

or that’s how i interpreted it late last night

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?

oops I hate regexes

range, map and filyer I already learned

but now how to read from a file

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

I see , I think first learn more and get more familiar with clojure

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

Wouldn't it be 3^input?

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

oops sorry yes that’s what i meant

3^100 is a big number..

so basically a very big number

yeah you know it’s a problem when there is an ‘e’ in the google rsults

even being generous and assuming a branching factor of 2, that’s 2.1 billion paths for the second test input

so much for search

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

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

You could use a deps.edn file

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

I am still learning though so take that with a grain of salt!

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

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

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

an example: https://github.com/zelark/AoC-2020/blob/master/deps.edn

Thanks, Is now working

thanks both

glad its not just me!

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

1

[0 1 4 5 6 8 10] ;=> 2, where it should be 3

I got lucky my assumption held in the actual real data to pass 😄

The input being [1 4 5 6 8 10]? Because we were supposed to add 0 ourselves right?

yes

Mhh, yes I think I understand what the problem is

I ignored adding the final value, it changes nothing

since its + 3, it can't affect branching

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.

So, basically some math on part 1.

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

I can’t really prove it, but I can tell you how I arrived at it…

If you check, the lengths of runs of 1s 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 *))

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

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

Haha, yes. it produces 11. Can you elaborate?

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:

So, my solution breaks at runs > 4?

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.

Does your input have runs of 5?

just {1,2,4,7}

Mine has 1,2,3,4… quite strange.

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&amp;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

Sometimes it helps not knowing much math.

hahaha, yup.

It bothers me to know end that there wouldn’t be a formula solution to it, though.

You can still try to find one! I don't know if definitively does not exist. But yeah, probably not gonna be easy.🦜

I’m no Ramanujan for sure.

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.

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

Hmm.... I'll keep thinking then!

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.

I se 1, 2, 4, 7, 13 in that tribonacci sequence, hmmm.

Yup, that must be it

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)

(defn tribonacci [a b c]
  (lazy-seq (cons a (tribonacci b c (+' a b c)))))

Maybe you are not counting the max element + 3 you must add

ah, good catch. I somehow missed that. thanks, @lucaspolymeris!

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