Fork me on GitHub
#adventofcode
<
2020-12-16
>
st3fan02:12:18

I got Day 15 Part 2 down to 450ms

st3fan02:12:54

Rewrote it in C 😉

st3fan02:12:08

Will do a similar solution in Clojure though

alekszelark06:12:06

Day 16 answers thread - Post your answers here

rjray06:12:37

Long solution. I also plan to try to improve it. Tomorrow. https://github.com/rjray/advent-2020-clojure/blob/master/src/advent_of_code/day16.clj

🎉 6
👍 3
alekszelark08:12:45

Not long, but a bit dirty solution. Will try to refact it after work. https://github.com/zelark/AoC-2020/blob/master/src/zelark/aoc_2020/day_16.clj

👍 6
nbardiuk09:12:33

I am glad that today's problem does not require some fancy dynamic programming algorithm https://github.com/nbardiuk/adventofcode/blob/master/2020/src/day16.clj

👏 6
genmeblog11:12:24

True, but was much complicated than I thought at the beginning... https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2020/day16.clj

👍 6
benoit14:12:37

Maybe the only interesting bit is to sort the candidates for part2 so you can solve the problem in one pass in a reduce.

👍 6
Joe14:12:08

https://github.com/RedPenguin101/aoc2020/blob/main/day16.clj- I'm pretty happy with my implementation for once. Short, fast(ish) and a comprehensible api. I especially like the narrow-down function here, I thought that was going to much more difficult than it turned out to be.

👍 6
Joe14:12:26

Really fun puzzle too, I like this sort of thing much more than implementing efficient algorithms or fiddling with bits 😑

misha15:12:00

@U963A21SL how is sorting = one pass? kappa

erwinrooijakkers16:12:29

I overlooked Now that you've identified which tickets contain invalid values, _discard those tickets entirely_

erwinrooijakkers16:12:10

And it was bit more difficult than I thought (could not discard the non “departure” entries)

benoit17:12:09

@U051HUZLD sort by the number of candidates for each position. The first position will only have one candidate. The second will have two candidates, the one already picked in (1) + a new one which is the solution...

Vincent Cantin17:12:33

Hi, here is my solution, it runs in 30 msecs on my old computer. https://github.com/green-coder/advent-of-code-2020/blob/master/src/aoc/day_16.clj

🚀 9
euccastro18:12:33

@benoit is that guaranteed, or did it just happen to be true for the challenge input?

euccastro18:12:08

I imagine you could have several positions with the same number of candidates, and not the first one would resolve first?

3
euccastro18:12:31

my solution just does brute force since it works ~instantly anyway. I didn't clean it up, sorry:

(ns advent.day16
  (:require [clojure.string :as str]
            [ :as io]))


(def demo-input "class: 1-3 or 5-7
row: 6-11 or 33-44
seat: 13-40 or 45-50

your ticket:
7,1,14

nearby tickets:
7,3,47
40,4,50
55,2,20
38,6,12")


(defn parse-long [x]
  (Long/parseLong x))


(defn extents [input]
  (for [[_ & extents]
        (re-seq #"(\d+)-(\d+)" input)]
    (mapv parse-long extents)))


(defn nearby-tickets [input]
  (-> input
      (str/split #"nearby tickets:\n")
      second
      (str/split #"\R")
      (->> (map #(str/split % #","))
           (map #(mapv parse-long %)))))


(defn nearby-ticket-numbers [input]
  (flatten (nearby-tickets input)))


(defn valid-number? [n extents]
  (first (for [[begin end] extents
               :when (<= begin n end)]
           n)))


(defn invalid-numbers [input]
  (let [extents (extents input)]
    (remove #(valid-number? % extents) (nearby-ticket-numbers input))))


(defn solution [input]
  (apply + (invalid-numbers input)))


(solution demo-input)
;; => 71


(def real-input (slurp (io/resource "input16")))


(solution real-input)
;; => 21978

;; part 2


(defn attr-extents [input]
  (for [[_ attr & extents]
        (re-seq #"(\w+\s*\w*):\s+(\d+)-(\d+)\s+or\s+(\d+)-(\d+)" input)]
    (apply vector attr (map parse-long extents))))

(comment

  (attr-extents demo-input)

  )

(defn valid-ticket? [numbers extents]
  (every? #(valid-number? % extents) numbers))


(defn valid-nearby-tickets [input]
  (let [extents (extents input)]
    (filter #(valid-ticket? % extents) (nearby-tickets input))))


(comment
  (def valid-tickets* (valid-nearby-tickets demo-input (extents demo-input)))
  (def attr-extents* (attr-extents demo-input))
  (def num-positions (count (first valid-tickets*)))
  )


(defn attr-matches-position? [[_ begin1 end1 begin2 end2] position tickets]
  (every?
   #(or (<= begin1 % end1) (<= begin2 % end2))
   (map #(nth % position) tickets)))


(defn initial-state [aexts tickets]
  (vec
   (for [pos (range (count aexts))]
     (set (keep
           (fn [[attr :as attr-ext]]
             (when (attr-matches-position?
                    attr-ext
                    pos
                    tickets)
               attr))
           aexts)))))


(defn resolve-positions [initial-state]
  (let [num-positions (count initial-state)]
    (loop [state initial-state]
      (let [resolved (map
                      first
                      (filter #(= (count %) 1)
                              state))
            resolved-set (set resolved)]
        (if (= (count resolved) num-positions)
          resolved
          (recur
           (map
            (fn [x]
              (if (= (count x) 1)
                x
                (remove resolved-set x)))
            state)))))))


(def resolved
  (resolve-positions
   (initial-state
    (attr-extents real-input)
    (valid-nearby-tickets real-input))))


(defn my-ticket [input]
  (-> input
      (str/split #"ticket")
      second
      (->> (re-seq #"\d+")
           (map parse-long))))

(def m (zipmap resolved (my-ticket real-input)))


(apply * (vals (select-keys m (filter #(str/starts-with? % "departure") (keys m)))))
;; => 105368685

👍 3
euccastro18:12:42

names and factoring are very questionable, sorry

euccastro18:12:32

btw this is the first day I actually worked through the problem myself. so far I've just binge-watching @U07FP7QJ0's recorded videos (haven't caught up yet)

pez18:12:22

Step 1 done. Turns out my solution is not as applicable to step 2 as things were yesterday 😃

(->> input
       (parse)
       ((fn [notes]
          (let [valid? (reduce (fn [acc rule]
                                 (->> (:ranges rule)
                                      (map (fn [[start end]]
                                             (into #{} (range start (inc end)))))
                                      (apply (partial clojure.set/union acc))))
                               #{}
                               (:rules notes))]
            (filter (complement valid?) (apply concat (:nearby notes))))))
       (apply +))

😁 15
Vincent Cantin18:12:22

I am up to date with the puzzles ^_^

🎉 6
erwinrooijakkers20:12:33

How do I turn this into valid core.logic?

(run* [q]
  (fresh [i0 i1 i2 i3 i4 i5 i6 i7 i8 i9 i10 i11 i12 i13 i14 i15 i16 i17 i18 i19 i20]
    (logic/== q [i0 i1 i2 i3 i4 i5 i6 i7 i8 i9 i10 i11 i12 i13 i14 i15 i16 i17 i18 i19 i20])
    (fd/in i0 i1 i2 i3 i4 i5 i6 i7 i8 i9 i10 i11 i12 i13 i14 i15 i16 i17 i18 i19 i20 (fd/interval 0 21))
    (logic/membero i0 #{1 2 3 5 6 8 10 11 14})
    (logic/membero i1 #{0 1 2 3 4 5 6 8 10 11 14 15})
    (logic/membero i2 #{0 1 2 3 4 5 6 7 8 10 11 14 15 18 19})
    (logic/membero i3 #{1 2 3 4 5 6 8 10 11 14})
    (logic/membero i4 #{0 1 2 3 4 5 6 8 10 11 14})
    (logic/membero i5 #{6 8 10 11})
    (logic/membero i6 #{6 8 11})
    (logic/membero i7 #{1 5 6 8 10 11 14})
    (logic/membero i8 #{6 8 10 11 14})
    (logic/membero i10 #{1 2 5 6 8 10 11 14})
    (logic/membero i11 #{6 8})
    (logic/membero i12 #{1 6 8 10 11 14})
    (logic/membero i13 #{8})
    (logic/membero i14 #{0 1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 17 18 19})
    (logic/membero i15 #{0 1 2 3 4 5 6 7 8 10 11 14 15 17 18 19})
    (logic/membero i16 #{0 1 2 3 4 5 6 7 8 10 11 14 15 16 17 18 19})
    (logic/membero i17 #{0 1 2 3 4 5 6 7 8 10 11 12 14 15 16 17 18 19})
    (logic/membero i18 #{0 1 2 3 4 5 6 8 10 11 14 15 19})
    (logic/membero i19 #{0 1 2 3 4 5 6 8 10 11 14 15 18 19})
    (logic/membero i20 #{0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19})))

;=> ()...

erwinrooijakkers20:12:55

This does not make sense

erwinrooijakkers20:12:15

I’ll ask in core.logic

peterc21:12:47

@U65FN6WL9 @U963A21SL I also did the sort approach as I did it for speed. 1. Inspect the results after you removed the invalid fields for each position. There are some clues that a relatively "simple" solution can be used. 2. Next, sort the valid fields by count and do a set difference between each element to see that there is indeed a unique solution. Obviously a solution is not guaranteed, but step two is quick to test.

👍 6
misha09:12:49

chief loop officer

😃 6
misha09:12:09

(let [[rules mine other] (parse i)
      valid?     (->> rules vals (reduce into #{}))
      valid      (->> other
                   (remove #(seq (remove valid? %)))
                   (map vec))
      transposed (apply map vector valid)
      candidates (fn [pred]
                   (->> transposed
                     (map-indexed
                       (fn [idx col]
                         (when (every? pred col)
                           idx)))
                     (remove nil?)))
      labels     (loop [done {}
                        todo (->> rules
                               (map-vals candidates)
                               (sort-by #(-> % val count) <)
                               (into PersistentQueue/EMPTY))]
                   (if (empty? todo)
                     done
                     (let [[label cols] (peek todo)
                           todo (pop todo)
                           cols (remove done cols)]
                       (if (-> cols count (= 1))
                         (recur (assoc done (first cols) label) todo)
                         (recur done (conj todo [label cols]))))))]
  (->> labels
    (filter #(-> % val (str/starts-with? "departure")))
    (map key)
    (map mine)
    (reduce *)))

👍 3
misha09:12:11

ofc it would loop forever, if at some point every unmapped label had more than 1 candidate idx. that'd be job for core.logic

6
erwinrooijakkers18:12:31

did not think about core.logic but this is core.logic

mdallastella14:12:46

Namaste. I have a "philosophical" question about the first problem of day 1. I saw solutions like this around the internet:

(for [x input y input :when (= 2020 (+ x y))]
  (* x y))

mdallastella14:12:08

but what if my input list is (1010 )? Isn't going to stop on the first element?

andrea.crotti14:12:51

That's probably true

andrea.crotti14:12:04

Another check to make sure the numbers are not the same is enough

andrea.crotti14:12:08

But apparently it wasn't necessary given the input data

mdallastella14:12:17

I agree, but given the statement: > Specifically, they need you to find the two entries that sum to `2020` and then multiply those two numbers together.

mdallastella14:12:35

They won't be two entries, but one

mdallastella14:12:21

Anyway checking that are different can be enough

mdallastella14:12:25

but if I have, let's say (1010 ) the elements are two

mdallastella14:12:25

Maybe I'm a little pedantic...

andrea.crotti14:12:50

hehe well I think noone cares about the perfect solution as long as it works and it's fast enough 😄

😅 3
👍 3
misha14:12:52

you can compare indexes instead of actual numbers in case you want to be pedantic

(let [input [1010 1721 299 1465]]
  (for [[a x] (map-indexed vector input)
        [b y] (map-indexed vector input)
        :when (= 2020 (+ x y))
        :when (not= a b)]
    (* x y)))
=> (514579 514579)

3
misha15:12:53

but then :when (< a b) is even better

Vincent Cantin18:12:24

Day 17 answers thread - Post your answers here

Vincent Cantin05:12:25

so fast ! I can’t past part 1, I have a bug or a misunderstanding.

Vincent Cantin06:12:08

I don’t understand how the neighbors are counted, it seems inconsistent with the example .. maybe my english has a problem.

alekszelark06:12:12

I believe your english much better than mine. I often have difficulties to understand what they want in the end.

Vincent Cantin06:12:27

I don’t understand why at z=-1 in their example, the first cube becomes active. I don’t see 3 active neighbors.

Vincent Cantin06:12:24

Time to work, will continue tonight.

euccastro06:12:55

Today I got it cleaner than yesterday, but the solution to the second one takes ~780ms https://github.com/euccastro/advent-of-code-2020/blob/master/src/advent/day17.clj

👍 6
euccastro06:12:42

@U067R559Q really neat!

🙏 3
euccastro06:12:44

I left the first solution untouched (just redefined what had to be generalized for the second one) and much of my time went to generalize the neighbors function, just because it seemed fun

euccastro06:12:15

and yeah, my cycle function would be neater had I realized that cells with 3 neighbors are always activated, whether they were already or not

erwinrooijakkers06:12:06

Naive brute force (checking every neighbour for every point in every iteration) finished in 15 minutes or so for second part while I tried to optimize in the mean time https://github.com/transducer/adventofcode/blob/master/src/adventofcode/2020/day17.clj Not sure how to optimize though, maybe stop counting when it’s more than 3? Any other suggestions? I’ll take a look later.

👍 3
erwinrooijakkers06:12:24

AH maybe use keep-indexed and not store \. as false to start with 🙂

rjray06:12:53

I've thought of a way to avoid looping over the entire coordinate system, but it'll have to wait until tomorrow after I've slept.

Vincent Cantin06:12:15

I solved it. My problem was just that the text did not mention that the slides of the examples were shifted down by 1.

👏 9
alekszelark06:12:00

@vincent.cantin Yes, it isn’t illustrated. Sometimes it can give you wrong assumptions. Actually I didn’t look at the examples, because the description was enough to me today.

alekszelark06:12:47

Who wants more, here you go :)) https://adventofcode.com/2019/day/24

👍 3
Vincent Cantin07:12:47

I will keep it for january

peterc07:12:42

@vincent.cantin love your solution, learned a lot from it, ty!

Vincent Cantin07:12:41

Seriously ?? Which part?

peterc08:12:17

Ooops my mistake, I meant @@U067R559Q :X

😅 3
nbardiuk08:12:37

@U067R559Q I love the frequences approach, it improved my slow implementation from 5s to 450ms

misha09:12:09

9 seconds, and I don't care d

9
nbardiuk10:12:22

@U051HUZLD sometimes it is harder to "let it go"

misha10:12:15

not after ~day15 usually

benoit13:12:46

Representing the pocket dimensions as a set of active cubes. Looks similar to others here. https://github.com/benfle/advent-of-code-2020/blob/main/day17.clj

👍 9
benoit13:12:43

Of course I had to rewrite the function that compute the neighbor coordinates for part2 to support an arbitrary number of dimensions 🙂

Vincent Cantin13:12:19

https://github.com/benfle/advent-of-code-2020/blob/main/day17.clj#L55-L60 could also be written like (->> (all-neighbor-coordinates state) (filter (partial next-cube-active? state)) set)

Vincent Cantin13:12:05

There is also the transducer way which should run faster: (into #{} (filter (partial next-cube-active? state)) (all-neighbor-coordinates state))

benoit13:12:55

Thanks, done.

benoit13:12:46

That would be cool if my IDE could detect this kind of semantic-preserving transformations and automatically propose them :)

3
Vincent Cantin13:12:34

Which IDE are you using? Is it open source?

benoit14:12:32

emacs, I believe it is open source lol

benoit14:12:48

Yeah I would certainly leverage things in clj-kondo 🙂 But I'm not a fan of the overall approach of linters. This should be a la carte and an assistant to help you navigate the design space. Not a collection of rules that you must respect or be warned about.

euccastro03:12:06

nice! nit: (apply concat (map neighbors coords)) could be just (mapcat neighbors coords)

alekszelark18:12:20

@vincent.cantin I see you’re back in the game, that’s great!

bubblebobble 6
9