Programming Fundamentals

Download pass_the_parcel.c here

Or, copy these file(s) to your CSE account using the following command:

1511 fetch-activity pass_the_parcel

The pass_the_parcel function takes an array of SIZE integers, where each element is the gift held by the person at that position. Your task is to complete pass_the_parcel so that every gift moves one position to the right, and the last gift wraps around to the front.

The array should be modified in place.

Examples

If the array contains these elements:

{1, 2, 3, 4, 5}

After calling your function, it should contain:

{5, 1, 2, 3, 4}

The 5 at the end has wrapped around to the front, and everything else has shifted one place to the right.

Alternatively, if the array contains these elements:

{7, 7, 7, 7, 7}

After calling your function, it should contain:

{7, 7, 7, 7, 7}

Assumptions/Restrictions/Clarifications

• You may assume the array always contains exactly SIZE elements.
• You may assume SIZE is at least 1.
• The gifts do not need to be unique. The same value may appear more than once.
• Gifts may be any integer, including 0 and negative numbers.
• The array must be modified in place. Do not create a second array to build the result in.
• Your pass_the_parcel function will be called directly in marking. The main function is only there to let you test it.

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest pass_the_parcel

// pass_the_parcel.c
//
// Written by Holly Field (z5477436)
// on 4/8/26
//
// Passes each gift one position to the right around a circle.

#include <stdio.h>

#define SIZE 5

// Each person passes their gift to the person on their right.
// The gift at the end of the array wraps around to the front.
// The array is modified in place.
// DO NOT CHANGE THE FUNCTION DECLARATION
void pass_the_parcel(int gifts[SIZE]) {
    // Save the last gift before it gets overwritten.
    int last = gifts[SIZE - 1];

    // Work backwards so every cell is read before it is written to.
    for (int i = SIZE - 1; i > 0; i--) {
        gifts[i] = gifts[i - 1];
    }

    // The last gift wraps around to the front.
    gifts[0] = last;
}

// This is a simple main function which could be used
// to test your pass_the_parcel function.
// Only your pass_the_parcel function will be marked.
int main(void) {

    // This array should become {5, 1, 2, 3, 4}
    // after being passed to the pass_the_parcel function
    int test_gifts[SIZE] = {1, 2, 3, 4, 5};

    // DO NOT ADD YOUR FUNCTIONALITY/LOGIC IN MAIN
    // IT WILL NOT BE MARKED
    pass_the_parcel(test_gifts);

    for (int i = 0; i < SIZE; i++) {
        printf("%d ", test_gifts[i]);
    }
    printf("\n");

    return 0;
}

Download broken_wordle.c here

Or, copy these file(s) to your CSE account using the following command:

1511 fetch-activity broken_wordle

The program broken_wordle.c should read in a target word and a guess, then print the feedback for that guess, one character per letter:

• G - the letter is correct and in the correct position.
• Y - the letter is in the word, but in the wrong position.
• . - the letter is not in the word.

If every letter is correct, the program should also print You win!.

However, the program currently has some issues it is your job to figure them out and fix the code.

Examples

dcc broken_wordle.c -o broken_wordle
./broken_wordle
Enter the target word: CRANE
Enter your guess: SLOTH
Scoring your guess...
.....
dcc broken_wordle.c -o broken_wordle
./broken_wordle
Enter the target word: CRANE
Enter your guess: EARNS
Scoring your guess...
YYYG.
dcc broken_wordle.c -o broken_wordle
./broken_wordle
Enter the target word: CRANE
Enter your guess: CRANE
Scoring your guess...
GGGGG
You win!

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest broken_wordle

// broken_wordle.c
//
// This program should scan in a target word and a guess, then print the
// Wordle-style feedback for that guess:
//   'G' - the letter is correct and in the correct position
//   'Y' - the letter is in the word, but in the wrong position
//   '.' - the letter is not in the word
//
// Unfortunately, this code contains a number of errors.
// It's your job to fix them, good luck!

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

#define WORD_LENGTH 5
#define BUFFER_SIZE 20

////////////////////////////////////////////////////////////////////////////////
//                 DO NOT CHANGE ANY OF THE CODE BELOW HERE                   //
//   THE CODE BELOW IS SIMPLY TO ASSIST IN SCANNING IN THE TARGET WORD AND    //
//              THE GUESS. THERE ARE NO BUGS IN THIS SECTION.                 //
////////////////////////////////////////////////////////////////////////////////

int main(void) {

    char target[BUFFER_SIZE];
    char guess[BUFFER_SIZE];

    printf("Enter the target word: ");
    scanf("%s", target);

    printf("Enter your guess: ");
    scanf("%s", guess);

    printf("Scoring your guess...\n");

    ////////////////////////////////////////////////////////////////////////////
    //               DO NOT CHANGE ANY OF THE CODE ABOVE HERE                 //
    //  THE CODE ABOVE IS SIMPLY TO ASSIST IN SCANNING IN THE TARGET WORD AND //
    //             THE GUESS. THERE ARE NO BUGS IN THIS SECTION.              //
    ////////////////////////////////////////////////////////////////////////////

    ////////////////////////////////////////////////////////////////////////////
    ////////////////////// ONLY EDIT CODE BELOW HERE ///////////////////////////
    ////////////////////////////////////////////////////////////////////////////

    char result[WORD_LENGTH + 1];
    result[WORD_LENGTH] = '\0';

    // Mark every letter that is in the correct position.
    int i = 0;
    // BUG: was <=, read a sixth letter and overwrote the null terminator
    while (i < WORD_LENGTH) {           
                                        
        if (guess[i] == target[i]) {
            result[i] = 'G';
        } else {
            result[i] = '.';
        }
        // BUG: was missing, so the loop never ended 
        i++;
    }

    // Mark every remaining letter that appears somewhere in the word.
    for (int j = 0; j < WORD_LENGTH; j++) {
        // BUG: was =, an assignment, so the condition was always true
        if (result[j] == '.') {         
            for (int k = 0; k < WORD_LENGTH; k++) {
                // BUG: was target[j], which compared the same pair of
                // letters five times instead of scanning the whole word
                if (guess[j] == target[k]) { 
                    result[j] = 'Y';
                }
            }
        }
    }

    // BUG: was %c, given a char *
    printf("%s\n", result);             

    if (strcmp(result, "GGGGG") == 0) {
        printf("You win!\n");
    }
}

Download draw_and_debug.c here

Or, copy these file(s) to your CSE account using the following command:

1511 fetch-activity draw_and_debug

Every program in this activity contains a linked list function that builds a linked list from its command line arguments, prints it, runs the function, and prints the transformed list.

However, every program currently has some issues it is your job to figure them out and fix the code.

1. How Long Is This List? (Tutor Demo)

list_length should return the number of nodes in the list.

// debug_list_length.c
//
// Tutor demo: this function is supposed to count the nodes in a list.

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

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

int list_length(struct node *head);
struct node *strings_to_list(int len, char *strings[]);
void print_list(char *label, struct node *head);

// -----------------------------------------------------------------------------

