Fork me on GitHub
#adventofcode
<
2020-12-10
>
st3fan01:12:30

Totally over-thinking this one

6
fingertoe06:12:38

Kinda quiet in here tonight? 😉

👋 3
Vincent Cantin06:12:48

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

😆 3
plexus09:12:30

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

Vincent Cantin18:12:24

It is a "divide and reuse" way of doing. I guess the "dynamic" part is the non-constant cost of calculating things when memoized.

rjray07:12:24

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

☝️ 6
👍 3
plexus08:12:23

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.

Björn Ebbinghaus10:12:35

Don’t forget your old friend memoize. That takes the naive approach straight to O(n).

plexus10:12:59

I don't see how my solution benefits from memoize, it's not doing anything multiple times

plexus10:12:27

well, not 100% true, but still 🙂

plexus13:12:59

alright, got a solution now

🎉 3
plexus08:12:13

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

😁 6
Stuart08:12:35

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

🤯 6
oxalorg (Mitesh)09:12:05

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

andrea.crotti09:12:16

btw during reclojure I saw someone fire up a nice graph genreated from the profiler output

andrea.crotti09:12:10

anyone knows how it can be done? I used to love to generate these graphs with Python and https://github.com/gak/pycallgraph

andrea.crotti09:12:12

something like https://github.com/jstepien/flames maybe but I think it was a different one

alekszelark14:12:31

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]

bellissimo 6
🤯 3
alekszelark14:12:57

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

👍 3
Greg Sugiyama09:12:57

I'm having trouble wrapping my head around this solution for part 2. Anyone care to explain the logic behind it?

alekszelark11:12:04

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

🙏 3
misha14:12:21

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

Lars Nilsson15:12:17

Was trying to come up with some clever solution, but in the end gave up and memoized results.

Lars Nilsson15:12:53

Side-effect of my accomplishment is code that hurts my eyes.

pez15:12:22

Shiny gold stars does that to ya! 😃

Lars Nilsson15:12:59

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

Average-user15:12:47

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

🏃 9
👍 9
Mno16:12:11

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.

tws16:12:11

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

tws16:12:31

my input didn’t have more than run of 4

Average-user16:12:01

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

tws16:12:43

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

Average-user16:12:27

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

Mno16:12:28

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

Stuart17:12:49

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?

Mno17:12:46

make sure you have the beginning and ending pieces there

Stuart17:12:25

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

Stuart17:12:34

damn, thought i could ignore that

Mno17:12:55

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

Mno17:12:49

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}

Mno17:12:43

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

Stuart17:12:03

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

tws18:12:21

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

mchampine18:12:35

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

Jeff Evans21:12:39

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

andrea.crotti16:12:07

jeez it's getting hard even to understand the assignment

andrea.crotti16:12:31

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

🙏 3
3
Stuart20:12:41

glad its not just me!

roelof17:12:06

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

andrea.crotti17:12:32

depends what you mean by easily

andrea.crotti17:12:58

if you have never done clojure it might take a while but the algoriths to use are quite simple

alekszelark17:12:59

There is a couple guys who recorded videos. You can learn from them a lot.

andrea.crotti17:12:34

yeah but you should try by yourself first maybe

Lars Nilsson17:12:19

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.

roelof17:12:42

oops I hate regexes

roelof17:12:07

range, map and filyer I already learned

roelof17:12:16

but now how to read from a file

Lars Nilsson17:12:01

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

roelof17:12:49

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

Lars Nilsson18:12:27

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

Average-user18:12:32

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

roelof18:12:27

thanks both

alekszelark17:12:19

an interesting stats today

🤪 6
Mno17:12:48

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

markw17:12:54

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

markw17:12:03

Yeah that didn’t work

markw17:12:17

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

markw17:12:25

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

Average-user17:12:40

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 🙂

markw17:12:13

I guess my first indication should have been when using the second test input took like 5 seconds to count the valid paths

Lars Nilsson17:12:43

My clue was the word "trillions".

markw17:12:59

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

markw17:12:13

or that’s how i interpreted it late last night

markw17:12:46

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?

Lars Nilsson18:12:01

Wouldn't it be 3^input?

markw18:12:30

oops sorry yes that’s what i meant

Lars Nilsson18:12:40

3^100 is a big number..

markw18:12:43

so basically a very big number

markw18:12:58

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

markw18:12:56

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

markw18:12:07

so much for search

Average-user18:12:29

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

kpav18:12:13

You could use a deps.edn file

