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