Computational Problem $2$: Disaster Planning

Disasters$-$natural and unnatural$-$are inevitable, and cities need to be prepared to respond

to them. The problem is that stockpiling emergency resources can be really, really

expensive. As a result, it's reasonable to have only a few cities stockpile emergency

supplies, with the plan that they'd send those resources from wherever they're stockpiled

to where they're needed when an emergency happens. The challenge with doing this is to

figure out where to put resources so that $(1)$ we don't spend too much money stockpiling

fore than we need, and $(2)$ v

leave any cities too far away from emergency supplies.

Example from Western United States

Imagine that you have access to a country's major highway networks and know which cities

are are right down the highway from others. To the right is a fragment of the US Interstate

Highway System for the Western US$.$ Suppose we put emergency supplies in Sacramento,

Butte, Nogales, Las Vegas, and Barstow $($shown in gray$).$ In that case, if there's an

emergency in any city, that city either already has emergency supplies or is immediately

adjacent to a city that does. For example, any emergency in Nogales would be covered, since

Nogales already has emergency supplies. San Francisco could be covered by supplies from

Sacramento, Salt Lake City is covered by both Sacramento and Butte, and Barstow is

covered both by itself and by Las Vegas.

Although it's possible to drive from Sacramento to San Diego, for the purposes of this

problem the emergency supplies stockpiled in Sacramento wouldn't provide coverage to

San Diego, since they aren't immediately adjacent.

We'll say that a country is disaster$-$ready if every city either already has emergency supplies

or is immediately down the highway from a city that has them.

Your task is to write a function named can$\_$be$\_$disaster$\_$ready in the

supplies.py file.

def can$\_$be$\_$disaster$\_$ready$($road$\_$network: dict$[$str$,$ set$[$str$]],$ num$\_$cities: int,

supply$\_$locations: set$[$str$])->$ bool:

This function takes as input a dictionary representing the road network for a region

$($described below$)$ and the number of cities you can afford to put supplies in$,$ then returns

whether it's possible to make the region disaster$-$ready without placing supplies in more

than num$\_$cities cities. If so$,$ the function should then populate the argument

supply$\_$locations with all of the cities where supplies should be stored.

In this problem, the road network is represented as a dictionary where each key is a city

and each value is a set of cities that are immediately down the highway from them. For

example, here's a fragment of the map you'd get from the above transportation network:You can assume that supply$\_$locations is empty when this function is first called, and you can change it however you'd like if the function returns false.

You might be tempted to solve this problem by approaching it as a combinations problem. We need to choose some group of cities, and there's a limit to how many we can pick, so we could just list all combinations of num$\_$cities cities and see if any of them provide coverage to the entire network. The problem with this approach is that as the number of cities rises, the number of possible combinations can get way out of hand. For example, in a network with $35$ cities, there are $3,247,943,160$ possible combinations of $15$ cities to choose from. Searching over all of those options can take a very, very long time, and if you were to approach this problem this way, you'd likely find your program grinding to a crawl on many transportation grids.

To speed things up$,$ we'll need to be a bit more clever about how we approach this problem. There's a specific insight we'd like you to use that focuses the recursive search more intelligently and, therefore, reduces the overall search time.

Recursive Idea

Here's the idea. Suppose you pick some city that currently does not have disaster coverage. You're ultimately going to need to provide disaster coverage to that city, and there are only two possible ways to do it: you could stockpile supplies in that city itself, or you can stockpile supplies in one of its neighbors. For example, suppose city $x$ shown to the right isn't yet covered, and we want to provide coverage to it$.$ To do so$,$ we'd have to put supplies in either X itself or in one of A$,$ B$,$ C$,$ or D$.$ If we don't put supplies it at least one of these cities, there's no way $x$ will be covered.

With that in mind, use the following strategy to solve this problem. Pick an uncovered city, then try out each possible way of supplying that city $($either by stockpiling in that cityIn summary, here's what you need to do:

Write the docstring comment for the can$\_$be$\_$disaster$\_$ready function in

supplies.py$.$ Again, no need to write doctest examples.

Complete the pytest test functions in test$\_$supplies.py$.$

As before, a couple are already completed while the rest need