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

Totally over-thinking this one

2
fingertoe06:12:38

Kinda quiet in here tonight? 😉

👋 1
Vincent Cantin06:12:48

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

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

☝️ 2
👍 1
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

🎉 1
plexus08:12:13

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

😁 2
Stuart08:12:35

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

🤯 2
oxalorg09: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 2
🤯 1
alekszelark14:12:57

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

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

🙏 1
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 !

🏃 3
👍 3
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

🙏 1
1
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

🤪 2
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

👍 1
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

👍 1
alekszelark18:12:43

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

Average-user18:12:49

Thanks, Is now working

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

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 1