(This assignment is based on a problem used in the ACM Programming Contest, Mid-

Question

(This assignment is based on a problem used in the ACM Programming Contest, Mid-Atlantic Region, in 2005.)

Dr. Montgomery Moreau has been observing a population of Northern Madagascar Pie-bald Shrews in the wild for many years. He has made careful observations of all the shrews in the area, noting their distinctive physical characteristics and naming each one.

He has made a list of significant physical characteristics (e.g., brown fur, red eyes, white feet, prominent incisor teeth, etc.) and taken note of which if these appear to be dominant (if either parent has this characteristic, their children will have it) or recessive (the children have this characteristic only if both parents have it).

Unfortunately, his funding from the International Zoological Institute expired and he was forced to leave the area for several months until he could obtain a new grant. During that time a new generation was born and began to mature. Upon returning, Dr. Moreau hopes to resume his work, starting by determining the likely parentage of the each member of the new generation.

This program should help him to match children up with their possible parents.

Input

The program reads all input from standard in (cin).

The first line of input will containing a sequence of 1 to 80 consecutive ‘D’ and ‘R’ characters describing a list of physical characteristics, indicating whether each is dominant or recessive.

After this line will follow several lines, each describing a single adult shrew. Each shrew is described by a name of 1-32 non-blank characters terminated by a blank space, then a single M or F character indicating the gender of the animal, another blank space, then a list of consecutive 0 or 1 characters, describing the animal. A 1 indicates that the animal possesses that physical characteristic, a 0 indicates that it does not. The list of adults is terminated by a line containing only the string ***.

This is followed by one or more lines describing juvenile animals. These contain a name and description, each formatted identically to those for the adults, separated by a blank space. The list of juveniles is terminated by a line containing only the string ***.

Output

For each juvenile animal, print a single line consisting of the animal’s name, the string “ by ”, then a (possibly empty) list of all possible parents for that animal. A set of parents should be printed as the name of the mother, a hyphen, then the name of the father. If the animal has multiple pairs of possible parents, these pairs should be printed in alphabetic (lexicographic) order first by the mother’s name, then by the father’s name among pairs where the mother is the same. Each pair should be printed separated by the string “ or ”.

Example 1
Given the input:

RDDR
Speedy M 0101
Jumper F 0101
Slowpoke M 1101
Terror F 1100
Shadow F 1001
***
Frisky 0101
Sleepy 1101
***
The output should be and it is:
Frisky by Jumper-Slowpoke or Jumper-Speedy or Shadow-Speedy
Sleepy by Shadow-Slowpoke

Example 2
Given the input:

DRRD
Speedy M 0101
Jumper F 0101
Slowpoke M 1101
Terror F 1100
Shadow F 1001
***
Frisky 0101
Sleepy 1101
***

The output should be:
Frisky by Jumper-Speedy
Sleepy by Jumper-Slowpoke or Terror-Slowpoke or Terror-Speedy

But it is:
Frisky by Jumper-Speedy
Sleepy by Jumper-Slowpoke or Terror-Slowpoke
Problem
Find and fix the error in the code using cerr to debug.

Shrew.cpp
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct Shrew {
string name;
string genes;

bool couldBeDescendedFrom (Shrew& mother, Shrew& father, string dominance);
};

bool Shrew::couldBeDescendedFrom (Shrew& mother, Shrew& father, string dominance) {
for (int i = 0; i < dominance.length(); ++i) {
if (dominance[i] == 'D') {
if (genes[i] == '1') {
if ((mother.genes[i] = '0') && (father.genes[i] == '0')) {
return false;
}
}
else {
if ((mother.genes[i] == '1') || (father.genes[i] == '1')) {
return false;
}
}
}
else {
if (genes[i] == '1') {
if ((mother.genes[i] == '0') || (father.genes[i] == '0')) {
return false;
}
}
else {
if ((mother.genes[i] == '1') && (father.genes[i] == '1')) {
return false;
}
}
}
}

return true;
}

void sort (vector<string>& v) {
for (int i = 1; i < v.size(); ++i) {
string temp = v[i];
int p = i - 1;

while (p >= 0 && v[p] > temp) {
v[p+1] = v[p];
--p;
}
v[p+1] = temp;
}
}

int main (int argc, char** argv) {
string dominance;
cin >> dominance;
string nm;

vector<Shrew> females;
vector<Shrew> males;

while (cin >> nm && nm != "***") {
Shrew shrew;
shrew.name = nm;
char gender;
cin >> gender >> shrew.genes;

if (gender == 'M') {
males.push_back(shrew);
}
else {
females.push_back(shrew);
}
}

while (cin >> nm && nm != "***") {
Shrew juvenile;
juvenile.name = nm;
cin >> juvenile.genes;

bool firstPair = true;
cout << juvenile.name << " by ";

vector <string> pairs;
for (int f = 0; f < females.size(); ++f) {
for (int m = 0; m < males.size(); ++m) {
if (juvenile.couldBeDescendedFrom(females[f], males[m], dominance)) {
pairs.push_back (females[f].name + "-" + males[m].name);
}
}
}

sort (pairs);

for (int i = 0; i < pairs.size(); ++i) {
if (i > 0) {
cout << " or ";
}
cout << pairs[i];
}
cout << endl;
}

return 0;
}

Explanation / Answer

test0.in

RDDR
Speedy M 0101
Jumper F 0101
Slowpoke M 1101
Terror F 1100
Shadow F 1001
***
Frisky 0101
Sleepy 1101
***

main.cpp

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct Shrew {
string name;
string genes;

bool couldBeDescendedFrom (const Shrew& mother, const Shrew& father,
                 string dominance);

};

bool Shrew::couldBeDescendedFrom (const Shrew& mother, const Shrew& father,
                  string dominance)
{
for (int i = 0; i < dominance.length(); ++i)
    {
      if (dominance[i] == 'D')
   if (genes[i] == '1')
      {
        if (mother.genes[i] == '0' && father.genes[i] == '0')
          return false;
      }
   else
      {
        if (mother.genes[i] == '1' || father.genes[i] == '1')
          return false;
      }
      else
   if (genes[i] == '1')
      {
        if (mother.genes[i] == '0' || father.genes[i] == '0')
          return false;
      }
   else
      {
        if (mother.genes[i] == '1' && father.genes[i] == '1')
          return false;
      }
    }
return true;
}

bool operator< (const Shrew& left, const Shrew& right)
{
return left.name < right.name;
}

int main (int argc, char** argv)
{
string dominance;
cin >> dominance;
string nm;

vector<Shrew> females;
vector<Shrew> males;

while (cin >> nm && nm != "***")
    {
      Shrew shrew;
      shrew.name = nm;
      char gender;
      cin >> gender >> shrew.genes;
      if (gender == 'M')
   males.push_back(shrew);
      else
   females.push_back(shrew);
    }

sort (females.begin(), females.end());
sort (males.begin(), males.end());

while (cin >> nm && nm != "***")
    {
      Shrew juvenile;
      juvenile.name = nm;
      cin >> juvenile.genes;

      bool firstPair = true;
      cout << juvenile.name << " by ";
      for (int f = 0; f < females.size(); ++f)
   for (int m = 0; m < males.size(); ++m)
      {
        if (juvenile.couldBeDescendedFrom(females[f], males[m],
                          dominance))
          {
       if (!firstPair)
          cout << " or ";
       firstPair = false;
       cout << females[f].name << "-" << males[m].name;
          }
      }
      cout << endl;
    }

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.