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.

Advertisements

Pages: 1 2

6 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

    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"]
                           ]
    
    $ ./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"]
    
  3. ad said

    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)

    }

  4. ad said
    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)
    
    }
    
  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[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:

    $ ./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[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:

    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]
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: