Exercises on Processing Two Complex Inputs

Exercise 17.6.1

Develop the function merge. It consumes two lists of numbers, sorted in ascending order. It produces a single sorted list of numbers that contains all the numbers on both inputs lists (and nothing else). A number occurs in the output as many times as it occurs on the two input lists together.

Examples:

(merge (list 1 3 5 7 9) (list 0 2 4 6 8))
;; expected value:  
(list 0 1 2 3 4 5 6 7 8 9) 

(merge (list 1 8 8 11 12) (list 2 3 4 8 13 14))
;; expected value:  
(list 1 2 3 4 8 8 8 11 12 13 14) ; Solution 

Exercise 17.6.2

The goal of this exercise is to develop a version of the Hangman game of section  for words of arbitrary length.

Provide a data definition for representing words of arbitrary length with lists. A letter is represented with the symbols 'a through 'z plus '_.

Develop the function reveal-list. It consumes three arguments:

1. the chosen word, which is the word that we have to guess;
2. the status word, which states how much of the word we have guessed so far; and
3. a letter, which is our current guess.

1. If the guess is equal to the letter in the chosen word, the guess is the corresponding letter in the new status word.
2. Otherwise, the new letter is the corresponding letter from the status word.

Test the function with the following examples:

1. (reveal-list (list 't 'e 'a) (list '_ 'e '_) 'u)
2. (reveal-list (list 'a 'l 'e) (list 'a '_ '_) 'e)
3. (reveal-list (list 'a 'l 'l) (list '_ '_ '_) 'l)

Use the teachpack hangman.ss and the functions draw-next-part (from exercise ) and reveal-list to play the Hangman game. Evaluate the following expression:

(hangman-list reveal-list draw-next-part)

Exercise 17.6.3

In a factory, employees punch time cards as they arrive in the morning and leave in the evening. In the modern age of electronic punch cards, a punch card contains an employee number and the number of hours worked. Also, employee records always contain the name of the employee, an employee number, and a pay rate.

Develop the function hours->wages2. The function consumes a list of employee records and a list of (electronic) punch cards. It computes the weekly wage for each employee by matching the employee record with a punch card based on employee numbers. If a pair is missing or if a pair's employee numbers are mismatched, the function stops with an appropriate error message. Assume that there is at most one card per employee and employee number.

Hint: An accountant would sort the two lists by employee number first. Solution

Exercise 17.6.4

A linear combination is the sum of many linear terms, that is, products of variables and numbers. The latter are called coefficients in this context. Here are some examples:

In all three examples, the coefficient of x is 5, that of y is 17, and the one for z is 3.

If we are given values for variables, we can determine the value of a polynomial. For example, if x = 10, the value of is 50; if x = 10 and y = 1, the value of is 67; and if x = 10, y = 1, and z = 2, the value of is 73.

In the past, we would have developed functions to compute the values of linear combinations for specific values. An alternative representation is a list of its coefficients. The above combinations would be represented as:

(list 5)
(list 5 17) 
(list 5 17 3) 

Develop the function value. It consumes the representation of a polynomial and a list of numbers. The lists are of equal length. It produces the value of the polynomial for these values. Solution

Exercise 17.6.5

Louise, Jane, Laura, Dana, and Mary are sisters who would like to save money and work spent on Christmas gifts. So they decide to hold a lottery that assigns to each one of them a single gift recipient. Since Jane is a computer programmer, they ask her to write a program that performs the lottery in an impartial manner. Of course, the program must not assign any of the sisters to herself.

Here is the definition of gift-pick. It consumes a list of distinct names (symbols) and randomly picks one of those arrangements of the list that do not agree with the original list at any position:

;; gift-pick: list-of-names -> list-of-names
;; to pick a ``random'' non-identity arrangement of names 
(define (gift-pick names) 
  (random-pick 
    (non-same names (arrangements names)))) 

Develop the auxiliary functions

1. random-pick : list-of-list-of-names -> list-of-names, which consumes a list of items and randomly picks one of them as the result;
2. non-same : list-of-names list-of-list-of-names -> list-of-list-of-names, which consumes a list of names L and a list of arrangements and produces the list of those that do not agree with L at any position.

   Two permutations agree at some position if we can extract the same name from both lists by applying first and the same number of rest operations to both. For example, (list 'a 'b 'c) and (list 'c 'a 'b) do not agree, but (list 'a 'b 'c) and (list 'c 'b 'a) agree at the second position. We can prove that by applying rest followed by first to both lists.

Hint: Recall that (random n) picks a random number between 0 and n-1 (compare with exercise ). Solution

Exercise 17.6.6

Develop the function DNAprefix. The function takes two arguments, both lists of symbols (only 'a, 'c, 'g, and 't occur in DNA, but we can safely ignore this issue here). The first list is called a pattern, the second one a search-string. The function returns true if the pattern is a prefix of the search-string. In all other cases, the function returns false.

Examples:

(DNAprefix (list 'a 't) (list 'a 't 'c)) 

(not (DNAprefix (list 'a 't) (list 'a)))

(DNAprefix (list 'a 't) (list 'a 't)) 

(not (DNAprefix (list 'a 'c 'g 't) (list 'a 'g)))

(not (DNAprefix (list 'a 'a 'c 'c) (list 'a 'c)))

Modify DNAprefix so that it returns the first item beyond the pattern in the search-string if the pattern is a proper prefix of the search-string. If the lists do not match or if the pattern is no shorter than the search-string, the modified function should still return false. Similarly, if the lists are equally long and match, the result is still true.

Examples:

(symbol=? (DNAprefix (list 'a 't) (list 'a 't 'c)) 
          'c) 

(not (DNAprefix (list 'a 't) (list 'a)))

(DNAprefix (list 'a 't) (list 'a 't))