/* Practice problems for HW2-type rex questions */

/*
 * There are solutions below the problems... .
 */

1)  Write a function "lottoScore(W,T)" that takes in any
    two _sorted_ lists W and T (the winning and your ticket's
    lottery numbers, respectively) and outputs the number of
    matches between the two sets of numbers using the "merge" technique.
    
Example:

    lottoScore([4,8,15,29,33,47],[14,15,28,30,33,42]);
    
    2

    
    
    
    
2)  Write a function "allLeaves(G)" that takes in a graph represented
    as a binary relation (a set of [parent, child] ordered pairs) and
    outputs a list of all of the leaves of the graph. The leaves
    of a graph are those nodes that do not have any targets (children).
    
    
Example:

    allLeaves([ ['a','b'], ['b','c'], ['b','b'], ['d','c'], ['a','e'] ]);
    
    [ 'c', 'e' ]
    
    
    
3)  Write a function "allRoots(G)" that takes in a graph represented
    as a binary relation (a set of [parent, child] ordered pairs) and
    outputs a list of all of the roots of the graph. The roots
    of a graph are those nodes that do not have any parents.
    
    
Example:

    allRoots([ ['a','b'], ['b','c'], ['b','b'], ['d','c'], ['a','e'] ]);
    
    [ 'a', 'd' ]
    
    
    









/* 
 *
 * Practice problems for HW1-type rex questions 
 *
 */

1)  Write a function "flattenAll(L)" that takes in any
    list (arbirarily nested) and returns a list
    of leaves. That is, "flattenAll" removes all nesting.
    
Example:

    flattenAll([ 1, 2, [3, 4, [5], [[6]], 7], [8, [9, [10]]], 11 ]);
    
    [1,2,3,4,5,6,7,8,9,10,11]

    
    
    
2)  Write a function waldo(w,L) that takes in any datum at all (w) and
    any list L all (arbirarily nested). The function waldo then returns
    a 1 if w is an element at some level of nesting in L and returns
    a 0 otherwise.
    
    
Examples:

    waldo("waldo",[1, ["axe", ["waldo"], 7], 'd', 10]);
    
    1
    
    
    
    waldo(12,[1,2,3,14,[15,16,[17,19]],20]);
    
    0
    
    
    
    

3)  Write a function "lotto(W,L)" that takes two arguments -- W is
    a list of six winning lotto numbers and L is a list of "tickets,"
    which are themselves lists of the form
          ["name of ticketholder", firstNumber, secondNumber, ... sixthNumber ]
    "lotto" returns a pair (that is, a list of two elements) that contains
    the name of the person who matched the most numbers and 
    the quantity of numbers matched.
    
    
Example:

    lotto([1,2,3,4,5,6], [  ["Alice", 2, 10, 12, 14, 16, 18],
	                    ["Bob",   2,  3, 40, 41, 42, 43],
			    ["Chris", 1,  2,  3,  5, 15, 19] ]);
    
    ["Chris", 4]







/*
 * Solutions below
 */
















/* Practice problems for HW2-type rex questions */

/*

1)  Write a function "lottoScore(W,T)" that takes in any
    two _sorted_ lists W and T (the winning and your ticket's
    lottery numbers, respectively) and outputs the number of
    matches between the two sets of numbers using the "merge" technique.
    
Example:

    lottoScore([4,8,15,29,33,47],[14,15,28,30,33,42]);
    
    2
    
*/

// Answer:

    lottoScore([],T) => 0;
    lottoScore(W,[]) => 0;
    lottoScore([f|r],[F|R]) => f < F ? lottoScore(r,[F|R]);
    lottoScore([f|r],[F|R]) => f > F ? lottoScore([f|r],R);
    lottoScore([f|r],[F|R]) => f == F ? 1 + lottoScore(r,R);

    
    
    
/*
    
2)  Write a function "allLeaves(G)" that takes in a graph represented
    as a binary relation (a set of [parent, child] ordered pairs) and
    outputs a list of all of the leaves of the graph. The leaves
    of a graph are those nodes that do not have any targets (children).
    
    
Example:

    allLeaves([ ['a','b'], ['b','c'], ['b','b'], ['d','c'], ['a','e'] ]);
    
    [ 'c', 'e' ]
    
*/
    
// Answer:  (a good example of map, drop, and anonymous functions...)
    
    allLeaves(G) = remove_duplicates(drop( (x) => member(x,map(first,G)) , map(second,G) ));
    
    
/*
    
3)  Write a function "allRoots(G)" that takes in a graph represented
    as a binary relation (a set of [parent, child] ordered pairs) and
    outputs a list of all of the roots of the graph. The roots
    of a graph are those nodes that do not have any parents.
    
    
Example:

    allRoots([ ['a','b'], ['b','c'], ['b','b'], ['d','c'], ['a','e'] ]);
    
    [ 'a', 'd' ]
    
*/
    
    
    allRoots(G) = remove_duplicates(drop( (x) => member(x,map(second,G)) , map(first,G) ));


// flattenAll
//      input: anything -- atomic or list
//     output: a list of everything in the input with no nested structure

flattenAll(x) => atomic(x) ? [x];
flattenAll([]) => [];
flattenAll([F|R]) => append(flattenAll(F),flattenAll(R));



// waldo
//      input: any datum "w" and any list "L"
//     output: 0 if w appears nowhere in L, at any level of nesting
//             1 if w does appear in L at some level of nesting

waldo(w,[]) => 0;
waldo(w,w)  => 1;
waldo(w,x)  => atomic(x) ? 0;
waldo(w,[F|R]) => waldo(w,F) || waldo(w,R);



// lotto
//      input: a list of lottery numbers (N) and a nonempty list of
//             ticketholders and their numbers
//     output: the list of the winner (breaking ties arbitrarily)
//             and the number of matches the winner had

lotto(N, [ [name|ticket] | R ]) => 
   lotto(N, R, [name, Match(N,ticket)]);

lotto(N, [], bestSF) => bestSF;
lotto(N, [[name|ticket]|R], [nm,sc]) =>
   sc > Match(N,ticket) ? lotto(N, R, [nm,sc]) 
                        : lotto(N, R, [name,Match(N,ticket)]);


Match([],_) => 0;
Match(_,[]) => 0;
Match([F1|R1], [F2|R2]) =>
   F1 == F2  ?  1 + Match(R1,R2) :
   F1 <  F2  ?  Match(R1,[F2|R2]):
/* F1 >  F2 */  Match([F1|R1],R2);