King Triton's Ocean

In this assignment, you will be implementing some unfinished Rust code which models a mythical ocean ecosystem populated by crabs that live on beaches, and various prey they hunt in reefs.

These crabs have names, and come in any and all colors. Groups of them live together (and reproduce) at beaches along the coast line. Once the sun sets, they head out to their favorite reefs to hunt for food that matches their tastes. Some crabs only eat fish, some only shellfish, while yet others are vegetarian.

Luckily, the reefs dotting this ocean are populated with plenty of prey that fit into each crab's dietary preferences. However, finding the right reef with the right food can prove a challenge.

It's a tough life for a crab out there.

Learning Goals

By the end of this assignment you should have gained some hands-on experience the basics of the Rust language, as well as some features peculiar to its ownership model.

• Functions
• Structs
• Methods
• Trait Objects
• Mutable vs Immutable References
• Smart Pointers
  • Single Ownership (Boxes)
  • Multiple Ownership (Reference-counted Boxes)

This assignment is not intended to be algorithmically challenging, but rather to be something of a guided tour through some of Rust's distinct characteristics. No individual task should be too complicated to implement, and almost all have corresponding tests you can use to check your progress as you work.

Instructions

If you are unsure about how to do something in Rust, you should probably first consult the Rust Book.

Submission

You should only modify and submit the following files:

• beach.rs
• color.rs
• crab.rs
• ocean.rs
• reef.rs

Any changes made to other files will be ignored by the autograder, which will always use the originals.

Running Tests

You can run all tests with cargo test, and all tests with a given prefix with cargo test <prefix>.

To make things easy, all of the tests in this assignment are named according to the following convention:

cargo test part${n}_${entity_name}_${tested_behavior}

For example, to run all tests that relate to Crab from Part 1, you can simply run:

cargo test part1_crab 

By default, cargo captures the console output of your code while running tests. However, while working on this assignment you might want to use print! or println! while running your tests to debug. You can do this by passing the --nocapture flag while running tests after --, which separates test names from flags.

For example, to run tests involving the crab hunting tasks in Part 2 while showing console output:

cargo test part2_crab_hunt -- --nocapture

You should read the tests carefully. They may serve as examples of unfamiliar syntax, and even provide some useful insights into how to implement some of the later tasks.

Writing Tests

You should not modify the contents of the tests/public.rs file.

However, you may find it useful to write your own tests in tests/student.rs.

These tests will be ignored by the autograder, so don't worry if they don't pass.

Part 1. Basic

We will first implement a simple model of a Crab, and then a Beach which contains zero or more crabs. In this manner, we demonstrate how to define and work with single objects as well as collections in Rust. We will also implement a function for breeding crabs.

For this part, you will not have to worry about lifetimes, and ownership should be straightforward: just simple borrows and dereferences as shown in lectures.

Tasks

Simple Functions and Methods

First, implement the missing bits in crab.rs and color.rs:

• color.rs
  • The cross function, which crosses two colors by performing wrapped arithmetic.
  • Refer to the specification in the function's doc string for more details. Note that Rust, being a "safe" language, handles arithmetic operations much more strictly than you may be used to, and the "obvious" solution here is not the correct one and will panic.
  • Documentation for Primitive Type u8
• crab.rs
  • A new function according to the given signature.
  • The name, speed, color and diet fields on Crab and corresponding accessor functions.

You should now have the following tests passing:

• part1_color_cross_no_panic
• part1_crab_new

Crabs & Braches

Then, implement the missing functions in beach.rs:

• A new function according to the given signature.
• size: returns the number of Crabs on the beach.
• add_crab: adds a Crab to the beach.
• get_crab: returns a reference to a Crab at the given index.
• get_fastest_crab: returns None if the beach is empty. Otherwise, return Some of a reference to the Crab with the highest speed.
• breed_crabs: uses the functions in diet and colors to breed two crabs, resulting in a new Crab.
  • You will want to add a new breed function to Crab to avoid exposing Crab implementation details.
  • The new Crab should have its diet selected randomly using the provided Diet::random_diet.
  • The new Crab should have its color computed by Color::cross from before.
  • The new Crab should have a speed of 1 (babies go slowly).
