% 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;