SPOJ: 3442. The last digit

Nestor was doing the work of his math class about three days but he is tired of make operations a lot and he should deliver his task tomorrow. His math’s teacher gives two numbers a and b. The problem consist in find the last digit of the potency of base a and index b. Help Nestor with his problem. You are given two integer numbers: the base a (0 <= a <= 20) and the index b (0 <= b <= 2,147,483,000). You have to find the last digit of a^b.

Problem: Sphere Online Judge (SPOJ) – Problem LASTDIG

Solution: I don’t really have an background in number theory, so I decided to approach this problem empirically. My main source of information was this small Python program:

for i in xrange(1, 20):
    print i, str(base ** i)[-1:]

I checked the last digit for each base (0..20) and looked for patterns. Happily, I found them. Here’s a snippet:

x > 0

0 ^ x => 1
1 ^ x => 1
2 ^ x => 2^1 -> 2
         2^2 -> 4
         2^3 -> 8
         2^4 -> 6

3 ^ x => 3^1 -> 3
         3^2 -> 9
         3^3 -> 7
         3^4 -> 1

4 ^ x => 4^1 -> 4
         4^2 -> 6

5 ^ x => 5

The rest is straight forward and thanks to the 700B source code size limitations, the source code is pretty unreadable. ;)

Concrete Abstractions: Chapter 3

Let’s call the number of people in the circle n and number the positions from 1 to n. We’ll assume that the killing of every third person starts with killing the person in position number 3. […]
As we saw above, if the person we care about is in position 3, that person is the one killed and hence definitely not a survivor:
(define survives?
  (lambda (position n)
    (if (< n 3)
      #t
      (if (= position 3)
       #f
    ;we still need to write this part))))
Suppose we aren’t interested in the person in position number 3 but rather in some other person—let’s say J. Doe. The person in position number 3 got killed, so now we only have n – 1 people left. Of that smaller group of n – 1, there will still be two survivors, and we still want to know if J. Doe is one of them.

Exercise 3.9 How about the people who were in positions 1 and 2; what position numbers are they in after the renumbering?

Solution: In the example there were 8 persons at the start. After killing #3, the new #1 is #4, the new #2 is #5*, etc. #2 is #(n-1) and #1 is #(n-2).

*: clearly a reference to the Prisoner ;)

Exercise 3.10 Write a procedure for doing the renumbering. It should take two arguments: the old position number and the old number of people (n). (It can assume that the old position number won’t ever be 3, because that person is killed and hence doesn’t get renumbered.) It should return the new position number.

Solution:

(define renumber
  (lambda (position n)
   (if (< position 3)
     (+ position (- n 3))
     (- position 3))))

Exercise 3.11 Finish writing the survives? procedure, and carefully test it with a number of cases that are small enough for you to check by hand but that still cover an interesting range of situations.

Solution:

(define survives?
  (lambda (position n)
    (if (< n 3)
      #t
      (if (= position 3)
        #f
        (survives? (renumber position n) (- n 1))))))

I made a table for testing if the program works correctly. Each line represents a new round, i.e. somebody got killed. The killed person is labeled with X.

1 2 3 4 5 6 7 8
6 7 X 1 2 3 4 5
3 4   5 6 X 1 2
X 1   2 3   4 5
  3   4 X   1 2
  X   1     2 3
              X

Exercise 3.15 Consider the following two procedures:

(define f 
  (lambda (n)
    (if (= n 0)
      0
      (g (- n 1)))))

(define g 
  (lambda (n)
    (if (= n 0)
      1
      (f (- n 1)))))

a. Use the substitution model to evaluate each of (f 1), (f 2), and (f 3).
b. Can you predict (f 4)? (f 5)? In general, which arguments cause f to return 0 and which cause it to return 1? (You need only consider nonnegative integers.)
c. Is the process generated by f iterative or recursive? Explain.

Solution: a. I started to define each function mathematically. $f(0) = 0, f(n) = g(n-1)$ and $g(0) = 1, g(n) = f(n-1)$ . Now we can see what’s happening.
$f(1) = g(0) = 1$
$f(2) = g(1) = f(0) = 0$
$f(3) = g(2) = f(1) = g(0) = 1$
b. You see that odd numbers lead to $g(0) = 1$ and even numbers lead to $f(0) = 0$ .
c. I would say that f’s process iterative because you could stop at any time and just continue later with the saved parameters.

Exercise 3.16 Consider the following two procedures:

(define f (lambda (n)
  (if (= n 0)
  0
  (+ 1 (g (- n 1))))))

(define g (lambda (n)
  (if (= n 0)
  1
  (+ 1 (f (- n 1))))))

a. Use the substitution model to illustrate the evaluation of (f 2), (f 3), and (f 4).
b. Is the process generated by f iterative or recursive? Explain. c. Predict the values of (f 5) and (f 6).

