in Books, Doing Books, How to Solve it by Computer

How to Solve it by Computer #5

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:

 

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)

 

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:

 

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:

 

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.

 

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.

Write a Comment

Comment