SPOJ: 3374. Scavenger Hunt

He does a poor job, though, and wants to learn from Bill’s routes. Unfortunately Bill has left only a few notes for his successor. Bill never wrote his routes completely, he only left lots of little sheets on which he had written two consecutive steps of the routes. […]
This made much sense, since one step always required something from the previous step. George however would like to have a route written down as one long sequence of all the steps in the correct order.

Problem: Sphere Online Judge (SPOJ) – Problem SCAVHUNT

Solution:

scenarios = int(raw_input())

for i in xrange(0, scenarios):
    S = int(raw_input())

    myDict = dict()
    myRevDict = dict()

    for j in xrange(0, S - 1):
        fromLocation, toLocation = raw_input().split()
        myDict[fromLocation] = toLocation
        myRevDict[toLocation] = fromLocation
    

    # find start
    start = ""
    for key in myDict.keys():
        if key not in myRevDict:
            start = key
            break
    
    # print message
    print "Scenario #%i:" % (i + 1)

    # print path
    currentKey = start
    for l in xrange(0, S - 1):
        print currentKey
        currentKey = myDict[currentKey]

    print currentKey
    print ""

 

Concrete Abstractions: Chapter 7

Exercise 7.5 Generalize sum to a higher-order procedure that can accumulate together the elements of a list in an arbitrary fashion by using a combining procedure (such as +) specified by a procedural parameter. When the list is empty, sum returned 0, but this result isn’t appropriate for other combining procedures. For example, if the com- bining procedure is *, 1 would be the appropriate value for an empty list. (Why?) Following are two possible approaches to this problem:
a. Write the higher-order procedure so that it only works for nonempty lists. That way, the base case can be for one-element lists, in which case the one element can be returned.
b. Write the higher-order procedure so that it takes an additional argument, beyond the list and the combining procedure, that specifies the value to return for an empty list.

Solution:
a.

(define accumulate-lst
  (lambda (lst f)
    (if (= (length lst) 1)
      (f (car lst))
      (f (car lst) (accumulate-lst (cdr lst) f)))))

; b.

(define accumulate-lst-base
  (lambda (lst f b)
    (if (null? lst)
      b
      (f (car lst) (accumulate-lst-base (cdr lst) f b)))))

Exercise 7.6 a. Write a procedure that will count the number of times a particular element occurs in a given list.
b. Generalize this procedure to one that will count the number of elements in a given list that satisfy a given predicate.

Solution:

(define count-elements
  (lambda (lst pred)
    (if (null? lst)
      0
      (if (pred (car lst))
        (+ 1 (count-elements (cdr lst) pred))
        (+ 0 (count-elements (cdr lst) pred))))))

Exercise 7.13: The procedure map is extraordinarily handy for creating lists of all sorts. Each of the following problems can be solved by using map.
a. Write a procedure that, when given a positive integer n, returns a list of the first n perfect squares.
b. Write a procedure that, when given a positive integer n, returns a list of the first n even integers.
c. Write a procedure called sevens that, when given a positive integer n, returns a list of n sevens. For example:

(sevens 5)

d. Write a procedure that, when given a list of positive integers, returns a list of lists of integers. Each of these lists should be the positive integers from 1 to whatever was in the original list. For example,

(list-of-lists ’(1 5 3))
((1) (1 2 3 4 5) (1 2 3))

Solution:
a.

(define first-n-perfect-squares
  (lambda (n)
    (map (lambda (x) (* x x)) (integers-from-to 1 n))))

b.

(define first-n-even-integers
  (lambda (n)
    (map (lambda (x) (* x 2)) (integers-from-to 1 n))))

c.

(define sevens
  (lambda (n)
    (map (lambda (x) 7) (integers-from-to 1 n))))

d.

(define list-of-lists
  (lambda (lst)
    (map (lambda (n) (integers-from-to 1 n)) lst)))

Ex 7.14

(define my-map
  (lambda (f lst)
    (if (null? lst)
      '()
      (cons (f (car lst)) (my-map f (cdr lst))))))

Exercise 7.42: Write a procedure called apply-all that, when given a list of functions and a number, will produce the list of the values of the functions when applied to the number.

Solution:

(define apply-all
  (lambda (funs x)
    (if (null? funs)
      '()
      (cons ((car funs) x) (apply-all (cdr funs) x)))))

Exercise 7.44: Consider the following two procedures. The procedure last selects the last element from a list, which must be nonempty. It uses length to find the length of the list.

(define last
  (lambda (lst)
    (if (= (length lst) 1)
      (car lst)
      (last (cdr lst)))))</code>

(define length
  (lambda (lst)
    (if (null? lst)
      0
      (+ 1 (length (cdr lst))))))

a. How many cdrs does (length lst) do when lst has n elements?
b. How many calls to length does (last lst) make when lst has n elements?
c. Express in Theta notation the total number of cdrs done by (last lst), including cdrs done by length, again assuming that lst has n elements.
d. Give an exact formula for the total number of cdrs done by (last lst), including cdrs done by length, again assuming that lst has n elements.

