Programming Fundamentals

• This page contains additional revision exercises for week 10.
• These exercises are not compulsory, nor do they provide any marks in the course.
• You cannot submit any of these exercises, however autotests may be available for some them (Command included at bottom of each exercise if applicable).

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

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

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

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

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

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

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

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