int main(int argc, char *argv[]) {
    struct node *head = strings_to_list(argc - 1, &argv[1]);

    print_list("list", head);
    printf("length = %d\n", list_length(head));

    return 0;
}

// -----------------------------------------------------------------------------
// THE BROKEN FUNCTION
// -----------------------------------------------------------------------------

// Returns the number of nodes in the list.
int list_length(struct node *head) {
    int length = 0;
    struct node *curr = head;

    while (curr->next != NULL) {
        length++;
        curr = curr->next;
    }

    return length;
}

// -----------------------------------------------------------------------------
// PROVIDED FUNCTIONS
// -----------------------------------------------------------------------------
//////////////// DO NOT CHANGE ANY OF THE CODE BELOW HERE //////////////////////

// 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(char *label, struct node *head) {
    printf("%s = [", label);
    struct node *n = head;
    while (n != NULL) {
        printf("%d", n->data);
        if (n->next != NULL) {
            printf(", ");
        }
        n = n->next;
    }
    printf("]\n");
}

Example

./debug_list_length 1 2 3 4 5
list = [1, 2, 3, 4, 5]
length = 5
./debug_list_length 
list = []
length = 0

2. Insert at the nth Position

For insert_nth, you may assume the position entered is a valid position in the list. Position 0 means the new node becomes the new head.

// debug_insert_nth.c
//
// Written by YOUR-NAME (YOUR-ZID)
// on TODAYS-DATE
//
// This function is supposed to insert a new node at position n.

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

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

struct node *insert_nth(struct node *head, int value, int n);
struct node *strings_to_list(int len, char *strings[]);
void print_list(char *label, struct node *head);

// -----------------------------------------------------------------------------

int main(int argc, char *argv[]) {
    struct node *head = strings_to_list(argc - 1, &argv[1]);

    int value;
    int position;
    printf("Enter the value to insert: ");
    scanf("%d", &value);
    printf("Enter the position to insert it at: ");
    scanf("%d", &position);

    print_list("before", head);
    head = insert_nth(head, value, position);
    print_list("after ", head);

    return 0;
}

// -----------------------------------------------------------------------------
// THE BROKEN FUNCTION
// -----------------------------------------------------------------------------

// Inserts a new node holding value, so that it ends up at position n.
// Positions are counted from 0.
struct node *insert_nth(struct node *head, int value, int n) {
    struct node *new_node = malloc(sizeof(struct node));
    assert(new_node != NULL);
    new_node->data = value;
    new_node->next = NULL;

    // Walk to the node the new node should go after.
    struct node *curr = head;
    for (int i = 0; i < n; i++) {
        curr = curr->next;
    }

    new_node->next = curr->next;
    curr->next = new_node;

    return head;
}

// -----------------------------------------------------------------------------
// PROVIDED FUNCTIONS
// -----------------------------------------------------------------------------
//////////////// DO NOT CHANGE ANY OF THE CODE BELOW HERE //////////////////////

// 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(char *label, struct node *head) {
    printf("%s = [", label);
    struct node *n = head;
    while (n != NULL) {
        printf("%d", n->data);
        if (n->next != NULL) {
            printf(", ");
        }
        n = n->next;
    }
    printf("]\n");
}

Examples

dcc debug_insert_nth.c -o debug_insert_nth
./debug_insert_nth 1 2 3 4 5
Enter the value to insert: 99
Enter the position to insert it at: 2
before = [1, 2, 3, 4, 5]
after  = [1, 2, 99, 3, 4, 5]
./debug_insert_nth 1 2 3 4 5
Enter the value to insert: 99
Enter the position to insert it at: 0
before = [1, 2, 3, 4, 5]
after  = [99, 1, 2, 3, 4, 5]

3. Delete All Even Values

delete_even should remove every node holding an even value.

// debug_delete_even.c
//
// Written by YOUR-NAME (YOUR-ZID)
// on TODAYS-DATE
//
// This function is supposed to delete every node with an even value.

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

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

struct node *delete_even(struct node *head);
struct node *strings_to_list(int len, char *strings[]);
void print_list(char *label, struct node *head);

// -----------------------------------------------------------------------------

int main(int argc, char *argv[]) {
    struct node *head = strings_to_list(argc - 1, &argv[1]);

    print_list("before", head);
    head = delete_even(head);
    print_list("after ", head);

    return 0;
}

// -----------------------------------------------------------------------------
// THE BROKEN FUNCTION
// -----------------------------------------------------------------------------

// Removes every node holding an even value.
struct node *delete_even(struct node *head) {
    struct node *prev = head;
    struct node *curr = head->next;

    while (curr != NULL) {
        if (curr->data % 2 == 0) {
            prev->next = curr->next;
            free(curr);
            curr = prev->next;
        } else {
            prev = curr;
            curr = curr->next;
        }
    }

    return head;
}

// -----------------------------------------------------------------------------
// PROVIDED FUNCTIONS
// -----------------------------------------------------------------------------
//////////////// DO NOT CHANGE ANY OF THE CODE BELOW HERE //////////////////////

// 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(char *label, struct node *head) {
    printf("%s = [", label);
    struct node *n = head;
    while (n != NULL) {
        printf("%d", n->data);
        if (n->next != NULL) {
            printf(", ");
        }
        n = n->next;
    }
    printf("]\n");
}

Example

dcc debug_delete_even.c -o debug_delete_even
./debug_delete_even 2 3 4 5 6
before = [2, 3, 4, 5, 6]
after  = [3, 5]
./debug_delete_even 2 3 4 5 6
before = [2, 3, 4, 5, 6]
after  = [1, 3]
./debug_delete_even 2 4 6
before = [2, 4, 6]
after  = []

4. Swap the Smallest and Largest

swap_min_max should swap the values held by the smallest and largest nodes.

// debug_swap_min_max.c
//
// Written by YOUR-NAME (YOUR-ZID)
// on TODAYS-DATE
//
// This function is supposed to swap the smallest and largest values.

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

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

void swap_min_max(struct node *head);
struct node *strings_to_list(int len, char *strings[]);
void print_list(char *label, struct node *head);

// -----------------------------------------------------------------------------

int main(int argc, char *argv[]) {
    struct node *head = strings_to_list(argc - 1, &argv[1]);

    print_list("before", head);
    swap_min_max(head);
    print_list("after ", head);

    return 0;
}

// -----------------------------------------------------------------------------
// THE BROKEN FUNCTION
// -----------------------------------------------------------------------------

// Swaps the values held by the smallest and largest nodes.
void swap_min_max(struct node *head) {
    struct node *smallest = head;
    struct node *largest = head;

    struct node *curr = head;
    while (curr != NULL) {
        if (curr->data < smallest->data) {
            smallest = curr;
        }
        if (curr->data > largest->data) {
            largest = curr;
        }
        curr = curr->next;
    }

    smallest->data = largest->data;
    largest->data = smallest->data;
}

// -----------------------------------------------------------------------------
// PROVIDED FUNCTIONS
// -----------------------------------------------------------------------------
//////////////// DO NOT CHANGE ANY OF THE CODE BELOW HERE //////////////////////

