// File: a01.rex // Author: Robert Keller // Puprose: CS60 Assignment 1 Sample Solutions // Function factors was provided // factors(N) produces the prime decomposition of N, in the form of // a list of pairs [K, P] where K is a prime factor and P is the power // of K by which N is divisible. The argument to factors must be a // positive integer. factors(1) => []; // The rule above deals with the special case of factoring 1. factors(N) => divides(2, N) ? // If 2 divides N, ([Residue, Power] = factors1(2, N/2, 1), // get power of 2 [[2, Power] | factorsFrom(3, Residue)] // get the rest. ); // The rule above factors out all multiples of 2, then calls factorsFrom // to do the rest of the work. factors(N) => factorsFrom(3, N); // factorsFrom(K, N) produces factors of N starting with K as the first // possible factor. N is assumed to have no factors smaller than K, // and K is assumed to be odd (to allow stepping by 2). factorsFrom(K, 1) => []; factorsFrom(K, N) => divides(K, N) ? ([Residue, Power] = factors1(K, N/K, 1), [[K, Power] | factorsFrom(K+2, Residue)] ); factorsFrom(K, N) => factorsFrom(K+2, N); // factors1(K, N, Acc) adds to Acc the number of times K divides N, // returning the residual after dividing this number of times and the power. factors1(K, 1, Acc) => [1, Acc]; factors1(K, N, Acc) => divides(K, N) ? factors1(K, N/K, Acc+1) : [N, Acc]; // 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]]; // 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)); // Explanation: 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. test(unFactor([]), 1); test(unFactor([[23, 1]]), 23); test(unFactor([[2, 1], [47, 1]]), 94); test(unFactor([[2, 1], [5, 1], [19, 1]]), 190); // Problem 2a: Define uniqueFactors // uniqueFactors(N) gives the unique prime factors of N without regard to // multiplicity uniqueFactors(N) = map(first, factors(N)); test(map(uniqueFactors, range(1, 100)), [[], [2], [3], [2], [5], [2, 3], [7], [2], [3], [2, 5], [11], [2, 3], [13], [2, 7], [3, 5], [2], [17], [2, 3], [19], [2, 5], [3, 7], [2, 11], [23], [2, 3], [5], [2, 13], [3], [2, 7], [29], [2, 3, 5], [31], [2], [3, 11], [2, 17], [5, 7], [2, 3], [37], [2, 19], [3, 13], [2, 5], [41], [2, 3, 7], [43], [2, 11], [3, 5], [2, 23], [47], [2, 3], [7], [2, 5], [3, 17], [2, 13], [53], [2, 3], [5, 11], [2, 7], [3, 19], [2, 29], [59], [2, 3, 5], [61], [2, 31], [3, 7], [2], [5, 13], [2, 3, 11], [67], [2, 17], [3, 23], [2, 5, 7], [71], [2, 3], [73], [2, 37], [3, 5], [2, 19], [7, 11], [2, 3, 13], [79], [2, 5], [3], [2, 41], [83], [2, 3, 7], [5, 17], [2, 43], [3, 29], [2, 11], [89], [2, 3, 5], [7, 13], [2, 23], [3, 31], [2, 47], [5, 19], [2, 3], [97], [2, 7], [3, 11], [2, 5]]); // Problem 2b: 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 2c: 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. test(equiv(2, 6, [[1, 5], [3, 4], [6, 9, 2]]), 1); test(equiv(2, 2, [[1, 5], [3, 4], [6, 9, 2]]), 1); test(equiv(2, 9, [[2, 4], [3], [6, 9]]), 0); test(equiv(2, 9, [[2], [9]]), 0); test(equiv("foo", "bar", [["foo", "bar"]]), 1); test(equiv("foo", "baz", [["foo", "bar"], ["baz"]]), 0); // 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. test(isAnagramOf("goat", "toga"), 1); test(isAnagramOf("goata", "toga"), 0); test(isAnagramOf("goat", "atoga"), 0); test(isAnagramOf("goat", "moat"), 0); // 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. test(sort(anagramsOf("bread", ["bread", "bared", "downer", "listen", "slient", "tried", "rave", "retired", "admirer", "beard", "married", "wonder", "aver", "lose", "sole", "sloe"])), ["bared", "beard", "bread"]); // 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. test(sort(map(sort, anagramClasses(["bread", "bared", "downer", "listen", "slient", "tried", "rave", "retired", "admirer", "beard", "married", "wonder", "aver", "lose", "sole", "sloe"]))), [["admirer", "married"], ["aver", "rave"], ["bared", "beard", "bread"], ["downer", "wonder"], ["listen", "slient"], ["lose", "sloe", "sole"], ["retired"], ["tried"] ]); // (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: ["duct", "tape"] and ["cadet", "putt"]. // doubleAnagramClasses(Words) is to produce the list of equivalence classes // double anagrams that can be formed out of list Words. // doubleAnagramClasses(Words) forms the list of equivalence classes of // double anagrams made from a list of words. It intentionally does not // include the trivial cases of words paired with themselves, // nor does it include singleton classes, corresponding to pairs of words // that are not double anagrams with any other pair. doubleAnagramClasses(Words) = classes(triples(Words)); // doubleAnagrams first creates the list of "triples" from Words. A triple // consists of: // // a string containing the sorted list of letters of the two words, // // the first word // // the second word // // The purpose of the first component is so that the letters of two word // pairs can be compared easily, without recomputing. // // For example, if the two words are "duct" "tape", the triple will be // // ["acdeputt", "duct", "tape"] // // The function then finds the anagram pairs for each triple. // // For efficiency reasons, if a pair [A, B] is present in a triple // then the pair [B, A] is not present. This eliminates the redundant // construction of classes for both pairs, which would be the same. // triples(Words) returns the triples for a list of words. triples(Words) = mappend((Word1) => map((Word2) => makeTriple(Word1, Word2), wordsGreaterThan(Word1, Words)), Words); // triples creates triples for all pairs of words in list Words. // It only includes one triple for each symmetric pair, to avoid needless // work later on. This is done by restricting the words with which Word1 // is paired to words alphabetically greater than Word1. // All lists of triples are appended together using the mappend function. // wordsGreaterThan(Word1, Words) returns the list of words from Words // that are alphabetically greater than Word1. wordsGreaterThan(Word1, Words) = keep((Word2) => Word1 < Word2, Words); // makeTriple makes a triple from two words, consisting of the letters // in the word in sorted order, the first word, and the second word. makeTriple(Word1, Word2) = [letters(Word1, Word2), Word1, Word2]; // letters gets the sorted list of letters in a pair of words. letters(Word1, Word2) = sort(explode(concat(Word1, Word2))); // classes(Triples) creates the list of double-anagram equivalence classes // for all pairs of words in the list of triples. This list will contain // no duplicates of any class and no classes with only one element. classes(Triples) = rdsl(sort(dropSingles(map((Triple1) => class(Triple1, Triples), Triples)))); // class(Triple1, Triples) creates the double-anagram equivalnce classes of // the pair of words in Triple1 class(Triple1, Triples) = map(rest, keep((Triple2) => first(Triple1) == first(Triple2), Triples)); // class keeps only triples Triple2 in Triples that are double anagrams // with Triple1, based on comparing their sorted letters. The pair // part, consisting of the last two elements, is returned. // dropSingles(L) drops all elements of L that are lists of length 1 or less. dropSingles(L) => drop((X) => length(X) <= 1, L); // Note that the built-in remove_duplicates could be used in lieu of rdsl. // This is purely a matter of efficiency. // rdsl(L) means "remove duplicates from sorted list". Removing duplicates // from a sorted list is easier than from an unsorted list, because // all duplicates are found adjacent in a sorted list. The cost of // sorting the list combined with rdsl is generally less than calling // remove_duplicates, which preserves the order of first occurrences of // elements in the list. rdsl([]) => []; rdsl([A | X]) => [A | rdsl2(A, X)]; // rdsl is the interface function. The work is done by rdsl2. The // first argument of rdsl2 is an element already occurring in the // resulting list. Duplicates of it are removed, until the next // non-duplicate is encountered. rdsl2(A, []) => []; rdsl2(A, [A | X]) => rdsl2(A, X); rdsl2(A, [B | X]) => [B | rdsl2(B, X)]; // Test cases: wordset1 = ["aced", "cadet", "cut", "duct", "paint", "pine", "put", "putt", "tape", "taped", "twin", "watt", "wet"]; result1 = [[["aced", "putt"], ["cadet", "put"], ["cut", "taped"], ["duct", "tape"]], [["paint", "wet"], ["pine", "watt"], ["tape", "twin"]]]; // Show the output with quotes *q test(sort(doubleAnagramClasses(wordset1)), sort(result1));