DEV Community

Daily Challenge #29 - Xs and Os

dev.to staff on August 01, 2019

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("...
Collapse
 
avalander profile image
Avalander

Haskell again

import Data.Char (toLower)

compare_xos :: String -> Bool
compare_xos = same . foldl kevin (0, 0)
  where
    kevin (x, o) c
      | toLower c == 'x' = (x + 1, o)
      | toLower c == 'o' = (x, o + 1)
      | otherwise        = (x, o)
    same (x, o) = x == o
Collapse
 
thepeoplesbourgeois profile image
Josh

dammit kevin

Collapse
 
jacobmgevans profile image
Jacob Evans

Just being able to use Haskell impresses me lol

Collapse
 
avalander profile image
Avalander

I can't do anything useful with it yet, but it's fun to solve coding katas :D.

Collapse
 
alvaromontoro profile image
Alvaro Montoro • Edited

JavaScript

const xo = s => (s.match(/x/gi) || []).length == (s.match(/o/gi) || []).length;
Enter fullscreen mode Exit fullscreen mode

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

Collapse
 
savagepixie profile image
SavagePixie

Oh look, you had already come up with the same idea as I did!

Collapse
 
alvaromontoro profile image
Alvaro Montoro

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.

Thread Thread
 
savagepixie profile image
SavagePixie

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
Thread Thread
 
alvaromontoro profile image
Alvaro Montoro

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;
Thread Thread
 
savagepixie profile image
SavagePixie

I think this is my favourite solution. I hadn't checked its speed, but I thought that toLowerCase() probably didn't make it any smoother than returning an empty array if there are no matches.

Thread Thread
 
alvaromontoro profile image
Alvaro Montoro

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

Collapse
 
vimmer9 profile image
Damir Franusic • Edited

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

Enter fullscreen mode Exit fullscreen mode

Results:

ooxx: true
xooxx: false
ooxXm: true
zpzpzpp: true
zzoo: false
Enter fullscreen mode Exit fullscreen mode
Collapse
 
oscherler profile image
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; 
}
Collapse
 
vimmer9 profile image
Damir Franusic • Edited

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

Collapse
 
vimmer9 profile image
Damir Franusic • Edited

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

Thread Thread
 
oscherler profile image
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. :-)

Thread Thread
 
vimmer9 profile image
Damir Franusic • Edited

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

Collapse
 
thepeoplesbourgeois profile image
Josh

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

Collapse
 
vimmer9 profile image
Damir Franusic • Edited

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.

Collapse
 
choroba profile image
E. Choroba • Edited

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();
Collapse
 
vimmer9 profile image
Damir Franusic

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

Collapse
 
yzhernand profile image
Yozen Hernandez • Edited

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.

Thread Thread
 
alvaromontoro profile image
Alvaro Montoro

Thanks for a great explanation :)

Collapse
 
willsmart profile image
willsmart • Edited

How about a reduce to keep it in one loop? (JS)

XO = str => 
  [...str].reduce(
    (acc, c) => acc + (c == 'x' || c == 'X') - (c == 'o' || c == 'O'),
    0
  ) == 0;

// Check it
["ooxx","xooxx","ooxXm","zpzpzpp","zzoo"].map(s =>
  `${s} => ${XO(s)}`
).join('\n');
/* ^
"ooxx => true
xooxx => false
ooxXm => true
zpzpzpp => true
zzoo => false"
*/
Enter fullscreen mode Exit fullscreen mode
Collapse
 
thepeoplesbourgeois profile image
Josh

Oh, nice! I wouldn't have thought to use the array spread syntax to get the array of characters. 🎩✨

Collapse
 
nishu1343 profile image
nishu1343

Bro, nice solution .cud u explain me what is going inside the reduce. And im not able to reproduce it.

Collapse
 
willsmart profile image
willsmart • Edited

It's working for me in chrome just now. Try wrapping the output line in a console.log if you're outside a REPL

In the reduce acc is the accumulator, keeping a sum of values as they come up. The reduce returns the sum at the end.
Each c is a character from the string (...str is an array of the chars from str)
c == 'x' || c == 'X' is obv a boolean. The code uses the fact that in JS Number(true) == 1 and Number(false) == 0, so it's a shorter way of saying:

XO = str => 
  [...str].reduce(
    (acc, c) => acc + (c == 'x' || c == 'X' ? 1 : 0) - (c == 'o' || c == 'O' ? 1 : 0),
    0
  ) == 0;
