COMP1511 Week 10 Tutorial Sample Answers

Your tutor has asked a lab pair to present their week 8 work.
Discuss the good, the bad and the ugly aspects of their code.
Please be gentle in any criticism - we are all learning!
Who is your new lab partner?
Did you blog last week? What is this week's blogging theme?
Consider a Trader Bot world with these 5 locations and a game lasting 4 turns:

Name Type Commodity Quantity Price
CSE Start
Royal Australian Mint Buyer Gold 2 40000
BHP Seller Gold 8 30000
Caltex Petrol station Fuel 684 215
Dump Dump
Assume there is a single bot named Deckard who starts the game with $100000 and 48 fuel. Also assume Deckard has a maximum cargo weight of 70 and a maximum cargo volume of 90. And that the Gold commodity has weight 20 and volume 10.
Deckard makes these actions in the 4 turns the game lasts.
1. Move 2
2. Buy 6
3. Move -1
4. Sell 6
List all the changes which occur in the Trader Bot world each turn
Note, that the player requests to buy and sell more than is possible. There is no penalty for doing this.
1. Move 2
  - Deckard's location will change from CSE to BHP.
  - Deckard's fuel will change from 48 to 46.
2. Buy 6
  - 3 bars of gold will be placed in Deckard's cargo.
  - Deckard's cash will change from $100000 to $10000
  - The amount of Gold BHP has to sell will change from 8 to 5
3. Move -1
  - Deckard's location will change from the BHP to Royal Australian Mint.
  - Deckard's fuel will change from 46 to 45.
4. Sell 6
  - Deckard's cargo will change from 3 bars of Gold to 1 bar of Gold
  - Deckard's cash will change from $10000 to $90000
  - The amount of Gold Royal Australian Mint is willing to buy will change from 2 to 0

Name	Type	Commodity	Quantity	Price
CSE	Start
Royal Australian Mint	Buyer	Gold	2	40000
BHP	Seller	Gold	8	30000
Caltex	Petrol station	Fuel	684	215
Dump	Dump

Write a C function with this prototype:

int cargo_mars_bars(struct bot *b)

which given a pointer to a bot returns how many Mars Bars the bot's cargo contains.

Sample solution for cargo_mars_bars.c

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

// return how many "Mars Bars" the bot's cargo contains

int cargo_mars_bars(struct bot *b) {
    for (struct cargo *c = b->cargo; c != NULL; c = c->next) {
        if (strcmp("Mars Bars", c->commodity->name) == 0) {
            // A commodity  occur at most once in the cargo list
            return c->quantity;
        }
    }
    return 0;
}

Write a C function with this prototype:

int mars_bars_for_sale(struct bot *b)

which given a pointer to a bot returns how Mars Bars are for sale at the bot's current location

Sample solution for mars_bars_for_sale.c

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

// return how many "Mars Bars" for sale at the current location

int mars_bars_for_sale(struct bot *b) {
    struct location * l = b->location;

    if (l->type == LOCATION_SELLER && strcmp("Mars Bars", l->commodity->name) == 0) {
        return l->quantity;
    } else {
        return 0;
    }
}

How do the struct used to represent locations in the Trader Bot world differ from the linked lists you've seen in lectures?
There are doubly-linked (next & previous) pointers
They form a circular list.
What is tricky about circular lists ?
Discussed in tut.
How can the lab exercise help with the assignment ?
Discussed in tut.
C's sizeof operator is a prefix unary operator (precedes its 1 operand) - what are examples of other C unary operators?
++, -- are commonly used unary operators and they can be prefix or postfix (with different semantics).
Why is C's sizeof operator different to other C unary & binary operators?
sizeof can be given a variable, value or a type as argument. The syntax to distinguish this is weird, the type is surrounded by brackets
Discuss errors in this code:
```
    struct node *a, *b, *c, *d;
    a = NULL:
    b = malloc(sizeof b);
    c = malloc(sizeof struct node);
    d = malloc(8);
    c = a;
    d.data = 42;
    c->data = 42;
```
sizeof b should be sizeof *b
sizeof struct node should be sizeof (struct node)
malloc(8) is actually correct on CSE systems but is non-portable, e.g. on a 64-bit OS sizeof (struct node) == 12 (or maybe 16)
d.data is incorrect as d is not a struct its a pointer to a struct
c->data is illegal as c will be NULL when its executed
The function member tests if a specified value is a found in a specified list, i.e. the function should return 1 if the value occurs in the list 0 otherwise. It has this prototype:
```
int member(int value, struct node *list);
```
Implement this function both iteratively (using a while/for loop) and recursively.
Recursive:
```
int
member(int value, struct node *list) {
    return list != NULL && (list->data == value || member(value, list->next));
}
```
Iterative:
```
// return true iff value occurs in list

int
member(int value, struct node *list) {
    struct node *n;
    for (n = list; n != NULL; n = n->next)
        if (n->data == value)
            return 1;
    return 0;
}
```
Revision questions
The remaining tutorial questions are primarily intended for revision - either this week or later in session.
Your tutor may still choose to cover some of the questions time permitting.

Implement a function list_append which appends its first argument to its second. It should have this prototype:

struct node *list_append(struct node *list1, struct node *list2);

It should not create (malloc) any new list elements. It should just change the appropriate next field in the first list.

struct node *list_append(struct node *list1, struct node *list2) {
    struct node *n;
    if (list1 == NULL) {
        return list2;
    }
    n = list1;
    while (n->next != NULL) {
        n = n->next;
    }
    n->next = list2;
    return list1;
}

What does this code print

    int i;
    struct node *a[100];
    struct node *b = malloc(sizeof (struct node));
    b->data = 0;
    for (i = 0; i < 100; i = i + 1) {
        a[i] = b;
    }
    for (i = 0; i < 100; i = i + 1) {
        a[i]->data++;
    }
    printf("%d %d\n", a[0]->data, a[99]->data);

100 100

Name one advantage and one disadvantage of using a linked list compared to an array. Also state an example of when you would use an array over a linked list.

        There are several correct answers for this but some common ones are:
        You do not need to know the size of a linked list upfront; It is easier to remove the first element of a list.

        A disadvantage might be that you do not get random access. Random access means you can directly go to any element in the array.
        In contrast, you will need to step through all the nodes before to get to the 20th element in a linked list.

Revision questions