Programming Fundamentals

// Written by Sasha Vassar

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

struct node {
    struct node *next;
    int data;
};

// count_in_range should return the count of how many nodes in the list have a value 
// strictly between the values of the first and last node
int count_in_range(struct node *head) {
    if (head == NULL || head->next == NULL || head->next->next == NULL) {
        return 0;
    }
    int first_val = head->data;
    
    struct node *curr = head;
    while (curr->next != NULL) {
        curr = curr->next;
    }
    int last_val = curr->data;

    int count = 0;
    curr = head;
    while (curr != NULL) {
        if (curr->data > first_val && curr->data < last_val) {
            count++;
        }
        curr = curr->next;
    }

    return count;
}

////////////////////////////////////////////////////////////////////////
//               DO NOT CHANGE THE CODE BELOW                         //
////////////////////////////////////////////////////////////////////////

struct node *strings_to_list(int len, char *strings[]);

// DO NOT CHANGE THIS MAIN FUNCTION
int main(int argc, char *argv[]) {
    // create linked list from command line arguments
    struct node *head = strings_to_list(argc - 1, &argv[1]);

    // If you're getting an error here,
    // you have returned an uninitialized value
    printf("%d\n", count_in_range(head));

    return 0;
}

// DO NOT CHANGE THIS FUNCTION
// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
    struct node *head = NULL;
    for (int i = len - 1; i >= 0; i = i - 1) {
        struct node *n = malloc(sizeof(struct node));
        assert(n != NULL);
        n->next = head;
        n->data = atoi(strings[i]);
        head = n;
    }
    return head;
}

// Written by Sasha Vassar

#include <stdio.h>
#include <stdlib.h>

#define NUM_COLS 5

// sum_after_even should return the total sum of the values  
// in each row of the 2D array, after the first even number.

int sum_after_even(int num_rows, int array[][NUM_COLS]) {
    int total = 0;

    for (int i = 0; i < num_rows; i++) {
        int found_even = 0;
        for (int j = 0; j < NUM_COLS; j++) {
            if (found_even == 1) {
                total += array[i][j];
            } else if (array[i][j] % 2 == 0) {
                found_even = 1;
            }
        }
    }

    return total;
}

// This is a simple main function which could be used
// to test your sum_after_even function.
// It will not be marked.
// Only your sum_after_even function will be marked.
int main(void) {
    int test_array[][NUM_COLS] = {
        {16, 12, 8, 3, 1},  
        {2, 0, 10, 1, 4},  
        {1, 1, 1, 13, 1},  
        {5, 5, 5, 8, 2},  
        {5, 5, 5, 5, 5}
    };

    int result = sum_after_even(5, test_array);

    // Example Explanation:
    //    {16, 12, 8,  3,  1},  | 12 + 8 + 3 + 1 = 24
    //    {2,  0, 10,  1,  4},  | 0 + 10 + 1 + 4 = 15
    //    {1,  1,  1, 13,  1},  | 0
    //    {5,  5,  5,  8,  2},  | 2
    //    {5,  5,  5,  5,  5}   | 0
    //    --------------------------------------
    //    TOTAL = 24 + 15 + 0 + 2 + 0 = 41 
    
    printf("%d\n", result);

    return 0;
}

// Written by Sasha Vassar

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// DO NOT MODIFY THIS STRUCT
struct node {
    int          data;
    struct node *next;
};

////////////////////////////////////////////////////////////////////////////////
// DO NOT CHANGE THESE FUNCTION PROTOTYPES
////////////////////////////////////////////////////////////////////////////////
struct node *insert_between_diff(int value, struct node *head);
struct node *strings_to_list(int len, char *strings[]);
void print_list(struct node *head);
void free_list(struct node *head);




//##############################################################################
// TODO: IMPLEMENT THIS FUNCTION
//##############################################################################
// Insert the given 'value' node between the first occurence of 
// two consecutive nodes whose absolute difference is 6 or 7
struct node *insert_between_diff(int value, struct node *head) {
    struct node *new_node = malloc(sizeof(struct node));
    assert(new_node != NULL);
    new_node->data = value;
    new_node->next = NULL;

    if (head == NULL) {
        return new_node;
    }

    struct node *curr = head;

    while (curr->next != NULL) {
        int diff = abs(curr->data - curr->next->data);
      
        if (diff == 6 || diff == 7) {
            new_node->next = curr->next;
            curr->next = new_node;
            return head;
        }
        curr = curr->next;
    }