Enter fullscreen mode Exit fullscreen mode

So each x adds one to the sum, and each o subtracts one. If the sum is zero there are the same number of x's as o's

Thread Thread
 
nishu1343 profile image
nishu1343

Cool.its working😃

Collapse
 
bsides profile image
Rafael Pereira

Javascript (pretty readable):

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
}
Collapse
 
jacobmgevans profile image
Jacob Evans

Well done! I like a one-liner and clever answers as much as the next person HOWEVER I also love seeing elegant, more readable, and even sometimes simplified (broken down more step by step) solutions!

Awesome job!

Collapse
 
bsides profile image
Rafael Pereira

Thank you Jacob! I have the same opinion! 👍

Collapse
 
ynndvn profile image
La blatte • Edited

How about some ugly oneliner?

XO=p=>!(new Set(p.toLowerCase().split``.reduce((l,i)=>[l[0]+(i=='x'),l[1]+(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!

Collapse
 
scrabill profile image
Shannon Crabill • Edited

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 
Collapse
 
scrabill profile image
Shannon Crabill • Edited

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!

Collapse
 
databasesponge profile image
MetaDave 🇪🇺

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")

Collapse
 
thepeoplesbourgeois profile image
Josh • Edited

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. 👍👍🙌

Thread Thread
 
scrabill profile image
Shannon Crabill

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.

Collapse
 
mohamedelidrissi_98 profile image
Mohamed ELIDRISSI

This is my solution, I'm still learning javascript so nothing fancy

function XO(string) {
  const strArr = string.toLowerCase().split('');
  let os = 0, xs = 0;
  strArr.forEach(word => {
    switch (word) {
      case 'o': 
        os++;
        break;
      case 'x': 
        xs++;
        break;
    }
  });
  return os === xs;
}
Collapse
 
savagepixie profile image
SavagePixie

Hmmm... Something like this might work in JavaScript

const checkXO = str => str.match(/x/gi).length == str.match(/o/gi).length
Collapse
 
pmkroeker profile image
Peter

Rust

pub fn xo (value: &str) -> bool {
    let value = value.to_lowercase();
    let count_x = value.matches("x").count();
    let count_o = value.matches("o").count();
    count_x == count_o
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_1() {
        assert_eq!(xo("ooxx"), true);
    }
    #[test]
    fn test_2() {
        assert_eq!(xo("xooxx"), false);
    }
    #[test]
    fn test_3() {
        assert_eq!(xo("ooxXm"), true);
    }
    #[test]
    fn test_4() {
        assert_eq!(xo("zzoo"), false);
    }
    #[test]
    fn test_5() {
        assert_eq!(xo("zpzpzpp"), true);
    }

}

Rust Playground
GitHub Gist

Collapse
 
phallstrom profile image
Philip Hallstrom

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.

Collapse
 
mariocsee profile image
Mario See

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.

Collapse
 
colinb profile image
Colin Bounouar

Is there a reason why you prefer a for loop over a single call to lower on the str, and then returning lowered.count('x') == lowered.count('o') ?

Collapse
 
jacobmgevans profile image
Jacob Evans • Edited

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`));
Collapse
 
jacobmgevans profile image
Jacob Evans

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.

Collapse
 
thepeoplesbourgeois profile image
Josh • Edited
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…

Collapse
 
thepeoplesbourgeois profile image
Josh • Edited

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
Collapse
 
brightone profile image
Oleksii Filonenko

Elixir:

defmodule XO do
  def same(string),
    do: count(string, "x") == count(string, "o")

  defp count(string, letter) do
    string
    |> String.graphemes()
    |> Enum.filter(&(&1 == letter))
    |> Enum.count()
  end
end
Collapse
 
craigmc08 profile image
Craig McIlwrath

Haskell:

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
Collapse
 
motss profile image
Rong Sen Ng • Edited

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');

Collapse
 
raistlinhess profile image
raistlin-hess

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}`);
}
Collapse
 
hectorpascual profile image

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'))

Collapse
 
matrossuch profile image
Mat-R-Such

Python:

def xo(txt):
    return  True if txt.lower().count('x') == txt.lower().count('o') else False
Collapse
 
kvharish profile image
K.V.Harish

My solution in js


const XO = (str) => {
  const countX = (`${str}`.match(/x/gi) || '').length,
    countO = (`${str}`.match(/o/gi) || '').length;
  return countX === countO;
};