31
\$\begingroup\$

I have written a solution to the blood-type matching problem, as described at https://projectlovelace.net/problems/blood-types/. The problem is to determine whether a given recipient (in this case, argv[1]) will find a match for a blood transfusion in an array of available donors (argv + 2).

  • Input blood type: B+
  • Input list of available blood types: A- B+ AB+ O+ B+ B-
  • Output: match
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <err.h>

typedef struct {
    enum { O, A, B, AB } abo;
    enum { P, M } rh; 
} Blood;

const int abo[4][4] = {
    { O, O, O, O }, // O
    { O, A, O, A }, // A // *
    { O, B, O, B }, // B // *
    { O, A, B, AB }, // AB
};

const int rh[2][2] = {
    { P, M }, // P
    { M, M }, // M // *
};

Blood
parse(char *s){
    char rh0 = s[strlen(s)-1];
    char *abo0 = strdup(s);
    abo0[strlen(s)-1] = '\0';
    Blood b = {
        !strncmp(abo0, "O", 1) ? O
            : !strncmp(abo0, "A", 1) ? A
            : !strncmp(abo0, "B", 1) ? B
            : !strncmp(abo0, "AB", 2) ? AB
            : -1,
        rh0 == '+' ? P
            : rh0 == '-' ? M
            : -1,
    };
    return b;
}

int
main(int argc, char *argv[]) {
    if(argc < 3)
        err(1, "no arguments given\n");
    int n = argc - 2;
    char *a0 = argv[1];
    char **as = argv + 2;

    Blood b0 = parse(a0);
    Blood *bs = malloc(sizeof(Blood) * n);
    for(int i = 0; i < n; i++)
        bs[i] = parse(as[i]);

    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 2; j++) {
            for(int k = 0; k < n; k++) {
                if(abo[b0.abo][i] == bs[k].abo && rh[b0.rh][j] == bs[k].rh) {
                    printf("match\n");
                    return 0;
                }
            }
        }
    }
    printf("no match\n");
    return 1;
}

which works correctly in my tests, but uses some hacks. Specifically, lines marked with // * have repeated values of enums, since I couldn't find a way to make loop sizes conditional on blood types.

What would be a better way, without forcing the blood type enums to be the same size? And more generally, is there a simpler version of the blood-type matching algorithm?

\$\endgroup\$
  • 3
    \$\begingroup\$ Bug: if s has len 0, your parse function invokes undefined behavior. \$\endgroup\$ – D. Ben Knoble Nov 21 at 0:21
  • 1
    \$\begingroup\$ @D.BenKnoble A bug is when a program behaves badly on a valid input. As far as I can see it is not stated anywhere that an empty string given as a parameter is a valid input for the program. You might as well complain that the malloc may fail if argc is too large. I wouldn't expect an excersise program to be nuke-proof. IMHO this is at most a potential weaknes (if the parse() routine is ever used outside tis application), not a bug... :) There are more serious problems with the code than proper handling an improper input! \$\endgroup\$ – CiaPan Nov 22 at 13:06
  • 4
    \$\begingroup\$ @CiaPan I mostly agree in theory—but not paying attention to these kinds of bugs (yes, bug: the type and docs impose no limitations on the length, so its not stated not to be a valid input; worse, it could very well become an issue)—not paying attention to these kinds of bugs is a dangerous hubris that assumes « proper » input (which is a bad idea) and assumes the access will fail a particular way (eg, segfault). Bad idea. If one writes it here, lets learn not to before we get to larger systems! \$\endgroup\$ – D. Ben Knoble Nov 22 at 13:27
  • \$\begingroup\$ You said the code 'works correctly' in you tests. Can you, please, show them? I suspect your program would not pass some. Did you test, for example, a recipient with blood type A+ and an AB+ donor? \$\endgroup\$ – CiaPan Nov 22 at 18:16
53
\$\begingroup\$

Each blood factor can be present or not present. The blood types can be bit-encoded using one bit for the A factor, one bit for the B factor, and one bit for the Rh factor.

enum { A=1, B=2, Rh=4 };

You would parse the blood type "AB+" as A + B + Rh == 7, and "O-" as 0 because it does not contain any A factor, B factor, or Rh factor.

Survival requires the donor's blood not contain any factors missing in the recipient's blood type. Compliment the recipient's blood type to get the bad factors, and use a bit-wise and operation to test that all of the factors are not present in the donor's blood.

bool donor_matches = (donor & ~recipient) == 0;

If you want to leave you enum's as encoding the 4 blood types, and the Rh factor separately, you can get to a similar coding.

