Clojurians Log v2
lambdaisland
going live in a few moments https://youtu.be/VnXw58zGqDs
Been having some setup issues... new stream link https://youtu.be/1yLBj6kYTKc
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 *))got a solution now as well, much more complex then it needs to be, but also runs in ~2ms
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.
(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)))
;; => 396857386627072It’s quite similar to what I do. Even though I do not actually do it.
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…
hah, I don't think they specify that. that would make it easier I guess
That’s how the input data looks. ¯\(ツ)/¯
Criterium reports 140 µs for my solution actually. So it’s worth doing it the mathy way, I think.
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 *))got a solution now as well, much more complex then it needs to be, but also runs in ~2ms
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.
(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)))
;; => 396857386627072It’s quite similar to what I do. Even though I do not actually do it.
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…
hah, I don't think they specify that. that would make it easier I guess
That’s how the input data looks. ¯\(ツ)/¯
Criterium reports 140 µs for my solution actually. So it’s worth doing it the mathy way, I think.