Programming Fundamentals
Q1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
struct node {
struct node *next;
char character;
};
int is_vowel(char c) {
return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
}
// count_vowel_word_boundaries should return the number of vowel word boundaries
// in the given linked list.
//
// A vowel word boundary occurs when a node containing a vowel is immediately
// followed by a node containing a consonant.
// - The list will only contain lowercase characters (from a to z).
// - A vowel is one of the following characters: a, e, i, o, u.
// - A consonant is any character that is not a vowel.
int count_vowel_word_boundaries(struct node *head) {
if (head == NULL) {
return -1;
}
int count = 0;
struct node *curr = head;
while (curr->next != NULL) {
if (is_vowel(curr->character) && !is_vowel(curr->next->character)) {
count++;
}
curr = curr->next;
}
return count;
}
////////////////////////////////////////////////////////////////////////
// DO NOT CHANGE THE CODE BELOW //
////////////////////////////////////////////////////////////////////////
int count_vowel_word_boundaries(struct node *head);
struct node *list_from_string(char *string);
// DO NOT CHANGE THIS MAIN FUNCTION
int main(int argc, char *argv[]) {
// create linked list from command line arguments
struct node *head = NULL;
if (argc > 1) {
head = list_from_string(argv[1]);
}
// If you're getting an error here,
// you have returned an uninitialized value
printf("%d\n", count_vowel_word_boundaries(head));
return 0;
}
// DO NOT CHANGE THIS FUNCTION
// create a linked list of chars from a string
struct node *list_from_string(char *string) {
struct node *head = NULL;
struct node *tail = NULL;
for (int i = 0; string[i] != '\0'; i++) {
struct node *new = malloc(sizeof(struct node));
assert(new != NULL);
new->next = NULL;
new->character = string[i];
if (head == NULL) {
head = new;
tail = new;
} else {
tail->next = new;
tail = new;
}
}
return head;
}
Q2
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
int sum_border(int size, int array[MAX_SIZE][MAX_SIZE]);
// This is a simple main function which could be used
// to test your magic_square function.
// It will not be marked.
// Only your magic_square function will be marked.
int main(void) {
// In the below test array, the sum of the border is 16
// If you modify this array, that sum will change
int test_array[MAX_SIZE][MAX_SIZE] = {
{1, 1, 1, 1, 1},
{1, 1, 1, 1, 1},
{1, 1, 1, 1, 1},
{1, 1, 1, 1, 1},
{1, 1, 1, 1, 1}
};
int size = 5;
printf("The sum of all the border elements is: %d\n",
sum_border(size, test_array));
return 0;
}
// Returns the sum of all elements on the border of a (size x size) 2D array
int sum_border(int size, int array[MAX_SIZE][MAX_SIZE]) {
int sum = 0;
int i = 0;
while (i < size) {
int j = 0;
while (j < size) {
if (i == 0 || j == 0 || i == size - 1 || j == size - 1) {
sum += array[i][j];
}
j++;
}
i++;
}
return sum;
}
Q3
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
struct node {
struct node *next;
int data;
};
// delete_first_local_max deletes the first local maximum of the given list.
// A local maximum is any node with a value greater than both its previous node
// and its next node.
struct node *delete_first_local_max(struct node *head) {
if (head == NULL || head->next == NULL) {
return head;
}
int is_node_deleted = 0;
struct node *prev = head;
struct node *curr = head->next;
while (!is_node_deleted && curr->next != NULL) {
if (curr->data > prev->data && curr->data > curr->next->data) {
prev->next = curr->next;
free(curr);
curr = prev->next;
is_node_deleted = 1;
} else {
prev = prev->next;
curr = curr->next;
}
}
return head;
}
////////////////////////////////////////////////////////////////////////
// DO NOT CHANGE THE CODE BELOW //
////////////////////////////////////////////////////////////////////////
struct node *delete_first_local_max(struct node *head);
struct node *strings_to_list(int len, char *strings[]);
void print_list(struct node *head);
void free_list(struct node *head);
// 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]);
struct node *new_head = delete_first_local_max(head);
// If you're getting an error here,
// you have returned an invalid linked list
print_list(new_head);
free_list(new_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;
}
// 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) {
struct node *curr = head;
while (curr != NULL) {
struct node *temp = curr;
curr = curr->next;
free(temp);
}
}
Q4
#include <stdio.h>
#define ROWS 5
#define COLS 5
int find_min_in_row(int grid[ROWS][COLS], int row);
int find_max_in_col(int grid[ROWS][COLS], int col);
int find_saddle_point(int grid[ROWS][COLS]);
int main(int argc, char *argv[]) {
int array[ROWS][COLS];
int argv_i = 1;
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
array[r][c] = atoi(argv[argv_i]);
argv_i++;
}
}
printf("%d\n", find_saddle_point(array));
return 0;
}
int find_min_in_row(int grid[ROWS][COLS], int row) {
int curr_min = grid[row][0];
for (int j = 1; j < COLS; j++) {
if (curr_min > grid[row][j]) {
curr_min = grid[row][j];
}
}
return curr_min;
}
int find_max_in_col(int grid[ROWS][COLS], int col) {
int curr_max = grid[0][col];
for (int i = 0; i < ROWS; i++) {
if (curr_max < grid[i][col]) {
curr_max = grid[i][col];
}
}
return curr_max;
}
int find_saddle_point(int grid[ROWS][COLS]) {
for (int i = 0; i < ROWS; i++) {
int row_min = find_min_in_row(grid, i);
for (int j = 0; j < COLS; j++) {
if (row_min == grid[i][j] && find_max_in_col(grid, j) == grid[i][j]) {
return grid[i][j];
}
}
}
return -1;
}
Q5
// This program scans in a bank account number and the corresponding account
// balance.
// It prints out a message to indicate whether the account is in good standing,
// empty or overdrawn.
// Additionally, it also warns or congratulates the user if the their balance
// is below $100 or above $1000 respectively.
//
// Unfortunately, this code contains a number of errors. Please help fix it!
#include <stdio.h>
struct Account {
int account_number;
double balance;
};
int main(void) {
struct Account account; //
printf("Enter account number: ");
scanf("%d", &account.account_number); // BUG #0 - -> instead of .
printf("Enter account balance: ");
scanf("%lf", &account.balance); // BUG #1 - %d instead %lf
if (account.balance > 0) {
printf("Account %d is in good standing.\n", account.account_number);
} else if (account.balance == 0) { // BUG #2 - = instead of ==
printf("Account %d is empty.\n", account.account_number);
} else { // BUG 3 - else if instead of else
printf("Account %d is overdrawn.\n", account.account_number);
}
if (account.balance < 100) {
printf("Warning: Your account balance is below $100.\n");
}
if (account.balance > 1000) { // BUG 4 - else instead of > 1000
printf("Congratulations! Your account balance is above $1000.\n");
}
return 0;
}
Q6
// The following code is meant to print the sum of the first n natural numbers.
// However, it has some issues that you need to fix. Good luck!
#include <stdio.h>
int main(void) {
int number;
printf("Enter a number: ");
int return_value = scanf("%d", &number);
if (return_value != 1) {
printf("You have entered an invalid number!\n");
return 0; // BUG #2: forget this
}
int sum = 0; // BUG #0 - don't initialise this and don't declare int
int i = 1; // BUG #1 - don't decalre the int for this
while (i <= number) {
sum = sum + i; // BUG 3: sum + 1
i++; // BUG 4 - forget this
}
printf("The sum of the first %d natural numbers is: %d\n", number, sum);
return 0;
}
Q7
// The following code is meant to calculate the perimeter and area of a
// rectangle.
// However, it has some issues that you need to fix. Good luck!
// Note: You cannot change the function prototype of `calculate_rectangle`
#include <stdio.h>
void calculate_rectangle(int length, int width, int *perimeter, int *area);
int main(void) {
int length, width;
int perimeter, area;
printf("Enter length of the rectangle (in cm): ");
scanf("%d", &length);
printf("Enter width of the rectangle (in cm): ");
scanf("%d", &width);
calculate_rectangle(length, width, &perimeter, &area); // BUG 0 - forget the entire function call
printf("Perimeter of the rectangle: %dcm\n", perimeter);
printf("Area of the rectangle: %dcm\n", area); // BUG 3: change this to %lf
return 0;
}
void calculate_rectangle(int length, int width, int *perimeter, int *area) {
*perimeter = 2 * (length + width); // BUG 1 - forget the *s
*area = length * width; // BUG 4 - use x instead of *
}
Q8
// The following code is meant to ask the user to continuously enter **char**
// inputs, to be inserted at the head of a linked list until CTRL+D is pressed.
//
// Inputs that are not digits (between 0-9 inclusive) result in "Input
// '[character]' is not a digit!" being printed, and not adding to the linked
// list. This means that only digit inputs can be added to the linked list.
//
// The list is printed after CTRL+D is pressed, which should result in printing
// all digits scanned in, in reverse order.
//
// However, there are a number of issues found in the code that you need to fix
// Good luck!
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
struct node *prepend_list(struct node *list, int data);
void print_list(struct node *list);
int main(void) {
struct node *list = NULL;
char input;
printf("Enter digits:\n");
int success = scanf(" %c", &input);
while (success == 1) { // BUG: success == 0 instead of == 1
if (input <= '0' || input > '9') { // BUG: && instead of ||
printf("Input '%c' is not a digit!\n", input);
} else {
list = prepend_list(list, input);
}
success = scanf(" %c", &input);
}
print_list(list);
return 0;
}
// Prints all elements in the given `list`
void print_list(struct node *list) {
struct node *curr = list;
while (curr != NULL) {
printf("%d ", curr->data);
curr = curr->next;
}
printf("\n");
}
// Creates and adds a new node with given `data` to the head of a given `list`.
// Returns a pointer to this new head.
struct node *prepend_list(struct node *list, int data) {
struct node *new = malloc(sizeof(struct node));
// BUG 3: Missing - '0'
new->data = data - '0';
new->next = NULL;
// BUG 4: Missing head insertion
if (list == NULL) {
list = new;
} else {
struct node *current = list;
while (current->next != NULL) {
current = current->next;
}
current->next = new;
}
return list;
}
Q9
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LEN 100
char* transform_string(const char *original, int nums[26]);
int main(void) {
char original[MAX_LEN];
int nums[26];
// Prompt and read the original string
printf("Original: ");
fgets(original, MAX_LEN, stdin);
// Remove newline character from fgets
size_t len = strlen(original);
if (len > 0 && original[len - 1] == '\n') {
original[len - 1] = '\0';
}
// Prompt and read the nums array
printf("Nums: ");
for (int i = 0; i < 26; i++) {
scanf("%d", &nums[i]);
}
// Call the transform_string function which returns a malloc'ed string
char *result = transform_string(original, nums);
// Print the result
printf("Result string: %s\n", result);
free(result);
return 0;
}
char* transform_string(const char *original, int nums[26]) {
int total_len = 0;
// Calculate total result length
for (int i = 0; original[i] != '\0'; i++) {
total_len += nums[original[i] - 'a'];
}
// Allocate memory for result string (+1 for null terminator)
char *result = malloc(total_len + 1);
if (!result) return NULL;
int pos = 0;
for (int i = 0; original[i] != '\0'; i++) {
char c = original[i];
int n = nums[c - 'a'];
for (int j = 1; j <= n; j++) {
char new_c = 'a' + (c - 'a' + j) % 26;
result[pos++] = new_c;
}
}
result[pos] = '\0';
return result;
}
Q10
#include <stdio.h>
#include <stdlib.h>
enum passage_status {
OPEN,
CLOSED
};
struct tank {
int volume;
enum passage_status left_passage;
enum passage_status right_passage;
struct tank *next;
};
void print_tanks(struct tank *tanks);
struct tank *init_tanks(int n_tanks, char *tank_volumes[]);
void toggle_passage(struct tank *tanks, int position);
// DO NOT CHANGE THIS MAIN FUNCTION
int main(int argc, char *argv[]) {
struct tank *tanks = init_tanks(argc - 1, &argv[1]);
print_tanks(tanks);
int position;
printf("Enter passage: ");
while (scanf("%d", &position) == 1) {
toggle_passage(tanks, position);
print_tanks(tanks);
printf("Enter passage: ");
}
return 0;
}
enum passage_status complement_status(enum passage_status status) {
if (status == OPEN) {
return CLOSED;
}
return OPEN;
}
void recalculate_volumes(struct tank *tanks, int delta_position) {
struct tank *range_start = NULL;
struct tank *range_end = NULL;
struct tank *prev = NULL;
struct tank *curr = tanks;
while (delta_position > 0) {
// Whenever a closed passage is found between [0, delta_position], we
// know that every tank before it will not need a volume recalculation,
// so we update the start range to reflect this.
if (curr->left_passage == CLOSED) {
range_start = curr;
}
--delta_position;
prev = curr;
curr = curr->next;
}
// range_start identifies the start of the range we will need to modify.
// We also need the end. This code continues the loop until we find a closed
// passage, effectively finding range_end of what we will need to modify.
while (curr != NULL && curr->right_passage == OPEN) {
prev = curr;
curr = curr->next;
}
range_end = curr;
// In the case that either side of the range falls "out of" the list of
// tanks, then we are bringing infinite water into the tank range.
int inf_volume = 0;
if (range_start == NULL) {
inf_volume = 1;
range_start = tanks;
}
if (range_end == NULL) {
inf_volume = 1;
range_end = prev;
}
// Calculate total volume in range before adjustment
int total_volume = 0;
int range_count = 0;
struct tank *range_tank = range_start;
while (range_tank != range_end->next) {
++range_count;
total_volume += range_tank->volume;
range_tank = range_tank->next;
}
// Each tank in the range now gets the average of the total volume in the
// range because... water
int avg_volume = total_volume / range_count;
if (inf_volume) {
avg_volume = 99;
}
range_tank = range_start;
while (range_tank != range_end->next) {
range_tank->volume = avg_volume;
range_tank = range_tank->next;
}
}
void toggle_passage(struct tank *tanks, int position) {
struct tank *prev = NULL;
struct tank *curr = tanks;
int counter = 0;
while (counter < position && curr != NULL) {
++counter;
prev = curr;
curr = curr->next;
}
if (counter != position) {
printf("ERROR: Invalid passage position\n");
return;
}
// Flipping passage in first node
if (prev == NULL) {
curr->left_passage = complement_status(curr->left_passage);
// Flipping passage in last node
} else if (curr == NULL) {
prev->right_passage = complement_status(prev->right_passage);
// Any other passage
} else {
curr->left_passage = complement_status(curr->left_passage);
prev->right_passage = complement_status(prev->right_passage);
}
recalculate_volumes(tanks, position);
}
// DO NOT CHANGE THIS FUNCTION
// prints a linked list of tanks in a formatted fashion.
void print_tanks(struct tank *tanks) {
printf("Tanks:\n");
// Top level of tanks (roof)
struct tank *curr = tanks;
while (curr != NULL) {
printf("/----\\");
curr = curr->next;
}
printf("\n");
// Middle level of tanks (volumes & passages)
curr = tanks;
while (curr != NULL) {
printf(
"%c %02d %c",
curr->left_passage == CLOSED ? '|' : ' ',
curr->volume,
curr->right_passage == CLOSED ? '|' : ' '
);
curr = curr->next;
}
printf("\n");
// Bottom level of tanks (floor)
curr = tanks;
while (curr != NULL) {
printf("\\----/");
curr = curr->next;
}
curr = tanks;
printf("\n");
}
// DO NOT CHANGE THIS FUNCTION
// Given an array of strings, creates a linked list of tanks containing
// volumes specified in these strings.
struct tank *init_tanks(int n_tanks, char *tank_volumes[]) {
struct tank *head = NULL;
struct tank *tail = NULL;
for (int i = 0; i < n_tanks; ++i) {
struct tank *new_tank = malloc(sizeof(struct tank));
new_tank->volume = atoi(tank_volumes[i]);
new_tank->left_passage = CLOSED;
new_tank->right_passage = CLOSED;
new_tank->next = NULL;
if (head == NULL) {
head = new_tank;
tail = new_tank;
} else {
tail->next = new_tank;
tail = tail->next;
}
}
return head;
}
Q11
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_SIZE 100
#define MAX_STATES 10
struct node {
int state;
struct node *next;
};
struct state {
int collapsed_state;
struct node *possible_states;
};
struct node *new_state(int state);
struct node *add_state(int state, struct node *head);
void init_states(
int n_states,
int board_size,
struct state state_board[MAX_SIZE][MAX_SIZE]
);
void print_state_range(int start, int end, struct state *state);
void print_states(int board_size, struct state state_board[MAX_SIZE][MAX_SIZE]);
void perform_collapse(
int total_states,
int board_size,
struct state state_board[MAX_SIZE][MAX_SIZE]
);
int main(int argc, char **argv) {
struct state state_board[MAX_SIZE][MAX_SIZE];
int board_size;
if (argc != 2) {
printf("Command line argument for `total_states` expected.\n");
return 1;
}
printf("Board size: ");
scanf("%d", &board_size);
int total_states = argv[1][0] - '0';
init_states(total_states, board_size, state_board);
perform_collapse(total_states, board_size, state_board);
return 0;
}
void generate_lookup(int total_states, bool lookup[MAX_STATES][MAX_STATES]) {
for (int state = 1; state <= total_states; ++state) {
printf("Enter valid neighbours of state '%d', followed by 'x': ", state);
char next;
while (scanf(" %c", &next) == 1 && next != 'x') {
lookup[state][next - '0'] = true;
}
}
}
void collapse_single_state(int collapse_to, struct state *state) {
struct node *curr = state->possible_states;
while (curr != NULL) {
struct node *f = curr;
curr = curr->next;
free(f);
}
state->possible_states = NULL;
state->collapsed_state = collapse_to;
}
bool valid_neighbour(int neighbour,
bool valid_neighbours[MAX_STATES][MAX_STATES],
struct state *state
) {
if (valid_neighbours[state->collapsed_state][neighbour] &&
valid_neighbours[neighbour][state->collapsed_state]
) {
return true;
}
for (struct node* curr = state->possible_states;
curr != NULL;
curr = curr->next
) {
if (valid_neighbours[curr->state][neighbour] &&
valid_neighbours[neighbour][curr->state]
) {
return true;
}
}
return false;
}
void propagate_collapse(
int board_size,
bool valid_neighbours[MAX_STATES][MAX_STATES],
struct state state_board[MAX_SIZE][MAX_SIZE]
) {
bool changed = true;
// Continuously apply collapse updates until no more updates can be made.
// this is basically a 1511 search algo.
while (changed) {
changed = false;
for (int row = 0; row < board_size; ++row) {
for (int col = 0; col < board_size; ++col) {
struct state *this_cell = &state_board[row][col];
// Already collapsed states are immutable...
if (this_cell->collapsed_state != 0) {
continue;
}
struct node *prev = NULL;
struct node *curr = this_cell->possible_states;
while (curr != NULL) {
// All neighbours must have the current state in their list
// for this current state to remain valid.
bool valid_state = true;
if (row > 0) {
valid_state = valid_state &&
valid_neighbour(curr->state,
valid_neighbours,
&state_board[row - 1][col]);
}
if (row < board_size - 1) {
valid_state = valid_state &&
valid_neighbour(curr->state,
valid_neighbours,
&state_board[row + 1][col]);
}
if (col > 0) {
valid_state = valid_state &&
valid_neighbour(curr->state,
valid_neighbours,
&state_board[row][col - 1]);
}
if (col < board_size - 1) {
valid_state = valid_state &&
valid_neighbour(curr->state,
valid_neighbours,
&state_board[row][col + 1]);
}
if (!valid_state) {
// Case: removing the head state
if (prev == NULL) {
this_cell->possible_states = curr->next;
free(curr);
curr = this_cell->possible_states;
// Case: removing a body state
} else {
curr = curr->next;
free(prev->next);
prev->next = curr;
}
// Any invalid state indicates that a change has occurred
changed = true;
} else {
prev = curr;
curr = curr->next;
}
}
}
}
}
}
void perform_collapse(
int total_states,
int board_size,
struct state state_board[MAX_SIZE][MAX_SIZE]
) {
// Lookup table. If valid_neighbours[i][j] == true, then state `i` can be
// placed next to state `j` (but not necessarily the other way around).
bool valid_neighbours[MAX_STATES][MAX_STATES] = {false};
generate_lookup(total_states, valid_neighbours);
printf("Initial state board:\n");
print_states(board_size, state_board);
int row, col, desired_state;
printf("Collapse next cell (row/col/state): ");
while (scanf("%d %d %d", &row, &col, &desired_state) == 3) {
collapse_single_state(desired_state, &state_board[row][col]);
propagate_collapse(board_size, valid_neighbours, state_board);
print_states(board_size, state_board);
printf("Collapse next cell (row/col/state): ");
}
}
struct node *new_state(int state) {
struct node *s = malloc(sizeof(struct node));
s->state = state;
s->next = NULL;
return s;
}
struct node *add_state(int state, struct node *head) {
struct node *new = new_state(state);
new->next = head;
return new;
}
void init_states(
int n_states,
int board_size,
struct state state_board[MAX_SIZE][MAX_SIZE]
) {
for (int row = 0; row < board_size; ++row) {
for (int col = 0; col < board_size; ++col) {
state_board[row][col].possible_states = NULL;
for (int state_idx = n_states; state_idx >= 1; --state_idx) {
state_board[row][col].collapsed_state = 0;
state_board[row][col].possible_states = add_state(state_idx, state_board[row][col].possible_states);
}
}
}
}
void print_state_range(int start, int end, struct state *state) {
struct node *curr = state->possible_states;
for (int i = 0; i < start && curr != NULL; ++i) {
curr = curr->next;
}
for (int i = start; i < end; ++i) {
if (state->collapsed_state != 0) {
printf("%d", state->collapsed_state);
} else if (curr == NULL) {
printf(" ");
} else {
printf("%d", curr->state);
curr = curr->next;
}
}
}
void print_states(int board_size, struct state state_board[MAX_SIZE][MAX_SIZE]) {
for (int row = 0; row < board_size * 3; ++row) {
if (row == 0) {
for (int i = 0; i <= board_size * 4; ++i) {
printf("-");
}
printf("\n");
}
for (int col = 0; col < board_size; ++col) {
if (col == 0) {
printf("|");
}
int start = (row % 3) * 3;
print_state_range(start, start + 3, &state_board[row / 3][col]);
printf("|");
}
if (row % 3 == 2) {
printf("\n");
for (int i = 0; i <= board_size * 4; ++i) {
printf("-");
}
}
printf("\n");
}
}