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.
Programming Praxis 
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'])]A Haskell version.
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"] ]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)
}
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.
/* 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[256]; 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[1], argv[2]); printf("%zu\n", index); return EXIT_SUCCESS; }Example Usage:
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[0]; 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:
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"