https://projecteuler.net/problem=78

euler.clj

(ns com.github.hindol.euler
  (:require
   [clojure.test :refer [is]]
   [clojure.tools.trace :refer [trace-ns untrace-ns]])
  (:gen-class))

(set! *unchecked-math* true)
(set! *warn-on-reflection* true)

(defn pentagonal-seq
  []
  (let [xf (comp
            (mapcat (juxt identity -))
            (map #(/ (* % (dec (* 3 %))) 2)))] ;; k (3k - 1) / 2
    (sequence xf (iterate inc 1))))

(def cached-pentagonal-seq
  (pentagonal-seq))

;; https://projecteuler.net/problem=78
;;
;; *
;;
;; **
;; * *
;;
;; ***
;; ** *
;; * * *
;;
;; ****
;; *** *
;; ** **
;; ** * *
(def count-partitions
  "Given n coins, how many distinct partitions are possible?"
  (memoize
   (fn
     [n]
     {:pre  [(is (not (neg? n)))]
      :post [(is (not (neg? %)))]}
     (cond
       (neg? n)  0
       (zero? n) 1
       :else     (let [xf    (comp
                              (take-while #(<= % n))
                              (map #(count-partitions (- n %))))
                       terms (sequence xf cached-pentagonal-seq)
                       signs (cycle [+1 +1 -1 -1])]
                   (reduce +' (map * signs terms)))))))

(defn -main
  [& _]
  (let [n  6
        xf (comp
            (map count-partitions)
            (take-while #(pos? (rem % 1000000))))]
    (+ n (count (sequence xf (iterate inc n))))))

(time (-main))

Evaluating file: euler.clj
"Elapsed time: 14151.4932 msecs"

=> ######

Reference implementation in C++: https://euler.stephan-brumme.com/78/
Runs in ~100ms.

I got curious about this, and tried a jab at it. I got it to be much closer to the C++ time. On my machine it takes 150ms, and on repl.it where I'm comparing it against the C++ version as well, the C++ takes ~1s on repl.it and my Clojure solution takes ~3s.

C++ running on repl.it: https://repl.it/@didibus/stephan-brumme-euler-78 [around 1 second]
Clojure running on repl.it: https://repl.it/@didibus/stephan-brumme-euler-78-clj-port [around 3 second]

Here's the code:

(set! *unchecked-math* true)

(def ^:const modulo
  1000000)

(def ^:const limit
  100000)

(defn solve []
  (let [partitions (doto (int-array limit) (aset 0 1))]
    (loop [n 1]
      (if (<= n limit)
        (let [sum (unchecked-long
                    (loop [sum 0 i 0]
                      (let [alternate (+ 1 (quot i 2))
                            alternate (if (= 1 (rem i 2)) (- alternate) alternate)
                            offset (quot (* alternate (dec (* 3 alternate))) 2)]
                        (if (< n offset)
                          sum
                          (if (< (rem i 4) 2)
                            (recur (rem (+ sum (aget partitions (- n offset))) modulo) (inc i))
                            (recur (rem (- sum (aget partitions (- n offset))) modulo) (inc i)))))))
              sum (if (neg? sum) (+ sum modulo) sum)]
          (if (zero? sum)
            n
            (do
              (aset partitions n sum)
              (recur (inc n)))))
        n))))

(time (solve))

It's pretty much a straight port of the C++ solution.

I also played a bit with it, and it is such a hot loop, that it is very sensitive to any kind of overhead.

• Changing the array for a java mutable ArrayList adds about 250ms extra.
• Changing the array for a Clojure immutable vector adds 1s extra.
• Changing the array for a Clojure transient vector adds 650ms extra.
• Trying to use transducers to generate the offset adds 3.15s extra.
• Trying to add lazy-seqs to generate the offset adds 9s extra.
• Presence of reflection and boxed math adds 700ms extra.

This is the most simple port to Clojure, without unchecked math, without any casting or type hinting, using immutable data-structures:

(def modulo
  1000000)

(def limit
  100000)

(defn solve []
  (loop [n 1 partitions [1]]
    (if (<= n limit)
      (let [sum (loop [sum 0 i 0]
                  (let [alternate (+ 1 (quot i 2))
                        alternate (if (= 1 (rem i 2)) (- alternate) alternate)
                        offset (quot (* alternate (dec (* 3 alternate))) 2)]
                    (if (< n offset)
                      sum
                      (if (< (rem i 4) 2)
                        (recur (rem (+ sum (nth partitions (- n offset))) modulo) (inc i))
                        (recur (rem (- sum (nth partitions (- n offset))) modulo) (inc i))))))
            sum (if (neg? sum) (+ sum modulo) sum)]
        (if (zero? sum)
          (count partitions)
          (recur (inc n) (conj partitions sum))))
      (count partitions))))

(time (solve))

And still on my machine (a 2012 dell xps 13) it just takes 2.1s total. So 2s extra then the C++ version. On repl.it it takes 15s.

So my impression would be that, I think what you are doing is a different algorithm. One thing I've noticed, your take-while goes really big, the number passed to it exceeds the size of long, which is why you need to use +' in your reduce, but the algorithm I copied from C++ never reaches such high n.

For posterity, here it is with the transducer:
Takes 4.2s on my machine.

(set! *unchecked-math* true)

(def ^:const modulo
  1000000)

(def ^:const limit
  100000)

(defn solve []
  (loop [n 1 partitions (vector-of :long 1)]
    (if (<= n limit)
      (let [sum (unchecked-long
                  (loop [sum 0 i 0 offsets (sequence (comp (mapcat (juxt identity -))
                                                           (map (fn [^long %] (quot (* % (dec (* 3 %))) 2))))
                                                     (iterate inc 1))]
                    (let [offset (unchecked-long (first offsets))]
                      (if (< n offset)
                        sum
                        (if (< (rem i 4) 2)
                          (recur (rem (+ sum (unchecked-long (nth partitions (- n offset)))) modulo) (inc i) (rest offsets))
                          (recur (rem (- sum (unchecked-long (nth partitions (- n offset)))) modulo) (inc i) (rest offsets)))))))
            sum (if (neg? sum) (+ sum modulo) sum)]
        (if (zero? sum)
          (count partitions)
          (recur (inc n) (conj partitions sum))))
      (count partitions))))

(time (solve))