    curr->next = new_node;

    return head;
}





///////////////////////////////////////////////////////////////////////////////
// DO NOT EDIT MAIN
///////////////////////////////////////////////////////////////////////////////
int main(int argc, char *argv[]) {
    int value;
    scanf("%d", &value);
    // create linked list from command line arguments
    struct node *head = NULL;
    if (argc > 1) {
        // list has elements
        head = strings_to_list(argc - 1, &argv[1]);
    }
    struct node *new_head = insert_between_diff(value, head);
    print_list(new_head);
    free_list(new_head);
    return 0;
}
////////////////////////////////////////////////////////////////////////////////
// DO NOT CHANGE BELOW HERE INCLUDING THIS FUNCTION OR THE FUNCTIONS BELOW
////////////////////////////////////////////////////////////////////////////////
// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
    struct node *head = NULL;
    int i = len - 1;
    while (i >= 0) {
        struct node *n = malloc(sizeof (struct node));
        assert(n != NULL);
        n->next = head;
        n->data = atoi(strings[i]);
        head = n;
        i -= 1;
    }   
    return head;
}

// print linked list
void print_list(struct node *head) {
    printf("[");    
    struct node *n = head;
    while (n != NULL) {
        // If you're getting an error here,
        // you have returned an invalid list
        printf("%d", n->data);
        if (n->next != NULL) {
            printf(", ");
        }
        n = n->next;
    }
    printf("]\n");
}

// free linked list
void free_list(struct node *head) {
    struct node *curr = head;
    while (curr != NULL) {
        struct node *temp = curr;
        curr = curr->next;
        free(temp);
    }
}

// Written by Sasha Vassar

#include <stdio.h>
#include <stdlib.h>

#define NUM_COLS 5

// Return the index of the first row where every element is strictly greater than the element to its left.
// If no such row exists, return -1.
int first_sorted_row(int num_rows, int array[][NUM_COLS]) {
    for (int i = 0; i < num_rows; i++) {
        int is_sorted = 1;
        for (int j = 1; j < NUM_COLS; j++) {
            if (array[i][j] <= array[i][j - 1]) {
                is_sorted = 0;
            }
        }
        if (is_sorted == 1) {
            return i;
        }
    }
    return -1;
}

// This is a simple main function which could be used
// to test your first_sorted_row function.
// It will not be marked.
// Only your first_sorted_row function will be marked.
int main(void) {
    int test_array[4][NUM_COLS] = {
        {16, 12, 8, 4, 1},  // Row 0: Decreasing
        {2, 4, 10, 15, 20}, // Row 1: Strictly Increasing!
        {3, 6, 12, 11, 20}, // Row 2: Not sorted (11 < 12)
        {5, 5, 5, 5, 5}     // Row 3: Not strictly increasing
    };

    int result = first_sorted_row(4, test_array);
    printf("%d\n", result);

    return 0;
}

// Written by Grace Murray

// This program should scan in 3 buses with their bus number, maximum passenger 
// capacity and current number of passengers on the bus and store it in struct 
// array. The program should then scan in the number of passengers waiting for 
// a bus and determine which buses have enough space for all the passengers.
//
// Unfortunately, this code contains a number of errors. 
// It's your job to fix them, good luck!

#include <stdio.h>
#include <stdlib.h>

#define SIZE 3

struct bus {
    int bus_number;
    int max_capacity;
    int current_passengers;
};

// BUG: Missing index on all array accesses
int main(void) {

    printf("Enter 3 buses and their information: \n");

    struct bus buses[SIZE];
    for (int i = 0; i < SIZE; i++) {
        printf("Bus %d: \n", i + 1);

        printf("Bus number: ");
        scanf("%d", &buses[i].bus_number);
        printf("Maximum capacity: ");
        scanf("%d", &buses[i].max_capacity);
        printf("Current number of passengers: ");
        scanf("%d", &buses[i].current_passengers);
    }

    printf("How many passengers are waiting for the bus: ");
    int passengers_waiting;
    scanf("%d", &passengers_waiting);

    printf("Checking bus capacity...\n");

    int has_space = 0;
    int j = 0;
    // BUG: Using > instead of <
    while (j < SIZE) {
        // BUG: Incorrect calculation, using + not -
        int space_on_bus = buses[j].max_capacity - buses[j].current_passengers;
        // BUG: Missing = in the >=
        if (space_on_bus >= passengers_waiting) {
            has_space++;
        }
        // BUG: Missing increment
        j++;
    }

    if (has_space == SIZE) {
        printf("Excellent! All 3 buses have enough space!\n");
    } else if (has_space == 0) {
        printf("Oh no! None of the 3 buses have enough space!\n");
    } else {
        // BUG: Initialise k to 1 instead of 0
        int k = 0;
        printf("Buses that have enough space:\n");
        while (k < SIZE) {
            // BUG: Incorrect calculation, using + not -
            int space_on_bus = buses[k].max_capacity - buses[k].current_passengers;
            // BUG: Missing = in the >=
            if (space_on_bus >= passengers_waiting) {
                // BUG: Printing current_passengers instead of .bus_number
                printf("%d\n", buses[k].bus_number);
            }
            k++;
        }
    }

    return 0;
}