Solution: a. Same trick at last time.
$f(0) = 0, f(n) = 1 + g(n-1)$ and $g(0) = 1, g(n) = 1 + f(n - 1)$
Therefore: $f(2) = 1 + g(1) = 1 + (1 + f(0)) = 1 + 1 + 0 = 2$
$f(3) = 1 + g(2) = 1 + (1 + f(1)) = 1 + (1 + (1 + g(0)))$ $1 + (1 + (1 + 1) = 3$
$f(4) = 1 + g(3) = 1 + (1 + f(2)) = 1 + (1 + (1 + g(1)))$ $= 1 + (1 + (1 + (1 + f(0)))) = 3$

b. The process is recursive because you can’t just stop and continue later. This happens because of the (+ 1 f) which have to be saved on the stack.
c. The values of (f 5) and (f 6) are both 6.

Exercise 3.18 We’ve already seen how to raise a number to an integer power, provided that the exponent isn’t negative. We could extend this to allow negative exponents as well by using the following definition:
$b^n = \begin{cases} 1 & \text{ if } x=0 \\ b^{n-1}*b & \text{ if } n>0 \\ b^{n+1}/b & \text{ if } n<0 \end{cases}$
a. Using this idea, write a procedure power such that (power b n) raises b to the n power for any integer n.
b. Use the substitution model to show how (power 2 -3) would be evaluated. (You can leave out steps that just determine which branch of a cond or if should be taken.) Does your procedure generate a recursive process or an iterative one?

Solution a.

(define power
  (lambda (b n)
    (cond ((= n 0) 1)
          ((> n 0) (* b (power b (- n 1))))
          ((< n 0) (* (/ 1 b) (power b (+ n 1)))))))

(power 2 -3)
(* (/ 1 2) (power 2 (+ -3 1)))
(* 0.5 (power 2 -2))
(* 0.5 0.5 (power 2 -1))
(* 0.25 0.5 (power 2 0))
(* 0.125 1)
0.125

It’s an recursive one because you can’t determine the final solution without knowing the beginning parameters.

Exercise 3.19 Prove that, for all nonnegative integers n and numbers a, the following procedure computes the value $2^n *a$ :

(define foo (lambda (n a)
  (if (= n 0)
    a
    (foo (- n 1) (+ a a)))))

Solution Let’s define the function again mathematically. $f(0, a) = a, f(n, a) = f(n-1, 2a)$ . The base case is correct:
$f(0, a) = 2^0*a = a$ .
We assume that $f(n+1, a) = 2^{n+1}*a = 2^n * 2a$ which can be written as $2^n * 2a = 2^n * b$ .
With our assumption it should follow that $f(n+1, a) = f(n, b).$
If we look at the definition, we see that $f(n, a) = f(n-1, 2a)$ which implies $f(n+1, a) = f(n, 2a) = f(n, b).$

SPOJ: 400. To and Fro

Mo and Larry have devised a way of encrypting messages. They first decide secretly on the number of columns and write the message (letters only) down the columns, padding with extra random letters so as to make a rectangular array of letters. For example, if the message is “There’s no place like home on a snowy night” and there are five columns, Mo would write down
t o i o y
h p k n n
e l e a i
r a h s g
e c o n h
s e m o t
n l e w x
Note that Mo includes only letters and writes them all in lower case. In this example, Mo used the character ‘x’ to pad the message out to make a rectangle, although he could have used any letter. Mo then sends the message to Larry by writing the letters in each row, alternating left-to-right and right-to-left. So, the above would be encrypted as

toioynnkpheleaigshareconhtomesnlewx

Your job is to recover for Larry the original message (along with any extra padding letters) from the encrypted one.

Problem: Sphere Online Judge (SPOJ) – Problem TOANDFRO

Solution: Let’s do this on a small example. The message should be ABCDEFGHIJKL with three columns. Therefore we get:

A E I
B F J
C G K
D H L

If we merge these lines together, we get:

A E I   J F B   C G K   L H D

You can see that you need the first character from the first element, the third from the second, the first from the third, etc. To make this a bit easier I decided to reverse every second element.

A E I   B F J  C G K  D H L

Now we can just take all the firsts characters from every element, then the second characters and finally the thirds and we’re done.

while True:
    code = int(raw_input())
    if code == 0:
        break
     
    line = raw_input()

    segments = []
    j = 0

    for i in xrange(0, len(line), code):
        if j % 2 == 1:
            # reverse every odd segment
            tmp = list(line[i:i + code])
            tmp.reverse()
            segments.append("".join(tmp))
        else:
            segments.append(line[i:i+code])
                
        j += 1
        
    out = []
    for i in xrange(0, code):
        for f in segments:
            out.append(f[i])

    print "".join(out)

Concrete Abstractions: Chapter 2

At the moment I’m working through Concrete Abstractions which is so far pretty great. I enjoy the writing style and the difficulty of the exercises. You can buy a used copy for about 10 bucks or read it for free online.

I’m going to present solutions to some exercises. However, I recommend working through this book by yourself. You’ll learn a lot!

Exercise 2.9 Write a procedure that computes the number of 6s in the decimal representation of an integer. Generalize this to a procedure that computes the number of d’s, where d is another argument.

Solution: Idea behind this algorithm is to find the last digit, evaluate it and shorten the number by one digit. You can achieve the first one by taking the reminder of the number n and 10. For example: Reminder of $151 / 10 = 1$ , because $151 / 10 = 15.1 \implies 0.1 * 10 = 1$ .
The last thing to do is to shorten the number. It’s easy done by subtracting the reminder of the number and dividing it by ten: $151 - 1 = 150 \implies 150 / 10 = 15$

(define (num-of-d n d)
  (if (< n 10)
    (if (= n d)
      1
      0)
    (+ (if (= d (remainder n 10))
      1
      0)
       (num-of-d (/ (- n (remainder n 10)) 10) d))))

Exercise 2.12 Any positive integer $i$ can be expressed as $i=2^nk$ , where $k$ is odd, that is, as a power of 2 times an odd number. We call $n$ the exponent of 2 in $i$ . For example, the exponent of 2 in 40 is 3 (because $40 = 2^35$ ) whereas the exponent of 2 in 42 is 1. If i itself is odd, then n is zero. If, on the other hand, i is even, that means it can be divided by 2. Write a procedure for finding the exponent of 2 in its argument.

Solution: The trick here is quite easy. We know that $k$ needs to be an integer. I just test this by comparing the results of $i / 2^n$ . Furthermore, I calculated a upper limit for n which equals $\log_2 (i)$ . If you choose the smallest positive $k$ , i.e. 1 then $i = 2^n*1 \implies \log_2 i = n$ . This makes the implementation in Scheme a bit more convenient.

(define (find-n i)
  (find-n-iter i (round (/ (log i) (log 2)))))

(define (find-n-iter i n)
  (if (= (/ i (expt 2 n)) (round (/ i (expt 2 n))))
    n
    (find-n-iter i (- n 1))))

Exercise 2.16 Consider the following procedure foo:

(define foo
  (lambda (x n)
    (if (= n 0)
      1
      (+ (expt x n) (foo x (- n 1))))))

Use induction to prove that (foo x n) terminates with the value $\frac{x^{n+1} - 1}{x-1}$
for all values of $x \neq 1$ and for all integers $n \geq 0$ . You may assume that expt works correctly, (i.e., (expt b m) returns $b^m$ ).

Info: I show a inductive proof a bit more verbose in the following exercise.

Solution: The base case is $foo(x, 0) = \frac{x^{0+1} - 1}{x-1} = 1$ .
We assume that $foo(x, n) = \frac{x^{n+1} - 1}{x-1}$ .
Therefore $foo(x, n+1) = x^{n+2} + foo(x, n)$ which is $foo(x, n+1) = x^{n+2} + \frac{x^{n+1} - 1}{x-1}$
$= \frac{x^{n+2}(x-1)}{x-1} + \frac{x^{n+1} - 1}{x-1} = \frac{x^{n+1}(x-1) + x^{n+1} - 1}{x-1} = \frac{x^{n+2} - 1}{x-1}.$

Exercise 2.18 Prove by induction that for every nonnegative integer n the following procedure computes 2n:

(define f (lambda (n)
  (if (= n 0)
    0
    (+ 2 (f (- n 1))))))

Solution: At first look at the definition. $f(0) = 0$ and $f(n) = 2 + f(n-1)$ .
Now we test the base case: $f(0) = 2*0 = 0$ which is true.
The inductive step is $f(n+1) = 2 + f(n)$ where we assume that $f(n) = 2n$ . Therefore $f(n+1) = 2 + 2n = 2(1+n).$

Exercise 2.20 Prove that the following procedure computes $n/(n+1)$ for any nonnegative integer $n$ . That is, (f n) computes $n/(n+1)$ for any integer $n \geq 0.$

(define f (lambda (n)
  (if (= n 0)
    0
    (+ (f (- n 1))
       (/ 1 (* n (+ n 1)))))))

Solution: The function is defined as $f(0) = 0$ and $f(n) = f(n-1) + \frac{1}{n * (n+1)}$ . First we test the base case. $f(0) = 0/(0+1) = 0$ . Afterwards the inductive step:
$f(n+1) = f(n) + \frac{1}{(n+1) * ((n+1)+1)}$ where we assume that $f(n) = n/(n+1)$ . Therefore, $f(n+1) = \frac{n}{n+1} + \frac{1}{(n+1) * ((n+1)+1)} = \frac{n(n+2)+1}{(n+1)(n+2)} = \frac{n^2+2n+1}{(n+1)(n+2)}.$ You can see that the numerator is the first binomial formula: $\frac{(n+1)^2}{(n+1)(n+2)} = \frac{(n+1)}{(n+2)} = \frac{n+1}{(n+1) + 1}.$

The one-layer thinking maxim: Don’t try to think recursively about a recursive process.