Software Programming

Kunuk Nykjaer

Facebook Hacker Cup 2013 Qualification Round Solution part 2

with 2 comments


Balanced Smileys

References:
FB hacker cup
Analysis
Solution part 1
Solution part 3

Your friend John uses a lot of emoticons when you talk to him on Messenger. In addition to being a person who likes to express himself through emoticons, he hates unbalanced parenthesis so much that it makes him go :(

Sometimes he puts emoticons within parentheses, and you find it hard to tell if a parenthesis really is a parenthesis or part of an emoticon.

A message has balanced parentheses if it consists of one of the following:

– An empty string “”
– One or more of the following characters: ‘a’ to ‘z’, ‘ ‘ (a space) or ‘:’ (a colon)
– An open parenthesis ‘(‘, followed by a message with balanced parentheses, followed by a close parenthesis ‘)’.

– A message with balanced parentheses followed by another message with balanced parentheses.
– A smiley face “:)” or a frowny face “:(”
Write a program that determines if there is a way to interpret his message while leaving the parentheses balanced.

Input
The first line of the input contains a number T (1 ≤ T ≤ 50), the number of test cases.
The following T lines each contain a message of length s that you got from John.

Output
For each of the test cases numbered in order from 1 to T, output “Case #i: ” followed by a string stating whether or not it is possible that the message had balanced parentheses. If it is, the string should be “YES”, else it should be “NO” (all quotes for clarity only)

Constraints
1 ≤ length of s ≤ 100

Example input

5
:((
i am sick today (:()
(:)
hacker cup: started :):)
)(

Example output

Case #1: NO
Case #2: YES
Case #3: YES
Case #4: YES
Case #5: NO

Program.cs

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

// C# .Net 4
namespace ConsoleApplicationFB
{
    /// <summary>
    /// Author: Kunuk Nykjaer
    /// Balanced Smileys
    /// </summary>
    class Program
    {
        const char Beg = '(';
        const char End = ')';
        const char Colon = ':';

        static void Main(string[] args)
        {
            var lines = ReadFile("input.txt");
            Run(lines);
        }

        static void Run(IList<string> lines)
        {
            var result = new List<string>();
            for (var i = 1; i < lines.Count; i++)
            {
                var value = Algo(lines[i]) ? "YES" : "NO";
                result.Add(string.Format("Case #{0}: {1}", i, value));
            }
            WriteFile(result);
        }

        static bool Algo(string line)
        {
            if (string.IsNullOrWhiteSpace(line)) return true;

            var result = new List<Path>();

            // Recursive version, simpler imple, but will stackoverflow on large dataset
            Recursive(new Path { Line = line }, result);

            // Stack version, less simpler imple, but handles large dataset better
            //Loop(new Path { Line = line }, result);

            return result.Any(i => i.Valid);
        }


        // Recursive version
        static void Recursive(Path p, List<Path> result)
        {
            if (result.Count > 0) return; // found a valid path, don't eval others

            for (var i = 0; i < p.Line.Length; i++)
            {
                var c = p.Line[i];
                if (c == Colon)
                {
                    if (i + 1 < p.Line.Length)
                    {
                        var c2 = p.Line[i + 1];
                        if (IsParan(c2))
                        {
                            // split path to smiley and parantheses
                            var smiley = p.Line.Substring(i + 2);
                            var paran = p.Line.Substring(i + 1);

                            // Eval smiley path first
                            Recursive(new Path
                            {
                                Line = smiley,
                                Stack = p.Stack
                            },
                                result);

                            Recursive(new Path
                            {
                                Line = paran,
                                Stack = p.Stack
                            },
                                result);

                            return; // end current branch
                        }
                    }
                }
                else if (c == Beg) p.Stack++;
                else if (c == End)
                {
                    if (p.Stack == 0) return; // Invalid path

                    p.Stack--;
                }
                else if (IsText(c)) { } // Valid
                else return; // Invalid path                
            }

            if (p.Stack != 0) return;

            // Found valid path
            p.Valid = true;
            result.Add(p);
        }

        // Stack version
        static void Loop(Path path, List<Path> result)
        {
            // Stop on first found valid path

            var stack = new Stack<Path>();
            stack.Push(path);

            #region while

            while (stack.Count > 0)
            {
                var p = stack.Pop();
                var endbranch = false;

                # region loop
                for (var i = 0; i < p.Line.Length; i++)
                {
                    var c = p.Line[i];
                    if (c == Colon)
                    {
                        if (i + 1 < p.Line.Length)
                        {
                            var c2 = p.Line[i + 1];
                            if (IsParan(c2))
                            {
                                // Split path to smiley and parantheses
                                var smiley = p.Line.Substring(i + 2);
                                var paran = p.Line.Substring(i + 1);

                                stack.Push(new Path
                                               {
                                                   Line = paran,
                                                   Stack = p.Stack
                                               });

                                // Always eval smiley paths first, push last
                                stack.Push(new Path
                                               {
                                                   Line = smiley,
                                                   Stack = p.Stack
                                               });

                                endbranch = true;
                            }
                        }
                    }
                    else if (c == Beg) p.Stack++;
                    else if (c == End)
                    {
                        p.Stack--;
                        if (p.Stack < 0) endbranch = true; // Invalid path
                    }
                    else
                    {
                        if (IsText(c)) {} // Valid
                        else endbranch = true; // Invalid path
                    }

                    if (endbranch) break;
                }


                // Done branch

                if (endbranch) continue; // Eval next stack
                if (p.Stack != 0) continue; // Eval next stack

                // Found valid path
                p.Valid = true;
                result.Add(p);
                return; // Don't evaluate other branch, we have a valid path

                #endregion loop
            }

            #endregion while
        }

        static bool IsParan(char c)
        {
            return c == Beg || c == End;
        }

        static bool IsText(char c)
        {
            const int a = (int)'a';
            const int z = (int)'z';

            if (c == ' ') return true;
            if (c == Colon) throw new ApplicationException("algo error");
            if (c >= a && c <= z) return true;

            return false;
        }

        class Path
        {
            public string Line = "";
            public int Stack = 0;

            private static int _counter = 0;
            private int Id { get; set; }
            public Path() { Id = ++_counter; }
            public bool Valid = false;

            public override string ToString()
            {
                return string.Format("{0}; {1}; {2}; {3}", Id, Stack, Valid, Line);
            }
        }

        #region File
        
        static IList<string> ReadFile(string path)
        {
            var list = new List<string>();
            try
            {
                using (var reader = new StreamReader(path, true))
                {
                    var line = reader.ReadLine();
                    while (line != null)
                    {
                        list.Add(line);
                        line = reader.ReadLine();
                    }
                }
            }
            catch { throw; }

            return list.ToArray();
        }
        static bool WriteFile(IEnumerable<string> lines)
        {
            var fileInfo = new FileInfo("output.txt");

            try
            {
                using (StreamWriter sw = fileInfo.CreateText())
                {
                    foreach (var line in lines) sw.WriteLine(line);
                }
                return true;
            }
            catch { throw; }
        }

        #endregion File
    }
}

Running time: 1 sec.

input.txt

20
(:)
:((:()):))(a::(:)))(aa)a(a)()():)a(()(::()))((((()a)a((((()())((a()()()(()()(():a))()a)):a))))))
hacker cup: started :):)
a()(())(())(:)(:((:aa)()(a(():()()a)a()():(((:))()(()(a:(:aa)())))(:::()((::aa)))))(:)(((()())
)(
i am sick today (:()
(:)())()a()(()::(():())(:))):((:(a:())()()a)((()(a))()(:a()a:((:)a(())(:)(()())))())(a)))()
(:a))
(()()((((((((:)aa())a():(:()a(a)):)()(:))())(a)a((((a:()(a((()()a)a)):(a(a)))a)((():))):a())
()((:a(a()()a))())((:a(:a)(()a((((a((a(()(:aa()()()))):)(():):)(:(a))():(())(():()):):(()a))
(()a:::)a((:))(::a((a)(::aa((a):(:)(:)a()a(()))))facebook is hiring:)()()()a(a((:(a((:)()()))a))
()aa():):(a:))a()a(:))()()((()(:((())a)()(:)()):)::(()a:(:(:)((:(:a):(()(((a(())a:aaaa(()))))
(:a()a)(a)a(aa(()(::)())(:a(a):()a(a()a(()():)))this is a min cost max flow problem(a)((a(()a)))a
:)()((a)):(():a:a:)(:a)):)(()(:)::::(a(::a())(a):(:((((:(aa(()))a)(((((((((()a()a):)))((:)))))))))
aa:a:((a)(aa(::((((::((())aaa(()a(()a)))::a(((:(():()aa))a((:a:(:()((:(:():)))()):a(()a(()))
()(((a)((aa)))a)a()(a)(aa:a)()(((:())aa)):()():():a:(a)(a())a:)::a:(aa:):()((a:)())aa)a(a:)
:):)(::)a)()a((:a(a(((((a):)))(::()))(a)):))((a))):a:():)):()a(())aa(a(:))(aa()()::)):)(())
:((
(::a((a)a:()):):a)aa:)a(:::))(a())aa(a():))(:)a)((():)(:a:)a))):a(a)((:()(()())a))()a((()a))
(()aa):a:():((a(():(a()(aa((a()(a)(:)()(a(::))):)(:a::a:()aaa::a):a(((()(:)))(((()a:)a::(())))))

logo

Advertisements

Written by kunuk Nykjaer

January 29, 2013 at 6:02 pm

Posted in Algorithm, Csharp

Tagged with

2 Responses

Subscribe to comments with RSS.

  1. […] reference: link Solution part 1 Solution part 2 […]

  2. […] link Solution part 2 Solution part […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: