Discussion on: Daily Challenge #29 - Xs and Os

[Damir Franusic]

C 😱 don't kill me please

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

// bool as string
#define BOOL_STR(b) b ? "true" : "false"

// X/x check
static bool check_x(char d) {
    if (d == 88 || d == 120) return true;
    return false;
}

// O/o check
static bool check_o(char d){
    if (d == 79 || d == 111) return true;
    return false;
}

static bool count_xo(const char* d){
    // null pointer
    if(!d) return true;
    // get size
    size_t l = strlen(d);
    // no data
    if(!l) return true;
    // res counters
    unsigned xc = 0, oc = 0;
    // mid point
    unsigned mp = l / 2, rm = l % 2;
    // check for 88 (X) and 79 (O)
    // O(N/2)
    for(unsigned i = 0, j = l - 1; i < mp; i++, j--){
        // X counter
        xc += check_x(d[i]) + check_x(d[j]);
        // O counter
        oc += check_o(d[i]) + check_o(d[j]);
    }
    // remainder
    if(rm){
        // X counter
        xc += check_x(d[mp + 1]);
        // O counter
        oc += check_o(d[mp + 1]);
    }

    // res
    return (xc == oc ? true : false);
}

int main(void) { 
    // test strings
    const char* str_00 = "ooxx";
    const char* str_01 = "xooxx";
    const char* str_02 = "ooxXm";
    const char* str_03 = "zpzpzpp";
    const char* str_04 = "zzoo";
    // results
    printf("%s: %s\n", str_00, BOOL_STR(count_xo(str_00)));
    printf("%s: %s\n", str_01, BOOL_STR(count_xo(str_01)));
    printf("%s: %s\n", str_02, BOOL_STR(count_xo(str_02)));
    printf("%s: %s\n", str_03, BOOL_STR(count_xo(str_03)));
    printf("%s: %s\n", str_04, BOOL_STR(count_xo(str_04)));
    // no error
    return 0; 
}

Results:

ooxx: true
xooxx: false
ooxXm: true
zpzpzpp: true
zzoo: false

[Olivier “Ölbaum” Scherler]

Is it allowed to modify someone else’s solution? I think you made it a bit more complicated than necessary. Anyone please correct me if I’m wrong:

• C strings end with the null character '\0', so you can skip getting the string length and do a while loop that checks for the null character (strlen does just that anyway);

• I didn’t really understand why you’re walking the string from the start and the middle, instead of from beginning to end, so I changed it;

• since we then only test for x and o once, I could inline the tests;

• xc == oc and d == 88 || d == 120 are already boolean expressions, so you don’t need the ternary operator ... ? true : false or an if(...) return true; else return false;;

• since I never used assertions in C, I took the opportunity to try them for the test cases (I intentionally wrote assert(count_xo("xooxx") == false) in the tests instead of assert(! count_xo("xooxx")) for consistency and readability.
  

#include <stdio.h>
#include <stdbool.h>

// bool as string
#define BOOL_STR(b) b ? "true" : "false"

static bool count_xo(const char* d){
    // null pointer
    if(!d) return true;
    // counters
    unsigned xc = 0, oc = 0, i = -1;
    while(d[++i] != '\0'){
        // X counter
        if( d[i] == 88 || d[i] == 120 ) xc++;
        // O counter
        if( d[i] == 79 || d[i] == 111 ) oc++;
    }
    // res
    return xc == oc;
}

int main(void) { 
    // test strings
    assert(count_xo("ooxx") == true);
    assert(count_xo("xooxx") == false);
    assert(count_xo("ooxXm") == true);
    assert(count_xo("zpzpzpp") == true);
    assert(count_xo("zzoo") == false);
    assert(count_xo("xoffxffo") == true);

    return 0; 
}

[Damir Franusic]

Hi and no problem changing the code

The following is indeed not needed:

(xc == oc ? true : false);

The loop tests strings from both sides to be more performant. Try doing benchmarks of both versions and post the results. I don't have time right now but might do it in the evening and show you the difference. Or, I might just embarrass myself lol.

Cheers

[Damir Franusic]

I wrote this too fast without even thinking too much, so once again, I appreciate your comment. Anyway, I know that inlining helps, but speed wasn't on my priority list for this challenge. :)

Here are my results:

Your code: ~550 nsec
My code: ~1140 nsec

Thumbs up for faster code.

P.S.
I suspected that strlen might be the culprit, and I was right.

If I change the code like this, I get results similar to yours, around 500 nsec more/less

static bool count_xo(const char* d, size_t l){
    // null pointer
    if(!d) return true;
    // no data
    if(!l) return true;
    // res counters
    unsigned xc = 0, oc = 0;
    // mid point
    unsigned mp = l / 2, rm = l % 2;
    // check for 88 (X) and 79 (O)
    // O(N/2)
    for(unsigned i = 0, j = l - 1; i < mp; i++, j--){
        // X counter
        xc += check_x(d[i]) + check_x(d[j]);
        // O counter
        oc += check_o(d[i]) + check_o(d[j]);
    }
    // remainder
    if(rm){
        // X counter
        xc += check_x(d[mp + 1]);
        // O counter
        oc += check_o(d[mp + 1]);
    }

    // res
    return xc == oc;
}

[Olivier “Ölbaum” Scherler]

Nice. I didn’t inline for speed, but for compactness, so that people don’t say C is too complicated, so verbose, etc. :-)

[Damir Franusic]

C is my baby, just started embedded C on SBCs, mostly arm 32bit. And people will always say that 🤣👍

[Josh]

I feel like the C might've already done you in? dang, that's some verbose low-level lang 😶

[Damir Franusic]

Well that's C, just how it is, you either hate it or you love it 😁. I missed a comma there; what I wanted to say was: guys, please don't kill me, this is C and it's gonna get ugly.