Как перевести этот алгоритм с Ruby на Clojure?

Question

Я решал задачу программирования на Ruby, и после ее завершения я подумал, что мне следует попробовать применить свои ограниченные знания Clojure для реализации того же самого. Я потратил немало времени, но не смог заставить его работать.

Задача: у нас есть массив типов монет и ожидаемая сумма. Как лучше всего представить ту сумму с имеющимися у нас типами монет, тратя минимальное количество монет. Таким образом, для представления 325 с типами монет [100, 50, 20, 10, 5] мы бы получили следующий результат: [100, 100, 100, 20, 5].

Вот мой код Ruby, который, кажется, работает:

  def calc(coin_types, expected)
    calc_iter(coin_types.sort.reverse, expected, [])
  end

  def calc_iter(coin_types, expected, coins)
    sum = coins.sum

    return coins if sum == expected
    return nil if sum > expected

    coin_types.each do |type|
      result = calc_iter(coin_types, expected, coins + [type])
      return result if result
    end

    nil
  end

  # test
  calc([25, 10], 65) # should return [25, 10, 10, 10, 10]

А теперь две из моих неудачных реализаций Clojure:

1) (чтобы бежать, нужно вечно, поэтому мне пришлось его убить):

  (defn calc [types expected]
    (let [types (reverse (sort types))]
      (loop [coins []]
        (let [sum (count coins)]
          (if (= sum expected)
            coins
            (if (> sum expected)
              nil
              (first (filter #(not (nil? %))
                             (map #(recur (cons % coins))
                                  types)))))))))

2) (этот завершает за разумное количество раз, но возвращает неправильный результат):

  (defn calc-iter [types expected coins]
    (let [sum (count coins)]
      (if (= sum expected)
        coins
        (if (> sum expected)
          nil
          (first (filter #(not (nil? %))
                         (map #(calc-iter types
                                          expected
                                          (cons % coins))
                              types)))))))

  (defn calc [types expected]
    (calc-iter (reverse (sort types))
               expected
               []))

Answer 1

Это крутая проблема, которую нужно решить с помощью логического программирования и core.logic .

. 1004 * Clojure. Сначала определите рекурсивную цель productsumo, которая принимает последовательность свежих логических переменных, наборконфессий, и сумма, которую мы хотим достичь.Эти свежие логические переменные в vars будут равны количеству монет для каждого номинала, когда эта цель будет успешной.

• Bind head и tail vars для обоихvars и dens.В каждой рекурсии мы будем решать только для head var и рекурсировать на tail до тех пор, пока у нас не закончится vars.
• Используйте арифметические функции изконечное доменное пространство имен, чтобы ограничить новые новые переменные product и run-sum таким образом, чтобы умножить каждый номинал на некоторое число, а затем добавить это к текущей сумме, в конечном итоге достигнув желаемой суммы (или нет)

