/*
 
  part1.rex (for cs60 hw2, S09)

  Name:
  
  Comments to the graders:




*/  

// problem 1, part 1
erdos( x ) => x%2 == 0 ? x/2;
erdos( x ) => 3*x + 1;

test( erdos(3),   10 );
test( erdos(4),    2 );
test( erdos(  3 ),      10 );
test( erdos( 10 ),       5 );
test( erdos(  5 ),      16 );
test( erdos( 16 ),       8 );
test( erdos(  8 ),       4 );
test( erdos(  4 ),       2 );
test( erdos(  2 ),       1 ); // repeated application leads to 1...


// problem 1, part 2
countIter( f, x, d ) => x == d ? 0;
countIter( f, x, d ) => 1 + countIter( f, f(x), d );

test( countIter( (x)=>x*2, 1, 1024 ),    10 ); 
test( countIter( erdos, 17, 1 ),         12 );
test( countIter( erdos,  3,  1 ),     7 );
test( countIter( erdos, 16,  1 ),     4 );
test( countIter( erdos, 16, 16 ),     0 );
test( countIter( (x)=>x+1, 17, 19 ),  2 ); // using an anonymous function



// problem 2
divBy( 0 ) => (x)=>0;
divBy( k ) => (x)=>x%k == 0;

f = divBy(7);          // let f be the name of the function output by the call divBy(7)
test( f(42),    1 );
test( f(41),    0 );

g = divBy(0);
test( g(42),    0 );
test( g(41),    0 );

test( divBy(3)(15),    1 );
test( divBy(3)(14),    0 );



// problem 3
all_pairs( [], L ) => [];
all_pairs( [f|R], L ) => append( map( (s)=>[f,s], L ), all_pairs( R,L ) );


test( all_pairs( [],[8,9] ),              [] );
test( all_pairs( [1,2,3],[8,9] ),   [ [1,8], [1,9], [2,8], [2,9], [3,8], [3,9] ] );



//min_diff( L ) => length(L) < 2 ? "too few elements!";
//min_diff( [a,b|R] ) => reduce( ([a,b],[c,d])=> abs(a-b)<abs(c-d)?
//                                    [a,b]:[c,d] , [1,100], all_pairs( [a,b|R] ));



// example trees
T1 = [10, [3, [], []], [42, [20, [], []], [60, [], []] ] ];
T2 = [20, [3, [], []], [42, [], [60, [], []] ] ];

T3 = [42, [21, [12, [], []],
               [41, [27, [], []], []] ], // end of left subtree
          [60, [47, [44, [], [46, [], []]], [58, [], []]],
               [77, [], [100, [], []]] ] ]; // end of right subtree

T4 = [44, [21, [12, [], []],
               [41, [27, [], []], []] ], // end of left subtree
          [60, [47, [46, [], []], [58, [], []]],
               [77, [], [100, [], []]] ] ]; // end of right subtree



// problem 4 - treemin
treemin( [r, [], R ] ) => r;
treemin( [r, L, R] ) => treemin(L);

test(treemin(T1),    3 );
test(treemin(T3),   12 );



// bestWord





// problem 6 - tail recursive functions

lg2_tail( x ) => lg2_help( x, 0 );

lg2_help( x, acc ) => x <= 1 ? acc;
lg2_help( x, acc ) => lg2_help( x/2.0, acc + 1 );



fib_tail( 0 ) => [];
fib_tail( 1 ) => [1];
fib_tail( n ) => fib_help( n-2, [1,1], 1, 1 );

fib_help( 0, racc, t_2, t_1 ) => reverse( racc );
fib_help( n, racc, t_2, t_1 ) => fib_help( n-1, [t_2+t_1|racc], t_1,
t_2+t_1 );


test( lg2_tail( 7 ),    3 );
test( lg2_tail( 8 ),    3 );
test( lg2_tail( 9 ),    4 );


test( fib_tail( 0 ),    [] );
test( fib_tail( 2 ),    [1,1] );
test( fib_tail( 8 ),    [1,1,2,3,5,8,13,21] );



// problem 7 - indiv
indivisibles( d, L ) = drop( divBy(d), L );

R1_10 = range(1,10); // inclusive in Rex
test( indivisibles( 3, R1_10 ),  [1,2,4,5,7,8,10] );
test( indivisibles( 3, R1_10 ),  [1,2,4,5,7,8,10] );
test( indivisibles( 2, [0,1,2,3,4] ),    [1,3] );
test( indivisibles( 3, [0,1,2,3,4] ),    [1,2,4] );
test( indivisibles( 0, [0,1,2,3,4] ),    [0,1,2,3,4] );


// problem 8 - reachable

reachable( a, a, G ) => 1;
reachable( a, b, [] ) => 0;
reachable( a, b, G ) => asKids = kids( a, G ),
                        reduce( or, 0, map( (s)=>reachable(s,b,G), asKids ) );



// problem 9 - mostKids
// functions done in class:
// flatten
flatten( [] ) => [];
flatten( [f|R] ) => is_list(f) ? append( flatten(f), flatten(R) );
flatten( [f|R] ) => [f|flatten(R)];
// kids
kids( n, [] ) => [];
kids( n, [[a,b]|R] ) => n==a ? [b|kids(n,R)] : kids(n,R);

countKids( n, G ) => length( kids(n,G) );
nodes( G ) => remove_duplicates( flatten( G ) );


test( sort( nodes( [["D","A"], ["D","B"], ["D","C"], ["E","A"],
                    ["E","D"], ["F","E"], ["A","F"]] ) ),         
      ["A","B","C","D","E","F"] );


mostKids( G ) => KidsPairs = map( (n)=>[countKids(n,G),n], nodes(G) ),
                 mostKidsPair = reduce( max, [-1,0], KidsPairs ),
                 second( mostKidsPair );



test( mostKids([ ["D","A"], ["D","B"], ["D","C"], ["E","A"],
                 ["E","D"], ["F","E"], ["A","F"]  ]),         "D" );
test( member( mostKids([ ["C","B"], ["B","A"] ]), ["C","B"] ), 1  );



// problem 10 - delete
delete( x, [r, L, R] ) => r < x ? [r, L, delete(x,R)];
delete( x, [r, L, R] ) => r > x ? [r, delete(x,L), R];
delete( x, [x, L, []] ) => L;
delete( x, [x, [], R] ) => R;
// the trickiest case...
delete( x, [x, L, R] ) => newr = treemin(R),
                          [newr, L, delete(newr,R)];

// tests
test( delete( 42, T3 ),     T4 );
test( delete( 10, T1 ),     T2 );





// extra credit
shortestPath( a, b, [] ) => [];
shortestPath( a, b, G ) => "need to work on this...";