2
\$\begingroup\$

I am trying to learn Clojure for some time. In my experience, it has been rather too easy to produce write-only code.

Here is a solution to a simple problem with very little essential complexity. Input and output formats are extremely simple, too. Which means all complexity in it must be accidental. How to improve its legibility, intelligibility?

  • Is the decomposition of the problem into functions all right?

Also other specific problems:

  • How to input/output numbers? Is there any benefit to use read-string instead of Double/parseDouble? How to format floating point numbers to fixed precision without messing with the default locale?

  • How to avoid the explicit loop/recur, which is currently a translation of a while loop?

  • Are there definitions that should/shouldn't have bee private/dynamic?

Problem

You start with 0 cookies. You gain cookies at a rate of 2 cookies per second [...]. Any time you have at least C cookies, you can buy a cookie farm. Every time you buy a cookie farm, it costs you C cookies and gives you an extra F cookies per second.

Once you have X cookies that you haven't spent on farms, you win! Figure out how long it will take you to win if you use the best possible strategy.

(ns cookie-clicker
  (:use [clojure.string :only [split]])
  (:require [clojure.java.io :as io]
            [clojure.test :refer :all]))

;;See http://code.google.com/codejam/contest/2974486/dashboard#s=p1

(defn parse-double [s] (java.lang.Double/parseDouble s))