(require '[clojure.core.logic.fd :as fd])

(defn productsumo [vars dens sum]
  (fresh [vhead vtail dhead dtail product run-sum]
    (conde
      [(emptyo vars) (== sum 0)]
      [(conso vhead vtail vars)
       (conso dhead dtail dens)
       (fd/* vhead dhead product)
       (fd/+ product run-sum sum)
       (productsumo vtail dtail run-sum)])))

Затем, чтобы использовать эту цель, проинформируйте ее о количестве и номиналах и заархивируйте каждый счет для каждого номинала в карту с номиналами:

(defn change [amount denoms]
  (let [dens (sort > denoms)
        vars (repeatedly (count dens) lvar)]
    (run* [q]
      (== q (zipmap dens vars))
      ;; prune problem space: must be 0 <= n <= amount
      (everyg #(fd/in % (fd/interval 0 amount)) vars)
      (productsumo vars dens amount))))

Вы можете получить все решения, позвонив по номеру change ссумма и набор номиналов:

(change 325 [100 50 20 10 5])
=>
({100 0, 50 0, 20 0, 10 0, 5 65}
 {100 1, 50 0, 20 0, 10 0, 5 45}
 {100 0, 50 1, 20 0, 10 0, 5 55}
 ...)

Каждое решение представляет собой карту от номиналов монет до количества монет, используемых для решения задачи.

Чтобы найти решение с наименьшим количествоммонет, вы можете sort-by значения / количество на каждой карте.Чтобы вернуть список значений монет, вы можете repeat ключи по значениям.

(->> (change 325 [100 50 20 10 5])
     (sort-by #(apply + (vals %)))
     (first)
     (mapcat #(repeat (val %) (key %))))
=> (100 100 100 20 5)

Answer 2

Мне нравится Ответ Тейлора , но в качестве прямого перевода от Руби вот моя версия:

(defn calc-iter [coin-types expected coins]
  (let [sum (reduce + coins)]
    (cond
      (= expected sum) coins
      (< expected sum) nil
      :else (->> coin-types
                (keep #(calc-iter coin-types expected (cons % coins)))
                first))))

(defn calc [coin-types expected]
  (calc-iter (->> coin-types sort reverse) expected nil))

(calc [25 10] 65)
;; => (10 10 10 10 25)

Оригинальный автор почти получил ее - нужно исправить только строку суммы монет.

Answer 3

Вот простой пример:

(def coin-values [100, 50, 20, 10, 5])

(defn coins-for-amount [amount]
  (loop [amount-remaining amount
         coins-avail      coin-values
         coins-used       []]
    (cond
      (zero? amount-remaining) coins-used ; success
      (empty? coins-avail) nil ; ran out of coin types w/o finding answer
      :else (let [coin-val              (first coins-avail)
                  num-coins             (quot amount-remaining coin-val)
                  curr-amount           (* coin-val num-coins)
                  amount-remaining-next (- amount-remaining curr-amount)
                  coins-avail-next      (rest coins-avail)
                  coins-used-next       (conj coins-used num-coins)]
              (recur amount-remaining-next coins-avail-next coins-used-next)))))


(coins-for-amount 325) => [3 0 1 0 1]
(coins-for-amount 326) => nil
(coins-for-amount 360) => [3 1 0 1]

Обратите внимание, что в текущей форме он не накапливает конечные нули.

---

Обновление

В моем первоначальном ответе выше я никогда не думал, что могут быть выбраны такие хитрые монеты, как [25 10], поэтому вам понадобится 1 квартал и 4 цента, чтобы получить в общей сложности 0,65 доллара. Приведенный выше алгоритм выбрал бы 2 квартала, а затем застрял с оставшимися $ 0,15 и только десять центов.

Если допускаются хитрые значения монет, вам необходимо использовать исчерпывающий алгоритм поиска. Вот одна версия в Clojure:

(ns tst.demo.core
  (:use tupelo.core demo.core tupelo.test))

(defn total-amount [coins-used]
  (let [amounts (mapv (fn [[coin-value num-coins]] (* coin-value num-coins))
                  coins-used)
        total   (reduce + amounts)]
    total))

(defn coins-for-amount-impl
  [coins-used coin-values amount-remaining]
  (when-not (empty? coin-values)
    (let [curr-coin-value       (first coin-values)
          coin-values-remaining (rest coin-values)
          max-coins             (quot amount-remaining curr-coin-value)]
      (vec (for [curr-num-coins (range (inc max-coins))]
             (let [coins-used-new       (conj coins-used {curr-coin-value curr-num-coins})
                   amount-remaining-new (- amount-remaining (* curr-coin-value curr-num-coins))]
               (if (zero? amount-remaining-new)
                 coins-used-new
                 (coins-for-amount-impl
                   coins-used-new coin-values-remaining amount-remaining-new))))))))

(defn coins-for-amount [coin-values amount]
  (remove nil?
    (flatten
      (coins-for-amount-impl {} coin-values amount))))

И несколько коротких юнит-тестов:

(dotest
  (is= 48 (total-amount {25 1    ; quarter
                         10 2    ; dime
                         1  3})) ; penny


  (let [results (coins-for-amount [10 5 1], 17)]
    (is= results
      [{10 0, 5 0, 1 17}
       {10 0, 5 1, 1 12}
       {10 0, 5 2, 1 7}
       {10 0, 5 3, 1 2}
       {10 1, 5 0, 1 7}
       {10 1, 5 1, 1 2}]))

  (is= (coins-for-amount [25 10], 65)
    [{25 1, 10 4}] ))

Таким образом, он находит все возможные комбинации, которые достигают правильной суммы. Подсчет монет и поиск решения с наименьшим количеством монет (не забывайте о галстуках!) Оставлено в качестве упражнения для читателя. ;)