Fork me on GitHub
#adventofcode
<
2020-12-09
>
Vincent Cantin03:12:25

Polling for yesterday's solution: PC people bmo vs. IP people bananadance

bmo 5
bananadance 4
djblue05:12:04

I'm going to rename my repo to advent-of-for 馃槅

馃槀 6
plexus07:12:54

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 馃檪

馃憤 1
Vincent Cantin07:12:20

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.

Vincent Cantin09:12:01

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.

Vincent Cantin09:12:02

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.

metal 1
imre09:12:43

@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

馃憤 1
imre09:12:37

I used it in a lot of places in my solutions so far https://github.com/imrekoszo/advent-2020/

馃憤 1
Vincent Cantin09:12:44

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

imre09:12:18

Nice one, that 馃檪

Vincent Cantin09:12:48

on the shiny bag day

imre09:12:40

I don't think I got that far just yet

imre09:12:47

I'm 3 days behind rn

Vincent Cantin09:12:49

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.

Vincent Cantin09:12:24

Until now, performance was not the issue in all the puzzles, so lazy collections are still in the game.

imre09:12:58

I prefer using transducers even then. Easy to go back to lazyland from there

andrea.crotti20:12:29

what's the best way to do a cartesian product but without the order?

markw20:12:21

what do you mean by without the order?

misha20:12:40

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

andrea.crotti21:12:42

yeah I mean having [0 1] but not [1 0] for example

andrea.crotti21:12:07

so imagining a square, taking the diagonal and the lower or upper half

tws21:12:08

combination instead of permutation?

imre21:12:19

ha. Is this for day 1?

imre21:12:18

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

Lars Nilsson21:12:01

I used (for [i (range size) j (range i size)] ...) to get a triangle of indices (where size if the count of the collection)

markw21:12:06

@andrea.crotti There is more than one way to do it, but as mentioned above that鈥檚 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

markw21:12:04

basically you want your inner loop to always start at 1 + the outer loop var

raicotop21:12:28

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

markw21:12:47

Yep - I think @plexus mentioned this in the most recent video

raicotop21:12:52

That's where I saw it too I guess. Came in handy for day 9.

misha21:12:18

lacks diagonal: [0 0] 鈥 [4 4]

markw21:12:50

if you need diagonals you can just add a condition to the :when

markw21:12:23

:when (or ( = x y) (< x y))

Lars Nilsson21:12:28

Or change < to <=, I would imagine...

Lars Nilsson21:12:26

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

markw21:12:08

if you want efficient generation i would use combinatorics and tack on the diagonals explicitly

Lars Nilsson21:12:09

It just won't generate an entry for the failing conditions.

Lars Nilsson21:12:50

As I mentioned above, I did it using the two argument version of range to get the triangular shape of indices.

馃憤 1
markw21:12:57

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

Lars Nilsson21:12:29

In my actual for sequence I do have :let and :when for other purposes, just not the range/index checking.

Lars Nilsson21:12:42

I feel somewhat stupid about my day 1, part 2 implementation where I just added another index instead of doing something else.

misha21:12:14

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

markw21:12:20

oh yeah i brute forced that one O^N(3)

markw21:12:30

i鈥檓 not going to be clever on day 1 馃槢

misha21:12:55

Depends on what your goals are for this puzzle thing. And there are a bunch of conflicting ones there.

Lars Nilsson21:12:01

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

Lars Nilsson21:12:33

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.

andrea.crotti21:12:27

I'm using loom for problem 7 https://github.com/aysylu/loom and it worked out nicely for the first part of the problem

andrea.crotti21:12:56

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

andrea.crotti21:12:15

but I can't find anything useful to do that

misha21:12:37

> it worked out nicely for the first part of the problem famous last words鈩

Lars Nilsson21:12:16

Thanks for the heads-up on loom.. I might need to look at that for some non-aoc stuff.

andrea.crotti21:12:17

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)

misha21:12:17

someone shared loom solution here

andrea.crotti21:12:03

it's pretty much just

(->> "shiny gold"
       (la/bf-traverse (get-graph))
       count
       ;; removing the node itself
       dec)
once you have the graph

andrea.crotti21:12:14

but yeah getting the actual weights to do something seems to be another matter

misha21:12:16

> Aysylu Greenberg - Loom and Graphs in Clojure

andrea.crotti21:12:17

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

andrea.crotti21:12:32

would be nice if there was an easier way though

misha21:12:17

sounds like one ugly loop would do just fine here kappa

andrea.crotti21:12:26

hehe yeah that would work I guess

andrea.crotti21:12:34

was trying to avoid that since that's all I'm doing apparently

misha21:12:02

yeah, story of my aoc life for 5 years

Lars Nilsson21:12:08

Day 7 was some ugly for comprehension over recursive calls for me.

misha21:12:22

but yeah, downloading a bunch of ugly loop s from clojars might seem more idiomatic :)

andrea.crotti22:12:44

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

andrea.crotti22:12:30

but aoc doesn't agree with me

andrea.crotti22:12:59

mm weird my result is exactly (actual-result / 2 + 1) using the example from the instructions

andrea.crotti22:12:21

but of course if I (dec (* 2 current)) it still doesn't work 馃槃

andrea.crotti22:12:29

so probably just a coincidence

andrea.crotti22:12:18

I think the problem is maybe the graph generated because the algorithm I think it's correct, bah I'll see tomorrow

andrea.crotti22:12:50

that's quite neat thanks

markw22:12:04

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鈥檝e 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.

Lars Nilsson22:12:15

Cheating to use instaparse?

markw23:12:51

that鈥檚 next, first i want to understand how to do it though

st3fan23:12:07

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

st3fan23:12:26

Totally out of my comfort zone, but it is a good learning exercise

鉂わ笍 2
馃憤 2
st3fan23:12:48

Got some code snippets in a file that need to work together and then 鈥