This page is not created by, affiliated with, or supported by Slack Technologies, Inc.
2021-12-07
Channels
- # adventofcode (114)
- # announcements (3)
- # aws (5)
- # babashka (62)
- # beginners (111)
- # calva (4)
- # cider (20)
- # clara (5)
- # clj-kondo (1)
- # cljs-dev (9)
- # clojure (255)
- # clojure-europe (75)
- # clojure-italy (10)
- # clojure-nl (3)
- # clojure-norway (5)
- # clojure-uk (6)
- # clojuredesign-podcast (5)
- # clojurescript (34)
- # community-development (28)
- # conjure (1)
- # cursive (3)
- # data-science (1)
- # datavis (1)
- # datomic (4)
- # figwheel-main (1)
- # fulcro (14)
- # graalvm (1)
- # graphql (8)
- # integrant (4)
- # introduce-yourself (2)
- # jobs (2)
- # juxt (4)
- # kaocha (2)
- # malli (6)
- # membrane-term (53)
- # mount (2)
- # nextjournal (2)
- # off-topic (27)
- # pathom (11)
- # polylith (3)
- # portal (11)
- # reagent (4)
- # reitit (4)
- # remote-jobs (1)
- # reveal (14)
- # shadow-cljs (22)
- # tools-deps (24)
- # vim (6)
- # xtdb (19)
Too bad they didn't go a bit larger. ;D
(time (part-2 input 500))
"Elapsed time: 3.192168 msecs"
=> 2759581742718205387412N
(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
Just brute force https://github.com/zelark/AoC-2021/blob/main/src/zelark/aoc_2021/day_07.clj
nice use of frequencies
to skip over duplicates
https://github.com/kconner/advent-of-code/blob/master/2021/7a.clj, https://github.com/kconner/advent-of-code/blob/master/2021/7b.clj
https://github.com/axelarge/advent-of-code/blob/master/src/advent_of_code/y2021/day07.clj
(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)You can sort the input and do a binary search on it You can do a binary search on the possible positions
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
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))
realised after looking at part2 that mean will be good approach/ thanks @U1NLKFVC4
There are a bunch of bugs in my code actually, my the input is nice enough to give me the correct solution.
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
@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))
?
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
brute force solution, memoize fuel calculations https://github.com/jacoelho/advent-of-code-clj/blob/main/src/aoc/2021/day07.clj
@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.
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
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
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).
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))))))
binary search ~50ms https://github.com/callum-oakley/advent-of-code/blob/main/src/aoc/2021/07.clj
@U076FM90B your floor-median
should probably be floor-mean
?
Avoided doing too much maths 😅 https://github.com/v-garcia/aoc_2021/blob/main/day_seven.clj
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)
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
(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))
i decided to return two candidates for median and average just in case
and code: https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2021/day07.clj
ups, sorry, density was wrong... had to delete previous message above - submarine trace, below - initial density of submarines 🙂
Day 7 in #babashka and #clojure https://gist.github.com/borkdude/b5cf0e9d2d8ab7c678d88e27a3357b33#file-aoc21_07-clj
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
@UA2U3KW0L Awesome! How fast is yours?
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
nice! https://github.com/mknoszlig/aoc2021/commit/76ef20928dd59d3810ca5e04f7f879357389268b this is surprising for me
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
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/
if you have an intcode computer handy, there’s an easter egg in today’s puzzle :o

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
cheater version with credit given: https://github.com/tschady/advent-of-code/blob/main/src/aoc/2021/d07.clj
adding the type hints really changes the performance!! thanks @U04V15CAJ for pointing that out
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)))
; Syntax error (IllegalArgumentException) compiling fn* at (/home/antbbn/aoc_2021/day7.clj:63:1).
; Only long and double primitives are supported
but on the reference it says that int
is acceptable
but not as a type hint for a function arguments, you can use type hinting in any other places and there ^int
is possible.
for example, this is ok:
(defn cost-1 [[^int pos ^int crab]]
(Math/abs (- pos crab)))
Ah I see, I guess it's a bit off topic but do you know the reason for that?
yep, there is a stub for a function for every combination of arguments and returning value
@U01HY37QQUA it's here: https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/IFn.java#L97
oh wow
thanks 🙂
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
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
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
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.I derived the sum of the consumption of the crabs for an alignment x
https://twitter.com/MrEbbinghaus/status/1468359022453612549
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 😄
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..
Haha, it reminds me about day 22 last year https://adventofcode.com/2020/day/22
Uh oh, for me, part 1 test and real data work, part 2 test data works and real data fails. Hmm… dang.
What was your approach?
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.
Ah I see I did also a brute force approach but not optimized at all :D
I also did binary search, it could be either and error on the cost function or on the stop condition of the binary search
are you doing binary search over the range from min to max pos or just on existing positions?
I’m guessing it must be my cost function because my brute force also fails in same way.
But costs all look good for test data. So… must be something silly… but I don’t know what yet.
Oh yeah, very silly! I don’t know why I was, but I was answering the with the position and not the fuel cost.
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.
(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 argumentsbut 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)
I'm hoping for another interpreter / mini machine language one, those are pretty fun.
just to learn something new ¯\(ツ)/¯