Problem of the Day -- Smiley Face

Smiley Face

Welcome back to another exciting week of Problem of the Day :)

Since Mondays are all about smiles we're going to make something that checks for them in a string. The goal for today will be to take in a string and return true or false if the parentheses in the string are closed properly (same number of opening and closing () not including smiley faces).

For instance:

#True
Today (Monday) is a day all about smiles ( :) )

#False
Weirdly formatted (strings (sometimes :) aren't easy :)) to read))

Permalink: http://problemotd.com/problem/smiley-face/

Comments:

Carlos - 10 years ago

It doesn't say that it has to be in order so, i'll take that flaw in the text and use it has an advantage to create a simpler algorithm.

private static int nLeft = 0;
private static int nRight = 0;
private static int nSmiley = 0;

public static void main(String[] args) {
    testCase();
}

public static void testCase() {
    smileys("Today (Monday) is a day all about smiles ( :) )");
}

public static void smileys(String s) {
    nSmiley = countOccurencesInString(s, ":)");   
    nLeft = countOccurencesInString(s, "(");
    nRight = countOccurencesInString(s, ")") - nSmiley;

    System.out.println(nLeft + " - " + nRight);

    if(nLeft == nRight) {
        System.out.println("TRUE - There's " + nSmiley + " smileys though...");
    } else {
        System.out.println("FALSE - There's " + nSmiley + " smileys though...");
    }
}

//Look ma... its recursive!!!
private static int countOccurencesInString(String s, String c) {
    int x = 0;
    if(s.length() == 0) {
        return 0;
    }

    if(s.endsWith(c)) {
        x += 1 + countOccurencesInString(s.substring(0, s.length() - 1), c);
    } else {
        x += countOccurencesInString(s.substring(0, s.length() - 1), c);
    }

    return x;
}

reply permalink

Anonymous - 10 years ago

Balanced parentheses, in C.

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

bool has_balanced_parens(const char *string)
{
    int level = 0;
    for (char *p = (char *) string; *p != '\0'; p++) {
        switch (*p) {
        case '(':
            level++;
            break;
        case ')':
            level--;
            if (level < 0) return false;
            break;
        case ':':
            if (p[1] == ')') p++;
            break;
        }
    }
    return level == 0;
}

int main()
{
    char *string1 = "Today (Monday) is a day all about smiles ( :) )";
    printf("%d\n", has_balanced_parens(string1));
    char *string2 = "Weirdly formatted (strings (sometimes :) aren't easy :)) to read))";
    printf("%d\n", has_balanced_parens(string2));
}

reply permalink

btgrant - 10 years ago

Checking for balanced parens in Scala:

def areParensBalanced(text: String): Boolean = {

  def countParens(chars: List[Char], index: Int, openPTotal: Int, closedPTotal: Int, pCount: Int): Boolean = {
    if (chars.isEmpty)
      if (closedPTotal == 0 && openPTotal == 0)
        true
      else
        pCount == 0 && (closedPTotal > openPTotal)
    else {
      if (chars.head == '(')
        countParens(chars.tail, index + 1, openPTotal + index, closedPTotal, pCount + 1)
      else if (chars.head == ')')
        countParens(chars.tail, index + 1, openPTotal, closedPTotal + index, pCount - 1)
      else
        countParens(chars.tail, index + 1, openPTotal, closedPTotal, pCount)
    }
  }

  countParens(text.replaceAllLiterally(":)", "").toList, 1, 0, 0, 0)
}

assert(areParensBalanced("Today (Monday) is a day all about smiles ( :) )"))
assert(!areParensBalanced("Weirdly formatted (strings (sometimes :) aren't easy :)) to read))"))

reply permalink

Anonymous - 10 years ago

And a short one in J.

balancedparens=: monad define
  parens=. -/ '()' =/ ':)' delstring y
  (0 = +/ parens) *. (*./ 0 <: +/\ parens)
)

balancedparens 'Today (Monday) is a day all about smiles ( :) )'  NB. => 1
balancedparens 'Weirdly formatted (strings (sometimes :) aren''t easy :)) to read))'  NB. => 0

reply permalink

Jt - 10 years ago

namespace ProblemOtd20140407
{
  using System;

  class Program
  {
    static void Main(string[] args)
    {
      string checkString = "Today (Monday) is a day all about smiles ( :) )";
      Console.WriteLine(checkString);
      Console.WriteLine(CheckParens(checkString));
      checkString = "Weirdly formatted (strings (sometimes :) aren't easy :)) to read))";
      Console.WriteLine(checkString);
      Console.WriteLine(CheckParens(checkString));
      checkString = "Sometimes parenthesis ) may be in the wrong order ( those should fail too :).";
      Console.WriteLine(checkString);
      Console.WriteLine(CheckParens(checkString));

      Console.WriteLine("Finished, press enter to exit");
      Console.ReadLine();
    }

