TASK 1A
function make_k_list(k, d) {
    if (d === 0){
        return 0;
    } else { 
        const wish = make_k_list(k, d - 1); //each time an inner element is accessed, number of lists(degree) decreases by 1, while no. of elem kk is the same.
        return build_list(x=> wish, k);
    }
}

TASK 1B
function sum_k_list(klist) {
    
    if (!is_list(klist)){ //BC: if not list, return number
        return klist;
    } else {              //if list, apply recursion to get sum of internal list, continue addition.
        return accumulate ((x, acc) => sum_k_list(x) + acc, 0, klist);
    }
}
TASK 1C
function map_k_list(f, klist) {
    if (!is_list(klist)){
        return f(klist);
    } else {
        return map(x => map_k_list(f,x), klist);
    }
}
TASK 2A
function has_no_consecutive_pairs(list){
    for ( let i = 0; i < length(list) - 1; i = i + 1){
        if (list_ref(list, i) === list_ref(list, i + 1)){
            return false;
        } else {
            return true;
        }
    }
}


function route_distance(mat, route) {
    let total_distance = 0;
    if (length(route) < 2){
        return false;
    } else if (!has_no_consecutive_pairs(route)){
        return false;
    } else {
        for ( let i = 0; i < length(route) - 1; i = i + 1){
            const from = list_ref(route, i);
            const to = list_ref(route, i + 1);
            total_distance = total_distance + mat[from][to];
        }
        return total_distance;
    }

}

// Route: length of at least 2
// no repeating of houses back to back
TASK 2B
// The route_distance function for the preceding task has been
// pre-declared here for you to use in this task.
// Do not declare your own route_distance function.
/*
function route_distance(mat, route) {
    // Pre-declared
}
*/

function shortest_paper_route(n, mat, start) {

        // You can keep, modify or remove the permutations function.
    function permutations(ys) { //Ultimately generates a list of lists of all different permutations as lists
        return is_null(ys)
            ? list(null)
            : accumulate(append, null,
                map(x => map(p => pair(x, p), 
                             permutations(remove(x, ys))),
                    ys));
                    
            //permutations(remove(x, ys)): removes x, generates permutations for all other elements
            //Outer map: loops through each x in ys
                //Inner map: pairs x with every new permutation p genrated
    }       //accumulate: accumulates all different permutations(lists) in one list (becomes a list of lists)


// n is the total number of houses
// peter's house can be any
// One simple possible permutations is list(1,2, 3 ... , n)

    const route_without_start = remove(start, build_list(x => x, n));
    const all_routes_without_start = permutations(route_without_start);
    const all_routes = map ( x => append(pair(start, x), list(start)), all_routes_without_start);
    
    function filter_shortest(lst){
        let smallest_distance = Infinity;
        let smallest_permutation = null;

        for ( let i = 0; i < length(lst); i = i + 1){
            const current_distance = route_distance(mat, list_ref(lst, i));
            const current_permutation = list_ref(lst, i);
            
            if ( current_distance < smallest_distance){
                smallest_distance = current_distance;
                smallest_permutation = current_permutation;
            }
        }
        return pair(smallest_permutation, smallest_distance);
    }
    return filter_shortest(all_routes);
}

//generate list of permutations 
//Define function to return smallest distance and list using route distance
//Options:
  //1. Apply sort list, get head.
  
  
/*
Mistakes:
1. build_list : list required includes from 0 to n not 1 to n)
2. all_routes --->place pair after append to avoid a nested pair structure
3. smallest_distance variable: initialise it to infinity instead of 0
4. for loop: place return statement outside of if and for loop to not besl loop
5. for loop: starting varible should be i = 0 not 1
6. for loop: termination condition to be i < length(lst) instead of i < length(lst) - 1
    i < length(lst) - 1 : used to compare between 2 consecutive elements for sorting
    i < length(lst): used to go through the while list
7. current_distance and current_permutation should be defined as constants instead of variables
   as they shouldn't be changed within each iteration of loop
*/
TASK 3A
function make_postfix_exp(bae) {
    if (is_number(bae)){   //base case: if number, return number in array
       return [bae];
    } else {
       const left = make_postfix_exp(bae[0]);
       const right = make_postfix_exp(bae[2]);
       const op = bae[1]; //Why doesn't op require make_postfix_exp command?
       
       const result = [];
       for ( let i = 0; i < array_length(left); i = i + 1){ 
           result[array_length(result)] = left[i]; //next element of result is symbolised by array_length(result)
       } 
       
       for ( let i = 0; i < array_length(right); i = i + 1){
           result[array_length(result)] = right[i];
       }
       result[array_length(result)] = op; //no loop required, since will only have 1 element
       return result;
   }
}
    
/*
Key concepts:
1. "appending" different arrays by using a loop.
2. Rearranging elements of an array
*/
TASK 3B
let stack = []; // ionitialize stack

function eval_postfix_exp(pfe) { //evaluates through array pfe
    stack = [];
    for (let i = 0; i < array_length(pfe); i = i + 1){ //look at each element
        if(is_number(pfe[i])){ //check if current element is a number
            push(pfe[i]); //to add current elem named in pfe into stack
        } else {
            const operands = take_two(); //side effect of shortening stack, but calls the 2 most recent numbers from stack, returning in pair format
            const result = evaluate(head(operands), tail(operands), pfe[i]);  
            push(result); //add result to stack
        }
    }
    const final_result = stack[0]; //assigns value to final computed value of stack
    stack = [];       //good practice to clear stack
    return final_result;
}

function push(elem){
    stack[array_length(stack)] = elem;
}

function take_two(){
    const len = array_length(stack);
    const right = stack[len - 1]; //last elem of stack
    const left = stack[len - 2];  //2nd to last elem of stack
    const new_stack = [];         //new array to 
    for (let i = 0; i < len - 2; i = i + 1){ // for loop removes the last 2 elements, by copying every element except last 2 to new_stack
        new_stack[i]=stack[i];    //stack is then assigned to new_stack
    }
    stack = new_stack;
    return pair(left, right); 
}


//Purpose:
//1. retrieve last 2 elem from stack
//2. remove these elem ofrom stack
//3. return these 2 numbers s a pair, so they can be used in a operation

function evaluate(left, right, op){
    if (op === '+'){
        return left + right;
    }
    if (op === '-'){
        return left - right;
    }
    if (op === '*'){
        return left * right;
    }
    if (op === '/'){
        return left / right;
    }
}
///If number, add it to stack