/* HW3 solutions (Rex problems) */ // Unicalc functions // diff is a helper function that removes all of the // elements in the second list from the first list diff( [], M ) => []; diff( L, [] ) => L; diff( [f|R], [e|S] ) => f==e? diff(R,S) : f [ q1, diff(N1, D1), diff(D1, N1) ]; test( simplify( [42, ["kg", "meter", "second", "second"], ["kg", "kg", "second"]] ), [42, ["meter", "second"], ["kg"]] ); test( simplify( [3.14, ["meter", "second"], ["meter", "second", "second"]] ), [3.14, [], ["second"]] ); // multiply does just that, but for Quantity lists... multiply( [q1, N1, D1], [q2, N2, D2] ) => simplify( [q1*q2, sort(append(N1,N2)), sort(append(D1,D2)) ] ); // divide does just that, but for Quantity lists... divide( [q1, N1, D1], [q2, N2, D2] ) => simplify( [q1*1.0/q2, sort(append(N1,D2)), sort(append(D1,N2)) ] ); test( multiply( [2, ["kg"], ["second"]], [3, ["meter"], ["second"]] ), [6, ["kg", "meter"], ["second", "second"]] ); test( divide( [10, ["meter"], ["second"]], [5, ["meter"], []] ), [2, [], ["second"]] ); // load in the database named miniDB *i miniDB.rex // convUnit looks up u in the database DB convUnit( u, DB ) => r = assoc( u, DB ), r != [] ? second(r) : [1.0, [u], []]; // norm returns a normalized Quantity list equivalent // to the input quantity list (uses normUnit) norm( [q, [], []], DB) => [q, [], []]; norm( [q, [f|R], []], DB) => multiply(normUnit(f, DB), norm( [q,R,[]], DB )); norm( [q, N, [f|R]], DB) => divide(norm( [q,N,R], DB ), normUnit( f, DB )); // normUnit returns a normalized Quantity list equivalent // to the input unit string (uses norm) normUnit( u, DB ) => r = assoc( u, DB ), r != [] ? norm(second(r), DB) : [1.0, [u], []]; test( normUnit( "hour", miniDB ), [3600.0, ["second"], []] ); test( normUnit( "meter", miniDB ), [1.0, ["meter"], []] ); test( norm( [1.0, ["hour"], []], miniDB ), [3600.0, ["second"], []] ); test( norm( [42, ["meter"], []], miniDB ), [42.0, ["meter"], []] ); test( norm( [2, ["meter"], ["cm", "cm"]], miniDB ), [20000.0, [], ["meter"]] ); // convert does the final divide that converts from one unit to another convert( QL1, QL2, DB ) => divide( norm(QL1, DB), norm(QL2, DB) ); test( convert( [125, ["cm"], ["second"]], [1.0, ["meter"], ["second"]], miniDB ), [1.25, [], []] ); test( convert( [125, ["cm"], ["second"]], [1.0, ["meter"], ["second","second"]], miniDB ), [1.25, ["second"], []] ); test( convert( [125, ["cm"], ["second","second"]], [1.0, ["meter"], ["second"]], miniDB ), [1.25, [], ["second"]] ); /* Testing: convert( [1, ["furlong"], ["fortnight"]], [1, ["mile"], ["hour"]], miniDB ); convert( [1, ["furlong"], ["hour"]], [1, ["mile"], ["fortnight"]], miniDB ); norm( [1, ["furlong"], ["fortnight"]], miniDB ); */ // two acyclic graphs G1 = [["A","B"],["B","C"],["C","D"],["D","E"],["E","F"], ["A","Z"],["Z","F"]]; G2 = [["A","B"],["B","C"],["C","D"],["D","E"],["E","F"], ["A","Z"],["Z","E"],["E","Y"],["Y","F"],["F","G"]]; // two graphs with cycles G3 = [["A","B"],["B","C"],["C","D"],["D","E"],["E","A"]]; G4 = [["A","B"],["B","C"],["C","D"],["D","E"],["E","A"], ["X","Y"],["Y","Z"],["Z","B"],["E","X"]]; // flatten removes all nesting structure... flatten( [] ) => []; flatten( [f|R] ) => !is_list(f) ? [f|flatten(R)]; flatten( [f|R] ) => append( flatten(f), flatten(R) ); // smaller: the shorter of two lists smaller( L, M ) => length(L) < length(M) ? L : M; // shortestPath - direct "weirdo" style // the order of these base cases matters! sp( a, a, G ) => [ a ]; sp( a, b, [] ) => []; sp( a, b, [[c,d]|R] ) => loseit = sp( a, b, R ), // without the edge u1 = sp( a, c, R ), // with the edge, part 1 u2 = sp( d, b, R ), // with the edge, part 2 useit = (u1==[] || u2==[]) ? [] : append(u1,u2), // did it work? // end of local definnitions, now our return value: loseit == [] ? useit : // if one fails, use the other useit == [] ? loseit : // if one fails, use the other smaller(useit, loseit); // take the smaller // sublists sublists( [] ) => [ [] ]; sublists( [f|R] ) => loseit = sublists(R), useit = map( (L)=>[f|L] , loseit ), append( loseit, useit ); test( sublists( [] ), [ [] ] ); test( sort(sublists( [1] )), [ [], [1] ] ); test( sort(sublists( [1,2] )), [ [], [1], [1,2], [2] ] ); test( sort(sublists( [1,2,3] )), [ [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3] ] ); shortestPath = sp; // give it a longer name test( shortestPath("Z", "A", G1), [] ); test( shortestPath("A", "A", G1), ["A"] ); test( shortestPath("A", "B", G1), ["A","B"] ); test( shortestPath("A", "D", G1), ["A","B","C","D"] ); // sum sum( L ) => reduce( +, 0, L ); // makeChange makeChange( Coins, value ) => CoinSets = sublists( Coins ), GoodCoinSets = keep( (L)=>value==sum(L), CoinSets ), append(GoodCoinSets, GoodCoinSets); //sort( remove_duplicates( GoodCoinSets ) ); srd( LoL ) = sort(remove_duplicates( LoL )); test( srd( makeChange( [5,10,10,10,25], 30 ) ), [[5, 25], [10, 10, 10]] ); test( srd( makeChange( [5,10,10,10,25], 35 ) ), [[5,10,10,10],[10, 25]] ); test( srd( makeChange( [5,5,10,10,10,25], 30 ) ), [[5,5,10,10], [5, 25], [10, 10, 10]] ); test( srd( makeChange( [5,5,10,10,10,25], 35 ) ), [[5,5,25], [5,10,10,10], [10, 25]] ); // make change "use-it-or-lose-it" makeChange2( Coins, value ) => sort(remove_duplicates( mcHelper2( Coins, value ))); mcHelper2( [], 0 ) => [ [] ]; // can make a zero value with no coins mcHelper2( [], x ) => []; // can't make a non-zero value mcHelper2( [f|R], value ) => loseit = mcHelper2( R, value ), useit = map( (L)=>[f|L], mcHelper2( R, value-f ) ), append( loseit, useit); test( makeChange2( [5,10,10,10,25], 30 ), [[5, 25], [10, 10, 10]] ); test( makeChange2( [5,10,10,10,25], 35 ), [[5,10,10,10],[10, 25]] ); test( makeChange2( [5,5,10,10,10,25], 30 ), [[5,5,10,10], [5, 25], [10, 10, 10]] ); test( makeChange2( [5,5,10,10,10,25], 35 ), [[5,5,25], [5,10,10,10], [10, 25]] );