6
\$\begingroup\$

I’ve been dabbling in Clojure by solving programming puzzles. This particular puzzle is from HackerRank, with the objective of figuring out how much chocolate one could eat given three parameters:

  • The cost of a piece of chocolate
  • How much money you have
  • The candy shop owner will give you a free chocolate for x number of wrappers

In the code below, those three numbers are passed to total-chocolates-consumed which returns the answer.

(ns hr.clojure.algorithms.implementation.implementation.chocolate-feast)

(defn int-division
  [numerator denominator]
  (->>
    (/ numerator denominator)
    int))

(defn number-to-purchase
  [totalToSpend costPerChocolate]
  (int-division
    totalToSpend
    costPerChocolate))

(defn number-of-freebies
  [totalWrappers wrappersPerFreebie]
  [(int-division
    totalWrappers
    wrappersPerFreebie)
   (int
     (mod
       totalWrappers
       wrappersPerFreebie))])

(defn total-chocolates-consumed
  [totalToSpend
   costPerChocolate
   wrappersPerFreebie]
   (let [purchasedChocolates (number-to-purchase totalToSpend costPerChocolate)
         freebies (first (number-of-freebies purchasedChocolates wrappersPerFreebie))
         totalChocolates [purchasedChocolates freebies]
         startRemainder (second (number-of-freebies purchasedChocolates wrappersPerFreebie))]
         (loop
           [chocs totalChocolates
            remainder startRemainder]
           (cond
            (> wrappersPerFreebie (+ remainder (last chocs)))
               (reduce + chocs)
             :else
              (recur
                (conj chocs (first (number-of-freebies (+ (last chocs) remainder) wrappersPerFreebie)))
                (second (number-of-freebies (+ (last chocs) remainder) wrappersPerFreebie)))))))

I've written tests for this code here:

(ns hr.clojure.algorithms.implementation.implementation.chocolate-feast.spec)

(load-file "YOUR-PATH-TO-FILE")
(use 'hr.clojure.algorithms.implementation.implementation.chocolate-feast)
(use 'clojure.test)

(deftest chocolate-feast
  (testing "number-to-purchase"
    (is (= 0 (number-to-purchase 2 10)))
    (is (= 2 (number-to-purchase 10 4)))
    (is (= 666 (number-to-purchase 1000 1.5)))
    (is (= 3 (number-to-purchase 6 2)))
    (is (= 5291 (number-to-purchase 10000 1.89))))
  (testing "number-of-freebies"
    (is (= [0 1] (number-of-freebies 1 2)))
    (is (= [100 0] (number-of-freebies 100 1)))
    (is (= [2 0] (number-of-freebies 3 1.5)))
    (is (= [1 1] (number-of-freebies 3 2))))
  (testing "total-chocolates-consumed"
    (is (= 6 (total-chocolates-consumed 10 2 5)))
    (is (= 3 (total-chocolates-consumed 12 4 4)))
    (is (= 5 (total-chocolates-consumed 6 2 2)))
    (is (= 899 (total-chocolates-consumed 43203 60 5)))))

(deftest math-library
  (testing "int-division"
    (is (= 0 (int-division 7 12)))
    (is (= 2 (int-division 12 6)))
    (is (= 2 (int-division 12 5)))))

(run-tests)

General Questions

  1. Is this how tests are written in Clojure?
  2. Is the code readable? Can you tell what I was thinking?

How idiomatic is my code?

  • Should I use camel case for parameter names?
  • Should I hyphenate my function names?
  • Is this “waterfall” sort of formatting typical?

What is a good way to communicate what a function does?

  • For instance, number-of-freebies returns a vector of [chocolates earned with wrappers, wrappers leftover]. Could I return a type that actually indicates what those values are to the consumer of that function?

How do I refactor total-chocolates-consumed to be less complex?

  • There is some redundant code in there for figuring the number of freebies, could I pull that out into a local value within the loop?
  • Should I be using a loop or some higher-order function?
\$\endgroup\$
8
\$\begingroup\$

General Questions

  1. Yes. Your tests are fine.
  2. I found the code hard to follow without the requirements. To some degree, that's to be expected. Even once I read the requirements, there were things that I found hard to follow. More on that later.

How idiomatic is my code?

  1. Never use camel case for your clojure-defined symbols.
  2. You should always use lower-cased, hyphenated names in Clojure.
  3. Your formatting was fine, except the let statement. It should be formatted like so:

    (let [my-thing :a
          other-thing :b]
      (code-that-does-stuff ...))
    

The clojure style guide should tell you everything you need to know about styling your code.

What is a good way to communicate what a function does?

This is a complex question. My first piece of advice is to accurately name the function. number-of-freebies implies a number, but you are returning a vector. So a more appropriate name might be division-tuple or, better, quotient-remainder-tuple.

Regarding return types, the options you have, in order of increasing ceremony, are:

  1. Return a tuple.
  2. Return a map whose keys denote the return values.
  3. Define a type or record.

For this example, I think a tuple is fine. If I thought the return value might need to expand in the future, I'd consider using a map. I generally use records and types when:

  • I'm designing a large(er) system (i.e. doing design work as opposed to implementing functions)
  • I want to reify a complex type
  • I want type dispatch

So, for something like this, I'd consider types to be a little overkill. Your tastes may vary.

How do I refactor total-chocolates-consumed to be less complex?

I implemented a solution in preparing your feedback, and the most straightforward method I could come up with on the fly was indeed recursive. Though, I will say this tends to be the kind of problem that you realize can be solved with map/reduce after a night or two of sleep.

There are two things you can do to make total-chocolates-consumed less complex:

  • Use destructuring:

    (let [[freebies startRemainder] (number-of-freebies purchasedChocolates wrappersPerFreebie)]
      ...)
    
  • Use more let statements. Specifically inside the loop-recur.

I have a version of total-chocolates-consumed that does those things if you want to see it. I thought you might like to take a stab at it before you see what I did.

Other Notes

When I moved from Java to Clojure, I tended to like very small functions (e.g. number-to-purchase or int-division). Over time, I've found it's a) more idiomatic and b) easier to read if you start with a rather large function and break it up as needed to increase understanding. My reasoning for this preference is that Clojure already gives you really good, simple building blocks. This allows you to define the simple functions that directly enrich your domain without worrying as much about length. If I want added documentation, I will let a variable with a good name.

