Programming Fundamentals

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

#define FALSE 0
#define TRUE 1

#define MAX_LIST_LEN 100

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

struct node *delete_range(struct node *head, int start, int end);
struct node *array_to_list(int len, int array[]);
void print_list(struct node *head);
void free_list(struct node *head);

// DO NOT CHANGE THIS MAIN FUNCTION

int main(void) {
    // get list size
    int list_size;
    printf("Total numbers: ");
    scanf(" %d", &list_size);

    // read in numbers
    int list[MAX_LIST_LEN] = {0};
    int index_count = 0;
    while (index_count < list_size && scanf(" %d", &list[index_count])) {
        index_count++;
    }

    if (index_count < list_size) {
        printf("You must enter numbers equal to the total provided.\n");
        return 1;
    }

    // create linked list from input numbers
    struct node *head = NULL;
    if (index_count > 0) {
        // list has elements
        head = array_to_list(list_size, list);
    }

    int range_start;
    int range_end;
    printf("Enter delete range: ");
    if (scanf("%d %d", &range_start, &range_end) != 2) {
        printf("You must enter both a start and an end for the range.\n");
        return 2;
    }
    
    printf("List before: ");
    print_list(head);
    struct node *new_head = delete_range(head, range_start, range_end);
    printf("List after: ");
    print_list(new_head);
    free_list(new_head);

    return 0;
}


//
// Given the head of a linked list, deletes all nodes in range `start` to `end`.
// Nodes can be identified by an "index", of which the first node has index 0.
//
// Returns the head of the list afterwards.
//
struct node *delete_range(struct node *head, int start, int end) {
    // `start` should always be less than `end` in a range.
    if (start > end) {
        return head;
    }

    // Keep track of the nodes before and after deletion range.
    struct node *before_range = NULL;
    struct node *after_range = NULL;

    // Flag for whether we are currently in the deletion range
    int in_deletion_range = FALSE;

    int node_count = 0;

    struct node *previous = NULL;
    struct node *current = head;

    while (current != NULL) {
        if (node_count == start) {
            before_range = previous;
            in_deletion_range = TRUE;
        }
        if (node_count == end + 1) {
            after_range = current;
            in_deletion_range = FALSE;
        }

        previous = current;
        current = current->next;
        if (in_deletion_range == TRUE) {
            // Update the head if it were to be deleted, for ease of use later.
            if (previous == head) {
                head = NULL;
            }
            free(previous);
        }

        node_count++;
    }

    // In this case, we either never entered the range or the entire list was
    // in the range.
    if (before_range == NULL && after_range == NULL) {
        return head;
    }
    // This indicates that the head was in range and thus removed. As a result,
    // `after_range` is the new head.
    if (before_range == NULL) {
        return after_range;
    // Otherwise, we link up the two nodes at the boundaries to get our new
    // list.
    } else {
        before_range->next = after_range;
        return head;
    }
}


// DO NOT CHANGE THIS FUNCTION
// create linked list from array of ints
struct node *array_to_list(int len, int array[]) {
    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 = array[i];
        head = n;

        i--;
    }

    return head;
}

// DO NOT CHANGE THIS FUNCTION
// print linked list
void print_list(struct node *head) {
    printf("[");

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

// DO NOT CHANGE THIS FUNCTION
// free linked list
void free_list(struct node *head) {
    if (head != NULL) {
        free_list(head->next);
        free(head);
    }
}

// Program that solves a sudoku puzzle using recursive backtracking
// Date: 2024 (z5363683@unsw.edu.au)
/*
    This solution uses recursion, which occurs when a function calls itself in
    order to solve smaller sub problems of an overall problem, until it reaches
    a base case that does not require recursion to calculate.
*/

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

#define N 9
#define VALID 1
#define INVALID 0
#define SOLVED 1
#define UNSOLVED 0

void print_grid(int grid[N][N]);

int is_valid(int grid[N][N], int row, int col, int num);

int solve_sudoku(int grid[N][N]);

int main(void) {
    // DO NOT CHANGE BELOW HERE

    int grid[N][N];

    // Scan in values for the grid.
    printf("Enter values: ");
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            assert(scanf("%d", &grid[i][j]) == 1);
        }
    }

    // DO NOT CHANGE ABOVE HERE

    /**
     * You may insert code below as you require
    */

    if (solve_sudoku(grid)) {
        printf("Solution found!\n");
        print_grid(grid);
    }
    else {
        printf("No solution found!\n");
    }

    return 0;
}

