Fork me on GitHub
#lambdaisland
<
2020-12-10
>
plexus07:12:02

going live in a few moments https://youtu.be/VnXw58zGqDs

plexus07:12:07

Been having some setup issues... new stream link https://youtu.be/1yLBj6kYTKc

pez12:12:36

I went for combinatorics and found this solution which runs in 1ms with my input data:

(defn ! [n]
  (reduce *' (range 1 (inc n))))

(defn combinations [n r]
  (if (= 1 n)
    0
    (let [n! (! n)
          r! (! r)
          r-n! (! (- n r))]
      (/ n! (* r! r-n!)))))

(->> parsed-input
     (sort)
     (cons 0)
     (#(concat % [(+ 3 (last %))]))
     (partition 2 1)
     (map #(- (second %) (first %)))
     (partition-by identity)
     (keep #(seq (filter #{1} %)))
     (map count)
     (map #(inc (combinations % 2)))
     (apply *))
(Maybe I should memoize the factorial function? But doesn’t much matter on my input maybe, where the longest 1-distance streaks are 7.)

plexus13:12:00

got a solution now as well, much more complex then it needs to be, but also runs in ~2ms

plexus13:12:48

reusing my earlier combos function, but only applied to sections of the input. Basically I look for elements that can't be removed, use those to split the input in two parts, do that recursively until I can't split it further, then count the combinations for the parts and multiply them.

plexus13:12:10

(defn divide [input]
  (let [split-points (remove #(can-be-removed? input %) (range 1 (dec (count input))))]
    (if (seq split-points)
      (let [split-idx (long (nth split-points (quot (count split-points) 2)))
            left (take (inc split-idx) input)
            right (drop split-idx input)]
        [left right])
      (combos (vec input) 1))))

(defn conquer [input]
  (let [parts (divide input)]
    (if (number? parts)
      parts
      (apply * (map conquer parts)))))

(time 
 (let [input (add-boundaries real-input)]
   (conquer input)))
;; => 396857386627072

pez13:12:02

It’s quite similar to what I do. Even though I do not actually do it.

pez13:12:45

However, my solution relies on the fact that there are never gaps other than 3 or 1. Not sure you can actually assume that from the problem description…

plexus13:12:36

hah, I don't think they specify that. that would make it easier I guess

pez13:12:05

That’s how the input data looks. ¯\(ツ)

pez20:12:00

Criterium reports 140 µs for my solution actually. So it’s worth doing it the mathy way, I think.