// File:    a01.rex
// Author:  Robert Keller
// Puprose: CS60 Assignment 1 Sample Solutions

// Problem 1a: Provide variable definitions:
// Each variable vN is equated to N factored into primes. 
// The factors are listed in the form [prime, multiplicity]. 
// For example, in v24 we have 2^3 * 3^1 == 24

v24 = [[2, 3], [3, 1]];
v576 = [[2, 6], [3, 2]];
v1024 = [[2, 10]];
v255255 = [[3, 1], [5, 1], [7, 1], [11, 1], [13, 1], [17, 1]];
v139843693414425 = [[3, 1], [5, 2], [7, 3], [11, 4], [13, 5]];
v19556258587787694114798080625 = [[3, 2], [5, 4], [7, 6], [11, 8], [13, 10]];


// Problem 1b: Define unFactor(L)

// unFactor produces the number from a primes representation as described above

multiplyOut(Pair) = pow(first(Pair), second(Pair));

unFactor(L) = reduce(*, 1, map(multiplyOut, L));

// Explanatoin: multiplyOut produces the contribution of a single pair 
// [prime, multiplicity] by computing pow(prime, multiplicity).  
// This is done for each pair in the list using map, and the resulting list 
// of numbers are multiplied together using reduce,
// with 1 as the appropriate multiplicative unit.


// Problem 2a: Provide variable definition for ec32

// For this problem, we have defined an equivalence relation on numbers:
// two numbers are equivalent if they have the same prime factors, ignoring
// multiplicity.  For example, 6 and 24 are equivalent because they both
// have 2 and 3 as their prime factors.

// The problem was to define ec32 as the list of equivalence classes
// for the numbers in the range 2 to 32.

ec32 = [[2, 4, 8, 16, 32],
        [3, 9, 27], 
        [5, 25], 
        [6, 12, 18, 24],
        [7], 
        [10, 20], 
        [11], 
        [13], 
        [14, 28], 
        [15], 
        [17], 
        [19], 
        [21], 
        [22], 
        [23], 
        [26], 
        [29], 
        [30], 
        [31]
       ];


// Problem 2b: Define equiv(M, N, EC)

// equiv(M, N, EC) is to determine whether M and N are equivalent in an
// equivalence relation where EC is the list of equivalence classes.
// We are allowed to assume that M and N always appear in one of the classes,
// but of course they are equivalent iff they appear in the same one.

equiv(M, N, EC) = member(N, first(find((C) => member(M, C), EC)));

// Explanation: From the list of equivalence classes EC we first find the class
// contains M as a member (there should be exactly one, if EC is well-formed).
// The result is a list with the class as its first member, so we need to use 
// first to get the actual class.  
// Then we check whether N is also a member of that class. 


// Problem 3a, Define isAnagramOf(X, Y)

// isAnagramOf(A, B) is true when A is an anagram of B, i.e. the two have
// exactly the same characters.

isAnagramOf(A, B) = sort(explode(A)) == sort(explode(B));

// Explanation: explode the strings to get lists of characters, then 
// sort those lists.  If the original strings had the same letters, then
// the sorted exploded lists are the same, and vice-versa.


// Problem 3b, Define anagramsOf(Word, List)

// anagramsOf(Word, List) returns the list of anagrams of Word that appear in
// List

anagramsOf(Word, List) = keep((Other)=>isAnagramOf(Word, Other), List);

// Explanation: Using isAnagramOf defined above, we keep all words in
// List that are anagrams of the given Word.


// Problem 3c: Define anagramClasses(Words)

// Noting that isAnagramOf is an equivalence relation, we can define 
// anagramClasses(Words) to be the list of equivalence classes of this
// relation over words in the list Words.

anagramClasses(Words) = 
    remove_duplicates(map((Word) => anagramsOf(Word, Words), Words));

// Explanation: Use map and anagramsOf to determine, for each word in the
// list Words its list of anagrams.  The same resulting list elements will
// appear multiple times in general, once for each member of an equivalence
// class.  remove_duplicates gets rid of the duplicates.  It relies on the
// fact that each list is ordered in exactly the same way, since each was
// derived from anagramsOf, which keeps returns the words in the same order
// as in the original list.  In this sense, the function anagramClasses
// is coupled to this particular implementaton of anagramsOf.  A different
// implementation might not return every set in the same order.


// (Optional) Problem 4c: Define doubleAnagramClasses(Words)

// A double anagram is a pair of pairs of words such that the words formed
// by concatenating the two words in each pair are anagrams of each other.
// Example:  ["flap", "hint"] and ["filth", "pan"].
// doubleAnagramClasses(Words) is to produce the list of equivalence classes
// double anagrams that can be formed out of list Words.  

// Method: From Words, create the list of all "unordered" pairs of words, along
// with their sorted letters, which form a triple.  Unordered means that we 
// do not include the symmetric cases of pairs reversed, and we do not
// include words paired with themselves, for these provide no useful added
// information.  For example from a pair "flap" and "hint" we would produce
// the triple ["afhilnpt", "flap", "hint"].  

// Then find the anagram classes among the first words in the triples,
// using the same technique as in the previous problem, but ignoring the
// original words.  From these anagram classes, extract the original pairs 
// of words.  