• find_crabs_by_name: returns a vector of references to crabs with the given name.

The tests for these functions are:

• part1_beach_add_get_crab
• part1_beach_iter_crabs
• part1_beach_size
• part1_beach_fastest_empty
• part1_beach_fastest_fastest_first
• part1_beach_fastest_fastest_second
• part1_crab_breeding
• part1_crab_find_by_name

Notes

• If you are accustomed to functional-style programming, you may find methods on std::slice::Iter useful or more natural to implement get_fastest_crab, find_crabs_by_name, and some functions in the next part.

Part 2. Advanced

While working on this section, you should consult some sections of the Rust Book for guidance and examples.

We will make use of trait objects to represent Prey that Crabs go out and hunt. Trait objects are often used in similar places to interfaces, abstract classes in other languages like Java, Go, and C++, though they differ in some ways. They allow us to refer to something which implements a given trait.

• 17.2 Trait Objects

We will also make use of smart pointers to heap allocations: both single-ownership Box<T>, and multiple-ownership (reference-counted) Rc<T>. The referents of smart pointers in Rust are immutable. Therefore, in order to represent a pointer to something mutable, we use Box<RefCell<T>> or Rc<RefCell<T>>. This is a common, but cumbersome, design pattern in Rust that results from some of the choices made in the design of the language.

• 15.1 Box<T>
• 15.4 Rc<T>
• 15.5 RefCell<T> and interior mutability

Things to Note in the Starter Code

In prey.rs note (but not modify) the definitions:

• pub trait Prey: defines the interface which all Prey must implement.
  • The diet method returns the kind of Diet this Prey is compatible with.
  • The try_escape method returns whether or not this Prey can escape from a given Crab, in a given Reef.
    • This method is side-effecting, and can therefore mutate the Prey it is called on, such as with the Shrimp.

In reef.rs, you should take note of a few facts:

• A VecDeque is Rust's standard library queue structure.
  • It can be used as a double-ended queue, but here we are only using it as a single-ended queue.
• We had to declare the prey field of struct Reef using the dyn keyword.
  • However, VecDeque<dyn Prey> would not work, because the size in memory of dyn Prey is not known at compile time. Therefore, we use Box<dyn Prey>, which represents a pointer to something implementing Prey on the heap.

Tasks

Lifetimes with Recipes

First, let's look at a simple example of where explicit lifetime annotations are needed. It turns out that our crabs like to cook their food before they eat it (this is a mythical ocean, remember?). In crab.rs implement:

• choose_recipe: returns a recipe from the Cookbook that matches the Crab's diet.
  • This is the only case in this assignment where you will need to modify the signature of a method.
  • You should only add lifetime annotations.

Implementing Reefs

Next, let's implement the missing methods on reef.rs. A Reef is a wrapper around a queue of Box<dyn Prey>. We use a queue here as we will later have a Crab take Prey from the Reef, and potentially put it back. Using a queue removes the need to keep track of indices and supports both fast insertion and removal at the ends.

• new
• add_prey: push prey to the back of the reef.
• take_prey: pop prey from the front of the reef.

At this point the test part2_reef_add_take_prey should pass.

Next, add a reefs field to struct Crab with an appropriate type. Consult discover_reef for some ideas. Note that multiple crabs can share the same Reef, and both can mutate it. We represent a reference-counter/multiply-owned pointer with Rc, and a cell containing a mutable reference with RefCell. Put together: Rc<RefCell<Reef>>.

Then, in crab.rs, implement:

• discover_reef: add a reef to a Crab's list of reefs.
  • There is no corresponding forget_reef, but you are welcome to add one if it helps you write your own tests. We will ignore it.

At this point the test part2_crab_discover_reefs should pass.

Catching Prey and Going Hunting

Crabs in this ocean hunt in a very particular way. They are greedy, but they will never try to catch the same prey twice. In this manner, they avoid getting stuck chasing the same uncatchable prey all day long. When a Crab catches Box<dyn Prey>, it removes it from the reef, since a Box can only have one owner.

