% PROBLEM 1 %

% 1 -- 5points%

% 1A %

function myPack (X) = 
let (vals, flags) = unzip(X);
    flag_count = plus_scan ({btoi(i): i in flags});
  in cond_put(vals, flag_count, flags, dist(0, count(flags)));

% PROBLEM 2 -- 5 points%
% Two ways of doing this %

function stock (X) =
  let mins_to_date = min_scan(X);
      max_gain_to_date = {today-mins : today in X; mins in mins_to_date};
      max_gain = max_val(max_gain_to_date);
  in 
      if(max_gain>0) then max_gain else 0;

function stock_aux (a,start,end) =
 if (start == end) then [a[start], a[end], 0]
 else let mid = floor(float(start+end)/2.0);
     ranges = [(start,mid), (mid+1,end)];
     ma = {stock_aux(a,x,y): (x,y) in ranges};
     gmin = min(ma[0][0], ma[1][0]);
     gmax = max(ma[0][1], ma[1][1]);
     gdiff = max(max(ma[0][2], ma[1][2]), ma[1][1] - ma[0][0]);
 in [gmin, gmax, gdiff];

function stock(a) =
  let retval = stock_aux(a,0,(#a)-1)
  in if(retval[2]>0) then retval[2] else 0;

% PROBLEM 3 -- 10 points %

function ptr_jump (X, count) =
 if (count == 0) then X
 else    ptr_jump({X[i]: i in X}, count-1);

function ptr_jump_log (X) =
 ptr_jump (X, 2+ceil(log(float(#X),2.0)));


% 3A %

function findCycle (X) =
 let P = ptr_jump_log(X);
 in any({((P[P[i]] /= P[i]) and (P[i] /= i)): i in P});

$ 3B%

function findRoots (X) =
 ptr_jump_log(X);

% 3C %

function ptr_jump_max (X, max_array, count) = 
 if (count == 0) then max_array
 else let max_array_new = {max(max_array[X[i]],max_array[i])  : i in X};
      in ptr_jump_max ({X[i]: i in X}, max_array_new, count-1);


function ptr_jump_cycles (X) = 
  ptr_jump_max(X,X, 2+ceil(log(float(#X),2.0)));

function countCycles (X) =
  let cycle_max = ptr_jump_cycles (X);
      index_cycle_max = zip([0:#X], cycle_max);
      unique = {i==ptr: (i,ptr) in index_cycle_max};
    in count(unique);

% 3D %

function rand_jump(X) =
  if (all ({X[i] == i: i in X})) then X
  else let rand_inits = dist(2,#X); 
       rand_vals = {rand(i): i in rand_inits};
       X_pairs = zip([0:#X], X);
       flag_list = {if(rand_vals[ptr]==0 and rand_vals[i]==1)
                       then (ptr,F)
                       else (ptr,T)
                     : (i,ptr) in X_pairs };
       flag_removal = write (dist(T,#X), flag_list);
       removal_count = plus_scan ({1-btoi(i): i in flag_removal});
       X_new_list = {if(rand_vals[ptr]==0 and rand_vals[i] == 1)
                        then (i,X[ptr])
                        else (i,ptr)
                     : (i,ptr) in X_pairs};
       X_new_raw = write (X, X_new_list);
       X_new = { ptr-removal_count[ptr]: ptr in X_new_raw};
     in rand_jump (pack(zip(X_new,flag_removal)));

function countCyclesFast (X) =
  let cycles = rand_jump(X);
    in #cycles;