# Daily Challenge #29 - Xs and Os

### dev.to staff twitter logo Aug 1 '19・1 min read

Daily Challenge (159 Part Series)

Can you check to see if a string has the same amount of 'x's and 'o's?

Examples input/output:

``````XO("ooxx") => true
XO("xooxx") => false
XO("ooxXm") => true
XO("zpzpzpp") => true // when no 'x' and 'o' is present should return true
XO("zzoo") => false
``````

Note: The method must return a boolean and be case insensitive. The string can contain any character

This challenge comes from user joh_pot. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge for a future post? Email yo+challenge@dev.to with your suggestions!

DISCUSS (55) 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
``````

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;
}
``````

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

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:

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;
}

``````

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

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

Very easy (and rather fast) in Perl:

``````sub xo { local (\$_) = @_; tr/xX// == tr/oO// }
``````

It uses the transliteration operator which returns the number of matching characters in scalar context, and numeric comparison imposes scalar context.

The tests:

``````use Test::More;

ok   xo('ooxx');
ok ! xo('xooxx');
ok   xo("ooxXm");
ok   xo("zpzpzpp");
ok ! xo("zzoo");

done_testing();
``````

Perl sorcery 😁. This syntax always turns me inside out hehe. Nice job 👍

Sure, but this one is pretty easy to demystify, luckily: `tr/set1/set2/` just replaces characters in `set1` with those in `set2` (positionally), and returns the number of characters replaced/deleted. So in this code, he just compares the number of X's replaced with the number of O's replaced, and includes the lower-case variants too.

The `local(\$_)` is just there to let him make the code more brief. `\$_` is the "default input/pattern-searching space", so its like the default argument that `tr` will search. But it's also a global, so this lets you make a local copy and set it to be the first argument to the function.

If he didn't do that, it might look like this:

``````sub xo { my \$xos = shift; (\$xos =~ tr/xX//) == (\$xos =~ tr/oO//) }
``````

So just a bit more verbose.

Thanks for a great explanation :)

JavaScript

``````const xo = s => (s.match(/x/gi) || []).length == (s.match(/o/gi) || []).length;
``````

A solution using regular expressions in JavaScript. Live demo on CodePen.

Yes. Although mine looks a bit uglier because I ran into an issue: if the string doesn't have Xs or Os, the result of `match` is null so it fails when trying to do `.length` (test `checkXO("zpzpzpp")` on your code).

I had to add the fallback into empty array for those cases. But I feel like there has to be a cleaner way of doing the same thing.

Yeah, I found the same issue when I tried to solve it in Codewars. So I had to do the same. Looking through other people's solutions, there's one that I find interesting that uses `split()` instead of a regular expression. Something like this:

``````const xo = str => str.toLowerCase().split('x').length == str.toLowerCase().split('y').length
``````

The split approach is interesting. I was playing with different options, but not with this. Also, I found that using `toLowerCase()` made the code considerably slower, it works considerably faster if you use a regular expression in the split:

``````const xo6 = str => str.split(/x/i).length == str.split(/o/i).length;
``````

I checked different solutions with jsperf and this was the second fastest by a little (but results may vary.)

``````const makeArrayOfGivenChar = (text, givenChar) => text.split('').filter(c => c.toLowerCase() === givenChar.toLowerCase())

function XO(str) {
const x = makeArrayOfGivenChar(str, 'x')
const o = makeArrayOfGivenChar(str, 'o')
return x.length === o.length
}
``````

``````XO=p=>!(new Set(p.toLowerCase().split``.reduce((l,i)=>[l+(i=='x'),l+(i=='o')],[0,0])).size-1)
``````

Which produces the following output:

``````XO("ooxx"); // true
XO("xooxx"); // false
XO("ooxXm"); // true
XO("zpzpzpp"); // true
XO("zzoo"); // false
``````

It basically works by lowercasing everything and building an array with the number of Xs and Os. After that, it builds a Set with it, and check if the Set size is 1 or 2!

Not a pretty solution, but it seems to work in Ruby

``````def gossip_girl(string)
new_string = string.downcase

if new_string.include?("x") == false && new_string.include?("o") == false
true
elsif new_string.include?("x") == true && new_string.include?("o") == true
x_count = new_string.count("x")
o_count = new_string.count("o")

if x_count == o_count
true
else
false
end
else
false
end
end
``````

Returns

``````gossip_girl("ooxx") => true
gossip_girl("xooxx") => false
gossip_girl("ooxXm") => true
gossip_girl("zpzpzpp") => true
gossip_girl("zzoo") => false
``````

WAIT. Here's a much cleaner solution in Ruby.

``````def gossip_girl(string)
string.downcase.count("x") == string.downcase.count("o")
end
``````

Which returns

``````gossip_girl("ooxx") => true
gossip_girl("xooxx") => false
gossip_girl("ooxXm") => true
gossip_girl("zpzpzpp") => true
gossip_girl("zzoo") => false
``````

This is why you refactor!

It turns out that you could avoid the `#downcase` with `string.count("xX") == string.count("oO")`

I don't know whether the performance would be significantly different, though it would avoid creating a couple of extra string instances.

There are some other interesting variations for `#count`, such as using it to count lower case letters with `"abGvf".count("a-z")`

Very nice! I love your choice of method name 😂 And it's great that you went back to refactor once you realized there were optimizations you could make. No matter what "stakeholders" say about features driving revenue, any developer worth their salt knows that a clean codebase drives features. 👍👍🙌

Thanks. I can't think of X's and O's without Gossip Girl.

Clean codebases are so much easier to work with. Not to mention, cost and performance savings.

I broke out the work a little more, I tried to be a tad clever and utilize switch but wasn't able to get it to work quite the way I wanted.

Hopefully, the slightly more vanilla JS will be useful in some way.

``````function XO(s) {
const arr = [...s];
let countX = 0;
let countO = 0;
arr.map((ele, i) => {
if (ele === `x`) {
countX++;
delete arr[i];
}
if (ele === `X`) {
countX++;
delete arr[i];
}
if (ele === `o`) {
countO++;
delete arr[i];
}
if (ele === `O`) {
countO++;
delete arr[i];
} else {
delete arr[i];
}
});
const compare = countO === countX;
return compare;
}

console.log(XO(`xxxoooxxxoooxxxoooxoxoppppppppppppxoooxx`)); // true
// console.log(XO(`ooxx`)); // true
// console.log(XO(`xooxx`)); // false
// console.log(XO(`zpzpzpp`)); // true
// console.log(XO(`zzoo`)); // false
// console.log(XO(`zzoOOOoo`));
``````

I was removing elements with plans of creating two for loops going in opposite directions to speed up the process... but that was for fun and it lost interest in it.

Ruby

``````def xo(str)
tally = 0
str.each_char do |c|
case c.upcase
when "X" then tally += 1
when "O" then tally -= 1
end
end
tally.zero?
end
``````

Shorter solutions, but this only loops through the string once which might be nice for enormous strings.

``````import Data.Char (toLower)

xo :: String -> Bool
xo xs = let o's = count 'o' str
x's = count 'x' str
str = map toLower xs
count c = foldl (\sum char -> if c == char then sum + 1 else sum) 0
in o's == x's
``````

JavaScript:

``````const XO = (string) => {
const chars = string.toLowerCase().replace(/[^xo]/g, '').split('');
const reducer = (accumulator, char) => char === 'x' ? ++accumulator : --accumulator;

return chars.reduce(reducer, 0) === 0;
};
``````

``````const XO = (string) => {
return (string.match(/[xo]/gi) || []).reduce((acc, char) => char === 'x' ? ++acc : --acc, 0) === 0;
};
``````

``````const exsAndOhs = // "🎙 they haunt me…" (https://www.youtube.com/watch?v=0uLI6BnVh6w)
(string) => string
.toLowerCase()
.split("")
.reduce((count, letter) =>
/x/.test(letter) ? count += 1
: /o/.test(letter) ? count -= 1
: count
, 0) === 0;

exsAndOhs("xoxo") // => true
exsAndOhs("like ghosts, they want me") // => false
exsAndOhs("to make them all, they won't let go") // => false
exsAndOhs("ex's and ohs") // => true
``````

TERNARY CHAINS?? Yeah. I'm a loner, Dottie. A rebel…

Now in elixir because hey all the cool kids are using not-Javascript here.

``````defmodule ExsAndOhs do

def try_to_get_over_them(string) do
string
|> String.downcase
|> test(0) # The `Enum` module's for chumps.
end

defp test("", count), do: count == 0  # whole string is traversed
defp test("x" <> string, count), do:  # next grapheme is an "x"
test(string, count + 1)
defp test("o" <> string, count), do:  # next grapheme is an "o"
test(string, count - 1)
defp test(string, count), do:         # String.next_grapheme/1 is a tuple 😃
string
|> String.next_grapheme
|> elem(1)
|> test(count)

end
``````

A little Python here.

``````def count_xo(s):
count_x, count_o = 0, 0
for c in s:
if c.lower() == "x":
count_x += 1
if c.lower() == "o":
count_o += 1
return count_x == count_o
``````

This method uses a for loop to go through each character. It converts each character to lower case for a case insensitive comparison with "x" and "o" and increments the respective counters. The return line checks for count equality to return a boolean.

The time complexity in big O notation is `O(n)` or linear, where `n` is the size of input string `s`, and the space complexity is `O(1)` or constant since it just uses two variables to keep track of counts.

This can be done in linear time and linear space in terms of complexity by keeping track of the number of letter in a Map object as you traverse the string. Do note that the letter should be case insensitive which that actually gives us a hint that we can make each of the character to be always lowercased before using it as a cache key.

Pseudocode:

a = 'xoxo'
m = Map()
loop for each n in a {
l = n.toLowerCase()

m.set(l, 1) if not m.has(l)
else m.set(l, 1 + m.get(l))
}

return True if not m.has('x') and not m.has('o')

return m.get('x') == m.get('o');

Javascript with no loops:

``````function XO(str) {
let str_arr = str.toLowerCase()
.replace(/[^xo]/g, '')
.split('')    //Convert String into an Array to allow using Array.sort()
.sort();

//All of the o's will be placed before the x's thanks to Array.sort()
//Add 1 to account for 0-indexing and to turn -1 into 0 when there are no o's
let oCount = str_arr.lastIndexOf('o') + 1;
let xCount = str_arr.length - oCount;

return !(xCount - oCount);
}

//Run the test cases
const testCases = [
"ooxx",
"xooxx",
"ooxXm",
"zpzpzpp",
"zzoo"
];
for(str of testCases) {
let result = XO(str);
console.log(`"\${str}" => \${result}`);
}
``````

Python goes there :

``````def XO(input):
x_count = 0
o_count = 0
for c in input:
if c.lower() == 'x':
x_count += 1
elif c.lower() == 'o':
o_count += 1
return bool(x_count == o_count)
``````

[V2] - One liner :

``````XO = lambda input : bool(input.lower().count('x') == input.lower().count('o'))

``````

Classic DEV Post from Jun 9 '19

## Top 5 Soft Skills for Software Engineer  