• catch_prey: catch some Prey from one of the Crab's reefs and return Some of it and the index of the Reef it came from, or None if none can be found.
  • Consult the docstring for specific details.
  • In order to call take_prey on one of the Reefs stored in a Rc<RefCell<Reef>>, you will need to borrow mutably from it.
    • Consult the documentation and relevant Rust book chapter to figure out which method to use.
    • You may also find it helpful to look at some of the tests.
• release_prey: release Prey back into the Reef at the given index.
• hunt: implements the hunting behavior of the crab.
  • Consult the docstring for full pseudocode for this method, as it is a bit more involved than any so far.

Note that the latter of these two methods are not public. They are implementation details, and helper functions to implement hunt.

You should now have the following tests passing:

• part2_crab_hunt_empty_reef
• part2_crab_hunt_escaped_prey
• part2_crab_hunt_incompatible
• part2_crab_hunt_success

The Ocean Itself

So far, you've been tasked with using smart pointers from the callee side. That is, you have always received them from elsewhere, but have not had to construct them or in the case of Rc take additional references to them yourself using Rc::clone.

We will now define Ocean, which provides an interface to many of the definitions implemented so far.

First, in ocean.rs, add appropriate struct fields to back the beaches and reefs accessors. Then, implement the missing methods:

• new
• add_beach: adds a beach to this Ocean
• beaches: returns an iterator over this Ocean's beaches.
• reefs: returns an iterator over this Ocean's reefs.
• generate_reef: generates a reef with the number of each type of prey specified in the arguments, adds a reference to it to this Ocean's reefs, and returns a reference.
  • This will require creating both kinds of smart pointers used so far (Box, Rc) as well as RefCell.
  • Note that you will need to get a second reference to an Rc here as well, since you need one to add to reefs, and one to return.

Tip: start by considering Algae only, getting part2_ocean_generate_algae_only passing.

You should now have the following tests passing:

• part2_ocean_generate_algae_only
• part2_ocean_generate_algae_bountiful

Clan Competitions

The crabs in King Triton's Ocean like to socialize by forming different clans and competing among themselves. Using the clan system, the crabs can join a clan and engage in the competition. Multiple crabs can belong to the same clan, but a crab cannot join more than one clan. Every beach has a clan system in place.

Your task is to extend the existing model for beaches and clans. Note: Every clan has a unique clan id, and for the purposes of this task, every crab will have a unique name.

In clans.rs , add appropriate fields, add a new method, and complete the following methods with the given signatures:

• get_clan_member_names: returns a list of the member names for the given clan id.
• get_clan_count: returns the number of clans currently in existence.
• get_clan_member_count: returns the number of members for the given clan id.
• get_largest_clan_id: returns the id of the clan with the most number of crabs, or None if such a clan does not exist.

In beach.rs, add a field for the ClanSystem, update existing methods where necessary and complete the following methods with the given signatures:

• get_clan_system: returns a reference to the clan system associated with the beach.
• add_member_to_clan: adds a crab that lives on the beach as a member for the given clan id and crab name. If a clan with this id does not exist, create one. You may define and call a method in clans.rs to perform this operation.
• get_winner_clan: returns the id of the clan that wins the competition given two clan ids and returns a Result type. The winner is decided based on the average speed of the clan members. Return None if there are no clear winners between two different existing clans. If the inputs are invalid, return an Err string.

You should now have the following tests passing:

• part3_clans_get_clan_member_names_zero
• part3_clans_get_clan_member_names
• part3_clans_get_clan_member_count_first
• part3_clans_get_clan_member_count_all
• part3_clans_get_clan_count_zero
• part3_clans_get_clan_count_all
• part3_clans_get_largest_clan_id_empty_beach
• part3_clans_get_largest_clan_id_first
• part3_clans_get_largest_clan_id_second
• part3_beach_get_winner_clan_empty_beach
• part3_beach_get_winner_clan_tie
• part3_beach_get_winner_clan

Submitting your Work

That's it! You're done!

You should double check your tests all pass by ensuring all files have been saved and then running cargo clean and cargo test.

You should submit the following files to Gradescope:

• beach.rs
• color.rs
• crab.rs
• ocean.rs
• reef.rs
• clans.rs