kpav18:12:49

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

👍 3
Average-user18:12:15

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

kpav18:12:18

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

Average-user18:12:08

Anything special in deps.edn ? Mine still fails

alekszelark18:12:32

touch hw.clj                             
echo "(println \"Hello world\")" > hw.clj
clj hw.clj                               
WARNING: When invoking clojure.main, use -M
Hello world

kpav18:12:37

I think you might just need {:deps}? heres the documentation https://clojure.org/guides/deps_and_cli

👍 3
alekszelark18:12:43

at least you have to have {:paths [“src”]}, that’s enough to start

Average-user18:12:49

Thanks, Is now working

🙌 6
kpav18:12:14

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

Lars Nilsson18:12:04

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)

Stuart20:12:10

I must be missing something obvious but why are the intervals between any 2 adapters today either 1 or 3. Why not 2?

R.A. Porter20:12:19

That’s just the way the Institute of Elvish Electrical Engineers spec’d them, I guess.

😁 3
pez20:12:52

Not sure, but I “misunderstood” the description such that this was the case and based my solution on it. 😃

Stuart20:12:50

yeah, i just realised i think my solution totally breaks if any 2 adapters were seperated by 2 (and not 1 or 3)

pez20:12:35

Mine certainly will produce the wrong answer then. But I think it is quite small adaption needed,

Average-user21:12:51

How do they fail? Are working with prime factorization? Or am I missing something?

Stuart21:12:24

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.

3
Stuart21:12:31

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

Average-user21:12:52

what woul return to [1 3 5]?

Stuart21:12:14

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

Stuart21:12:05

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

Average-user21:12:26

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

Average-user21:12:49

Mhh, yes I think I understand what the problem is

Stuart21:12:50

I ignored adding the final value, it changes nothing

Stuart21:12:02

since its + 3, it can't affect branching

Average-user21:12:50

Mine I think it works with differences of two

Average-user21:12:09

But I'm not so sure anymore haha

pez21:12:09

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.

pez21:12:39

So, basically some math on part 1.

Average-user21:12:38

Could you elaborate? I thought there was no close formula (even under the assumption that the there are no differences of 2)

pez21:12:43

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

Average-user21:12:59

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

pez21:12:36

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.

Average-user21:12:05

I really don't understand why your solution works 😂 But nicely done. Can you prove that it does what it should?

Average-user21:12:30

Ore give me an insight?

pez21:12:45

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

pez21:12:35

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

Average-user21:12:53

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.

Average-user21:12:38

And I think I'm understanding why it works now Thanks!

pez21:12:01

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 1s 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.

pez21:12:52

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

Average-user21:12:29

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

pez21:12:06

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

Average-user21:12:06

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:

pez21:12:43

So, my solution breaks at runs > 4?

Average-user21:12:54

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

pez22:12:37

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.

pez22:12:07

Does your input have runs of 5?

Average-user22:12:34

just {1,2,4,7}

pez22:12:53

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

Average-user22:12:22

No no, I lied sorry

Average-user22:12:39

It does have runs of at most 4, there it is. I was looking at the wrong output

Average-user22:12:23

haha. yes with runs of <= 4 it works as you found the formula so it fitted that pattern

pez22:12:23

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.

Average-user22:12:29

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

pez22:12:01

Sometimes it helps not knowing much math.

pez22:12:38

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

Average-user22:12:28

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

pez22:12:13

I’m no Ramanujan for sure.

Average-user22:12:21

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

pez22:12:57

Interesting. My daughter and I was “seeing” fibbonacci sequences a while, but then when we blinked they were gone. 😃

pez22:12:08

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.

parrot 3
pez22:12:48

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

Average-user22:12:54

Yup, that must be it

pez22:12:15

(defn tribonacci [a b c]
  (lazy-seq (cons a (tribonacci b c (+' a b c)))))
According to stackoverflow.

❤️ 3
pez23:12:53

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

Average-user00:12:42

Gonna take a closer look to it, but probably tomorrow

erwinrooijakkers07:12:28

I read on the subreddit that it’s indeed a tribonacci sequence, but not sure what that means for the solution

Average-user13:12:58

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

pez16:12:00

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.

rfisher22:12:46

Part 2 feels like it requires some knowledge of mathematics which I do not have. Presumably some aspect of combinatorics.

pez22:12:33

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

rfisher22:12:20

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

Jeff Evans22:12:08

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)

Average-user22:12:11

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

Jeff Evans22:12:49

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

parrot 3