Clojurians Log v2

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

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.

I have no excuses. simple_smile

good catch @pithyless and nice to see you around.

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

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)

the input inside map

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

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

thank you

Happy to duckie :)

mine on a graph one

please god, no graphs

i’m still working on assembunny interpreter from 2016

how come? how does it help?

just to learn something new ¯\(ツ)/¯

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

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

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

oh, great catch!

tossing in a pmap seems like the easiest win

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

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

binary search ~50ms https://github.com/callum-oakley/advent-of-code/blob/main/src/aoc/2021/07.clj

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

thank you! fixed

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

https://github.com/benjamin-asdf/advent-of-code-2021/blob/master/src/day7.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

@felipecortezfi Awesome! How fast is yours?

Not that it matters, just wondering

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

this is because of laziness probably which escapes the time call

yeah, mapv yields "Elapsed time: 11779.226753 msecs"

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

Math/abs reflects in the absence of type hints

oh! makes sense

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/

woah! :)

welp, time to update my code 🙂

oh, to be young again

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

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

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

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

or this:

(defn cost-1 [pos crab]
  (Math/abs (- ^int pos ^int 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

@antbbn 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 derived the sum of the consumption of the crabs for an alignment x https://twitter.com/MrEbbinghaus/status/1468359022453612549

https://gitlab.com/maximoburrito/advent2021/-/blob/main/src/day7/main.clj

https://github.com/jhny/adventofcode2021/blob/main/src/day7.clj

(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

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

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

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

https://github.com/jreighley/aoc2021/blob/master/src/day7.clj

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

(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 @peterc

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

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

I got bitten by that mistake after reading this!

I also stated with this “tactic”.