Week 02 Weekly Exercises

Objectives

To practice using Rust's basic collection tyoes
Exposure to simple derive macros
Understand and use Rust's error handling philosopy, and the try trait

Activities To Be Completed

The following is a list of all the markedactivities available to complete this week...

Tribonacci
To Upper (Investigating strings!)
Collections
Data analysis

The following practice activities are optional and are not marked, or required to be completed for the week.

None - all exercises this week are marked.

Preparation

Before attempting the weekly exercises you should re-read the relevant lecture slides and their accompanying examples.

Getting Started

Create a new directory for this week's exercises called lab02, change to this directory, and fetch the provided code for this week by running these commands:

mkdir lab02
cd lab02
6991 fetch lab 02

Or, if you're not working on CSE, you can download the provided code as a tar file.

Exercise:
Tribonacci

In this task, you will write a function that computes a variable number of Tribonacci numbers , and also their sum.

Your program should read a single positive integer, n, from the command-line arguments, and subsequently compute the first n Tribonacci numbers, along with their sum.

If no command-line arguments are given, assume the value of n is assumed to be 10.

Invalid input (i.e. negative enumbers, or non-valid numbers) should be handled by returning a custom error message "Please enter a valid size!" (this is in the error_msg parameter of the compute_tribonacci function), through the struct TribonacciError, and then subsequently exiting the program.

Your program need only be able to calculate from n = 3 to n = 145 inclusive. We will not use positive integers outside of this range. Note that n = 145 produces very large numbers that increase far past the width of a i64 type. You may want to (strongly) consider using one of i128 or u128 instead, both of which can fit the largest number in that sequence.

You need only change the compute_tribonacci function.

6991 cargo run -- 4
    Finished dev [unoptimized + debuginfo] target(s) in 0.00s
     Running `target/debug/tribonacci 4`
Values: [1, 1, 1, 3]

Sum: 6
6991 cargo run -- 10
    Finished dev [unoptimized + debuginfo] target(s) in 0.00s
     Running `target/debug/tribonacci 10`
Values: [1, 1, 1, 3, 5, 9, 17, 31, 57, 105]

Sum: 230
6991 cargo run -- -1
    Finished dev [unoptimized + debuginfo] target(s) in 0.00s
     Running `target/debug/tribonacci -1`
Error: Please enter a valid size

Click to reveal further hint

You can approach this by storing all intermediate values into a vector, where all values should be of type i128 or u128. The vector's initial values should be [1, 1, 1].

i.e. z

let mut values: Vec<u128> = vec![1, 1, 1]

You may find the below documentation, especially the examples, particularly helpful:

The documentation for the args function may be useful.

The documentation for the vec type may be useful.

The documentation for the result type may be useful.

The documentation for the parse method may be useful.

The documentation for the map method may be useful.

The documentation for the map_err method may be useful.

The documentation for the sum method may be useful.

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

6991 autotest

When you are finished working on this exercise, you must submit your work by running give:

6991 give-crate

The due date for this exercise is Week 3 Wednesday 21:00:00.

Note that this is an individual exercise; the work you submit with give must be entirely your own.

main.rs

use std::env;
use std::num::ParseIntError;

#[derive(Debug)]
struct TribonacciError(String);

fn main() {
    let args: Vec<String> = env::args().collect();
    let error_message = String::from("Please enter a valid size");
    
    let n = match args.get(1) {
        Some(s) => s.parse::<usize>(),
        None => Ok(10),
    };

    if let Err(e) = compute_tribonacci(n, error_message) {
        println!("Error: {}", e.0)
    }
}

/// Computes the tribonacci sequence of a given size
/// Prints the sequence, and its sum
fn compute_tribonacci(size: Result<usize, ParseIntError>, error_msg: String) -> Result<(), TribonacciError> {
    let mut tribonacci = vec![1_u128; 3];
    let size = size.map_err(|_| TribonacciError(error_msg))?;

    for i in 3..size {
        tribonacci.push(tribonacci[i - 1] + tribonacci[i - 2] + tribonacci[i - 3]);
    }

    println!("Values: {:?}", tribonacci);
    
    let value: u128 = tribonacci.into_iter().sum();
    println!("\nSum: {}", value);
    
    Ok(())
}