// Written by Sofia De Bellis

// The following code is meant to convert a given temperature in Kelvin into
// degrees Celsius according to the provided formula.
// However, it has some issues that you need to fix. Good luck!
// Note: You cannot change the function prototype of `kelvin_to_celsius`

#include <stdio.h>

void kelvin_to_celsius(double kelvin, double *celsius);

int main(void) {
    double kelvin;
    double celsius; // BUG: 4: Incorrect type

    printf("Enter temperature in Kelvin: ");
    scanf("%lf", &kelvin); // BUG 2: %d instead of %lf and missing &

    kelvin_to_celsius(kelvin, &celsius); // BUG 0: missing entire function call

    printf("%.2lf Kelvin is equal to %.2lf Celsius.\n", kelvin, celsius); // BUG 3: no .2 precision and incorrect format specifier

    return 0;
}

void kelvin_to_celsius(double kelvin, double *celsius) {
    *celsius = kelvin - 273.15; // BUG 1: missing * dereference
}

// Written by Sofia De Bellis

// The following code is meant to prompt the user to enter a string and a 
// position, then remove the character at that position from the string. The
// updated string, with the character deleted, is then printed to the screen.
//
// Unfortunately, this code contains a number of errors. 
// It's your job to fix them, good luck!

#include <stdio.h>
#include <string.h>

#define SIZE 50

void delete_char_from_string(char input[SIZE], int position);
void strip_newline(char *string);

int main(void) {
    printf("Enter a string: "); // BUG: missing semicolon
    char input[SIZE];
    fgets(input, SIZE, stdin); // BUG: missing 'stdin' from arguments
    strip_newline(input);

    printf("Enter a position to remove: ");
    int position; // BUG: missing declaration
    scanf("%d", &position);

    delete_char_from_string(input, position); // BUG: called with 'input[]', extra '0' arg

    printf("Result: %s\n", input);

    return 0;
}

void delete_char_from_string(char string[SIZE], int position) {
    int i = position - 1; // LOGIC BUG: missing "- 1" from initialisation
    while (i < strlen(string)) { 
        string[i] = string[i + 1];
        i++; // LOGIC BUG: missing increment
    }
}


////////////////////////////////////////////////////////////////////////////////
//                  DO NOT CHANGE ANY OF THE CODE BELOW HERE                  //
//      The code below is correct as given. You do NOT need to modify it      //
////////////////////////////////////////////////////////////////////////////////

// Removes a newline character from end of the given string, if it exists.
void strip_newline(char *string) {
    int length = strlen(string);
    if (length != 0 && string[length - 1] == '\n') {
        string[length - 1] = '\0';
    }
}

// Written by Grace Murrary

#include <stdio.h>
#include <stdlib.h>

// Do not change this struct
struct node {
    struct node *next;
    int          data;
};

// MODIFY THIS FUNCTION
// list_delete_min takes in the head of a linked list and deletes (and frees) 
// all instances of the minimum value in the list
struct node *list_delete_min(struct node *head) {
    struct node *curr = head;
    struct node *prev = NULL;

    if (curr == NULL || curr->next == NULL) {
        free(curr);
        return NULL;
    }

    // Find the minimum
    int minimum = curr->data; // BUG: Initialise minimum to 0
    while (curr != NULL) {
        // BUG: Using == minimum instead of <
        if (curr->data < minimum) {
            minimum = curr->data;
        }

        curr = curr->next;
    }