/**
 * Function that prints the grid.
 *
 * DO NOT CHANGE THIS FUNCTION
*/
void print_grid(int grid[N][N]) {
    // DO NOT CHANGE THIS FUNCTION
    for (int row = 0; row < N; row++) {
        for (int col = 0; col < N; col++) {
            printf("%d ", grid[row][col]);
        }
        printf("\n");
    }
    // DO NOT CHANGE THIS FUNCTION
}

/**
 * Returns 0 when invalid
 * Returns 1 when valid
 *
 * There are three conditions required for a number to be valid.
 *      - The number must not be present in the row
 *      - The number must not be present in the column
 *      - The number must not be present in the 3x3 sub-grid
 * */
int is_valid(int grid[N][N], int row, int col, int num) {
    // Check if the number is already in the row
    for (int j = 0; j < N; j++) {
        if (grid[row][j] == num) {
            return INVALID;
        }
    }

    // Check if the number is already in the column
    for (int i = 0; i < N; i++) {
        if (grid[i][col] == num) {
            return INVALID;
        }
    }

    // Check if the number is already in the 3x3 sub-grid
    int row_start = row - row % 3;
    int col_start = col - col % 3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (grid[i + row_start][j + col_start] == num) {
                return INVALID;
            }
        }
    }

    return VALID;
}

/**
 * Returns 0 when a solution is found
 * Returns 1 when no solution was found
 *
 * This function uses recursion to search for valid numbers.
 * If a valid number isn't found, it backtracks, resetting numbers and searching for
 * a different valid number.
 * If there are no empty cells, then the grid is full and the game has been solved.
 * Otherwise, if the recursion cannot find a valid combination, the function will return
*/
int solve_sudoku(int grid[N][N]) {
    int row, col;

    // Loop over the grid, searching for an empty cell
    int found = 0;
    for (row = 0; row < N; row++) {
        for (col = 0; col < N; col++) {
            if (grid[row][col] == 0) {
                found = 1;
                break;
            }
        }
        if (found) {
            break;
        }
    }

    // If no empty cell is found, we have solved sudoku!!
    if (!found) {
        return SOLVED;
    }

    // Try placing numbers from 1 to 9 in the empty cell
    for (int num = 1; num <= 9; num++) {
        // This loop will only be entered if we have found a cell with no number.
        // This prevents the backtracking from removing a cell from the base grid.

        if (is_valid(grid, row, col, num)) {
            grid[row][col] = num;
            if (solve_sudoku(grid)) {
                return SOLVED;
            }
            grid[row][col] = 0; // If the solution is not found, backtrack
        }
    }

    return UNSOLVED;
}

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

struct node {
    struct node *left;
    struct node *right;
    char         data;
};

void print_list(struct node *head);
struct node *scan_in_list();

// DO NOT CHANGE THIS MAIN FUNCTION

int main(void) {
    printf("Enter list: ");
    struct node *head = scan_in_list();
    print_list(head);
    return 0;
}

// Given the `head` of a list, prints the string it contains as well as the
// numbers of lefts/rights taken.
void print_list(struct node *head) {
    struct node *current = head;

    int left_count = 0;
    int right_count = 0;
    
    printf("List string:   ");
    while (current != NULL) {
        printf("%c", current->data);

        // Traverse either left or right based on where the next node would be.
        // Since left/right counts need to be accounted for, both the left and
        // right pointers need to be checked more explicitly.
        if (current->left == NULL && current->right == NULL) {
            current = NULL;
        } else if (current->left == NULL) {
            current = current->right;
            right_count++;
        } else {
            current = current->left;
            left_count++;
        }
    }

    printf("\n");
    printf("#Lefts Taken:  %d\n", left_count);
    printf("#Rights Taken: %d\n", right_count);
}

// Malloc's a new node given `left`, `right`, `data` values. Returns this node.
struct node *create_node(struct node *left, struct node *right, char data) {
    struct node *new = malloc(sizeof(struct node));
    new->left = left;
    new->right = right;
    new->data = data;

    return new;
}

// DO NOT CHANGE THIS FUNCTION
// Handles input/output to scan in a list
struct node *scan_in_list() {
    char data;
    char direction;

    // Head of list is NULL if no initial data is given.
    if (scanf(" %c", &data) != 1) {
        return NULL;
    }

    struct node *head = create_node(NULL, NULL, data);

    struct node *previous_node = head;
    // Loop through for every (direction, data) pair and linked up list
    while (scanf(" %c %c", &direction, &data) == 2) {
        assert(direction == 'L' || direction == 'R');

        struct node *new = create_node(NULL, NULL, data);
        if (direction == 'L') {
            previous_node->left = new;
            previous_node = previous_node->left;
        } else {
            previous_node->right = new;
            previous_node = previous_node->right;
        }
    }

    return head;
}