## Mid-Term Exam

### March 16, 2018

Both exam questions need some kind of associative memory; we will use association-lists, because we are working in Scheme, but hash tables would also be suitable.

For the first problem, we build an associative array of string positions indexed by character for the characters in the second string, then scan the first string until we find a character that is a member of the associative array:

(define (task1 str1 str2) (do ((cs (string->list str2) (cdr cs)) (idx 0 (+ idx 1)) (pos (list) (cons (cons (car cs) idx) pos))) ((null? cs) (let loop ((cs (string->list str1))) (cond ((null? cs) #f) ((assoc (car cs) pos) => cdr) (else (loop (cdr cs))))))))

And here’s the output:

> (task1 "ayc4xbz" "012345") 4 > (task1 "ayc7xbz" "012345") #f

For the second problem we need a list of recipes; we use letters for recipe names and numbers for ingredients:

(define recipes '((a 1 2 3) (b 2 4 6) (c 3 6 7) (d 4 5) (e 5 7 9) (f 6 7 8) (g 8 9)))

Then our solution loops over each ingredient in each recipe, accumulating a list of recipes in which that ingredient appears, then groups by common ingredient and produces an output list. We give all ingredient lists, not just those of length 2 or greater:

(define (task2 xs) (map (lambda (xs) (list (cadar xs) (map car xs))) (group-by (lambda (a b) (= (cadr a) (cadr b))) (sort (lambda (a b) (< (cadr a) (cadr b))) (list-of (list (car r) i) (r in xs) (i in (cdr r)))))))

`Group-by`

is a useful primitive; it first appeared in a previous exercise:

(define (group-by eql? xs) (let loop ((xs xs) (ys '()) (zs '())) (cond ((null? xs) (reverse (if (null? ys) zs (cons (reverse ys) zs)))) ((null? (cdr xs)) (reverse (cons (reverse (cons (car xs) ys)) zs))) ((eql? (car xs) (cadr xs)) (loop (cdr xs) (cons (car xs) ys) zs)) (else (loop (cddr xs) (list (cadr xs)) (cons (reverse (cons (car xs) ys)) zs))))))

And here’s the output:

> (task2 recipes) ((1 (a)) (2 (a b)) (3 (a c)) (4 (b d)) (5 (d e)) (6 (b c f)) (7 (c e f)) (8 (f g)) (9 (e g)))

You can run the program at https://ideone.com/YJdy8H.

In Python.

A Haskell version.

Kotlin version

fun main(args: Array<String>) {

val recipes = listOf(listOf("a", 1, 2, 3),

listOf("b", 2, 4, 6), listOf("c", 3, 6, 7), listOf("d", 4, 5),

listOf("e", 5, 7, 9),

listOf("f", 6, 7, 8),

listOf("g", 8, 9) )

val commonIngredients = recipes.map {

l -> Pair(l.take(1)[0], l.drop(1))

} . flatMap {

p -> p.second.map { ingredient -> Pair(ingredient, p.first) }

} . groupBy {

it.first

} . filter {

it.value.size > 1

} . mapValues {

it.value.map { p -> p.second }

}

println(commonIngredients)

}

Here’s a solution to the first problem in C.

Example Usage:

Here’s a solution to the second problem in C++11.

Output:

Mumps version