    // Delete minimum
    curr = head;
    while (curr != NULL) {
        // BUG: Using < minimum instead of ==
        if (curr->data == minimum) {

            struct node *to_delete = curr;
            // BUG: Missing below if statement 
            if (prev == NULL) {
                head = curr->next;
            } else {
                prev->next = curr->next;
            }

            // BUG: No curr = curr->next
            curr = curr->next;
            free(to_delete);

        } else {
            // BUG: Missing putting this into it's own if statement so misses a node
            prev = curr;
            curr = curr->next;
        }

    }

    return head;
}

struct node *args_to_list(int argc, char *argv[]);
void print_list(struct node *head);
void free_list(struct node *head);

// DO NOT CHANGE THIS FUNCTION
int main(int argc, char *argv[]) {
    struct node *head = args_to_list(argc, argv);

    printf("BEFORE: ");
    print_list(head);

    head = list_delete_min(head);

    printf("AFTER : ");
    print_list(head);
    free_list(head);

    return 0;
}

// DO NOT CHANGE THIS FUNCTION
// Converts command-line args to a linked list of characters
struct node *args_to_list(int argc, char *argv[]) {
    struct node *head = NULL;
    for (int i = argc - 1; i >= 1; i--) {
        struct node *new = malloc(sizeof(struct node));
        new->data = atoi(argv[i]);  
        new->next = head;
        head = new;
    }
    return head;
}

// DO NOT CHANGE THIS FUNCTION
// Prints a linked list of integers
void print_list(struct node *head) {
    struct node *curr = head;
    if (curr == NULL) {
        printf("NULL\n");
        return;
    }
    while (curr != NULL) {
        printf("%d", curr->data);
        if (curr->next != NULL) {
            printf(" -> ");
        }
        curr = curr->next;
    }
    printf(" -> NULL\n");
}

void free_list(struct node *head) {
    struct node *curr = head;
    while (curr != NULL) {
        struct node *to_free = curr;
        curr = curr->next;
        free(to_free);
    }
}

// Written by Sofia De Bellis

#include <stdio.h>
#include <stdlib.h>

int is_space(char c);
int words_match(char *word1, int len1, char *word2, int len2);
char *remove_target_word(char *target, char *text);

int main(void) {
    char target[4096];
    char input[4096];

    fgets(target, 4096, stdin);
    fgets(input, 4096, stdin);

    char *output = remove_target_word(target, input);
    printf("%s\n", output);
    free(output);

    return 0;
}

// Check if the character is a whitespace
int is_space(char c) {
    return (c == ' ' || c == '\t' || c == '\n' || c == '\r' || c == '\0');
}

// Manual comparison: do these two words match?
int words_match(char *word1, int len1, char *word2, int len2) {
    if (len1 != len2) {
        return 0;
    }
    for (int i = 0; i < len1; i++) {
        if (word1[i] != word2[i]) {
            return 0;
        }
    }
    return 1;
}

char *remove_target_word(char *target, char *text) {
    // Find the length of the target word (up to first whitespace)
    int target_len = 0;
    while (!is_space(target[target_len])) {
        target_len++;
    }

    // Allocate for the result string (max possible size)
    char *result = malloc(4097);
    int res_index = 0;
    int i = 0;

    while (text[i] != '\0') {
        // 1. Skip whitespace to find the start of a word
        while (text[i] != '\0' && is_space(text[i])) {
            i++;
        }

        if (text[i] == '\0') {
            break;
        }

        // 2. Mark the start and find the length of the current word
        char *word_start = &text[i];
        int word_len = 0;
        while (text[i] != '\0' && !is_space(text[i])) {
            word_len++;
            i++;
        }

        // 3. If this word does NOT match the target, keep it
        if (!words_match(word_start, word_len, target, target_len)) {
            if (res_index > 0) {
                result[res_index++] = ' ';
            }
            for (int j = 0; j < word_len; j++) {
                result[res_index++] = word_start[j];
            }
        }
    }

    // Final null terminator for the result
    result[res_index] = '\0';
    return result;
}

