8.12

#### Lab 6: Working with Cyclic DataðŸ”—

Goals: The goals of this lab is are learn how to design and use circularly referential data.

Notes:

As announced last week, we are switching partners, and your new partner will start working with you on homework six. If you have not already, find someone you want to partner with (who is not your current partner!). Then please go to the handin server and request them as your teammate. We will accept most of the requests and randomize whoever is left at the end of lab.

This lab will be with your current partner; next lab will be with your new partner.

##### Movie costarsðŸ”—

As you all know, the Fundies Choice Awards are the most coveted awards in the world of Fundieswood. Coincidentally, they provide us a great opportunity to examine actors and their network of costars. We’ll simplify everything about acting and Fundieswood away, and simply claim that an actor is identified by their name and their list of other actors who were in movies with them. By definition, if one actor costarred in a movie with someone else, then that second actor costarred in the same movie with the first, so we immediately get cyclic data.

Your starter code for this problem is as follows. (NOTE: We’re using non-generic lists in the lab deliberately, so we can add whatever helper methods we need. Really, these lists are being used as part of a graph, and so they might deserve to have some special-purpose methods.)

 // represents a Actor with a user name and a list of costars class Actor { String username; ILoActor costars; Actor(String username) { this.username = username; this.costars = new MtLoActor(); } // Methods will be given below } // represents a list of Actor's costars interface ILoActor { } // represents a list of Actor's costars class ConsLoActor implements ILoActor { Actor first; ILoActor rest; ConsLoActor(Actor first, ILoActor rest) { this.first = first; this.rest = rest; } } // represents an empty list of Actor's costars class MtLoActor implements ILoActor { MtLoActor() {} }
• Before we can design any methods for the lists of costars, we need to be able to make examples of them.

We would like to make examples of the following filmography of actors from the 2021 Fundies Choice Awards:

If you happen to know of additional movies where these actors appear together, you can build larger examples as you so choose.

• Fundies starred Amal Ahmed, Ben Lerner, Margaryta Polishchuk, and Sam Lyon

• Fundies 2: Fun Harder starred Ben Lerner, Margaryta Polishchuk , Matt Guthrie, and Dylan Dinio

• Aoun’s Promised Land starred Joseph Aoun

• 21 Forsyth Street starred Ben Lerner, Matthias Felleisen, and Elizabeth Mynatt

• 2021: A Pandemic Odyssey starred Amal Ahmed and Ben Lerner

• Raiders of the Last Wollastons starred Dillon Scott, Matt Guthrie, and Matthias Felleisen

• Inception: Stack Overflow starred Joseph Aoun, Amal Ahmed, and Regan Murphy

• Java starred James Gosling

• Java 2: 2 hot 2 caffeinated starred James Gosling and Ben Lerner

Trying to make such examples directly, via simple variable declarations like Actor amy = ...; Actor tom = ...; will not work, for the same reason we couldn’t directly create Books and Authors that referred to each other. Where does the data break down?

• Design the method addCostar that modifies the actor’s costar list by adding the given actor to one actor’s costar list.

This method should be defined in the class Actor and have the following purpose/effect statement and header:

 // EFFECT: // Change this actor's costar list so that it includes the given actor void addCostar(Actor costar) {...}

Add any additional methods you may need to make sure you can represent the circle of costars given above.

Suppose that an actor wins a Fundies Choice Award, and wants to invite their costars to the afterparty to celebrate. This being Fundieswood, of course those guests will invite everyone they know as well, who will in turn invite their costars as well..., eventually inviting everyone that can be reached through this network of costars.

We call those on the actor’s costar list the direct costars and the others that will also be invited to the party the indirect costars. (Note: some people technically qualify as both direct and indirect costars; find an example of such a pair in the examples above.) We call the set of direct and indirect costars the extended costars of a actor.

Now we would like to ask some pretty common questions. For each question design the method that will find the answer. As always, follow the Design Recipe! The purpose/effect statements and the headers for the methods are already given:

• Does this actor have another actor as a direct costar?

 // Has this Actor costarred in a movie as that Actor? boolean hasDirectCostar(Actor that)
• How many direct costars do the two actors have in common?

 // returns the number of actors that are direct costars of both this and that actor int countCommonCostars(Actor that)
• Is there any movie connection between two actors?
 // Is there a chain of 1 or more movies such that this Actor costarred with someone, // who costarred with someone, ..., who eventually costarred with the given Actor? boolean hasExtendedCostar(Actor that)

• How many people will be at the party if everyone that this actor invites (directly or indirectly) show up?

 // If this Actor wins a Fundies Choice Award, and invites all their costars to celebrate, and they // invite all their costars, etc., how many people will show up to the party? int partyCount()

HINT: some of these methods will benefit greatly from designing a helper method first, that can be reused to help solve more than one of the questions above. You are encouraged to make a work-list for each problem, to figure out what the high-level steps are first, before diving into writing code without a plan.

Challenge: as everyone knows, the main purpose of examining costars is to play "Six degrees of Kevin Bacon". Design a new method to compute the length of the shortest path from one actor to another. (It’s a variant on hasExtendedCostar...)

##### Game of telephoneðŸ”—

Kids often played a game of telephone, where they sat in a circle and one person whispers a secret message to the next person, who whispers whatever they heard to the next person, and so on, until the last person in the circle announces whatever final message they received...which is often hilariously garbled from the original message.

Now that they’re older (and coincidentally all taking Fundies 2 together) they’ve decided to see how often they can “win” at the game, to see how likely they can convey a message without garbling. So:

• Each Person has a diction score, between 0 and 1, that represents how likely it is that a Person with perfect hearing will hear their whispered message correctly.

• Each Person has a hearing score, between 0 and 1, that represents how likely it is that they understand a Person with perfect diction.

The likelihood of person A being understood by person B is therefore the product of person A’s diction with person B’s hearing.

By the rules of the game, each Person will only ever whisper their message to their buddies. Your task is to compute the maximum likelihood that person X can convey a message correctly to person Y.

For example, let’s say:
• person A has 0.95 diction, and 0.8 hearing, and is buddies with B and C

• person B has 0.85 diction, and 0.99 hearing, and is buddies with D

• person C has 0.95 diction, and 0.9 hearing, and is buddies with D

• person D has 1.0 diction, and 0.95 hearing.

• no one is friends with person E

Then:
• The total likelihood of A getting a message to D by way of B is (0.95*0.99)*(0.85*0.95) = 0.759

• The total likelihood of A getting a message to D by way of C is (0.95*0.95)*(0.9*0.95) = 0.772

So the maximum likelihood is 0.772, by way of person C.

To begin with, you should not compute the actual path the message needs to take, but just produce the maximum likelihood that the message will be received correctly.

Once you have completed that method, you should design another that does produce the path of maximum likelihood.

##### DiscussionðŸ”—

The Fundieswood afterparty methods earlier, and the game of telephone problem above, form two common styles of problem encountered while processing cyclic graphs. The hint in the first problem suggests that there might be some common abstraction you might use to help solve those first tasks. The telephone problem has a similar feel. Brainstorm a little bit: if you had to compare the kinds of computation needed in these problems to a list-processing function, which would it be most like: map, foldr, foldl, filter...? Make some suggestions for what an appropriate abstraction might be for these graph-processing problems.