Mid-Term Exam
March 16, 2018
At many colleges and universities, Spring Break is approaching soon, and that means mid-term exams are also imminent. Here are two questions suitable for a mid-term exam for not-too-advanced students:
First: You are given two strings, say “aet6ukm” and “123678”; neither is necessarily sorted. You are to find the first character in the first string that also appears in the second string, and return the index of the character in the second string. For the two strings above, the character “6” appears in the first string and also in the second string, at index position 3 (counting from zero), so your program should return 3.
Second: You are given a list of recipes, where each recipe is a list with a name in the first position of the list and a list of ingredients in the remaining positions of the list; for instance, (“Pasta” “Spaghetti” “Tomato sauce” “Basil”) is a simple recipe for pasta. Your program should return a list of all ingredients that are used in more than one recipe, with a list of recipe names attached to each ingredient.
Your task is to answer the two mid-term exam questions given above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
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"