// Written by Sofia De Bellis, z5418801

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
    int num_courses = atoi(argv[1]);
    int num_prereqs = (argc - 2) / 2;

    int *in_degree = calloc(num_courses, sizeof(int));
    int *adj_count = calloc(num_courses, sizeof(int));
    int **adj = malloc(num_courses * sizeof(int *));

    int *prereq_a = malloc(num_prereqs * sizeof(int));
    int *prereq_b = malloc(num_prereqs * sizeof(int));

    for (int i = 0; i < num_prereqs; i++) {
        prereq_a[i] = atoi(argv[2 + i * 2]);
        prereq_b[i] = atoi(argv[2 + i * 2 + 1]);
        in_degree[prereq_a[i]]++;
        adj_count[prereq_b[i]]++;
    }

    for (int i = 0; i < num_courses; i++) {
        adj[i] = malloc(adj_count[i] * sizeof(int));
        adj_count[i] = 0;
    }

    for (int i = 0; i < num_prereqs; i++) {
        int from = prereq_b[i];
        int to = prereq_a[i];
        adj[from][adj_count[from]++] = to;
    }

    int *queue = malloc(num_courses * sizeof(int));
    int *result = malloc(num_courses * sizeof(int));
    int front = 0;
    int back = 0;
    int result_size = 0;

    for (int i = 0; i < num_courses; i++) {
        if (in_degree[i] == 0) {
            queue[back++] = i;
        }
    }

    while (front < back) {
        int min_idx = front;
        for (int i = front + 1; i < back; i++) {
            if (queue[i] < queue[min_idx]) {
                min_idx = i;
            }
        }
        int temp = queue[front];
        queue[front] = queue[min_idx];
        queue[min_idx] = temp;

        int course = queue[front++];
        result[result_size++] = course;

        for (int i = 0; i < adj_count[course]; i++) {
            int next = adj[course][i];
            in_degree[next]--;
            if (in_degree[next] == 0) {
                queue[back++] = next;
            }
        }
    }

    if (result_size == num_courses) {
        printf("Order: [");
        for (int i = 0; i < result_size; i++) {
            if (i == result_size - 1) {
                printf("%d]\n", result[i]);
            } else {
                printf("%d, ", result[i]);
            }
        }
    } else {
        printf("Order: []\n");
    }

    free(in_degree);
    for (int i = 0; i < num_courses; i++) {
        free(adj[i]);
    }
    free(adj);
    free(adj_count);
    free(prereq_a);
    free(prereq_b);
    free(queue);
    free(result);

    return 0;
}

// Written by Sofia De Bellis, z5418801

#include <stdio.h>
#include <stdlib.h>

struct box {
    int w;
    int h;
};

void merge(struct box *boxes, struct box *temp, int left, int mid, int right);
void merge_sort(struct box *boxes, struct box *temp, int n);
int lower_bound(int *arr, int size, int target);
int max_nested_boxes(struct box *boxes, int n);

int main(int argc, char *argv[]) {
    int n = (argc - 1) / 2;

    struct box *boxes = malloc(n * sizeof(struct box));
    for (int i = 0; i < n; i++) {
        boxes[i].w = atoi(argv[i * 2 + 1]);
        boxes[i].h = atoi(argv[i * 2 + 2]);
    }

    int result = max_nested_boxes(boxes, n);
    printf("Max boxes: %d\n", result);

    free(boxes);

    return 0;
}


void merge(struct box *boxes, struct box *temp, int left, int mid, int right) {
    int i = left;
    int j = mid + 1;
    int k = left;
    while (i <= mid && j <= right) {
        if (boxes[i].w < boxes[j].w ||
            (boxes[i].w == boxes[j].w && boxes[i].h > boxes[j].h)) {
            temp[k++] = boxes[i++];
        } else {
            temp[k++] = boxes[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = boxes[i++];
    }
    while (j <= right) {
        temp[k++] = boxes[j++];
    }
    for (int x = left; x <= right; x++) {
        boxes[x] = temp[x];
    }
}

void merge_sort(struct box *boxes, struct box *temp, int n) {
    for (int width = 1; width < n; width *= 2) {
        for (int left = 0; left < n; left += 2 * width) {
            int mid = left + width - 1;
            int right = left + 2 * width - 1;
            if (mid >= n) {
                break;
            }
            if (right >= n) {
                right = n - 1;
            }
            merge(boxes, temp, left, mid, right);
        }
    }
}

int lower_bound(int *arr, int size, int target) {
    int low = 0;
    int high = size;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

int max_nested_boxes(struct box *boxes, int n) {
    if (n == 0) {
        return 0;
    }

    struct box *temp = malloc(n * sizeof(struct box));
    merge_sort(boxes, temp, n);
    free(temp);

    int *tails = malloc(n * sizeof(int));
    int length = 0;

    for (int i = 0; i < n; i++) {
        int pos = lower_bound(tails, length, boxes[i].h);
        tails[pos] = boxes[i].h;
        if (pos == length) {
            length++;
        }
    }

    free(tails);
    return length;
}