// 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(char *label, struct node *head) {
    printf("%s = [", label);
    struct node *n = head;
    while (n != NULL) {
        printf("%d", n->data);
        if (n->next != NULL) {
            printf(", ");
        }
        n = n->next;
    }
    printf("]\n");
}

Example

dcc debug_swap_min_max.c -o debug_swap_min_max
./debug_swap_min_max 3 9 1 7 5
before = [3, 9, 1, 7, 5]
after  = [3, 1, 9, 7, 5]
./debug_swap_min_max -5 10 8
before = [-5, 10, 8]
after  = [10, -5, 8]

5. Insert Third Last

insert_third_last should insert a new node so that it becomes the third last node in the list.

// debug_insert_third_last.c
//
// Written by YOUR-NAME (YOUR-ZID)
// on TODAYS-DATE
//
// This function is supposed to insert a new third last node.

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

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

struct node *insert_third_last(struct node *head, int value);
struct node *strings_to_list(int len, char *strings[]);
void print_list(char *label, struct node *head);

// -----------------------------------------------------------------------------

int main(int argc, char *argv[]) {
    struct node *head = strings_to_list(argc - 1, &argv[1]);

    int value;
    printf("Enter the value to insert: ");
    scanf("%d", &value);

    print_list("before", head);
    head = insert_third_last(head, value);
    print_list("after ", head);

    return 0;
}

// -----------------------------------------------------------------------------
// THE BROKEN FUNCTION
// -----------------------------------------------------------------------------

// Inserts a new node holding value, so that it becomes the third last
// node in the list.
struct node *insert_third_last(struct node *head, int value) {
    struct node *new_node = malloc(sizeof(struct node));
    assert(new_node != NULL);
    new_node->data = value;
    new_node->next = NULL;

    // Walk to the node the new node should go after.
    struct node *curr = head;
    while (curr->next->next != NULL) {
        curr = curr->next;
    }

    new_node->next = curr->next;
    curr->next = new_node;

    return head;
}

// -----------------------------------------------------------------------------
// PROVIDED FUNCTIONS
// -----------------------------------------------------------------------------
//////////////// DO NOT CHANGE ANY OF THE CODE BELOW HERE //////////////////////

// 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(char *label, struct node *head) {
    printf("%s = [", label);
    struct node *n = head;
    while (n != NULL) {
        printf("%d", n->data);
        if (n->next != NULL) {
            printf(", ");
        }
        n = n->next;
    }
    printf("]\n");
}

Example

dcc debug_insert_third_last.c -o debug_insert_third_last
./debug_insert_third_last 1 2 3 4 5
Enter the value to insert: 99
before = [1, 2, 3, 4, 5]
after  = [1, 2, 3, 99, 4, 5]
./debug_insert_third_last 2 3 
Enter the value to insert: 99
before = [2, 3]
after  = [99, 2, 3]

Download dancing_bird.c here

Or, copy these file(s) to your CSE account using the following command:

1511 fetch-activity dancing_bird

A bird has taken to the dance floor. (・v・)

Before splitting into groups, your tutor will live-code a demo of dancing_bird_two_step.c, which moves the bird around the floor and implements the bird's first special move.

Each of the programs below will:

• Print the dance floor, then read single characters from standard input until [Ctrl-D] is pressed.
• Move the bird according to the character entered, then print the floor again.

The commands are:

• w - move one cell up.
• s - move one cell down.
• a - move one cell left.
• d - move one cell right.
• x - move according to the special move.

The dance floor is a 2D array of struct tile. Each tile stores what is currently on it, and how much energy it holds.

• A tile the bird is standing on has type BIRD.
• Once the bird moves off a tile, that tile becomes DANCED_ON.
• Tiles the bird has never visited stay EMPTY.
• When the floor is printed, each tile shows its state followed by its energy value: . for EMPTY, * for DANCED_ON, and v for the BIRD.

The bird's position is tracked with a struct position, and any information a special move needs to remember between moves lives in a struct dance_state.

1. Basic Movement and the Two Step (Tutor Demo)

Complete move_bird so that it moves the bird by the given change in row and column, updating the tiles it leaves and arrives at. If the move would take the bird off the floor, the bird stays where it is and no tiles change.

Then complete special_move so that the bird alternates between stepping right and stepping left each time x is pressed.

Example

dcc dancing_bird_two_step.c -o dancing_bird_two_step
./dancing_bird_two_step
Let's dance!

+----+----+----+----+----+
| v3 | .1 | .4 | .1 | .5 |
+----+----+----+----+----+
| .9 | .2 | .6 | .5 | .3 |
+----+----+----+----+----+
| .5 | .8 | .9 | .7 | .9 |
+----+----+----+----+----+
| .3 | .2 | .3 | .8 | .4 |
+----+----+----+----+----+
| .6 | .2 | .6 | .4 | .3 |
+----+----+----+----+----+
d

+----+----+----+----+----+
| *3 | v1 | .4 | .1 | .5 |
+----+----+----+----+----+
| .9 | .2 | .6 | .5 | .3 |
+----+----+----+----+----+
| .5 | .8 | .9 | .7 | .9 |
+----+----+----+----+----+
| .3 | .2 | .3 | .8 | .4 |
+----+----+----+----+----+
| .6 | .2 | .6 | .4 | .3 |
+----+----+----+----+----+
x

+----+----+----+----+----+
| *3 | *1 | v4 | .1 | .5 |
+----+----+----+----+----+
| .9 | .2 | .6 | .5 | .3 |
+----+----+----+----+----+
| .5 | .8 | .9 | .7 | .9 |
+----+----+----+----+----+
| .3 | .2 | .3 | .8 | .4 |
+----+----+----+----+----+
| .6 | .2 | .6 | .4 | .3 |
+----+----+----+----+----+
x

+----+----+----+----+----+
| *3 | v1 | *4 | .1 | .5 |
+----+----+----+----+----+
| .9 | .2 | .6 | .5 | .3 |
+----+----+----+----+----+
| .5 | .8 | .9 | .7 | .9 |
+----+----+----+----+----+
| .3 | .2 | .3 | .8 | .4 |
+----+----+----+----+----+
| .6 | .2 | .6 | .4 | .3 |
+----+----+----+----+----+
[Ctrl-D]

The first x steps right, the second steps left, and so on.

2. Happy Feet

Complete special_move so that the bird steps to whichever of its neighbouring tiles has the highest energy value.

Only the four tiles directly up, down, left and right of the bird count as neighbours — not the diagonals. Neighbours off the edge of the floor are not options. If two neighbours are tied on energy, move to whichever you find first when checking in the order up, down, left, right.

Example

./dancing_bird_happy_feet
Let's dance!

+----+----+----+----+----+
| v3 | .1 | .4 | .1 | .5 |
+----+----+----+----+----+
| .9 | .2 | .6 | .5 | .3 |
+----+----+----+----+----+
| .5 | .8 | .9 | .7 | .9 |
+----+----+----+----+----+
| .3 | .2 | .3 | .8 | .4 |
+----+----+----+----+----+
| .6 | .2 | .6 | .4 | .3 |
+----+----+----+----+----+
x