Solution:
a. n, which can be easily seen. An empty list needs 0 cdrs, a list with length 1 needs one cdrs. If we use induction, we can assume that this holds. For a list of length (n+1), we can see that length uses one cdr and then generates (length ). Therefore there are n uses of cdr for a list of length n.
b. Let’s start with the base case. (last ‘(1)) here last calls length one time. We can see that each time last have to call length. Therefore we can see that it needs n calls for a list of length n. The idea of the proof follows the last one.
c. and d. How many cdrs does last need without considering length? If the length is 1, it needs 0. If the length is 2, it needs 1. In general it needs (n-1) times cdr. We already know how often last calls length, so we can calculate the number of all calls. There are (n-1) calls from last directly. For each iteration in last we need 1 call of length. And each call of length needs (k+1) cdrs. If we merge everything together, we get the following table

len of list     cdr from last      calls of length     cdr from length
    1               0                    1                 1
    2               1                    2                 2 + 1
    3               2                    3                 3 + 2 + 1
    ...
    n              (n-1)                 n                 n + (n-1) + (n-2) + ... + 1

Now we just have to add cdr from last and cdr from length and get:
(n-1) + sum_{i=1}{n} i = (n-1) + frac{n(n-1)}{2} = frac{n^2 + 3n - 2}{2}
Which is Theta(n^2) in Theta notation.

Exercise 7.47: Write a procedure map-2 that takes a procedure and two lists as arguments and returns the list obtained by mapping the procedure over the two lists, drawing the two arguments from the two lists. Write this procedure map-2. You may assume that the lists have the same length.

Solution:

(define map-2
  (lambda (f lst1 lst2)
    (if (null? lst1)
      '()
       (cons (f (car lst1) (car lst2)) (map-2 f (cdr lst1) (cdr lst2))))))

SPOJ: 1268. CN Tower (Easy)

On the way, she stops in Toronto to do some sightseeing. The unfortunate thing about travelling is that everyone back home expects her to bring back pictures of everything. […] 351 m up the tower is the “360” rotating restaurant, which rotates a full 360 degrees every 72 minutes. From there, Christy can see the whole city, and take close-up pictures of all the landmarks using her fancy new 100x optical zoom camera. Since the restaurant itself rotates, she only needs to stand in one place to take pictures in all directions. […] Since the restaurant staff only realize she is a tourist once she starts taking pictures, we begin measuring the time required once she takes her first picture.

Problem: Sphere Online Judge (SPOJ) – Problem CNEASY

Solution: Afterwards this problem is really easy, however I first made it too hard. The trick is pretty easy we are looking for the biggest distance between each consecutive degree. To check the difference between the highest and the lowest I appended (lowest + 360) to the list of degrees. The + 360 helps to calculate the distance more easily. Afterwards just select the biggest difference and calculate the minimum time.

from math import ceil

for i in xrange(0, int(raw_input())):
    n = int(raw_input())
    degrees = []
    for i in xrange(0, n):
        degrees.append(float(raw_input().split()[1]))

    degrees.sort()
    degrees.append(degrees[0] + 360)
    maxDegrees = max([(degrees[i] - degrees[i-1]) for i in xrange(1, n + 1)])

    print "%i" % (ceil ((360 - maxDegrees) * 12))

Concrete Abstractions: Chapter 6

Exercise 6.23
A three-dimensional (3D) vector has x, y, and z coordinates, which are numbers. 3D vectors can be constructed and accessed using the following abstract interface:

(make-3D-vector x y z)
(x-coord vector)
(y-coord vector)
(z-coord vector)

a. Using this abstract interface, define procedures for adding two vectors, finding the dot-product of two vectors, and scaling a vector by a numerical scaling factor.
b. Choose a representation for vectors and implement make-3D-vector, x-coord, y-coord, and z-coord.

Solution: a.

(define add-vectors
  (lambda (a b)
    (make-3D-vector 
     (+ (x-coord a) (x-coord b))
     (+ (y-coord a) (y-coord b))
     (+ (z-coord a) (z-coord b)))))

(define dot-vectors
  (lambda (a b)
    (+
     (* (x-coord a) (x-coord b))
     (* (y-coord a) (y-coord b))
     (* (z-coord a) (z-coord b)))))

(define scale-vector
  (lambda (a s)
    (make-3D-vector (* s (x-coord a))
                    (* s (y-coord a))
                    (* s (z-coord a)))))

b.

(define make-3D-vector
  (lambda (x y z)
    (cons x (cons y z))))

(define x-coord
  (lambda (a)
    (car a)))

(define y-coord
  (lambda (a)
    (car (cdr a))))

(define z-coord
  (lambda (a)
    (cdr (cdr a))))

This was a quite short chapter. However chapter 7 is rather long. This exercise above covers pretty much the whole chapter, it was just about cons, car and cdr.