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.

SPOJ: 277. City Game

The strategic task of his game is to win as much rent money from these free spaces. To win rent money you must erect buildings, that can only be rectangular, as long and wide as you can. Bob is trying to find a way to build the biggest possible building in each area.

Problem: Sphere Online Judge (SPOJ) – Problem CTGAME

Solution: The basic idea behind my algorithm is to expand rectangles continuously. It looks for a free space, marks it as a rectangle with the size 1×1 and expands in each direction alternately.

def checkRight(f, i, j):
    if j >= int(w) - 1 or i > int(h) - 1:
        return False
    else:
        if f[i][j+1] == 'F':
            return True
        else:
            return False


def checkBottom(f, i, j):
    if i >= int(h) - 1 or j > int(w) - 1:
        return False
    else:
        if f[i+1][j] == 'F':
            return True
        else:
            return False


def checkSelf(f, i, j):
    if field[i][j] == 'F':
        return True
    else:
        return False


def checkExpandWidth(f, i, j, height, width):
    for y in xrange(i, height + i):
        if checkRight(field, y, j + width - 1) == False:
            return False
    
    return True


def checkExpandHeight(f, i, j, height, width):
    for x in xrange(j, width + j):
        if checkBottom(field, i + height - 1, x) == False:
            return False
    return True


k = int(raw_input())

for areas in xrange(0, k):
    
    line = raw_input()
    h, w = line.split()
    field = []

    for li in xrange(0, int(h)):
        line = raw_input()
        field.append(line.split())
     
    # blank line
    try:
        t = raw_input()
    except:
        break


    maxSquare = 0


    for i in xrange(0, int(h)):
        for j in xrange(0, int(w)):
            if checkSelf(field, i, j) == False:
                continue
            else:
                height = 1
                width = 1

                eWidth = True
                eHeight = True

                # expand width first
            
                while eWidth == True or eHeight == True:
                    if eWidth == True and checkExpandWidth(field, i, j, height, width) == True:
                        width += 1
                    else:
                        eWidth = False

                    if eHeight == True and checkExpandHeight(field, i, j, height, width) == True:
                        height += 1
                    else:
                        eHeight = False

                # found bigger square
                if height * width > maxSquare:
                    maxSquare = height * width



                # reset vars
                height = 1
                width = 1
  
                eWidth = True
                eHeight = True

                

                # expand height first
            
                while eWidth == True or eHeight == True:
                    if eHeight == True and checkExpandHeight(field, i, j, height, width) == True:
                        height += 1
                    else:
                        eHeight = False

                    if eWidth == True and checkExpandWidth(field, i, j, height, width) == True:
                        width += 1
                    else:
                        eWidth = False

                # found bigger square
                if height * width > maxSquare:
                    maxSquare = height * width
                

    print maxSquare * 3

SPOJ: 1163. Java vs C ++ (JAVAC)

I started doing programming challenges again and chose SPOJ for it. I try to do about three challenges per week which should be possible. As Stephen King says:

Read and write four to six hours a day. If you cannot find the time for that, you can’t expect to become a good writer.

I actually wonder how much you would learn if you’re going to solve (harder) algorithmic problems four hours a day for a year. Probably a lot! In any case here’s the first problem and its solution.

Problem: Sphere Online Judge (SPOJ) – Problem JAVAC

def recognize(s):
    # -1: c++
    #  0: error
    # +1: java
    

    if s == s.lower():
        typ = 1
        last = 0
        for c in s:
            if c == '_':
                if last == 0: # last character was _
                    typ = -1
                    last = 1
                else:
                    typ = 0
                    break
            else:
                last = 0

        if s[-1] == '_' or s[0] == '_':
            typ = 0
    else:
        if s[0] == s[0].lower():
            typ = 1
            # if _ in java => error
            for c in s:
                if c == '_':
                    typ = 0
        else:
            typ = 0
    return typ

def transformJava(s):
    l = list(s)
    r = []
    for i in xrange(0, len(l)):
        if l[i] == l[i].upper():
            r.append('_')
            r.append(l[i].lower())
        else:
            r.append(l[i])

    return "".join(r)

def transformCpp(s):
    l = list(s)
    r = []
    for i in xrange(0, len(l)):
        if i > 1 and l[i-1] == '_':
            continue

        if l[i] == '_':
            r.append(l[i+1].upper())
            continue
        else:
            r.append(l[i])


    return "".join(r)


while True:
    try:
        s = raw_input()
    except:
        break

    r = recognize(s)
    if r == -1:
        print transformCpp(s)
    elif r == 1:
        print transformJava(s)
    else:
        print "Error!"

#83/111: Strategic Database Marketing

What is it about?

You collected data from your customer and then? Arthur M. Hughes explains how to analyze customer data and use it in the decision making process.

What can I learn?

Recency, Frequency, Monetary: The easiest metric is RFM. You divide each customer in one of many groups and test your offering/ad/etc. on a small subset. Let’s say you got 10000 customers. Now you are going to sort them by recency, e.g. latest sales, and split them up in 10 groups. Do the same thing for frequency and monetary. Now every customer got a recency group, a frequency group and a monetary group. Now comes the beauty. You just test your offering to a subset (e.g. 10% of each group) and notice how much each group spend. Finally, you can see which groups were the most profitable and just send them the final offering.

Know what you want to do: It’s essential. Hughes wrote that companies often just collect tons of data without a purpose. Data alone won’t help you. Spare your time and resources and define at first what you want to achieve and then start collecting data.

Customer Lifetime Value: I explained the concept early, however the RFM approach makes this more interesting because you can now easily test the impact on small groups.

Conclusion

Strategic Database Marketing is a pretty good book. It got lots of examples and the author explains each approach in detail. I especially like the RFM approach because it is so easy but works well. If you want to learn more about analyzing customer data this book is for you.