+----+----+----+----+----+
| *3 | .1 | .4 | .1 | .5 |
+----+----+----+----+----+
| v9 | .2 | .6 | .5 | .3 |
+----+----+----+----+----+
| .5 | .8 | .9 | .7 | .9 |
+----+----+----+----+----+
| .3 | .2 | .3 | .8 | .4 |
+----+----+----+----+----+
| .6 | .2 | .6 | .4 | .3 |
+----+----+----+----+----+
x

+----+----+----+----+----+
| *3 | .1 | .4 | .1 | .5 |
+----+----+----+----+----+
| *9 | .2 | .6 | .5 | .3 |
+----+----+----+----+----+
| v5 | .8 | .9 | .7 | .9 |
+----+----+----+----+----+
| .3 | .2 | .3 | .8 | .4 |
+----+----+----+----+----+
| .6 | .2 | .6 | .4 | .3 |
+----+----+----+----+----+
[Ctrl-D]

From the corner, the bird's only neighbours are the 1 to its right and the 9 below it, so it steps down. From there its best neighbour is the 5 below it, so it steps down again.

Press x a third time and the bird will step straight back up to the 9 — this bird has no memory, and will happily bounce between two tiles forever.

Extra challenge: stop the bird from moving straight back to the tile it came from on the previous special move.

3. Moonwalk

Complete special_move so that the bird keeps moving in the same direction it moved on the previous special move.

"Previous move" here means the last time x was pressed, not the last time the bird moved at all. Pressing w, a, s or d moves the bird but does not change the direction the moonwalk will take — that direction lives in state, and only special_move ever writes to it.

If moving in that direction would take the bird off the floor, the direction inverts, and the bird moves in the new direction instead. The direction stays inverted for following moves.

The starting direction is set up for you in main.

Example

./dancing_bird_moonwalk
Let's dance!

+----+----+----+----+----+
| v3 | .1 | .4 | .1 | .5 |
+----+----+----+----+----+
| .9 | .2 | .6 | .5 | .3 |
+----+----+----+----+----+
| .5 | .8 | .9 | .7 | .9 |
+----+----+----+----+----+
| .3 | .2 | .3 | .8 | .4 |
+----+----+----+----+----+
| .6 | .2 | .6 | .4 | .3 |
+----+----+----+----+----+
x

+----+----+----+----+----+
| *3 | v1 | .4 | .1 | .5 |
+----+----+----+----+----+
| .9 | .2 | .6 | .5 | .3 |
+----+----+----+----+----+
| .5 | .8 | .9 | .7 | .9 |
+----+----+----+----+----+
| .3 | .2 | .3 | .8 | .4 |
+----+----+----+----+----+
| .6 | .2 | .6 | .4 | .3 |
+----+----+----+----+----+
s

+----+----+----+----+----+
| *3 | *1 | .4 | .1 | .5 |
+----+----+----+----+----+
| .9 | v2 | .6 | .5 | .3 |
+----+----+----+----+----+
| .5 | .8 | .9 | .7 | .9 |
+----+----+----+----+----+
| .3 | .2 | .3 | .8 | .4 |
+----+----+----+----+----+
| .6 | .2 | .6 | .4 | .3 |
+----+----+----+----+----+
x

+----+----+----+----+----+
| *3 | *1 | .4 | .1 | .5 |
+----+----+----+----+----+
| .9 | *2 | v6 | .5 | .3 |
+----+----+----+----+----+
| .5 | .8 | .9 | .7 | .9 |
+----+----+----+----+----+
| .3 | .2 | .3 | .8 | .4 |
+----+----+----+----+----+
| .6 | .2 | .6 | .4 | .3 |
+----+----+----+----+----+
[Ctrl-D]

The bird starts out facing left, but it is already against the left wall, so the first x inverts the direction and steps right instead.

The s in the middle moves the bird down, but leaves the moonwalk direction alone — so the next x still steps right, not down. Keep pressing x and the bird will walk into the right wall and come back the other way.

Extra challenge: make w, a, s and d set the direction too, so the moonwalk continues whichever way the bird last moved. Note that this means main writes to state as well, so think about where that update belongs.

4. Shy Dancer

Complete special_move so that the bird checks the tiles around it in the order right, down, left, up, and moves to the first one that is both:

• still on the dance floor, and
• not already DANCED_ON.

If none of the four are available, the bird stays where it is.

Example

./dancing_bird_shy_dancer
Let's dance!

+----+----+----+----+----+
| v3 | .1 | .4 | .1 | .5 |
+----+----+----+----+----+
| .9 | .2 | .6 | .5 | .3 |
+----+----+----+----+----+
| .5 | .8 | .9 | .7 | .9 |
+----+----+----+----+----+
| .3 | .2 | .3 | .8 | .4 |
+----+----+----+----+----+
| .6 | .2 | .6 | .4 | .3 |
+----+----+----+----+----+
x

+----+----+----+----+----+
| *3 | v1 | .4 | .1 | .5 |
+----+----+----+----+----+
| .9 | .2 | .6 | .5 | .3 |
+----+----+----+----+----+
| .5 | .8 | .9 | .7 | .9 |
+----+----+----+----+----+
| .3 | .2 | .3 | .8 | .4 |
+----+----+----+----+----+
| .6 | .2 | .6 | .4 | .3 |
+----+----+----+----+----+
x

+----+----+----+----+----+
| *3 | *1 | v4 | .1 | .5 |
+----+----+----+----+----+
| .9 | .2 | .6 | .5 | .3 |
+----+----+----+----+----+
| .5 | .8 | .9 | .7 | .9 |
+----+----+----+----+----+
| .3 | .2 | .3 | .8 | .4 |
+----+----+----+----+----+
| .6 | .2 | .6 | .4 | .3 |
+----+----+----+----+----+
[Ctrl-D]

Right is available at first, so the bird hugs the top of the floor. Once it reaches the right wall, right is out of bounds and it starts heading down. At the bottom-right corner both right and down are out of bounds, so it turns left along the bottom, then up the left side. Chain enough x presses together and the bird will trace a full lap of the room — and because the border is now all DANCED_ON, it then spirals inwards.

Extension: Counting Energy

Once your rule works, add a function that counts the total energy of the session:

int count_energy(struct tile dance_floor[SIZE][SIZE]);

It should add up the energy_value of every tile that has been DANCED_ON, and return the total. Call it after the input loop in main and print the result, so your bird gets a score at the end of the session.

Assumptions/Restrictions/Clarifications

• No error checking is required.

Download speed_friending.c here

Or, copy these file(s) to your CSE account using the following command:

1511 fetch-activity speed_friending

Your task is to complete the program speed_friending.c using the provided starter code.

A main function has been implemented for you. The program reads in the individual looking for a friend, then reads in everybody else in the room, until [Ctrl-D] is pressed. Each person is entered as a name followed by a favourite colour, and is stored as a struct person.

However, the function that searches for a match is currently incomplete.

You must implement the function find_match:

• Given an individual and an array of people, find the first person in the array whose favourite_colour matches the individual's favourite_colour.
• Print the name of the first matching person, in the form "%s found a match with %s!\n", where the first name is the individual's and the second is the match's.
• If no one in the array shares the individual's favourite colour, print "No match found!\n" instead.

Examples

dcc speed_friending.c -o speed_friending
./speed_friending
Enter your name and favourite colour: alex green
Enter everyone else in the room:
blair red
casey green
devon green
[Ctrl-D]

alex found a match with casey!
./speed_friending
Enter your name and favourite colour: alex green
Enter everyone else in the room:
blair red
casey blue
devon yellow
[Ctrl-D]

No match found!
./speed_friending
Enter your name and favourite colour: alex purple
Enter everyone else in the room:
[Ctrl-D]

No match found!

Assumptions/Restrictions/Clarifications

• String comparison should be case sensitive, meaning "Blue" and "blue" are considered different colours.

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest speed_friending

// speed_friending.c
//
// Written by Holly Field (z5477436)
// on 4/8/2026
//
// Finds the first person in a room who shares an individual's
// favourite colour.

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

// Constants
#define MAX_PEOPLE 100
#define MAX_LENGTH 32

struct person {
    char name[MAX_LENGTH];
    char favourite_colour[MAX_LENGTH];
};

// Function prototypes
void find_match(struct person individual, struct person people[MAX_PEOPLE],
                int num_people);
struct person read_person(void);
int read_people(struct person people[MAX_PEOPLE]);
int scan_token(char *buffer, int buffer_size);

// -----------------------------------------------------------------------------
//////////////// DO NOT CHANGE THE MAIN FUNCTION ///////////////////////////////

int main(void) {
    printf("Enter your name and favourite colour: ");
    struct person individual = read_person();

    struct person people[MAX_PEOPLE];
    printf("Enter everyone else in the room:\n");
    int num_people = read_people(people);

    printf("\n");
    find_match(individual, people, num_people);

    return 0;
}

// -----------------------------------------------------------------------------
// YOUR FUNCTIONS
// -----------------------------------------------------------------------------

// Find the first person in the array who shares the individual's
// favourite colour, and print the result.
void find_match(struct person individual, struct person people[MAX_PEOPLE],
                int num_people) {
    for (int i = 0; i < num_people; i++) {
        if (strcmp(people[i].favourite_colour,
                   individual.favourite_colour) == 0) {
            printf("%s found a match with %s!\n", individual.name,
                   people[i].name);
            return;
        }
    }

    printf("No match found!\n");
}

// -----------------------------------------------------------------------------
// PROVIDED FUNCTIONS
// -----------------------------------------------------------------------------
// DO NOT CHANGE ANY OF THE CODE BELOW HERE

// Read people from stdin into the given array, returning how many
int read_people(struct person people[MAX_PEOPLE]) {
    int num_people = 0;

    while (num_people < MAX_PEOPLE &&
           scan_token(people[num_people].name, MAX_LENGTH) == 1 &&
           scan_token(people[num_people].favourite_colour, MAX_LENGTH) == 1) {
        num_people++;
    }

    return num_people;
}

// Read a single person from stdin
struct person read_person(void) {
    struct person p;
    scan_token(p.name, MAX_LENGTH);
    scan_token(p.favourite_colour, MAX_LENGTH);

    return p;
}

// scan a single whitespace-separated token from stdin
int scan_token(char *buffer, int buffer_size) {
    if (buffer_size == 0) {
        return 0;
    }

    char c;
    int i = 0;
    int num_scanned = 0;

    scanf(" ");

    while (i < buffer_size - 1 && (num_scanned = scanf("%c", &c)) == 1 &&
           !isspace(c)) {
        buffer[i++] = c;
    }

    if (i > 0) {
        buffer[i] = '\0';
    }

    return num_scanned;
}

Download carrot_harvest.c here

Or, copy these file(s) to your CSE account using the following command:

1511 fetch-activity carrot_harvest

Your task is to complete the program carrot_harvest.c using the provided starter code.

A main function has been implemented for you. The program reads in the dimensions of the patch, then reads in the contents of each plot. It harvests the patch and prints the result. However, the function that harvests the patch is currently incomplete.

Each plot is entered as a single character:

• c - CARROT
• t - TURNIP
• p - POTATO
• . - EMPTY

You must implement the function carrot_harvest:

• Given the grid and its dimensions, check each row to see if every cell in that row is CARROT.
• If an entire row consists only of CARROT cells, harvest it by setting every cell in that row to EMPTY.
• Rows that contain anything other than CARROT should be left completely unchanged.

Examples

dcc carrot_harvest.c -o carrot_harvest
./carrot_harvest
Enter the size of the patch: 3 4
Enter the contents of the patch:
cccc
cctc
cccc

The patch after harvesting:
....
cctc
....
./carrot_harvest
Enter the size of the patch: 3 3
Enter the contents of the patch:
ctp
tpc
ptc

The patch after harvesting:
ctp
tpc
ptc
./carrot_harvest
Enter the size of the patch: 2 5
Enter the contents of the patch:
ccccc
ccccc

The patch after harvesting:
.....
.....
./carrot_harvest
Enter the size of the patch: 2 3
Enter the contents of the patch:
...
ccc

The patch after harvesting:
...
...

Assumptions/Restrictions/Clarifications

• No error checking required.

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest carrot_harvest

// carrot_harvest.c
//
// Written by Holly Field (z5477436)
// on 4/8/2026
//
// Harvests every row of a vegetable patch that is entirely carrots.

#include <stdio.h>

// Constants
#define MAX_SIZE 20

enum vegetable {
    CARROT,
    TURNIP,
    POTATO,
    EMPTY
};

// Function prototypes
void carrot_harvest(enum vegetable patch[MAX_SIZE][MAX_SIZE], int rows,
                    int cols);
void read_patch(enum vegetable patch[MAX_SIZE][MAX_SIZE], int rows, int cols);
void print_patch(enum vegetable patch[MAX_SIZE][MAX_SIZE], int rows, int cols);

// -----------------------------------------------------------------------------
//////////////// DO NOT CHANGE THE MAIN FUNCTION ///////////////////////////////

int main(void) {
    enum vegetable patch[MAX_SIZE][MAX_SIZE];
    int rows;
    int cols;

    printf("Enter the size of the patch: ");
    scanf("%d %d", &rows, &cols);

    printf("Enter the contents of the patch:\n");
    read_patch(patch, rows, cols);

    carrot_harvest(patch, rows, cols);

    printf("\nThe patch after harvesting:\n");
    print_patch(patch, rows, cols);

    return 0;
}


// -----------------------------------------------------------------------------
// YOUR FUNCTIONS
// -----------------------------------------------------------------------------

