hw3.cpp

/*
 * File: UniversalHealthCoverage.cpp
 * ----------------------
 * Name: robertdo
 * Section: mmateen
 * This file is the starter project for the UniversalHealthCoverage problem
 * on Assignment #3.
 */
#include <iostream>
#include <string>
#include "set.h"
#include "vector.h"
#include "console.h"
#include "foreach.h"
using namespace std;

/* Function: canOfferUniversalCoverage(Set<string>& cities,
 *                                     Vector< Set<string> >& locations,
 *                                     int numHospitals,
 *                                     Vector< Set<string> >& result);
 * Usage: if (canOfferUniversalCoverage(cities, locations, 4, result)
 * ==================================================================
 * Given a set of cities, a list of what cities various hospitals can
 * cover, and a number of hospitals, returns whether or not it's
 * possible to provide coverage to all cities with the given number of
 * hospitals.  If so, one specific way to do this is handed back in the
 * result parameter.
 */

/* Function prototypes */
bool canOfferUniversalCoverage(Set<string>& cities,
                               Vector< Set<string> >& locations,
                               int numHospitals,
                               Vector< Set<string> >& result);
Set<string> getRemovedCities(Set<string>& cities, Set<string> location);


int main() {
    /* Set up the cities and locations */
    Set<string> cities;
    cities += "A", "B", "C", "D", "E", "F";
    
    Set<string> hospital1;
    hospital1 += "A", "B", "C";
    
    Set<string> hospital2;
    hospital2 += "A", "C", "D";
    
    Set<string> hospital3;
    hospital3 += "B", "F";
    
    Set<string> hospital4;
    hospital4 += "C", "E", "F";
    
    Vector<Set<string> > locations;
    locations += hospital1, hospital2, hospital3, hospital4;
    
    int numHospitals = 3;
    Vector<Set<string> > result;
    if (canOfferUniversalCoverage(cities, locations, numHospitals, result)) {
        cout << "Yes, it can offer universal coverage!" << endl;
    } else {
        cout << "No, it cannot offer universal coverage." << endl;
    }
    cout << "Result: " << result << endl;
    
    return 0;
}

/* Helper function to determine any matching cities in a hospital location and the cities set.
 * It produces a the set of matched cities to be removed and removes those matched cities
 * from the cities vector.
 */
Set<string> getRemovedCities(Set<string>& cities, Set<string> location) {
    Set<string> removedCities;
    foreach(string city in cities) {
        if (location.contains(city)) {
            removedCities.add(city);
            cities.remove(city);
        }
    }
    return removedCities;
}

/* Recursive function to try all combinations of hospital locations.
 * 
 * Base case 1: If all cities are covered, return true.
 * 
 * Base case 2: If cities are not covered and you have no more hospital chocies, return false.
 *
 * Base case 3: If cities are not covered and there are no more hospitals, return false.
 *
 * Recursive process: At each stage, it will call the function where it DOES select the location,
 *                    and also call the function where it does NOT select the location.
 */

/* Returns whether or not coverage can be provided to all cities using the limited number of hospitals */
bool canOfferUniversalCoverage(Set<string>& cities,
                               Vector< Set<string> >& locations,
                               int numHospitals,
                               Vector< Set<string> >& result) {
    if (cities.isEmpty()) {
        return true;
    }
    if (numHospitals == 0) {
        return false;
    }
    if (locations.isEmpty()) {
        return false;
    }
    
    for (int i = 0; i < locations.size(); i++) {
        Vector< Set<string> > currResult = result;
        Set<string> remainingCities = cities;
        Vector< Set<string> > remainingLocations = locations;
        
        Set<string> removedCities = getRemovedCities(remainingCities, locations[i]);
        if (!removedCities.isEmpty()) {
            remainingLocations.remove(i);
            currResult.add(locations[i]);
        }
        if (canOfferUniversalCoverage(remainingCities, remainingLocations, numHospitals - 1, currResult)) {
            result = currResult;
            return true;
        }
    }
    return false;
    
}

// Modified version where locations are removed before the for loop

/*

• File: UniversalHealthCoverage.cpp

---

• Name: robertdo
• Section: mmateen
• This file is the starter project for the UniversalHealthCoverage problem
• on Assignment #3.
  */
  #include
  #include
  #include "set.h"
  #include "vector.h"
  #include "console.h"
  #include "foreach.h"
  using namespace std;

/* Function: canOfferUniversalCoverage(Set& cities,

• Vector< Set >& locations,
• int numHospitals,
• Vector< Set >& result);
• Usage: if (canOfferUniversalCoverage(cities, locations, 4, result)
• ==================================================================
• Given a set of cities, a list of what cities various hospitals can
• cover, and a number of hospitals, returns whether or not it's
• possible to provide coverage to all cities with the given number of
• hospitals. If so, one specific way to do this is handed back in the
• result parameter.
  */

/* Function prototypes */
bool canOfferUniversalCoverage(Set& cities,
Vector< Set >& locations,
int numHospitals,
Vector< Set >& result);
Set getRemovedCities(Set& cities, Set location);

int main() {
/* Set up the cities and locations */
Set cities;
cities += "A", "B", "C", "D", "E", "F";
Set hospital1;
hospital1 += "A", "B", "C";
Set hospital2;
hospital2 += "A", "C", "D";
Set hospital3;
hospital3 += "B", "F";
Set hospital4;
hospital4 += "C", "E", "F";
Vector<Set > locations;
locations += hospital1, hospital2, hospital3, hospital4;
int numHospitals = 3;
Vector<Set > result;
if (canOfferUniversalCoverage(cities, locations, numHospitals, result)) {
cout << "Yes, it can offer universal coverage!" << endl;
} else {
cout << "No, it cannot offer universal coverage." << endl;
}
cout << "Result: " << result << endl;
return 0;
}

/* Helper function to determine any matching cities in a hospital location and the cities set.

• It produces a the set of matched cities to be removed and removes those matched cities
• from the cities vector.
  */
  Set getRemovedCities(Set& cities, Set location) {
  Set removedCities;
  foreach(string city in cities) {
  if (location.contains(city)) {
  removedCities.add(city);
  cities.remove(city);
  }
  }
  return removedCities;
  }

/* Recursive function to try all combinations of hospital locations.
*

• Base case 1: If all cities are covered, return true.
  *
• Base case 2: If cities are not covered and you have no more hospital chocies, return false.
  *
• Base case 3: If cities are not covered and there are no more hospitals, return false.
  *
• Recursive process: At each stage, it will call the function where it DOES select the location,
• and also call the function where it does NOT select the location.
  */

/* Returns whether or not coverage can be provided to all cities using the limited number of hospitals */
bool canOfferUniversalCoverage(Set& cities,
Vector< Set >& locations,
int numHospitals,
Vector< Set >& result) {
if (cities.isEmpty()) {
return true;
}
if (numHospitals == 0) {
return false;
}
if (locations.isEmpty()) {
return false;
}

Vector< Set<string> > remainingLocations = locations;
remainingLocations.remove(0);

for (int i = 0; i < locations.size(); i++) {
    Vector< Set<string> > currResult = result;
    Set<string> remainingCities = cities;
    Set<string> removedCities = getRemovedCities(remainingCities, locations[i]);
    if (!removedCities.isEmpty()) {
        currResult.add(locations[i]);
    }
    if (canOfferUniversalCoverage(remainingCities, remainingLocations, numHospitals - 1, currResult)) {
        result = currResult;
        return true;
    }
}
return false;

}