Algorithm 2.7: Design an algorithm that accepts a positive integer and reverses the order of its digits.
Example: 27593 -> 39572
In the past I solved it by converting the number to string and reversing it. However, this time I want to use the arithmetic approach.
The idea is simple. We can divide our number by 10 and use its reminder.
27593 / 10 = 2759 reminder 3
2759 / 10 = 275 reminder 9
275 / 10 = 27 reminder 5
27 / 10 = 2 reminder 7
2 / 10 = 0 reminder 2
Now we have to multiply these numbers. There’s a simple imperative solution however I want to write a functional one.
What we want to calculate is:
2 * 10 ^ 0
+ 7 * 10 ^ 1
+ 5 * 10 ^ 2
+ 9 * 10 ^ 3
+ 3 * 10 ^ 4
= 39572
What’s really nice is that this we build a heap and pop it. This characteristic fits nicely with functional programming.
OK, let’s start with the get-digits
function:
(defn div-by-10 "Divides an integer without the reminder" [n] (let [new-mod (mod n 10)] (/ (- n new-mod) 10))) (defn get-digits "Returns a list of all digits of a number in right order" [n] (let [new-n (div-by-10 n) digit (mod n 10)] (if (= 0 new-n) [digit] (conj (get-digits new-n) digit))))
Nothing interesting happens there. I just return the digit which is the reminder. div-by-10
just divides the integer by 10 without the reminder, i.e. ‘clear’. E.g. 241 = 24 instead of 24.1. And that’s it. (Notice that mod and reminder are equal for positive numbers)
user=> (get-digits 67890) [6 7 8 9 0] user=> (get-digits 2345) [2 3 4 5]
I like to create intermediate sequences just for debugging purposes and it makes the functions smaller than one big one.
Now we can take a look at the final function reverse-digits
:
(defn reverse-digits "Reverses an positive integer" [n] {:pre [(pos? n)]} (reduce + (map-indexed get-multiplied (get-digits n))))
This function takes our get-digits
function which creates the vector. Firstly, it checks whether our input is positive. Also it takes an other function get-multiplied
. Also an quite uninteresting function:
(defn get-multiplied [i digit] (* digit (int (Math/pow 10 i))))
It just takes a digit and an i and applies: digit * 10 ^ i. The function applies incrementally to get-multiplied. Example:
digit_0 * 10 ^ 0
digit_1 * 10 ^ 1
which is exactly what we want. Now we have a list of multiplies of 10. In the case of [2 3 4] we get: [2 30 400]. The last step is to sum the result with reduce
and we’re done.
user=> (reverse-digits 2345) 5432 user=> (reverse-digits 67890) 9876
I noticed that I tend to rewrite a lot of functions in short intervals. For example, I’ve written a few functions which I deleted or changed while writing this code. I have this idea that there has to be an easier way to do something in Clojure. And often there is.