Exercise:
To Upper (Investigating strings!)

This activity is an investigation of Rust's strings!

You have been provided a simple crate, to_upper, which does not compile! Your task is to modify to_upper/src/main.rs so that it takes in a single command-line argument and converts the appropriate characters to uppercase. It may help to RTFC!

You will always be given valid input (e.g. no empty arguments).

6991 cargo run -- 'hello world!!!'
    Finished dev [unoptimized + debuginfo] target(s) in 0.00s
     Running `target/debug/to_upper 'hello world'\!''\!''\!''`
arg = hello world!!!
upp = HELLO WORLD!!!
6991 cargo run -- "uwu🥺👉👈"
    Finished dev [unoptimized + debuginfo] target(s) in 0.00s
     Running `target/debug/to_upper 'uwu🥺👉👈'`
arg = uwu🥺👉👈
upp = UWU🥺👉👈

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

6991 autotest

When you are finished working on this exercise, you must submit your work by running give:

6991 give-crate

The due date for this exercise is Week 3 Wednesday 21:00:00.

Note that this is an individual exercise; the work you submit with give must be entirely your own.

main.rs

fn main() {
    // try and get the first argument
    // using some iterator methods
    let arg = std::env::args().nth(1).unwrap();

    // the compiler suggests to "borrow here"
    // but we haven't learnt how to borrow :(
    // we have a String type, and want to get a &str
    // Try find a function that can help us using
    // the docs https://doc.rust-lang.org/stable/std/string/struct.String.html
    let upp = uppercase(arg.as_str());

    println!("arg = {}", arg);
    println!("upp = {}", upp);
}

fn uppercase(src: &str) -> String {
    let mut destination = String::new();

    for c in src.chars() {
        // this doesn't work either!!
        // what type does to_uppercase return?
        // what type does push expect?
        for c in c.to_uppercase() {
            destination.push(c);
        }
    }

    destination
}

Exercise:
Collections

Rust's collection types could be generally categorised into four groups:

Sequences
- Vec
- VecDeque
- LinkedList
Maps
- HashMap
- BTreeMap
Sets
- HashSet
- BTreeSet
Misc.
- BinaryHeap

In this activity, we'll be exploring the performance of first three (Vec, VecDeque, and LinkedList), and HashMap collections.

For each of the four collections above, your code should:

Create a new instance of the collection.
Add some MAX_ITER elements to it.
Remove MAX_ITER elements from it.
Time each of the above operations.

For LinkedList insertion, you should insert at the end of the list. You should remove from the start of the list.

For HashMap you only need to insert at key i where i is the current iteration. Similarly, you should remove from key i.

Before you start, please write down some of your expectations about what you think will be the most performant collection for these operations.

The analysis of Vec and VecDeque has already been completed for you in the provided code.

This exercise also contains a theory section. At the end of your main function, you should write a comment that answers the following questions:

Which collection type was the fastest for adding and removing elements?
- Why do you think this was the case?
Is there any significant difference between Vec and VecDeque deletion?
- If so, why? If not, why not?
When would you consider using VecDeque over Vec?
When would you consider using LinkedList over Vec?
Did the results suprise you? Why or why not?.

The above will be manually marked. There will be an opportunity to discuss this with a tutor and get marked during your week 4 workshop. If you cannot attend, your work will instead be manually marked (offline) during week 5.

When you are finished working on this exercise, you must submit your work by running give:

6991 give-crate

The due date for this exercise is Week 3 Wednesday 21:00:00.

Note that this is an individual exercise; the work you submit with give must be entirely your own.

main.rs

use std::collections::{HashMap, LinkedList, VecDeque};

const MAX_ITER: i32 = 300000;

fn main() {
    // Vectors
    vec_operations();

    // VecDeque
    vec_deque_operations();

    // LinkedList
    linked_list_operations();

    // HashMap
    hashmap_operations();

    // TODO: your text answers to the questions in the spec
}