(defn parse-row [line] 
  (map parse-double (split line #"\s+")))

(defn parse-test-cases [rdr]
  (->> rdr
    line-seq
    rest
    (map parse-row)))

(def initial-rate 2.0)

(defn min-time [c f x]
  (loop [n 0 ; no of factories used
         tc 0 ; time cost of factories built
         r initial-rate ; cookie production rate
         t (/ x r)] ; total time
    (let [n2 (inc n)
          tc2 (+ tc (/ c r))
          r2 (+ r f)
          t2 (+ tc2 (/ x r2))]
      (if (> t2 t) 
        t
        (recur n2 tc2 r2 t2)))))

(java.util.Locale/setDefault (java.util.Locale/US))

(defn ans [n t]
  (str "Case #" n ": " (format "%.7f" t))) 

(defn answers [test-cases]
  (map #(ans %1 (apply min-time %2)) 
       (rest (range))
       test-cases))

(defn spit-answers [in-file]
  (with-open [rdr (io/reader in-file)]
    (doseq [answer (answers (parse-test-cases rdr))]
      (println answer))))

(defn solve [in-file out-file]
  (with-open [w (io/writer out-file :append false)]
    (binding [*out* w]
      (spit-answers in-file))))

(def ^:dynamic *tolerance* 1e-6)

(defn- within-tolerance [expected actual] 
  (< (java.lang.Math/abs (- expected actual)) 
     *tolerance*))

(deftest case-3 
    (is (within-tolerance 
          63.9680013
          (min-time 30.50000 3.14159 1999.19990))))

(defn -main []
  (solve "resources/cookie_clicker/B-large-practice.in" 
         "resources/cookie_clicker/B-large-practice.out"))
\$\endgroup\$
3
\$\begingroup\$

I have to admit, the actual "solving the problem" component of this is a little over my head. But, I thought I'd try to answer your questions and give you some style/structure feedback, for what it's worth :)

You can simplify your ns declaration like this:

(ns cookie-clicker
  (:require [clojure.string :refer (split)]
            [clojure.java.io :as io]
            [clojure.test :refer :all]))

(:require foo :refer (bar) does the same thing as :use foo :only (bar), and is generally considered preferable, especially as an alternative to having both :use and :require in your ns declaration)

I think Double/parseDouble is a good approach to parsing doubles in string form. Integer/parseInt is usually my go-to for doing the same with integers in string form. This is just a hypothesis, but Double/parseDouble might be faster and/or more accurate than read-string because it's optimized for doubles.

FYI, you can leave out the java.lang. and just call it as Double/parseDouble in your code. In light of that, you might consider getting rid of your parse-double function altogether and just using Double/parseDouble whenever you need it. The only thing is that Java methods aren't first-class in Clojure, so you would need to do things like this if you go that route:

(defn parse-row [line]
  (map #(Double/parseDouble %) (split line #"\s+")))

(Personally, I still like that better, but you might prefer to keep it wrapped in a function parse-double like you have it. It's up to you!)

I think needing to mess with the locale might be a locale-specific problem... I tried playing around with (format "%.7f" ... without changing my locale and it worked as expected. Granted, I'm in the US :)

I think the legibility issues you're seeing might be related to having too many functions. You might consider condensing and renaming things and see if you like that better. I would re-structure your program so that you parse the data into the data structure at the top, something like this:

(defn parse-test-cases [in-file]
  (with-open [rdr (io/reader in-file)]
    (let [rows (rest (line-seq rdr))]
      (map (fn [row] 
             (map #(Double/parseDouble %) (split row #"\s+")))
           rows))))

(I condensed your functions parse-row, parse-test-cases and half of spit-answers into the function above)

Then define the functions that "do all the work" like min-time, and then, at the end:

(defn spit-answers [answers out-file]
  (with-open [w (io/writer out-file :append false)]
    (.write w (clojure.string/join "\n" answers)))

(def -main []
  (let [in  "resources/cookie_clicker/B-large-practice.in"
        out "resources/cookie_clicker/B-large-practice.out"
        test-cases (parse-test-cases in)
        answers (map-indexed (fn [i [c f x]]
                               (format "Case #%d: %.7f" (inc i) (min-time c f x)))
                             test-cases)]
    (spit-answers answers out)))

I came up with a few ideas above:

  1. In your answers function you use (map ... (rest (range)) (test-cases)) in order to number each case, starting from 1. A simpler way to do this is with map-indexed. I used (inc i) for the case numbers, since the index numbering starts at 0.

  2. I condensed (str "Case #" n ": " (format "%.7f" t))) into a single call to format.

  3. I used destructuring over the arguments to the map-indexed function to represent each case as c f x -- that way it's clearer that each test case consists of those three values, and you can represent the calculation as (min-time c f x) instead of (apply min-time test-case).

As for your min-time function, I don't think loop/recur is necessarily a bad thing, and I often tend to rely on it in complicated situations where you're doing more involved work on each iteration, checking conditions, etc. I think it's OK to use it here. But if you want to go a more functional route, you could consider writing a step function and creating a lazy sequence of game states using iterate, like so:

(note: I'm writing step as a letfn binding so that it can use arbitrary values of c, f and x that you feed into a higher-order function that I'm calling step-seq -- this HOF takes values for c, f and x and generates a lazy sequence of game states or "steps.")

(defn step-seq [c f x]
  (letfn [(step [{:keys [factories time-cost cookie-rate total-time result]}]
            (let [new-time-cost (+ time-cost (/ c cookie-rate))
                  new-cookie-rate (+ cookie-rate f)
                  new-total-time (+ new-time-cost (/ x new-cookie-rate))]
              {:factories (inc factories)
               :time-cost new-time-cost
               :cookie-rate new-cookie-rate
               :total-time new-total-time
               :result (when (> new-total-time total-time) total-time)}))]
    (iterate step {:factories 0, :time-cost 0, :cookie-rate 2.0, 
                   :total-time (/ x 2.0), :result nil})))

Now, finding the solution is as simple as grabbing the :result value from the first step that has one:

(defn min-step [c f x]
  (some :result (step-seq c f x)))
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for the answer. As for spit-answers, I'd thought writing answers of test cases one by one would reduce memory requirement, but after reading your answer I realize the memory burden of the join would probably would be on the order of KBs for the majority of cases (and possibly having multiple disk seeks could hurt performance more). \$\endgroup\$ – abuzittin gillifirca May 13 '14 at 10:45

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.