LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

#1 September 6 2012

Ra8
Member

[Exercise] Braces

Today they gave us in the LCPC training this exercise:

We define a stable string:
1- the string is {}
2- if S is a stable string then {S} is also stable
3- if S and T are stable strings then TS is also stable

examples of stable strings:
{}, {}{}, {{}{}}...
examples of unstable strings:
}{, }{{{...

Given a string of size N 2<=N<=2000 (N is given even)

find the least operations to do on a string to make it stable:
the only operation allowed is to change { to } or vice-versa

Examples:
{{ result: 1
}{ result: 2
{{{} result:1

I will post my solution soon

Offline

#2 September 6 2012

arithma
Member

Re: [Exercise] Braces

def replacements(s):
	t = s.replace("{}","")
	while(t != s):
		s = t
		t = s.replace("{}","")
	return len(t)/2

Ah bummer. Found something wrong with it.

[edit]Hoping the fuck-ups have ceased.

def replacements(s):
	t = s.replace("{}","")
	while(t != s):
		s = t
		t = s.replace("{}","")
	count = 0
	s = t.lstrip("}")
	count += (len(t)-len(s))/2 + (len(t)-len(s))%2
	t = s.rstrip("{")
	count += (len(s)-len(t))/2 + (len(s)-len(t))%2
	return count + len([x for x in t if x == "{"]) - len(t)/2
print replacements("}{}}}{{{")

Last edited by arithma (September 6 2012)

Offline

#3 September 6 2012

Ra8
Member

Re: [Exercise] Braces

mine is similar to arithma's code

#include <iostream>
#include <string>

using namespace std;

int main()
{
    string s="}{{}";
    int total=0;
    int b=s.length()-1;
    for(int i=0;i<b;i++)
    {
        if(s[0]=='}')
        {
            s[0]='{';
            total++;
        }
        if(s[s.length()-1]=='{')
        {
            s[s.length()-1]='}';
            total++;
        }
        if(s.substr(i,2)=="{}")
        {
            s=s.substr(0,i)+s.substr(i+2);
            if(i==0)
                i=-1;
            else
                i-=2;
        }
        b=s.length()-1;
    }
    int size=s.length();
    cout << (total+size/2);
    return 0;
}

Offline

Board footer