/// measure the insertion and removal
/// operations of a vector
fn vec_operations() {
    let mut vec = Vec::new();

    let time_start = std::time::Instant::now();
    for i in 0..MAX_ITER {
        vec.push(i);
    }
    let time_end = std::time::Instant::now();

    println!("==== Vector ====");
    println!("insert: {:?}", time_end - time_start);

    let time_start = std::time::Instant::now();
    for _ in 0..MAX_ITER {
        vec.remove(0);
    }
    let time_end = std::time::Instant::now();

    println!("remove: {:?}", time_end - time_start);
}

/// measure the insertion and removal
/// operations of a VecDeque
fn vec_deque_operations() {
    let mut vec_deque = VecDeque::new();

    let time_start = std::time::Instant::now();
    for i in 0..MAX_ITER {
        vec_deque.push_back(i);
    }
    let time_end = std::time::Instant::now();

    println!("==== VecDeque ====");
    println!("insert: {:?}", time_end - time_start);

    let time_start = std::time::Instant::now();
    for _ in 0..MAX_ITER {
        vec_deque.pop_front();
    }
    let time_end = std::time::Instant::now();

    println!("remove: {:?}", time_end - time_start);
}

// measure the insertion and removal
// operations for a linked list
fn linked_list_operations() {
    let mut linked_list = LinkedList::new();

    let time_start = std::time::Instant::now();
    for i in 0..MAX_ITER {
        linked_list.push_back(i);
    }
    let time_end = std::time::Instant::now();

    println!("==== LinkedList ====");
    println!("insert: {:?}", time_end - time_start);

    let time_start = std::time::Instant::now();
    for _ in 0..MAX_ITER {
        linked_list.pop_front();
    }
    let time_end = std::time::Instant::now();

    println!("remove: {:?}", time_end - time_start);
}

// measure the insertion and removal
// operations for a hashmap
fn hashmap_operations() {
    let mut hashmap = HashMap::new();

    let time_start = std::time::Instant::now();
    for i in 0..MAX_ITER {
        hashmap.insert(i, i);
    }
    let time_end = std::time::Instant::now();

    println!("==== HashMap ====");
    println!("insert: {:?}", time_end - time_start);

    let time_start = std::time::Instant::now();
    for i in 0..MAX_ITER {
        hashmap.remove(&i);
    }
    let time_end = std::time::Instant::now();

    println!("remove: {:?}", time_end - time_start);
}

Exercise:
Data analysis

In this exercise, you are taking on the role of a prospective data analyst and have gotten your hands on a dataset of (fictional!) CSE enrolments.

The dataset is in the file enrolments.psv and each row contains the following columns (in order):

UNSW Course Code
UNSW Student Number
Name
UNSW Program
UNSW Plan
WAM
UNSW Session
Birthdate
Sex

Each row of data represents one enrolment. One student may have multiple rows, as they may be enrolled in multiple courses.

You've been asked to process the data, and output answers to the following questions:

How many unique students are there?
What is the most common course (with how many students)?
What is the least common course (with how many students)?
What is the average WAM of all students in the file(to 2 decimal places)?

Note that you can assume that there will be no two equally most-common or equally least-common courses in the dataset -- i.e. there will always be exactly one answer.

You can also assume there will always be a term provided, but think about how you would model it if not!

The contents of the enrollments.psv used for your program will change in marking

 6991 cargo run 
    Finished dev [unoptimized + debuginfo] target(s) in 0.01s
     Running `target/debug/data_analysis`
Number of students: 8065
Most common course: COMP1511 with 953 students
Least common course: BIOM9002 with 1 students
Average WAM: 61.94

Authors Note

This exercise may take a while to complete. If you get stuck, ask on the course forum!

But, this exercise was designed to mimic a real-world data analysis task.

Attempting the task will enable you to try:

How to read and process data from a file,
How to use serde, a library for serializing and deserializing data,
How to use HashMaps to count things,
How to use iterators to perform aggregations, filtering and transformations,

But more importantly, it's one of the first larger exercises that you'll complete in Rust, and gives you a good taste for the scope of tasks that you can accomplish with only two weeks of Rust experience.

There's no starter code for this, that is intentional! You have full control over how you want to structure, and design your program.

If you get stuck, please ask and discuss with your peers/staff on the course forum - we are happy for collaboration on weekly exercises!!

This is quite a lot for one exercise - but just do your best! You'll get there!