    public static bool CheckParens(string checkString)
    {
      int parenCount = 0;

      checkString = checkString.Replace(":)", "");
      foreach (char c in checkString)
      {
        if (c == '(')
        {
          parenCount++;
        }

        if (c == ')')
        {
          parenCount--;
          if (parenCount < 0)
          { // We have a close paren before an opening
            return false;
          }
        }
      }

      return parenCount == 0;
    }
  }
}

reply permalink

Pyro - 10 years ago

Python solution with some extra stuff [Number of ( and ) when it fails and code break when ) doesn't have a ( on the left]

def left_par(a):
    if a=='(':
        return True
def right_par(a):
    if a==')':
        return True
def smiley_eyes(a):
    if a== ':':
        return True

n=0
left_counter=0
right_counter=0

sentence=raw_input("Introduce sentence\n")
m=len(sentence)

while n<m:
    if smiley_eyes(sentence[n]) and right_par(sentence[n+1]):
        n+=1
    else:
        if left_par(sentence[n]):
            left_counter+=1
        if right_par(sentence[n]):
            right_counter+=1
        if right_counter>left_counter:
            print "Error: ) with no couple found"
            break
    n+=1

if left_counter==right_counter:
    print "True"
else:
    print "False"
    print "( = ", left_counter
    print ") = ", right_counter

reply permalink

Hueho - 10 years ago

Dumb Ruby version:

def check(str)
  open, closed, skip = 0, 0, false
  str.chars.each_cons(2) do |fst, snd|
    if skip
      skip = false
      next
    end

    if fst == '('
      open += 1
    elsif fst == ')'
      closed += 1
    elsif fst == ':' and snd == ')'
      skip = true
    end

    return false if closed > open
  end

  closed += 1 if str.chars.last == ')'

  return open == closed
end

reply permalink

zifnab06 - 10 years ago
Well, that was fun, although this is slightly messy:

https://zifb.in/0Dnv05XxRJ

reply permalink

Steven Braham - 10 years ago

Very simple python script I wrote:

#(C) 2014 Steven Braham: http://www.problemotd.com/

sString = "Weirdly formatted (strings (sometimes :) aren't easy :)) to read))"
#first get rid of the smiles
sString = sString.replace(":)","")
#if the number of ( and ) don't add up, the string is flawed
iCountOpen =  sString.count("(")
iCountClosed =  sString.count(")")
if iCountClosed==iCountOpen:
    print "good"
else:
    print "not good"

I know it is way to simple, but I wanted to share it anyway

reply permalink

Karl - 10 years ago

This is my bulky attempt in C# (comments on how to make it better / more efficient would be awesome! :-))

using System;

namespace ParentheSmiles
{
    internal class Program
    {
        private static void Main()
        {
            string strToCheck; //Define this now so we can loop back later

            Console.WriteLine("Enter a sentence and I'll tell you if it's valid or not");

        Loop: //Creates a checkpoint to loop back to (doesn't have to be called "Loop")

            strToCheck = Console.ReadLine();

            if (string.IsNullOrEmpty(strToCheck.Trim()))
            {
                Console.WriteLine("You gotta give me something to work with!");
            }
            else
            {
                Console.WriteLine("The text supplied " +
                    (HasValidParens(strToCheck) ? "IS" : "is NOT") +
                    " correctly formatted!");
            }

            goto Loop; //Accept another sentence
        }

        //TODO: Have check for balanced parens (not sure best way to do this) e.g.: "()" vs ")("
        private static bool HasValidParens(string strText)
        {
            int intLeftParen = 0, intRightParen = 0; //Declare counts
            string eyeList = ":;"; //:), ;), etc.
            string betweenList = "-'^"; //:-), :'(, :^), etc.

            for (int i = 0; i < strText.Length; i++) //Loop through chars
            {
                if ((strText[i] == '(' || strText[i] == ')') && //If current char is paren
                    !(
                        (i >= 1 && eyeList.Contains(strText[i - 1].ToString())) || //:), ;), etc
                        (i >= 2 && betweenList.Contains(strText[i - 1].ToString()) && //:-), ;-), etc.
                            eyeList.Contains(strText[i - 2].ToString())
                        )
                     )
                   )
                {
                    if (strText[i] == '(') { intLeftParen++; }
                    else { intRightParen++; }
                }
            }

            return (intLeftParen == intRightParen); //Return boolean value
        }
    }
}

reply permalink

Problem of the Day A new programming or logic puzzle every Mon-Fri

Smiley Face

Comments:

Problem of the Day
A new programming or logic puzzle every Mon-Fri