Note that:

enum { O, A, B, AB } abo;

will define O=0, A=1, B=2, AB=3, so you have a similar bit assignment as above. The Rh factor on the other hand would be better to reverse the order:

enum { M, P } rh;

so that M=0, P=1. Now you could express the match condition:

bool donor_match = (donor_abo & ~recipient_abo) == 0 && (donor_rh & ~recipient_rh) == 0;

Finally, if you want to leave the rh enum as you have originally defined it:

enum { P, M } rh;

then note that donor_rh >= recipient_rh would express that the rh factors match, or the donor has a less-restrictive (numerically higher) rh factor.

\$\endgroup\$
  • 5
    \$\begingroup\$ I suggest to write 0b001, 0b010, 0b100 for the bit encoding instead of decimal numbers in enum { A=1, B=2, Rh=4 };. This would express your idea in the code better. \$\endgroup\$ – Jonas Stein Nov 21 at 21:56
  • 2
    \$\begingroup\$ @JonasStein I like the idea, but as of C11, it looks like only decimal, hexadecimal and octal constants are standard. \$\endgroup\$ – AJNeufeld Nov 21 at 22:45
  • 2
    \$\begingroup\$ Not as elegant as @JonasStein's suggestion, but you could use bit-shifting: enum { A = 1 << 0, B = 1 << 1, C = 1 << 2 }, though it might be overkill for such a small enum (I've used this before when dealing with a large bitfield to ensure I didn't make a silly mistake defining my constants by hand). \$\endgroup\$ – Wasabi Nov 22 at 15:56
  • 3
    \$\begingroup\$ @Wasabi Perhaps not as elegant, but standard compliant. I approve (except for that weird C blood type). \$\endgroup\$ – AJNeufeld Nov 22 at 15:58
  • 1
    \$\begingroup\$ Brilliant example of how domain knowledge can help with elegant implementation. You knew what the underlying logic was. OP (and me) probably thought the pairings were random. \$\endgroup\$ – Greg Bell Nov 27 at 21:58
28
\$\begingroup\$

Your code is way too complicated. If any of A, B, or + is present in the donor, it must also be present in the recipient. That's all you need.

bool is_compatible(const char* donor, const char* recipient)
{
    if(strstr(donor, "A") != NULL && strstr(recipient, "A") == NULL)
        return false;
    if(strstr(donor, "B") != NULL && strstr(recipient, "B") == NULL)
        return false;
    if(strstr(donor, "+") != NULL && strstr(recipient, "+") == NULL)
        return false;
    return true;
}

int main(int argc, char *argv[])
{
    for (int i = 2; i < argc; i++)
    {
        if (is_compatible(argv[i], argv[1]))
        {
            printf("match: %s\n", argv[i]);
            return 0;
        }
    }
    printf("no match\n");
    return 1;
}
\$\endgroup\$
  • 9
    \$\begingroup\$ A model for blood type, even as simple as enumeration, I think, is required. Because blood models do change, and there are alternate representations. While this is certainly smaller and simpler, it hard codes blood typing logic into the source code and not into the data (of valid blood types). This is not necessarily the best approach for software intended for medical use, of course this is just an exercise. \$\endgroup\$ – crasic Nov 21 at 23:54
  • 1
    \$\begingroup\$ @crasic, the test function could follow your suggestion and be shorter, with a simple loop on if (strstr(donor,types[index]) && !strstr(recipient,types[index])) return false;, with types="AB+". \$\endgroup\$ – Ray Butterworth Nov 26 at 16:21
3
\$\begingroup\$

Forget about what they asked for, and think about what it really means.

Having a match means that at least one of the donor strings contains no characters that aren't in the recipient string, except for possibly the placeholders "O" and "-".

So check for that:

#include <malloc.h>
#include <stdio.h>
#include <string.h>

    int
main(int argc, char **argv) {
    if (argc>2) {
        auto int index;
        auto char **donor;
        auto char *donee = strcat(strcpy(malloc(3+strlen(argv[1])), argv[1]), "-O");
        for (donor=&argv[2]; *donor; ++donor) {
            for (index=0; index[*donor]; ++index)
                if (!strchr(donee, index[*donor])) break;
            if (!index[*donor]) return puts("Match"), 0;
        }
    }
    return puts("No match\n"), 1;
}

The unnecessary placeholders, "O" and "-", should have been stripped from the donor strings, but in this case it was easier to add them to the recipient string.

Note that except for that special case, this code has nothing specific to human blood types. The same program will work for Vulcans too (Spok is "T-").

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.