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:

 

(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.

How to Solve it by Computer #4

Problem 2.4.3: Design an algorithm to determine whether or not a number n is a factorial number.

I thought a bit about the design choices. I think the simplest solution is just by dividing i starting with 2 until it reaches one. There are several tricks which can be used. And my first idea was to use dynamic programming and work backwards which could use pretty fast. On the other hand division is also pretty fast in this case.

Here’s the code. Pretty straight forward:

(defn isfactorial?
  [n]
  (loop [i 1
         n n]
    (cond (= n 1) true
          (< n 1) false
          :else (recur (inc i) (/ n i)))))

We continuously divide by 1, 2, 3, etc. If the result is 1 then it is a factorial. If the result is smaller than 1 then it isn’t.

 

user=> (isfactorial? 2)
true
user=> (isfactorial? 4)
false
user=> (isfactorial? 6)
true
user=> (isfactorial? 5040)
true
user=> (isfactorial? 15511210043330985984000000)
true
user=> (isfactorial? 15511210043330985984000002)
false

Problem 2.4.4: Design an algorithm which, given some integer n, finds the largest factorial number present as a factor in n.

The problem isn’t that interesting in itself but the solution is nice because we already got it for free. Why you ask? Look back at the function. This number is i – 1, in case the number is a factorial and otherwise i – 2. Why? Firstly, we increment i each time we call – basically beforehand. That’s why we need to decrement it by one in any case. In the case that it isn’t an factorial we also try to get smaller than one, i.e. we need one more division. Therefore, we decrement this i by 2.

(defn nearest-factorial
  [n]
  (loop [i 1
         n n]
    (cond (= n 1) (- i 1)
          (< n 1) (- i 2)
          :else (recur (inc i) (/ n i)))))

 

How to Solve it by Computer #3

Problem 2.3.5: Develop an algorithm to compute the sums for the first n terms of the following series:

(a) s = 1 + 2 + 3 + ...
(b) s = 1 + 3 + 5 + ...
(c) s = 2 + 4 + 6 + ...
(d) s = 1 + 1/2 + 1/3 + ...

I want to generalize a function to create all these sums. Also there’s one from

Problem 2.3.8: Develop an algorithm to compute the sum of the first n terms of the series

s = 1 - 3 + 5 - 7 + 9 - ...

which should also be solved by the function.

One can easily see that all follow the general pattern on s = a_1 + a_2 + ... aka. a sum. The only thing that changes is the value of a_i. Let’s look at the individual patterns (I call 2.3.8 (e)):

(a) start = 1, increment = + 1
(b) start = 1, increment = + 2
(c) start = 2, increment = + 2
(d) start = 1, increment = ?
(e) start = 1, increment = ?

Let’s take a look at (d) first. It doesn’t follow the ‘increment’ formula so easy. However, we can see that it follows an other formula: 1/1 + 1/2 + 1/3 which is inversed. That is, we generally need the previous value to create the next one.

When we take a look at (e) we can see, that it also depends on the previous value. 1, -3, 5, -7. Generally it adds two but changes the sign. Now we can extend our table.

(a) start = 1, increment = previous + 1,
(b) start = 1, increment = previous + 2
(c) start = 2, increment = previous + 2
(d) start = 1, increment = (1 / ((1 / previous) + 1) )
(e) start = 1, increment = (abs(previous) + 2) * (-1)

I just want to explain quickly how I got the increments for (d) and (e). An example is always good.

For 1/2 we take the inverse which is (1 / (1/2)) = 2, add one which makes it 3 and take the inverse, which makes it 1/3. Done.
For (e) we add 2 to the absolute value (abs(-2) = 2), which is trivial and multiply it by -1 which just changes the sign. Example: 2 * -1 = -2, and -3 * -1 = 3.

Now, let’s write some code. I’m currently learning Clojure, so that’s my choice.

Clojure has some cool functions for doing that which I will use. Let’s start with the first series. The function is pretty straight forward:

(defn add-one
  [previous]
  (+ previous 1)) 

It takes a number and adds one. Looks good. One noticeable thing is that we also have the start attribute. And when you think about it it’s the same as the previous for the first call.

Here’s my function return-series which actually returns the series of terms. It’s evaluated lazily therefore it isn’t that problematic on the resources. Also it helps debugging the software in case something breaks.

(defn return-series
  "Returns a series of a given series which is generated
  by the function increment. This function takes a parameter
  which is the previous value"
  [start increment]
  (lazy-seq 
    (let [value (increment start)]
      (cons start (return-series value increment)))))

Here’s an example with the add-one function:

user=> (take 4 (return-series 1 add-one))
(1 2 3 4)

I need the take function because otherwise the return-series function creates an infinite series. Here are the functions for each series:

(defn add-one
  [previous]
  (+ previous 1)) 

(defn add-two
  [previous]
  (+ previous 2))

(defn inverse-add
  [previous]
  (/ 1 (+ 1 (/ 1 previous))))

(defn sign-add
  [previous]
  (* -1 (+ (abs previous) 2)))

Which return the sequence like we wanted:

user=> (take 4 (return-series 1 add-two))
(1 3 5 7)
user=> (take 4 (return-series 2 add-two))
(2 4 6 8)
user=> (take 4 (return-series 1 inverse-add))
(1 1/2 1/3 1/4)
user=> (take 4 (return-series 1 sign-add))
(1 -3 -5 -7)

Now that we verified that the terms look correct, we can call get-sum:

(defn get-sum
  "Returns the sum of a given start value, number of
   elements and function"
  [start n function]
  (reduce + (take n (sum-series start function))))
user=> (get-sum 1 10 add-two)
120
user=> (get-sum 1 10 inverse-add)
55991/27720

It works.

How to Solve it by Computer #2

Problem 2.1.4: Given two variables of integer type a and b, exchange their values without using a third temporary variable

I read about a nifty trick doing this a few years ago but I don’t remember it. So let’s try to figure it out. It’s quite clear that we have to do something to both variables so that we can calculate the one from the other. So, the first step is something like that:

A = A ? B
B = B

A simple idea would be to shift the bits which only works if we have enough space. An example would be if we have A = 1011 and B = 1111 in this case we could create shift B by 4 to create A = B = 1111 1011. And then take the first 4 bits for A and the last 4 bits for B.

Let’s think about a solution using the decimal system. Taking an example is easier: A = 12 and B = 4; I wanted to avoid using two prime numbers which would make that easier. Let’s try multiplication:

A = 12
B = 4

A = A * B = 48
B = A / B = 48 / 4 = 12
A = A / B = 48 / 12 = 4

Another example:

A = 7
B = 20
A = A * B = 140
B = A / B = 140 / 20 = 7
A = A / B = 140 / 7 = 20

I’m surprised but it works. Cool :)