Description

Question 1: Bark Park

Somewhere in Mississauga in the year 2050, there’s an off-leash dog park. Everyone likes to take their furry friends on a sunny Saturday morning, but there’s a hitch: not all of the dogs get along. In fact, some dogs are actively beefing with other dogs.

The park’s gatekeeper doesn’t tolerate beef. Endowed with encyclopædic knowledge of the dogs’ names and relationships, she’s quick to shut out any that are going to cause trouble. She has a simple rule: first come, first serve. If you show up with your dog and one of his enemies is already in the park, you can’t go in.

For example, say there are three dog owners on their way to the park with their dogs Rufus, Grimm, and Dogbert. Rufus has beef with Dogbert and Grimm, so he can’t be in there with either of them. There are a few possibilities for who ends up in the park:

1. Dogbert & Grimm — if these two are in the park, Rufus can’t join them.
2. Rufus alone — if he’s in the park, Dogbert and Grimm are out of luck.

But that’s not all. Some dog owners might decide to stay home. So there are a few more possibilities:

3. Dogbert alone; the others don’t come.
4. Grimm alone.
5. Nobody comes. Maybe it’s raining.

So for this case of 3 dogs and 2 beefs, there are 5 possible outcomes: the desired answer for this input. You’re going to write a solution that counts the outcomes for any given list of dogs and their beefs.

Your task is to write function solve in barkpark.py. Do not modify any of the existing code. You’re encouraged to use helper functions here.

Recursion

Note that you must solve this problem recursively, or you will lose the majority of the marks. As a reminder, recursion is when an algorithm contains itself as one of its steps. A recursive solution to a problem depends on solving instances of the same problem.

Here’s an example of a non-recursive algorithm:

# Non-recursive algorithm
def work(i: int, n: int) -> int:
    while i > 0:
        n += n
        i -= 1
    return n

print(work(10, 1))

Compare it with this recursive version of the same task:

# Recursive algorithm
def work(i: int, n: int) -> int:
if i == 0:
    return n
else:
    return work(i - 1, n + n)

print(work(10, 1))

This simple example doesn’t go very far in demonstrating the power of recursion, but you will soon discover how useful it can be as you work on this exercise.

Sample tests

For this question, we’ve provided two sample tests in test_barkpark.py. We encourage you to add more.

The first is a test with two dogs (Alma and Friede) that have one beef between them. Intuitively, you might think there are no good parks. But there are 3: Alma’s there alone; Friede’s there alone; or no one’s there. The only park that’s ruled out is one where they’re both there.

The second test is the one we worked through above, so you can run it on your code to make sure you’ve got at least that far.

Of course, don’t forget to test for larger cases and interesting edge cases. We’ll be doing so!

Question 2: Zingaro Hockey League

In Toronto’s Zingaro Hockey League (ZHL) in the year 2050, teams are named using integers from 1 to n. (It’s a very boring league, a reflection of the streamlined future of statistics-driven sports.)

During the season, every team plays every other team exactly once. For example, if there are 5 teams, then there are 10 games played: team 1 vs. 2, team 1 vs. 3, team 1 vs. 4, team 1 vs. 5, team 2 vs. 3, team 2 vs. 4, team 2 vs. 5, team 3 vs. 4, team 3 vs. 5, and team 4 vs. 5.

Every game has one of three outcomes: the first team wins, the first team loses (that is, the second team wins), or the game is a tie. A team is awarded 3 points for each game that they win and 1 point for each game that they tie. (A team doesn’t get any points for a game that they lose.) For example, if team 1 wins against team 2, team 1 and team 3 tie, and team 2 loses against team 3, then team 1 will have a total of 4 points, team 2 will have a total of 0 points, and team 3 will have a total of 4 points.

Some games in the season have already been played, and you know the outcome of each of those games.
For the games that haven’t been played yet, you don’t know what their outcome will be.

Consider all of the possible outcomes for the games that haven’t been played yet. Your task is to determine the number of those outcomes in which a specified team t will have strictly more points than each other team.

Your task is to write function solve in hockey.py. Again, do not modify any of the existing code. You’re encouraged to use helper functions here, too.

For this problem, too, your solution must use recursion to get most of the marks.

Sample tests

For this question, too, we’ve provided two sample test cases in file test_hockey.py. We encourage you to add more.

The first test shows what happens when three teams have played all of their games: team 1 has played team 2, team 1 has played team 3, and team 2 has played team 3. There are no games left, and therefore only one outcome to consider: the outcome of the three games that have been played. The test case asks about team 1. Team 1 has more points than team 2 and has more points than team 3, so the correct return value is 1. (If team 1 didn’t have more points than team 2 or didn’t have more points than team 3, the correct return value would have been 0.)

The second test is of five teams where some games (8 of the 10) have already been played. Here is the state after these games have been played:

There are two games remaining to be played: team 1 vs. team 2, and team 2 vs. team 5. There are six outcomes to these games, because there are two games and three outcomes for each game. But of these six outcomes, only 2 of them result in team 3 having strictly more points than the other teams. It’s a good exercise to work through which 2 outcomes these are!

Reminders

• Please don’t change what you have been given in the starter code. If you do, then our correctness tests on your code will not work correctly.

  • In particular, for the code we’ve given you, do not add or remove any parameters, change any parameters or return types, or change any type annotations.

• Please don’t add additional import statements.

• You can and should add helper functions to keep your code organized.