On the topic of int-division, I'm pretty sure you can solve this problem with just quot and rem. Wasn't sure you were aware of those functions. Feel free to let me know if I'm mistaken there.

Lastly, in my solution, I tried to focus first on calculating the purchased chocolates, then on calculating the freebies, as opposed to creating a seq of all chocolates, then summing them up at the end. This separation of concerns allows you to structure the program intent clearly at the topmost level. It has the added benefit of making the recursive part of the program a bit more straightforward.


Update

Per OP's request, here is my solution:

(defn calculate-freebies [purchased-chocolates wrappers-per-freebie]
  (loop [remaining-wrappers purchased-chocolates
         free-chocolates 0]
    (if (< remaining-wrappers wrappers-per-freebie)
      free-chocolates
      (let [new-chocolates (quot remaining-wrappers
                                 wrappers-per-freebie)]
        (recur
          (+ (rem remaining-wrappers
                  wrappers-per-freebie)
             new-chocolates)
          (+ free-chocolates new-chocolates))))))

(defn calculate-chocos [bobs-money cost-of-chocolate wrappers-per-freebie]
  (let [purchased-chocolates (quot bobs-money
                                   cost-of-chocolate)
        freebies (calculate-freebies purchased-chocolates
                                     wrappers-per-freebie)]
    (+ purchased-chocolates freebies)))

Note that I did go ahead and pull out calculate-freebies into a separate defn. I did that because a) it's a standalone concept and b) it makes calculate-chocos easier to read. If it weren't a standalone concept, I would have likely defined it in the let of calculate-chocos itself.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thank you for the answer! It was extremely informative. I would love to see your implementation. I was unaware of quot and rem.The final paragraph is especially interesting and will likely transform the way I'm going about writing programs in Clojure. \$\endgroup\$ – Thomas Sobieck Aug 4 '15 at 12:30
  • 1
    \$\begingroup\$ @Sobieck I just updated my answer per your request. Please let me know if you need further clarification. \$\endgroup\$ – Tim Pote Aug 4 '15 at 12:53
3
\$\begingroup\$

You can use the sequence library to express total-chocolates-consumed concisely:

(defn total-chocolates-consumed [cash cost redeem-count]
  (let [bought (long (/ cash cost))
        redeem-seq (iterate
                    (fn [[chocs wrappers]] 
                      ((juxt quot mod) (+ chocs wrappers) redeem-count))
                    [bought 0])]
    (->> redeem-seq (map first) (take-while pos?) (reduce +))))

This will be considerably slower than yours, since iterate, map, and take-while build layers of lazy sequences.

You can recover some speed by using the transducer forms that arrived with Clojure 1.7. These build a composite function instead.

To do so, change the last line from

    (->> redeem-seq (map first) (take-while pos?) (reduce +))

... to

    (transduce (comp (map first) (take-while pos?)) + redeem-seq)

You can find a simple explanation of transducers in this answer.


I got this wrong at first, forgetting that you can redeem leftover wrappers afterwards.

\$\endgroup\$
  • \$\begingroup\$ I had the same problem with forgetting that aspect of the problem. It was a pretty quick fix. Trying to think of a test case was the hardest part. Thanks for input! \$\endgroup\$ – Thomas Sobieck Aug 4 '15 at 21:13
2
\$\begingroup\$

Tim Pote has many good points. I assume you've seen that answer first, and won't repeat every point.

I'll concentrate on this question:

How do I refactor total-chocolates-consumed to be less complex?

use if, instead of cond, if you can.

Instead of this:

(cond
  (> ....) (reduce + chocs)
  :else (recur ....))

You can do this:

(if (> ....) (reduce + chocs) (recur ....))

Note also in cond condition are vertically aligned on the left, so you can scan the cases handled top to bottom, and each consequent is aligned horizontally to its condition.

Similarly prefer apply over reduce whenever appropriate. As in (apply + chochs). In clojure appropriate operations such as +, *, and, etc all get variable number of arguments. Including zero arguments.

Now let's remove some of the repetition. We have 2 (+ (last chocs) remainder) and 1 (+ (last chocs) remainder). What is this number? It is the current number of wrappers. Let's name it as such:

(let [wrappers (+ remainder (last chocs))]
     (if (> wrappersPerFreebie wrappers)
         (apply + chocs)
         (recur
           (conj chocs (first (number-of-freebies wrappers wrappersPerFreebie)))
           (second (number-of-freebies wrappers wrappersPerFreebie)))))

Note alse (> wrappersPerFreebie wrappers) makes more sense than (> wrappersPerFreebie (+ remainder (last chocs))). Conditionals reading better is a sign of a good rename, and vice versa.

With clutter reduced it's obvious (number-of-freebies wrappers wrappersPerFreebie) is repeated also. Let's extract it also, and use destructuring as suggested by the linked answer above:

  (let [wrappers (+ remainder (last chocs))
        [freebies' remainder'] (number-of-freebies wrappers wrappersPerFreebie)]
    (if (> wrappersPerFreebie wrappers)
      (apply + chocs)
      (recur (conj chocs freebies') remainder'))))))

In loops you often calculate the next version of a variable. And making it clear in the names, makes reading easier. e.g. remainder and remainder'.

A similar repetition is also present here:

     freebies (first (number-of-freebies purchasedChocolates wrappersPerFreebie))
     ......
     startRemainder (second (number-of-freebies purchasedChocolates wrappersPerFreebie))]

We could do the same thing above. But I notice not only these two lines repeat each other but they are also the same calculations we do in the loop body. In fact this loop is unecessarily unrolled for its first iteration. If we start counting from zero, as programmers do, we get

(defn total-chocolates-consumed [totalToSpend costPerChocolate wrappersPerFreebie]
  (let [purchasedChocolates (number-to-purchase totalToSpend costPerChocolate)
        totalChocolates [purchasedChocolates]
        startRemainder 0]
    (loop
      [chocs totalChocolates
       remainder startRemainder]
      (let [wrappers (+ remainder (last chocs))
            [freebies' remainder'] (number-of-freebies wrappers wrappersPerFreebie)]
        (if (> wrappersPerFreebie wrappers)
          (apply + chocs)
          (recur (conj chocs freebies') remainder'))))))
\$\endgroup\$
  • \$\begingroup\$ Thank you for the great answer! It is extremely informative. I really love the end result. \$\endgroup\$ – Thomas Sobieck Aug 4 '15 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.