// Harvest every row of the patch that consists entirely of carrots, by
// setting each cell in that row to EMPTY. All other rows are unchanged.
void carrot_harvest(enum vegetable patch[MAX_SIZE][MAX_SIZE], int rows,
                    int cols) {
    for (int i = 0; i < rows; i++) {
        // First check the whole row, before changing anything.
        int all_carrots = 1;
        for (int j = 0; j < cols; j++) {
            if (patch[i][j] != CARROT) {
                all_carrots = 0;
            }
        }

        // Only once we know the entire row is carrots do we harvest it.
        if (all_carrots) {
            for (int j = 0; j < cols; j++) {
                patch[i][j] = EMPTY;
            }
        }
    }
}

// -----------------------------------------------------------------------------
// PROVIDED FUNCTIONS
// -----------------------------------------------------------------------------
// DO NOT CHANGE ANY OF THE CODE BELOW HERE

// Read the contents of the patch from stdin
void read_patch(enum vegetable patch[MAX_SIZE][MAX_SIZE], int rows, int cols) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            char plot;
            scanf(" %c", &plot);
            if (plot == 'c') {
                patch[i][j] = CARROT;
            } else if (plot == 't') {
                patch[i][j] = TURNIP;
            } else if (plot == 'p') {
                patch[i][j] = POTATO;
            } else {
                patch[i][j] = EMPTY;
            }
        }
    }
}

// Print the contents of the patch
void print_patch(enum vegetable patch[MAX_SIZE][MAX_SIZE], int rows, int cols) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (patch[i][j] == CARROT) {
                printf("c");
            } else if (patch[i][j] == TURNIP) {
                printf("t");
            } else if (patch[i][j] == POTATO) {
                printf("p");
            } else {
                printf(".");
            }
        }
        printf("\n");
    }
}

Download vege_patch.c here

Or, copy these file(s) to your CSE account using the following command:

1511 fetch-activity vege_patch

Your task is to complete the program vege_patch.c using the provided starter code.

A main function has been implemented for you. The program reads in a 2D array representing a vegetable garden, divided into square plots. Each cell holds the yield (in kg) of vegetables harvested from that plot.

A gardener can walk a diagonal path across the garden, moving in a top-left to bottom-right diagonal direction. However, the function that finds the most productive diagonal path is currently incomplete.

You must implement the function get_best_yield:

• Given the grid and its dimensions, consider every diagonal path that moves from a top-left to bottom-right direction.
• Compute the total yield along each such diagonal.
• Return the highest total yield found across all diagonals.

Examples

dcc vege_patch.c -o vege_patch
./vege_patch
Enter the size of the garden: 3 3
Enter the yield of each plot:
1 2 3
4 5 6
7 8 9
The most productive path yields 15 kg.
./vege_patch
Enter the size of the garden: 3 4
Enter the yield of each plot:
1 1 1 9
1 1 1 1
9 9 1 1
The most productive path yields 10 kg.
./vege_patch
Enter the size of the garden: 4 4
Enter the yield of each plot:
1 5 1 1
1 1 5 1
1 1 1 5
1 1 1 1
The most productive path yields 15 kg.
./vege_patch
Enter the size of the garden: 1 5
Enter the yield of each plot:
3 1 4 1 5
The most productive path yields 5 kg.

Assumptions/Restrictions/Clarifications

• No error checking is required

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest vege_patch

// vege_patch.c
//
// Written by Holly Field (z5477436)
// on 3/8/2026
//
// Finds the most productive top-left to bottom-right diagonal path
// through a vegetable garden.

#include <stdio.h>

// Constants
#define MAX_SIZE 10

// Function prototypes
int get_best_yield(int garden[MAX_SIZE][MAX_SIZE], int rows, int cols);
int diagonal_sum(int garden[MAX_SIZE][MAX_SIZE], int rows, int cols,
                 int start_row, int start_col);

int main(void) {
    int garden[MAX_SIZE][MAX_SIZE];
    int rows;
    int cols;

    printf("Enter the size of the garden: ");
    scanf("%d %d", &rows, &cols);

    printf("Enter the yield of each plot:\n");
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            scanf("%d", &garden[i][j]);
        }
    }

    int best = get_best_yield(garden, rows, cols);
    printf("The most productive path yields %d kg.\n", best);

    return 0;
}

// Return the highest total yield of any top-left to bottom-right
// diagonal path through the garden.
//
// Every such path starts on the left column or the top row, so we try
// each of those starting plots in turn.
int get_best_yield(int garden[MAX_SIZE][MAX_SIZE], int rows, int cols) {
    // Yields are non-negative, so 0 is a safe starting point.
    int max_sum = 0;

    // Paths starting on the left column.
    for (int i = 0; i < rows; i++) {
        int sum = diagonal_sum(garden, rows, cols, i, 0);
        if (sum > max_sum) {
            max_sum = sum;
        }
    }

    // Paths starting on the top row, skipping [0][0] as it was
    // already covered above.
    for (int j = 1; j < cols; j++) {
        int sum = diagonal_sum(garden, rows, cols, 0, j);
        if (sum > max_sum) {
            max_sum = sum;
        }
    }

    return max_sum;
}

// Return the total yield of the diagonal path beginning at
// garden[start_row][start_col], stepping down and to the right until
// the path leaves the garden.
int diagonal_sum(int garden[MAX_SIZE][MAX_SIZE], int rows, int cols,
                 int start_row, int start_col) {
    int sum = 0;
    int i = start_row;
    int j = start_col;

    while (i < rows && j < cols) {
        sum += garden[i][j];
        i++;
        j++;
    }

    return sum;
}

Download count_steps.c here

Or, copy these file(s) to your CSE account using the following command:

1511 fetch-activity count_steps

A dance instructor breaks a routine into phrases, and counts each one out loud from the top: a phrase of length 4 is counted as "1 2 3 4", a phrase of length 6 as "1 2 3 4 5 6", and so on. The whole routine is counted through, one phrase after another, without pausing.

Your task is to complete the program count_steps.c using the provided starter code.

A main function has been implemented for you. The program reads in an array of positive integers, each representing the length of one phrase, until [Ctrl-D] is pressed. It then prints out the full count for the routine. However, the function that builds the count is currently incomplete.

You must implement the function count_steps:

• Given an array of phrase lengths and its length, malloc a new array large enough to hold the full result.
• For each phrase, in order, append the numbers 1 up to and including that phrase's length to the new array.
• Return a pointer to the newly allocated array.

For example, given the phrase lengths 5 3 2, the resulting array should be:

1, 2, 3, 4, 5, 1, 2, 3, 1, 2

Examples

dcc count_steps.c -o count_steps
./count_steps
Enter the phrase lengths:
5 3 2
[Ctrl-D]
Count: 1 2 3 4 5 1 2 3 1 2
./count_steps
Enter the phrase lengths:
8
[Ctrl-D]
Count: 1 2 3 4 5 6 7 8
./count_steps
Enter the phrase lengths:
1 1 1 4
[Ctrl-D]
Count: 1 1 1 1 2 3 4
./count_steps
Enter the phrase lengths:
2
4
6
[Ctrl-D]
Count: 1 2 1 2 3 4 1 2 3 4 5 6
./count_steps
Enter the phrase lengths:
[Ctrl-D]
No steps to count!

Assumptions/Restrictions/Clarifications

