## 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
#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)))
(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)))
(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.

Pages: 1 2

### 7 Responses to “Mid-Term Exam”

1. Paul said

In Python.

```from collections import defaultdict

def first(s1, s2):
D = {val:pos for pos, val in reversed(list(enumerate(s2)))}
return next((pos for pos, val in enumerate(s1) if val in D), False)

print(first("aet6ukm", "1236786"))  # -> 3
print(first("aet9ukm", "1236786"))  # -> False

def second(recipes):
D = defaultdict(list)
for meal, *ingredients in recipes:
for i in ingredients:
D[i].append(meal)
return [(ingredient, meals) for ingredient, meals in D.items()
if len(meals) > 1]

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)]

print(second(recipes))
# [(2, ['a', 'b']), (3, ['a', 'c']), (4, ['b', 'd']), (6, ['b', 'c', 'f']),
# (7, ['c', 'e', 'f']), (5, ['d', 'e']), (9, ['e', 'g']), (8, ['f', 'g'])]
```
2. Globules said

```import Data.Function (on)
import Data.List (findIndex, groupBy, sort)
import Data.Tuple (swap)

first :: Eq a => [a] -> [a] -> Maybe Int
first xs ys = findIndex (`elem` ys) xs

--------------------------------------------------------------------------------

-- For lists of length > 1: unpair . pair = id

pair :: [a] -> [(a, a)]
pair (x:xs) = map ((,) x) xs
pair _      = []

unpair :: [(a, a)] -> [a]
unpair xs@(x:_) = fst x : map snd xs
unpair _        = []

second :: Ord a => [[a]] -> [[a]]
second = filter ((> 2) . length)
. map unpair
. groupBy ((==) `on` fst)
. sort
. map swap
. concatMap pair

--------------------------------------------------------------------------------

main :: IO ()
main = do
print \$ first "aet6ukm" "123678"
print \$ first "aet9ukm" "123678"
putStrLn ""
mapM_ print \$ second [ ["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"]
]
```
```\$ ./midterm
Just 3
Nothing

["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"]
```

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), 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)

}

```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), 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)

}
```
5. Daniel said

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

```/* first.c */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Finds the first character in s1 that's also in
// s2, and returns the index in s2.
// Returns the index of the null character in s2
// on failure.
size_t find_first_char(char* s1, char* s2) {
size_t s1_len = strlen(s1);
size_t s2_len = strlen(s2);
size_t index_lookup;
for (size_t i = 0; i < 256; ++i) {
index_lookup[i] = s2_len;
}
for (size_t i = 0; i < s2_len; ++i) {
unsigned char c = s2[i];
if (index_lookup[c] < s2_len) continue;
index_lookup[c] = i;
}
for (size_t i = 0; i < s1_len; ++i) {
unsigned char c = s1[i];
size_t index = index_lookup[c];
if (index < s2_len) return index;
}
return s2_len;
}

static char usage[] = "Usage: first STRING1 STRING2";
#define PRINT_USAGE_AND_EXIT(stream) \
do {                               \
fprintf(stream, "%s\n", usage);  \
exit(EXIT_FAILURE);              \
} while (0)

int main(int argc, char* argv[]) {
if (argc != 3) PRINT_USAGE_AND_EXIT(stderr);
size_t index = find_first_char(argv, argv);
printf("%zu\n", index);
return EXIT_SUCCESS;
}
```

Example Usage:

```\$ ./first aet6ukm 123678
3
```
6. Daniel said

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

```/* second.cpp */

#include <cstdlib>
#include <iostream>
#include <unordered_map>
#include <vector>

using std::cout;
using std::endl;
using std::move;
using std::pair;
using std::string;
using std::unordered_map;
using std::vector;

void find_ingredients(
const vector<vector<string>>& recipes,
vector<pair<string,vector<string>>>* output) {
unordered_map<string, vector<string>> recipe_lookup;
for (const auto& recipe : recipes) {
const string& name = recipe;
for (size_t i = 1; i < recipe.size(); ++i) {
const string& ingredient = recipe[i];
if (recipe_lookup.find(ingredient) == recipe_lookup.end()) {
recipe_lookup.insert({ingredient, vector<string>()});
}
recipe_lookup[ingredient].push_back(name);
}
}
for (const auto& x : recipe_lookup) {
const vector<string>& recipes = x.second;
if (recipes.size() > 1) {
output->push_back(move(x));
}
}
}

int main() {
const vector<vector<string>> 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"}
};
vector<pair<string,vector<string>>> ingredient_recipes;
find_ingredients(recipes, &ingredient_recipes);
for (const auto& x : ingredient_recipes) {
const string& ingredient = x.first;
const vector<string>& recipes = x.second;
cout << ingredient << " [";
for (size_t i = 0; i < recipes.size(); ++i) {
if (i > 0) cout << ", ";
cout << recipes[i];
}
cout << "]" << endl;
}
return EXIT_SUCCESS;
}
```

Output:

```5 [d, e]
7 [c, e, f]
9 [e, g]
6 [b, c, f]
8 [f, g]
4 [b, d]
3 [a, c]
2 [a, b]
```
7. Mumps version

```
midtermexam ;
;
go(str1,str2) ; Find 1st char in 2nd string which occurs in 1st
n fnd,i
f i=1:1:\$l(str1) d  q:fnd
. s fnd=\$f(str2,\$e(str1,i))
q \$s(fnd:fnd-2,1:-1)
;
go2(str,arr) ; Find elemets common to recipes
n char,i,j,piece
f i=1:1:\$l(str,"|") d
. s piece=\$p(str,"|",i)
. s char=\$e(piece)
. f j=2:1:\$l(piece) d
. . s num=\$e(piece,j)
. . s arr(num)=\$s(\$g(arr(num))="":char,1:\$g(arr(num))_" "_char)
q
;
test    ; Test
n arr,i,str1,str2
s str1="ayc4xbz",str2="012345"
w !,str1,"/",str2," --> ",\$\$go(str1,str2)
s str1="ayc7xbz",str2="012345"
w !,str1,"/",str2," --> ",\$\$go(str1,str2)
;
s str1="a123|b246|c367|d45|e579|f678|g89"
d go2(str1,.arr)
w !!,str1," --> ",!
zwrite arr
q

Examples:

vista@steve-VirtualBox:~/EHR/r\$ gtm

GTM>d test^midtermexam

ayc4xbz/012345 --> 4
ayc7xbz/012345 --> -1

a123|b246|c367|d45|e579|f678|g89 -->
arr(1)="a"
arr(2)="a b"
arr(3)="a c"
arr(4)="b d"
arr(5)="d e"
arr(6)="b c f"
arr(7)="c e f"
arr(8)="f g"
arr(9)="e g"

```