Fork me on GitHub
#adventofcode
<
2021-12-07
>
rmprescott01:12:12

Too bad they didn't go a bit larger. ;D

(time (part-2 input 500))
"Elapsed time: 3.192168 msecs"
=> 2759581742718205387412N

alekszelark04:12:43

🧵Day 7 answers thread: post your answers here

mchampine05:12:38

(defn fuel [ex n] (apply + (map #(util/abs (- % n)) ex)))
(apply min (map (partial fuel input) (range (apply max input)))) ;; 335271

;; Part 2  (incfuel improved by mikelis observation)
(defn incfuel [n] (/ (* n (inc n)) 2))
(defn fuel2 [ex n] (apply + (map #(incfuel (util/abs (- % n))) ex)))
(apply min (map (partial fuel2 input) (range (apply max input)))) ;; 95851339

Miķelis Vindavs05:12:51

By the way 1 + 2 + 3 + … + n == n * (n + 1) / 2

👍 6
2
👌 1
Miķelis Vindavs06:12:42

nice use of frequencies to skip over duplicates

Pradeep B06:12:40

(def example-input-list (list 16,1,2,0,4,2,7,1,2,14))
(def example-input-frequencies (sort-by val (frequencies ex)))

(defn calculate-diff [n pos]
  (if (> pos n) (- pos n) (- n pos)))

(first (sort 
        (map (fn [input] 
               (reduce + (map #(calculate-diff %1 (first input)) example-input-list)))
             example-input-frequencies)))
feedback is more than welcome, what else can be done to optimize (part1 only, understanding formula to calculate cost for part2)

peterc07:12:57

You can sort the input and do a binary search on it You can do a binary search on the possible positions

👀 1
nbardiuk07:12:25

After solving using brute force, I've noticed that positions are very close to median and mean, and looks like for a lot of people on reddit it also works https://github.com/nbardiuk/adventofcode/blob/master/2021/src/day07.clj

👍 5
peterc07:12:02

Not the most idiomatic, but you can do something like this @U01BDUH28V7

(defn cost-fn-1 [start end]
  (abs start end))

(defn cost-fn-2 [start end]
  (let [n (abs start end)]
    (/ (* n (inc n)) 2)))

(defn cost [data cost-fn n]
  (reduce + (map (partial cost-fn n) data)))

(defn mid [a b]
  (int (+ a (/ (- b a) 2))))

(defn  min-cost [f]
  (let [d  (parse-data)]
    (loop [mn   0
           mx   (apply max d)
           best (cost d f (mid mn mx))]
      (if (= mn mx)
        best
        (let [md     (mid mn mx)
              lower  (cost d f (mid mn md))
              higher (cost d f (mid md mx))]
          (if (< lower higher)
            (recur mn md (min lower best))
            (recur (inc md) mx (min higher best))))))))

(def part-1 (min-cost cost-fn-1))
(def part-2 (min-cost cost-fn-2))

🙌 1
Pradeep B07:12:09

realised after looking at part2 that mean will be good approach/ thanks @U1NLKFVC4

peterc07:12:20

There are a bunch of bugs in my code actually, my the input is nice enough to give me the correct solution.

peterc07:12:55

Spits out an answer in about ~200ms on my machine

euccastro08:12:34

for day 7 I happened to remember the math trick to sum the 1..n integers. I tried an optimization (involving frequencies, of course) of the first thing I thought of, but that was hardly worth the trouble: https://github.com/euccastro/advent-of-code-2021/blob/main/day7.clj

euccastro08:12:48

@U067R559Q nice one! If you have already calculated the frequencies it's slightly more efficient and concise to iterate over the keys of that instead of (range min-pos (inc max-pos)) ?

euccastro08:12:56

anyway, I was surprised about how little time is saved by reducing the number of positions to compare against, either with frequencies or range from min to max

alekszelark08:12:21

@U65FN6WL9 that was my first thought, and it worked for my part 1. But for part 2 there is no position in the input which is the best to choose. So I ended up with a full range of the all positions.

euccastro08:12:44

oh, great catch!

peterc08:12:59

tossing in a pmap seems like the easiest win

euccastro08:12:33

I interpreted the problem as picking the cheapest position from the given crab positions, so I guess I just got lucky with my puzzle input

🤞 1
jherrlin08:12:49

Yeah I used a pmap, dont know if it was totally necessary but it felt cool 🙂 https://github.com/Kodkollektivet/advent-of-code-2021/blob/main/clojure/jherrlin/day7/problem2.clj

peterc09:12:15

Is this right? For part 1, sorting the input, and calculating the cost at the midpoint yields the first solution. (There are two midpoints, so use the min).

peterc09:12:41

Solution looks like this:

(defn part1 []
  (let [data (sort (input))
        mid  (/ (count data) 2)]
    (min (cost data (nth data mid))
         (cost data (nth data (dec mid))))))

peterc09:12:43

upon reflection, i think the answer can lie between the two points

tschady09:12:48

@U076FM90B your floor-median should probably be floor-mean?

nbardiuk09:12:19

thank you! fixed

Antonio Bibiano10:12:37

I have to admit I solved mine with raw brute force 😄

(defn cost-1 [pos crab]
  (Math/abs (- pos crab)))

(defn cost-2 [pos crab]
  (let [dist (Math/abs (- pos crab))]
    (/ (* dist (inc dist)) 2)))

(defn brute-min-cost [crabs cost]
  (let [far (apply max crabs)]
    (apply min
           (map (fn [pos]
                  (reduce +
                          (map #(cost pos %) crabs)))
                (range (inc far))))))

(brute-min-cost crabs cost-1)
(brute-min-cost crabs cost-2)

Antonio Bibiano10:12:46

then I wikipedia the shit out of the problem and found that median was the solution to part 1 and a friend suggested that the average is the solution to part 2 so here they are

Antonio Bibiano10:12:17

(defn median [l]
  (let [len (count l)
        middle (/ len 2)
        sorted (sort l)]
    [(nth sorted (dec middle)) (nth sorted middle)]))

(defn avg* [crabs]
  (/ (apply + crabs) (count crabs)))

(defn avg [crabs]
  (let [res (avg* crabs)]
    [(int res) (inc (int res))]))

(defn cost-1 [pos crab]
  (Math/abs (- pos crab)))

(defn cost-2 [pos crab]
  (let [dist (Math/abs (- pos crab))]
    (/ (* dist (inc dist)) 2)))

(defn min-cost [crabs cost candidates]
  (apply min
         (map (fn [pos]
                (reduce + (map #(cost pos %) crabs)))
              candidates)))

(def crabs (parse large))
(min-cost crabs cost-1 (median crabs))
(min-cost crabs cost-2 (avg crabs))

Antonio Bibiano10:12:52

i decided to return two candidates for median and average just in case

genmeblog11:12:18

ups, sorry, density was wrong... had to delete previous message above - submarine trace, below - initial density of submarines 🙂

👏 2
Felipe12:12:41

brute forced part 1 expecting part 2 to force me to think of a better solution, but my laziness paid off https://github.com/FelipeCortez/advent-of-code/blob/master/2021/07.clj

borkdude12:12:59

@UA2U3KW0L Awesome! How fast is yours?

borkdude12:12:26

Not that it matters, just wondering

Felipe12:12:52

huh, time says "Elapsed time: 0.235105 msecs" , but it's definitely more

borkdude12:12:13

this is because of laziness probably which escapes the time call

Felipe12:12:20

yeah, mapv yields "Elapsed time: 11779.226753 msecs"

borkdude12:12:30

This guy has optimized it so it runs in tens of milliseconds in both clojure and babashka: https://github.com/mknoszlig/aoc2021/blob/76ef20928dd59d3810ca5e04f7f879357389268b/src/aoc2021/day7.clj

borkdude12:12:12

Math/abs reflects in the absence of type hints

👍 1
Felipe12:12:54

oh! makes sense

borkdude12:12:02

user=> (set! *warn-on-reflection* true)
true
user=> (defn foo [x] (Math/abs x))
Reflection warning, NO_SOURCE_PATH:1:15 - call to static method abs on java.lang.Math can't be resolved (argument types: unknown).
#'user/foo

nbardiuk13:12:39

somebody worked out that correct answer differs from mean by up to 0.5 https://www.reddit.com/r/adventofcode/comments/rawxad/2021_day_7_part_2_i_wrote_a_paper_on_todays/

👌 5
tschady13:12:51

welp, time to update my code 🙂

tschady13:12:42

oh, to be young again

Callum Oakley13:12:48

if you have an intcode computer handy, there’s an easter egg in today’s puzzle :o

nice 2
🎉 1
genmeblog13:12:15

solution with optimizer (sometimes it can give wrong answer, mainly due to discrete domain):

(defn dist [a b] (int (m/abs (- a b))))
(defn fuel-burn [data cost-fn m] (reduce #(+ %1 (cost-fn %2 m)) 0 data))
(defn cost [d] (/ (* d (inc d)) 2))
(def target1 (comp (partial fuel-burn data dist) int))
(def target2 (comp (partial fuel-burn data (comp cost dist)) int))
(defn optimizer [target] 
  (->> {:bounds [[0 2000]] :N 100}
       (fastmath.optimization/scan-and-minimize :cmaes target)
       (second)
       (int)))

(optimizer target1)
;; => 336040
(optimizer target2)
;; => 94813675

;; --- also valid
(target1 (fastmath.stats/median data))
;; => 336040
(target2 (fastmath.stats/mean data))
;; => 94813675

Antonio Bibiano13:12:42

adding the type hints really changes the performance!! thanks @U04V15CAJ for pointing that out

Antonio Bibiano13:12:52

but I found this a bit odd when I tried to define the cost like this

(defn cost-1 [^int pos ^int crab]
  (Math/abs (- pos crab)))

Antonio Bibiano13:12:59

; Syntax error (IllegalArgumentException) compiling fn* at (/home/antbbn/aoc_2021/day7.clj:63:1).
; Only long and double primitives are supported

genmeblog13:12:54

yes, that works this way (I mean Clojure type hinting)

genmeblog13:12:21

only longs can be used and these are possible up to arity 4

Antonio Bibiano13:12:49

but on the reference it says that int is acceptable

genmeblog13:12:57

but not as a type hint for a function arguments, you can use type hinting in any other places and there ^int is possible.

genmeblog13:12:53

for example, this is ok:

(defn cost-1 [[^int pos ^int crab]]
  (Math/abs (- pos crab)))

genmeblog14:12:19

or this:

(defn cost-1 [pos crab]
  (Math/abs (- ^int pos ^int crab)))

Antonio Bibiano14:12:27

Ah I see, I guess it's a bit off topic but do you know the reason for that?

genmeblog14:12:38

yep, there is a stub for a function for every combination of arguments and returning value

karol16:12:44

https://github.com/kfirmanty/advent-of-code-2021/blob/main/src/day7.clj it was much easier for me than day7. Not very performant but when checking day6 solutions afterwards and seeing people using memoize it reminded me how nice of a function this is and basically used it today for part2

Sam Adams17:12:17

Best I could come up with (through trial and error) for part 2 was that the solution position seemed to be bounded by the median and rounded mean. Apparently that’s faulty… unless the median indicates which direction the mean is pulled by up to 1/2…? That’s a question for later 🙂   https://samadams.dev/2021/12/07/advent-of-code-day-7.html

gabo18:12:37

I brute forced it and part2 was taking ~20 s, just changing the naive summing of ranges for the gauss formula got me to 200ms 😳 https://gist.github.com/galuque/fdeba14c6103bf6482b6f7c53fd645db#file-aoc2021_day_7-clj

Stuart19:12:28

Part 2 got a bit messy for me:

(ns stuartstein777.2021.day7
  (:require [stuartstein777.file :as f]
            [stuartstein777.utils :as u]))

(defn get-distances [hps n]
  (mapv (fn [h] (Math/abs (- h n))) hps))

(let [input (f/parse-csv-ints "puzzle-inputs/2021/day7")
      minimum (apply min input)
      maximum (apply max input)
      h-positions (u/range-inclusive minimum maximum)]
  (->> input
       (mapv (partial get-distances h-positions))
       (apply mapv vector)
       (mapv #(reduce + 0 %))
       (apply min)))

;; part 2
(defn build-row [min max n]
  (let [to-max (if (= n max) [] (reductions + (u/range-inclusive 1 (- max n))))
        to-min (reverse (reductions + (u/range-inclusive min n)))]
    (concat to-min to-max)))

(let [input (f/parse-csv-ints "puzzle-inputs/2021/day7")
      minimum (apply min input)
      maximum (apply max input)]
  (->> input
       (mapv (partial build-row minimum maximum))
       (apply map vector)
       (mapv #(reduce + 0 %))
       (apply min)))
I built a table up of the distance to each possible horizontal position, then rotated it 90 degrees, summed each row and took the min. I expected it to be too slow but it runs in a couple of seconds or so for part 2.

Björn Ebbinghaus23:12:17

I derived the sum of the consumption of the crabs for an alignment x https://twitter.com/MrEbbinghaus/status/1468359022453612549

Miķelis Vindavs05:12:22

I can share a pro tip I figured out for myself today: Running today’s code on yesterday’s input is most likely not going to work 😄

😁 12
euccastro08:12:49

I got bitten by that mistake after reading this!

lread17:12:33

I also stated with this “tactic”.

fingertoe06:12:30

All caught up! My bingo card computation was buggy and overcomplicated. Rewrote it successfully today. Burnt out at about 23 stars last year. Better momentum this time..

👍 4
alekszelark09:12:01

Haha, it reminds me about day 22 last year https://adventofcode.com/2020/day/22

lread17:12:07

Uh oh, for me, part 1 test and real data work, part 2 test data works and real data fails. Hmm… dang.

Antonio Bibiano18:12:10

What was your approach?

lread18:12:59

For part1 I found pos via the median of positions, then calced cost. For part2 I started with brute force calcing cost for each possible pos, but found this slow, so I optimized via a binary-search-ish strategy. This leads me to same wrong answer for real-data, only faster. simple_smile

Antonio Bibiano18:12:09

Ah I see I did also a brute force approach but not optimized at all :D

sarcilav18:12:27

I also did binary search, it could be either and error on the cost function or on the stop condition of the binary search

sarcilav18:12:07

are you doing binary search over the range from min to max pos or just on existing positions?

lread18:12:40

I’m guessing it must be my cost function because my brute force also fails in same way.

lread18:12:19

But costs all look good for test data. So… must be something silly… but I don’t know what yet.

lread18:12:17

Oh yeah, very silly! I don’t know why I was, but I was answering the with the position and not the fuel cost.

🙌 2
lread18:12:00

I have no excuses. simple_smile

Stuart19:12:43

Can someone help with my code for part 2 today, I'm getting an arrity exception and I've not idea why. Code in thread in case it's a spoiler.

Stuart19:12:15

(defn build-row [min max n]
  (let [to-max (reductions + (u/range-inclusive 1 (- max n)))
        to-min (reverse (reductions + (u/range-inclusive min n)))]
    (concat to-min [0] to-max)))

(let [input (f/parse-csv-ints "puzzle-inputs/2021/day7-test")
      min (apply min input)
      max (apply max input)]
  (->> input
       (map (partial build-row min max) input)
       #_(apply map vector)
       #_(mapv #(reduce + 0 %))
       #_(sort)
       #_(first)))
I'm getting arrity exception in the call to to build-row , it says its getting 4 arguments

Stuart19:12:55

but i thought with partial, it will get min and max, that leaves one. Then it will get 1 from input. input here is a list like (1 0 16 2 1 0 4)

pithyless19:12:03

the input inside map

pithyless19:12:14

(->> input
       (map (partial build-row min max) input)

👍 1
Stuart19:12:22

oh balls! I missed that! so input is going in twice isnt it

☝️ 1
Pradeep B10:12:09

good catch @U05476190 and nice to see you around.

👋 1
tschady20:12:56

my 💰 is on a grid problem tonight

sarcilav20:12:44

mine on a graph one

Stuart20:12:19

please god, no graphs

Antonio Bibiano20:12:11

ahaha i bet on a "puzzle" thing

😩 1
Phil Shapiro21:12:40

I'm hoping for another interpreter / mini machine language one, those are pretty fun.

☝️ 3
tschady22:12:35

i’m still working on assembunny interpreter from 2016

Cora (she/her)21:12:20

I might mess with fennel for days 6 and 7

👍 1
Sidestep12:12:08

how come? how does it help?

Cora (she/her)12:12:10

just to learn something new ¯\(ツ)

lread23:12:54

Is that your fennel answer?

7
😂 6