• No error checking is required.

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest count_steps

// count_steps.c
//
// Written by Holly Field (z5477436)
// on 4/4/2026
//
// Counts out a dance routine, phrase by phrase, into a single array.

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

// Constants
#define MAX_PHRASES 100

// Function prototypes
int *count_steps(int phrases[MAX_PHRASES], int num_phrases);

// -----------------------------------------------------------------------------
//////////////// DO NOT CHANGE THE MAIN FUNCTION ///////////////////////////////

int main(void) {
    int phrases[MAX_PHRASES];
    int num_phrases = 0;
    int length;

    printf("Enter the phrase lengths:\n");
    while (num_phrases < MAX_PHRASES && scanf("%d", &length) == 1) {
        phrases[num_phrases] = length;
        num_phrases++;
    }

    if (num_phrases == 0) {
        printf("No steps to count!\n");
        return 0;
    }

    int *count = count_steps(phrases, num_phrases);

    // Work out how many steps were counted out in total.
    int total = 0;
    for (int i = 0; i < num_phrases; i++) {
        total += phrases[i];
    }

    printf("Count:");
    for (int i = 0; i < total; i++) {
        // If you're getting an error here,
        // you have returned an array that is too small
        printf(" %d", count[i]);
    }
    printf("\n");

    free(count);

    return 0;
}

// -----------------------------------------------------------------------------
// YOUR FUNCTIONS
// -----------------------------------------------------------------------------

// Return a newly allocated array holding the full count for the routine:
// the numbers 1 up to each phrase's length, for every phrase in order.
int *count_steps(int phrases[MAX_PHRASES], int num_phrases) {
    // The array needs one element for every count in every phrase.
    int total = 0;
    for (int i = 0; i < num_phrases; i++) {
        total += phrases[i];
    }

    int *count = malloc(total * sizeof(int));

    // Fill the array phrase by phrase, keeping track of where in the
    // new array the next step should go.
    int index = 0;
    for (int i = 0; i < num_phrases; i++) {
        for (int step = 1; step <= phrases[i]; step++) {
            count[index] = step;
            index++;
        }
    }

    return count;
}

Download crab_fight.c here

Or, copy these file(s) to your CSE account using the following command:

1511 fetch-activity crab_fight

Your task is to complete the program crab_fight.c using the provided starter code.

A main function has been implemented for you. The program repeatedly prompts a crab strength from the user and simulates that crab entering an arena, until [CTRL-D] is pressed. However, the functions that manipulate the linked list of fighters are currently incomplete.

You must implement the following functions:

1. insert_crab

   • Insert a new crab of the given strength into the list of fighters.
   • The new crab surpasses every existing crab it is strictly stronger than, and should be inserted immediately before the first crab it cannot surpass.
   • This keeps the list sorted in increasing order of strength.

2. filter_crabs

   • Remove all crabs from the list that have been knocked out.
   • A crab is knocked out once it has been surpassed by another crab 3 times.

For each crab strength read in, main calls insert_crab followed by filter_crabs, in that order.

Once [CTRL-D] is reached, the program prints the final list of surviving fighters from weakest to strongest, one per line, in the form "Strength: %d\n". If no crabs survive the tournament, it instead prints "No fighters left standing!\n".

Examples

dcc crab_fight.c -o crab_fight
./crab_fight
Enter the strength of the next crab: 10
10
Enter the strength of the next crab: 20
10 -> 20
Enter the strength of the next crab: 15
10 -> 15 -> 20
Enter the strength of the next crab: 5
5 -> 10 -> 15 -> 20
Enter the strength of the next crab: [Ctrl-D]

Final results:
5 -> 10 -> 15 -> 20
./crab_fight
Enter the strength of the next crab: 10
10
Enter the strength of the next crab: 20
10 -> 20
Enter the strength of the next crab: 30
10 -> 20 -> 30
Enter the strength of the next crab: 40
20 -> 30 -> 40
Enter the strength of the next crab: 50
30 -> 40 -> 50
Enter the strength of the next crab: [Ctrl-D]

Final results:
30 -> 40 -> 50
./crab_fight
Enter the strength of the next crab: 20
20
Enter the strength of the next crab: 30
20 -> 30
Enter the strength of the next crab: 40
20 -> 30 -> 40
Enter the strength of the next crab: 10
10 -> 20 -> 30 -> 40
Enter the strength of the next crab: 50
10 -> 30 -> 40 -> 50
Enter the strength of the next crab: [Ctrl-D]

Final results:
10 -> 30 -> 40 -> 50
./crab_fight
Enter the strength of the next crab: [Ctrl-D]

Final results:
No fighters left standing!

Assumptions/Restrictions/Clarifications

• No error checking is required

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest crab_fight

// crab_fight.c
//
// Written by Holly Field (z5477436)
// on 3/8/2026
//
// Simulates a crab fighting tournament using a linked list sorted by strength.

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

// A crab is knocked out once it has been surpassed this many times.
#define KNOCKOUT_LIMIT 3

// HINT: You may want to alter this struct
struct crab {
    int strength;
    int surpassed;
    struct crab *next;
};

// Function prototypes
struct crab *insert_crab(struct crab *fighters, int strength);
struct crab *filter_crabs(struct crab *fighters);
void print_fighters(struct crab *fighters);
struct crab *create_crab(int strength);

// -----------------------------------------------------------------------------
//////////////// DO NOT CHANGE THE MAIN FUNCTION ///////////////////////////////

int main(void) {
    struct crab *fighters = NULL;
    int strength;

    printf("Enter the strength of the next crab: ");
    while (scanf("%d", &strength) == 1) {
        fighters = insert_crab(fighters, strength);
        fighters = filter_crabs(fighters);
        print_fighters(fighters);
        printf("Enter the strength of the next crab: ");
    }

    printf("\nFinal results:\n");
    print_fighters(fighters);

    return 0;
}

// -----------------------------------------------------------------------------
// YOUR FUNCTIONS
// -----------------------------------------------------------------------------

// Insert a new crab of the given strength into the list of fighters.
// The list remains sorted in increasing order of strength. 
struct crab *insert_crab(struct crab *fighters, int strength) {
    struct crab *prev = NULL;
    struct crab *curr = fighters;

    // Walk past every crab the new crab is strictly stronger than
    while (curr != NULL && curr->strength < strength) {
        // the current crab has been surpassed by the new crab, 
        // so increment its surpassed count
        curr->surpassed++;
        prev = curr;
        curr = curr->next;
    }

    // Insert the new crab between prev and curr.
    struct crab *new_crab = create_crab(strength);
    new_crab->next = curr;
    if (prev == NULL) {
        // New crab is the new head of the list.
        fighters = new_crab;
    } else {
        prev->next = new_crab;
    }

    return fighters;
}

// Remove (and free) every crab that has been surpassed KNOCKOUT_LIMIT times.
struct crab *filter_crabs(struct crab *fighters) {
    struct crab *prev = NULL;
    struct crab *curr = fighters;