// allPrefixes(Words) produces a list of all prefixes of the list Words.

allPrefixes([]) => [];

allPrefixes([Word | Words]) => [[Word | Words] | allPrefixes(Words)];


// partialTriples(Words) produces the triples paired from a non-empty list
// which will be one of the prefixes above.

partialTriples([Word | Words]) => 
    map((Other) => [sortLetters(concat(Word, Other)), Word, Other], Words);


// sortLetters(Words) produces a new word with the same letters, sorted.

sortLetters(Word) = implode(sort(explode(Word)));


// allTriples produces all triples from a list by using partialTriples

allTriples(Words) = mappend(partialTriples, allPrefixes(Words));


// doubleAnagramsOf gets the Triples in List that have the same first component
// as Triple and returns the original pairs of words

doubleAnagramsOf(Triple, List) =
  map(rest, keep((Triple2) => first(Triple2) == first(Triple), List));


// doubleAnagramClasses forms the classes and removes classes of size one
// and duplicates.

doubleAnagramClasses(Words) = 
    triples = allTriples(Words),

    remove_duplicates(
      remove_singletons(
        map((Triple) => doubleAnagramsOf(Triple, triples), triples)));


// remove_singletons keeps only the lists in a list of lists that have
// more than one element.

remove_singletons(LoL) => keep((L) => length(L) > 1, LoL);


////////////////// Testing section //////////////////

// These three defintions are used for testing

// force forces evaluation (used for testing)

force([]) => [];
force([A | X]) => [force(A) | force(X)];
force(X) => X;


// check whether two lists (e.g. answers) are the same as sets

sameSets(S, T) = sort(S) == sort(T);

// check whether two lists (e.g. answers) are the same as sets of sets

sameSetOfSets(S, T) = sort(map(sort, S)) == sort(map(sort, T));


// Test 1a.

test(sameSets(v24, [[2, 3], [3, 1]]), 1);

test(sameSets(v576, [[2, 6], [3, 2]]), 1);

test(sameSets(v1024, [[2, 10]]), 1);

test(sameSets(v255255, 
              [[3, 1], [5, 1], [7, 1], [11, 1], [13, 1], [17, 1]]), 1);

test(sameSets(v139843693414425, 
              [[3, 1], [5, 2], [7, 3], [11, 4], [13, 5]]), 1);

test(sameSets(v19556258587787694114798080625, 
              [[3, 2], [5, 4], [7, 6], [11, 8], [13, 10]]), 1);


// Test 1b.

test(unFactor(v24), 24);
test(unFactor(v576), 576);
test(unFactor(v1024), 1024);
test(unFactor(v255255), 255255);
test(unFactor(v139843693414425), 139843693414425);
test(unFactor(v19556258587787694114798080625), 19556258587787694114798080625);

// Test 2a.

test(sameSetOfSets(ec32, 
        [[2, 4, 8, 16, 32], [3, 9, 27], [5, 25], [6, 12, 18, 24],
        [7], [10, 20], [11], [13], [14, 28], [15], [17], 
        [19], [21], [22], [23], [26], [29], [30], [31]]), 1);

// Test 3a.

test(isAnagramOf("elvis",  "lives"),  1);
test(isAnagramOf("eyes",   "yes"),    0);
test(isAnagramOf("wobble", "elbow"),  0);
test(isAnagramOf("bread",  "beard"),  1);
test(isAnagramOf("bread",  "bard"),   0);
test(isAnagramOf("goat",   "toga"),   1);


// Test 3b.

test(
sameSets(
  force(anagramsOf("bread",
   ["bread", "bared", "downer", "listen", "slient", "tried", "rave", "retired",
   "admirer", "beard", "married", "wonder", "aver", "lose", "sole", "sloe"]
)),
  ["bread", "bared", "beard"]), 1);


// Test 3c.

test(sameSetOfSets(force(anagramClasses(
["bread", "bared", "downer", "listen", "slient", "tried", "rave", "retired",
 "admirer", "beard", "married", "wonder", "aver", "lose", "sole", "sloe"]
)),
[["bread", "bared", "beard"], ["downer", "wonder"], ["listen", "slient"], ["tried"], ["rave", "aver"], ["retired"], ["admirer", "married"], ["lose", "sole", "sloe"]]), 1);


// Test 4.

test(sameSets(force(doubleAnagramClasses(

["flap", "hill", "hint", "pan", "olin", "loan", "hall", "filth", "pal",
 "flan", "paint", "lip", "pail", "pain", "plan", "toil", "tan", "pill",
 "fifth", "pith", "old", "dip", "pin"])),

[
[["flap", "hint"], ["pan", "filth"], ["flan", "pith"]], 
[["hill", "pan"], ["hall", "pin"]], 
[["hill", "loan"], ["olin", "hall"]], 
[["hill", "pal"], ["hall", "lip"]], 
[["pan", "olin"], ["loan", "pin"]], 
[["pan", "lip"], ["pal", "pin"]], 
[["pan", "pail"], ["pal", "pain"]], 
[["pan", "pill"], ["lip", "plan"]], 
[["olin", "pal"], ["loan", "lip"]], 
[["loan", "dip"], ["pain", "old"]], 
[["lip", "pain"], ["pail", "pin"]]
]), 
1
);