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

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

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

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

😄 https://github.com/dawranliou/advent-of-code/blob/master/2020/src/dawranliou/advent_of_code_2020/day_16.clj

Nothing very exciting to see here 🙂 https://github.com/benfle/advent-of-code-2020/blob/main/day16.clj

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

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.

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

@U963A21SL how is sorting = one pass?

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

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

Anyway, https://github.com/transducer/adventofcode/blob/master/src/adventofcode/2020/day16.clj

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

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

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

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

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

names and factoring are very questionable, sorry

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)

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

I am up to date with the puzzles ^_^

Will probably try to do some cleanup, time permitting: https://github.com/Solaxun/aoc2020_clj/blob/main/src/aoc2020_clj/day16.clj

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

;=> ()...

This does not make sense

I’ll ask in core.logic

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

https://github.com/peterhhchan/aoc2020/blob/main/src/aoc2020/day16.clj

This one was pretty fun! https://github.com/Dexterminator/advent-of-code-2020/blob/main/src/day16/core.clj

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

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

ah indeed

smart

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

That's probably true

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

But apparently it wasn't necessary given the input data

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.

They won't be two entries, but one

Anyway checking that are different can be enough

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

Maybe I'm a little pedantic...

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

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)

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

My solution ^_^ https://github.com/zelark/AoC-2020/blob/master/src/zelark/aoc_2020/day_17.clj

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

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

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

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

Time to work, will continue tonight.

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

@U067R559Q really neat!

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

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

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.

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

Pure brute force for today: https://github.com/rjray/advent-2020-clojure/blob/master/src/advent_of_code/day17.clj

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.

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

https://github.com/green-coder/advent-of-code-2020/blob/master/src/aoc/day_17.clj

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

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

I will keep it for january

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

Seriously ?? Which part?

TIL from @U067R559Q

Ooops my mistake, I meant @@U067R559Q :X

https://github.com/nbardiuk/adventofcode/blob/master/2020/src/day17.clj

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

https://github.com/akovantsev/adventofcode/blob/master/src/adventofcode/y2020/day17.cljc

9 seconds, and I don't care

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

not after ~day15 usually

https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2020/day17.clj

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

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

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)

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

Thanks, done.

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

Which IDE are you using? Is it open source?

emacs, I believe it is open source lol

It could eventually be in https://github.com/borkdude/clj-kondo/blob/master/doc/editor-integration.md#emacs

near the goal ... https://github.com/borkdude/clj-kondo/issues/323

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.

https://github.com/RedPenguin101/aoc2020/blob/main/day17.clj - Fun! About 500ms for Part 2

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

https://github.com/Dexterminator/advent-of-code-2020/blob/main/src/day17/core.clj

better late than never: https://github.com/Solaxun/aoc2020_clj/blob/main/src/aoc2020_clj/day17.clj