This is a substantial exercise, break it down into steps! Try and avoid for-loops, and practice using iterator functions.

It is expected that you use serde for this exercise to deserialize into structs.
The documentation for the serde crate may be useful.

Click to reveal further hint

Remember, when you are iterating over something (e.g x) that x.into_iter() can sometimes move x (or in other words, "consume" x such that it cannot be used again later). You may need to either clone the data, or preferably use x.iter() instead. If you get stuck, ask on the course forum!

The documentation for the csv crate may be useful.

Click to reveal further hint

Particularly, the ReaderBuilder struct, which will allow you to:

Specify the delimiter (pipe symbol),
Specify the headers (or alternatively that there are no headers),
Specify the path of the file.

Reading CSV into Structs resources

You may also find the following posts useful for reading PSV files into structs:

The seek method may be useful to reset the reader to the start.

Click to reveal further hint

You will need to enable the derive feature for the serde crate in your Cargo.toml such that your dependency looks like:
serde = { version = "1.0", features = ["derive"] }
This will allow you to use a derive macro for the csv crate to automatically generate the code to deserialize the CSV file into a struct.

The documentation for the HashMap type may be useful.

The documentation for the entry method may be useful. The example is of particular note.

The documentation for the max_by_key method may be useful. Similarly, min_by_key is also useful.

The documentation for the sum method may be useful. This is useful for calculating the average.

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

6991 autotest

When you are finished working on this exercise, you must submit your work by running give:

6991 give-crate

The due date for this exercise is Week 3 Wednesday 21:00:00.

Note that this is an individual exercise; the work you submit with give must be entirely your own.

main.rs

use csv::{Position, ReaderBuilder};
use serde::Deserialize;
use std::collections::HashMap;
use std::io::{self, Write};

#[derive(Deserialize, Debug)]
struct Student {
    course_code: String,
    zid: String,
    name: String,
    program: String,
    plan: String,
    wam: f64,
    session: String,
    birthdate: String,
    sex: String,
}

fn main() {
    // parse each line of input into a student struct
    // add each student to a hashmap, with the zid as a key
    // open the file enrollments.csv
    let mut rdr = ReaderBuilder::new()
        .delimiter(b'|')
        .has_headers(false)
        .from_path("enrolments.psv")
        .unwrap();

    // create hashmap
    let mut students: HashMap<String, Student> = HashMap::new();

    // iterate over each record, parse it, and add to hashmap
    rdr.deserialize().for_each(|result| {
        let student: Student = result.unwrap();
        students.insert(student.zid.clone(), student);
    });

    // print out the number of students
    println!("Number of students: {}", students.len());

    // find the most common course:
    // create a hashmap to store the number of students in each course
    let mut course_counts: HashMap<String, u32> = HashMap::new();
    rdr.seek(Position::new()).unwrap();
    rdr.deserialize().for_each(|student| {
        let student: Student = student.unwrap();
        // get the current count for the course
        course_counts
            .entry(student.course_code)
            .and_modify(|e| *e += 1)
            .or_insert(1);
    });

    // find the course with the highest count
    let (course, count) = course_counts
        .iter()
        .max_by_key(|(_, count)| *count)
        .unwrap();

    println!("Most common course: {} with {} students", course, count);

    // find the least common course:
    // find the course with the lowest course
    let (course, count) = course_counts
        .iter()
        .min_by_key(|(_, count)| *count)
        .unwrap();
    println!("Least common course: {} with {} students", course, count);

    // find the average wam
    let total_wam = students.values().map(|student| student.wam).sum::<f64>();
    let average_wam = total_wam / students.len() as f64;

    println!("Average WAM: {:.02}", average_wam);
}

Submission

When you are finished each exercise make sure you submit your work by running give.

You can run give multiple times.

Don't submit any exercises you haven't attempted.

If you are working at home, you may find it more convenient to upload your work via give's web interface.

The due date for this week's exercises is Week 3 Wednesday 21:00:00.

You cannot obtain marks by e-mailing your code to tutors or lecturers.

Automarking will be run continuously throughout the term, using test cases different to those autotest runs for you. (Hint: do your own testing as well as running autotest.)

After automarking is run you can view your results here or by running this command on a CSE machine:

6991 classrun -sturec