    while (curr != NULL) {
        struct crab *next = curr->next;
        if (curr->surpassed >= KNOCKOUT_LIMIT) {
            // current crab should be knocked out, so remove it from the list
            if (prev == NULL) {
                // current crab is the head of the list, so 
                // update the head pointer
                fighters = next;
            } else {
                prev->next = next;
            }
            free(curr);
        } else {
            prev = curr;
        }
        curr = next;
    }

    return fighters;
}

// Create a new crab with the given strength.
struct crab *create_crab(int strength) {
    struct crab *new_crab = malloc(sizeof(struct crab));
    new_crab->strength = strength;
    new_crab->surpassed = 0;
    new_crab->next = NULL;
    return new_crab;
}

// -----------------------------------------------------------------------------
// PROVIDED FUNCTIONS
// -----------------------------------------------------------------------------
// DO NOT CHANGE ANY OF THE CODE BELOW HERE

// Print the list of surviving fighters, from weakest to strongest.
// Print the list of surviving fighters, from weakest to strongest.
void print_fighters(struct crab *fighters) {
    if (fighters == NULL) {
        printf("No fighters left standing!\n");
        return;
    }

    struct crab *curr = fighters;
    while (curr != NULL) {
        printf("%d", curr->strength);
        if (curr->next != NULL) {
            printf(" -> ");
        }
        curr = curr->next;
    }
    printf("\n");
}

Download overstuffed_wrap.c here

Or, copy these file(s) to your CSE account using the following command:

1511 fetch-activity overstuffed_wrap

Your task is to complete the program overstuffed_wrap.c using the provided starter code.

A main function has been implemented for you. The program repeatedly reads in an ingredient name followed by 1 if the ingredient is vegan or 0 if it is not, until [Ctrl-D] is pressed, and builds a linked list of ingredients in the order they were entered. It then splits that list into two separate wraps and prints them both. However, the function that performs the split is currently incomplete.

You must implement the function split_wrap:

• Given the head of the original wrap's ingredient list, split it into two separate lists: one containing only the vegan ingredients, and one containing the remaining ingredients.
• An ingredient is vegan if its is_vegan field is 1.
• Ingredients must keep their original relative order within whichever list they end up in.

Since a function can only return one value, split_wrap should malloc a struct wrap_split, which holds the head of each of the two new lists, and return a pointer to it.

Examples

dcc overstuffed_wrap.c -o overstuffed_wrap
./overstuffed_wrap
Enter the ingredients in your wrap:
falafel 1
hummus 1
chicken 0
lettuce 1
cheese 0
tomato 1
[Ctrl-D]

Vegan wrap: [falafel, hummus, lettuce, tomato]
Non-vegan wrap: [chicken, cheese]
./overstuffed_wrap
Enter the ingredients in your wrap:
falafel 1
hummus 1
lettuce 1
[Ctrl-D]

Vegan wrap: [falafel, hummus, lettuce]
Non-vegan wrap: []
./overstuffed_wrap
Enter the ingredients in your wrap:
bacon 0
cheese 0
aioli 0
[Ctrl-D]

Vegan wrap: []
Non-vegan wrap: [bacon, cheese, aioli]
./overstuffed_wrap
Enter the ingredients in your wrap:
[Ctrl-D]

Vegan wrap: []
Non-vegan wrap: []

Assumptions/Restrictions/Clarifications

• No error checking required

Extra Challenge

Complete this task without allocating any new ingredients. Every ingredient already exists as a node in the original list, so the split can be done purely by rearranging the next pointers. The only thing you should need to malloc is the struct wrap_split itself.

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest overstuffed_wrap

// overstuffed_wrap.c
//
// Written by YOUR-NAME (YOUR-ZID)
// on TODAYS-DATE
//
// Splits an overstuffed wrap's ingredients into a vegan wrap
// and a non-vegan wrap.

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

// Constants
#define MAX_NAME 32

// Provided structs
struct ingredient {
    char name[MAX_NAME];
    bool is_vegan;
    struct ingredient *next;
};

struct wrap_split {
    struct ingredient *vegan;
    struct ingredient *non_vegan;
};

// Function prototypes
struct wrap_split *split_wrap(struct ingredient *wrap);
struct ingredient *read_wrap(void);
void print_wrap(char *label, struct ingredient *wrap);


// -----------------------------------------------------------------------------
//////////////// DO NOT CHANGE THE MAIN FUNCTION ///////////////////////////////

int main(void) {
    printf("Enter the ingredients in your wrap:\n");
    struct ingredient *wrap = read_wrap();

    struct wrap_split *split = split_wrap(wrap);

    printf("\n");
    print_wrap("Vegan wrap", split->vegan);
    print_wrap("Non-vegan wrap", split->non_vegan);

    return 0;
}

// -----------------------------------------------------------------------------
// YOUR FUNCTIONS
// -----------------------------------------------------------------------------

// Split the wrap's ingredients into a list of vegan ingredients and a
// list of non-vegan ingredients, preserving the original relative order
// of each. Return a malloced wrap_split struct holding both lists.
//
// No new ingredients are allocated: the existing nodes are relinked.
struct wrap_split *split_wrap(struct ingredient *wrap) {
    struct wrap_split *split = malloc(sizeof(struct wrap_split));
    split->vegan = NULL;
    split->non_vegan = NULL;

    struct ingredient *vegan_tail = NULL;
    struct ingredient *non_vegan_tail = NULL;

    struct ingredient *curr = wrap;
    while (curr != NULL) {
        // Save the next node before we overwrite curr->next.
        struct ingredient *next = curr->next;
        curr->next = NULL;

        if (curr->is_vegan) {
            if (vegan_tail == NULL) {
                split->vegan = curr;
            } else {
                vegan_tail->next = curr;
            }
            vegan_tail = curr;
        } else {
            if (non_vegan_tail == NULL) {
                split->non_vegan = curr;
            } else {
                non_vegan_tail->next = curr;
            }
            non_vegan_tail = curr;
        }

        curr = next;
    }

    return split;
}

// -----------------------------------------------------------------------------
// PROVIDED FUNCTIONS
// -----------------------------------------------------------------------------
// DO NOT CHANGE ANY OF THE CODE BELOW HERE

// Print a wrap's ingredients
void print_wrap(char *label, struct ingredient *wrap) {
    printf("%s: [", label);
    struct ingredient *n = wrap;
    while (n != NULL) {
        // If you're getting an error here,
        // you have returned an invalid list
        printf("%s", n->name);
        if (n->next != NULL) {
            printf(", ");
        }
        n = n->next;
    }
    printf("]\n");
}

// Read ingredients from stdin into a linked list
struct ingredient *read_wrap(void) {
    struct ingredient *head = NULL;
    struct ingredient *tail = NULL;
    char name[MAX_NAME];
    int vegan;

    while (scanf("%31s %d", name, &vegan) == 2) {
        struct ingredient *n = malloc(sizeof(struct ingredient));
        strcpy(n->name, name);
        n->is_vegan = vegan;
        n->next = NULL;

        if (head == NULL) {
            head = n;
        } else {
            tail->next = n;
        }
        tail = n;
    }

    return head;
}