3
\$\begingroup\$

My main concern is how messy the min-number-of-slices function is. I would appreciate help finding good ways to clean that up since it has a lot of nesting/scope.

This is my first ever Clojure program, so I know this is probably not idiomatic Clojure, nor is it neat, nor probably fast, either. Please give as much feedback as you would like on my code (especially regarding stuff that's bad about it).

The challenge is, given a list of 2D dimensions for pieces of bread, find the minimum number of perfect squares you could cut out of each piece without wasting any bread. https://www.hackerrank.com/challenges/restaurant

(ns clojure-solution.core)
(require '[clojure.string :as string])

(defn parse-int [s]
  (Integer. s))

(defn parse-line [s]
  (map parse-int (string/split s #" ")))

(defn get-loaf-dimensions []
  (let [numLoaves (parse-int (read-line))]
    (map #(%1) (repeat numLoaves (comp parse-line read-line)))))

(def squares (map #(* % %) (range 1 1001)))

(defn min-number-of-slices [dims]
  (let [l              (first dims)
        b              (second dims)
        area           (* l b)]
    (letfn [(perfect-slice-dimension? [slice-area]
              (= 0 (+ (mod area slice-area)
                      (mod b (int (Math/sqrt slice-area)))
                      (mod l (int (Math/sqrt slice-area))))))]
      (let [largest-square (last (filter perfect-slice-dimension? (take (min l b) squares)))]
        (int (/ area largest-square))))))

(defn -main [& args] (dorun (map println (map min-number-of-slices (get-loaf-dimensions)))))
\$\endgroup\$
  • \$\begingroup\$ Is this a bad question? \$\endgroup\$ – Josiah Dec 10 '14 at 21:22
  • 1
    \$\begingroup\$ It's a fine question. It's just that less-popular languages such as Clojure have a smaller pool of reviewers, so sometimes questions sit unanswered for a while. \$\endgroup\$ – 200_success Dec 12 '14 at 9:11
2
\$\begingroup\$
;(ns clojure-solution.core)
;(require '[clojure.string :as string])

Typically you only use the require, use, and import functions in the REPL. The ns macro supports all of those and it reduces the amount of quoting you need.

(ns clojure-solution.core
  (:require [clojure.string :as string]))

(defn parse-int [s]
  (Integer. s))

(defn parse-line [s]
  (map parse-int (string/split s #" ")))

Be careful with side effects (like read-line) in sequences. Your code definitely works because you force evaluation with dorun down in -main. You could also use doall here to evaluate the sequence and return the result.

(defn get-loaf-dimensions []
  (let [numLoaves (parse-int (read-line))]
    (map #(%1) (repeat numLoaves (comp parse-line read-line)))))

(def squares (map #(* % %) (range 1 1001)))

No huge changes here but using apply below lets you use ordinary arguments here instead of unpacking the list inside the function. Another option if you really needed to pass a list would be to use destructring: in this case (defn min-number-of-slices [[l b]]) would take the first two items of the list and bind them to l and b. Destructuring also works inside of let: (let [[l b] dims]])

Also you only need letfn if you have multiple functions that refer to each other. It's perfectly idiomatic Clojure to just bind an anonymous function to a name. My understanding is that letfn behaves more like let in Haskell (only restricted to just functions).

(defn min-number-of-slices [l b]
  (let [area (* l b)
        perfect-slice-dimension? 
        (fn [slice-area] 
              (= 0 (+ (mod area slice-area)
                      (mod b (int (Math/sqrt slice-area)))
                      (mod l (int (Math/sqrt slice-area))))))]
      (let [largest-square (last (filter perfect-slice-dimension? (take (min l b) squares)))]
        (int (/ area largest-square)))))

apply takes a function and a list (or anything that can be treated as a sequence) and uses the list as the arguments to the function:

(defn -main [& args] (dorun (map println (map (partial apply min-number-of-slices) (get-loaf-dimensions)))))
\$\endgroup\$
  • \$\begingroup\$ I'm choosing this one solely because it was the sort of feedback I was more looking for to learn the Clojure language better, but the other answer 200_success gave regarding the Euclidean algorithm is also excellent because it cuts more to the heart of the algorithm and the actual problem being solved. \$\endgroup\$ – Josiah Jan 4 '15 at 3:34
3
\$\begingroup\$

You've implemented a brute-force solution, trying every square dimension from 1 up to the minimum of l, b, and 1000.

The optimal square size is simply the greatest common divisor of l and b. A very simple algorithm to calculate the GCD is the Euclidean algorithm.

(defn gcd [a b]
      (if (= b 0) 
          a 
          (gcd b (mod a b))))

Calculating the minimum number of slices follows easily.

(defn min-number-of-slices [l b]
      (let [side (gcd l b)]
           (/ (* l b) (* side side))))

You can try calling min-number-of-slices in this ClojureScript demo:

.code { font-family: Monaco, monospace; font-size: 10pt; } #log { height: 10em; overflow: auto; white-space: pre-wrap; } #input { width: 100%; height: 12em; }
<script type="text/javascript" src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.1/jquery.min.js"></script><script type="text/javascript" src="https://kanaka.github.io/clojurescript/web/vendor/jq-console/jqconsole.min.js"></script><!-- script type="text/javascript" src="https://cdn.rawgit.com/google/closure-library/master/closure/goog/base.js"></script --><script type="text/javascript" src="https://kanaka.github.io/clojurescript/web/out/goog/base.js"></script><script type="text/javascript" src="https://kanaka.github.io/clojurescript/web/webrepl.js"></script><script type="text/javascript">goog.require('webrepl');</script>
<div id="log" class="code"></div><textarea id="input" class="code"
> (defn gcd [a b]
        (if (= b 0) 
            a             
            (gcd b (mod a b))))

  (defn min-number-of-slices [l b]  
        (let [side (gcd l b)]             
             (/ (* l b) (* side side))))

  (min-number-of-slices 6 9)
</textarea>

\$\endgroup\$
  • \$\begingroup\$ Excellent insight. I wish I could up-vote it twice. \$\endgroup\$ – Josiah Dec 12 '14 at 20:06
  • \$\begingroup\$ There is also Lehmer's algorithm. I think I'll try to implement them both in separate versions/files. en.wikipedia.org/wiki/Lehmer%27s_GCD_algorithm \$\endgroup\$ – Josiah Dec 12 '14 at 22:46

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.