885 - Telephone Directory Alphabetization

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

885 - Telephone Directory Alphabetization

Post by little joey » Tue Dec 14, 2004 5:39 pm

Getting lots of WAs on this one...
Two major problems I encounter are: what are the spelling rules for numbers and how to break ties when alphabetizing.

I've been looking on the internet for spelling rules, but there seems to be no uniform set. Most notably British and American English differ on this point. 727 is "seven hundred and twenty seven" in England, but "seven hundred twenty seven" in America. But there are more difficulties. How should 1701 be spelled? "seventeen hundred and one" is a possibility, but also "one thousand seven hundred and one", thousand seven hundred and one", "one thousand seven hundred one", thousand seven hundred one", etc.

As I can verify by using assert(), ties happen. Two or more names are the same when alphabetizing the converted strings. How should these ties be broken? Increasing telephone number sounds logical, but I can't get AC.

And then an other thing: how long can the input lines get? 52 characters? unbounded?

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Fri Dec 17, 2004 3:21 am

I am the potential guilty party, as I created the input and output files. I was hoping someone could solve this, so I could be sure that I created the files correctly.

I agree that the problem specification is very unclear about the numbers. So I assumed that they were similar to other problems:

http://acm.pku.edu.cn/JudgeOnline/showp ... em_id=2121
http://orgs.utulsa.edu/acm/problems/200 ... st/p2.html

I also found this converter, which is consistent with both my output and the way numbers are written in the problems above:

http://www.englisch-hilfen.de/en/texte/ ... eiben.html

No names should be the same after conversion, as I have an assert on this condition...

From the problem description:
Each line should contain the subscriber name as it appeared in the input in the first 52 positions
If the subscriber name is longer than 52 chars, then it would not appear in the output as in the input, as the output is restricted to 52 chars. This is why I have no names longer than 52 chars.

I hope I haven't given away too much in this post...

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Fri Dec 17, 2004 3:59 pm

I don't think your post is giving away too much. It's a clarification that realy should be included in the problem description, I think.

It looks like my number converter works correctly, so there must be some other problem with my code :( . As for long names: I just prune them to 52 characters before printing, so that should be no problem.

I'll keep on trying...

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Mon Dec 27, 2004 3:02 pm

I think the problem statement is ok, I can get AC in my first submission without reading this thread before. Although it is better to say "no tie after conversion of name". (Actually I forget this may happen when I code my program)

I think there is no formal rules about using "and" in spelling number, so I simply don't use any "and".

Little joey, are you sure that you make no typo in spell all the words, "one", "two", .... "hundred"? When I code my program, I copy these words into MS Word to make a spell check :lol:
And the comparison between converted name should be case insensitive.(I guess you will not make this error... but in the 0.000000001% case you may miss it, as it is possible to get the sample output using case sensitive comparison)
Last thing, the coverted name can be very long. Say the name is
377377377,377377377,377377377,377377377,377377377
The coverted name is about 500 chars long.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Dec 27, 2004 5:06 pm

.. wrote:Little joey, are you sure that you make no typo in spell all the words, "one", "two", .... "hundred"? When I code my program, I copy these words into MS Word to make a spell check :lol:
I made a typo: "FOURTY" in stead of "FORTY" :oops: :oops: :oops:

Although I got AC now, I'm still worried about the occurence of ties. If I leave the assert() call in the code it SIGABRTs on the judge, if I leave it out, I get AC ...

Ruben, are you sure you interpreted the phrase
Directories only use the letters A through Z for sorting, ignoring case.
correctly? In my view this means the two entries "49 steps" and "Forty-nine Steps" are the same; they both sort as "FORTY NINE STEPS", the hyphen in the second phrase is replaced by a space.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Mon Dec 27, 2004 5:58 pm

Hm~~
It sounds strange, if I add assert to check for tie, my program still gets AC.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Tue Dec 28, 2004 6:32 am

little joey wrote:Ruben, are you sure you interpreted the phrase
Directories only use the letters A through Z for sorting, ignoring case.
correctly? In my view this means the two entries "49 steps" and "Forty-nine Steps" are the same; they both sort as "FORTY NINE STEPS", the hyphen in the second phrase is replaced by a space.
I just checked the inputs "49 steps" and "Forty-nine Steps", according to my program they are equal (after converting) and it aborts due to assert. My program does not abort due to assert when I run in on the input I created. It's strange that your program aborts when you submit your code with the assert check added... And yes, I think I interpreted the above phrase correctly.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Dec 28, 2004 10:45 am

Well, that means my program still contains errors, even though it get's accepted. Very irritating...
Ruben, I sent you a PM.

Margarita
New poster
Posts: 8
Joined: Mon Jan 23, 2006 7:28 pm
Location: Ukraine, Kharkiv
Contact:

Post by Margarita » Mon Apr 24, 2006 12:30 pm

Hi 2 all. my program gets Runtime Error at 0.625, but i can't understand why. To find out where exception occures i used try & catch blocks, but i still get Runtime Error... i didn't find any input that causes exception. what to do? :)

tgoulart
New poster
Posts: 42
Joined: Sat Oct 21, 2006 8:37 am
Location: Alegrete, Brazil

Post by tgoulart » Wed Feb 21, 2007 6:53 am

In this very moment, there are 12 people on the world that are able to help me, and I wish at least one of them reads this! :D

Code: Select all

2222222x x a b c www
2222222XX-ABC aaa
3333333eight hundred eighty eight million eight hundred eighty eight thousand eight hundred eighty nine
3333333888888888!888888888!888888888!
1111111aaa lalalala 951
1111111AAA lalalala
1111111AAa  lalalala

Code: Select all

AAA lalalala                                           111 1111
AAa  lalalala                                          111 1111
aaa lalalala 951                                       111 1111
888888888!888888888!888888888!                         333 3333
eight hundred eighty eight million eight hundred eig   333 3333
XX-ABC aaa                                             222 2222
x x a b c www                                          222 2222
Is this correct?
Thiago Sonego Goulart - UFMG/Brazil

tgoulart
New poster
Posts: 42
Joined: Sat Oct 21, 2006 8:37 am
Location: Alegrete, Brazil

Post by tgoulart » Wed Feb 21, 2007 7:22 pm

Ouch, "12 people"... I could have gone to bed without this one... :oops:
Thiago Sonego Goulart - UFMG/Brazil

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Numbers out of range!!!

Post by baodog » Fri Jan 04, 2008 12:21 am

Finally AC, :P ... spelling error....

jimm1909
New poster
Posts: 1
Joined: Thu Mar 31, 2011 7:10 am

Re:

Post by jimm1909 » Thu Mar 31, 2011 7:14 am

tgoulart wrote:In this very moment, there are 12 people on the world that are able to help me, and I wish at least one of them reads this! :D

Code: Select all

2222222x x a b c www
2222222XX-ABC aaa
3333333eight hundred eighty eight million eight hundred eighty eight thousand eight hundred eighty nine
3333333888888888!888888888!888888888!
1111111aaa lalalala 951
1111111AAA lalalala
1111111AAa  lalalala

Code: Select all

AAA lalalala                                           111 1111
AAa  lalalala                                          111 1111
aaa lalalala 951                                       111 1111
888888888!888888888!888888888!                         333 3333 
eight hundred eighty eight million eight hundred eig   333 3333 
XX-ABC aaa                                             222 2222
x x a b c www                                          222 2222
Is this correct?




Thanks in advance,

-Jim
Last edited by jimm1909 on Thu Feb 26, 2015 7:52 am, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 885 - Telephone Directory Alphabetization

Post by brianfry713 » Sat Mar 31, 2012 9:58 pm

tgoulart your I/O matches my AC code.
Check input and AC output for thousands of problems on uDebug!

mathgirl
New poster
Posts: 36
Joined: Tue Apr 24, 2012 6:20 pm

Re: 885 - Telephone Directory Alphabetization

Post by mathgirl » Thu May 17, 2012 6:17 pm

I m getting RE for this code. Can I know what the exact error was ?

Code: Select all

#include<string>
#include<vector>
#include<iostream>
#include<algorithm>

using namespace std;

const char *ones[] = {"ZERO","ONE","TWO","THREE","FOUR","FIVE","SIX","SEVEN","EIGHT","NINE"};
const char *tens[] = {"ZERO","TEN","TWENTY","THIRTY","FORTY","FIFTY","SIXTY","SEVENTY","EIGHTY","NINETY"};
const char *ten[] = {"TEN","ELEVEN","TWELVE","THIRTEEN","FOURTEEN","FIFTEEN","SIXTEEN","SEVENTEEN","EIGHTEEN","NINETEEN"};

class listing
{

public:
	string name;
	string transform;
	string number;
	listing();
	listing(string,string,string);
};

listing::listing(string n,string nm,string t)
{
	number = n;
	name = nm;
	transform = t;
}

vector<string> convert(string num)
{
	int len = num.length();
	vector<string> parts;
	while(len > 3)
	{
		len = num.length();
		string part1 = num.substr(len-3,3);
		parts.push_back(part1);
		num = num.substr(0,len-3);
	}

	if(!num.empty())
		parts.push_back(num);

	return parts;
}

string alphabetise(string a)
{
	string ans("");
	int len = a.length();
	if(len > 2 && (a[2]-'0'))
	{	
		ans.append(ones[a[2]-'0']);
		ans.append(" HUNDRED");
	}
	if(len > 1 && (a[1]-'0'))
	{
		if(!ans.empty())
			ans.append(" ");

		if(a[1] == '1')
		{
			ans.append(ten[a[0]-'0']);
			a[0] = '0';
		}
		else
		{
			ans.append(tens[a[1]-'0']);
		}
	}
	if(a[0]-'0')
	{
		if(!ans.empty())
			ans.append(" ");

		ans.append(ones[a[0]-'0']);
	}

	return ans;
}

string transform(string input)
{
	string t(""),word;
	int i=0,len = input.length();
	
	while(i < len)
	{
		if(isalpha(input[i]))
		{	
			bool allcaps = true;
			while(i< len && isalpha(input[i]))
			{
				if(islower(input[i]))
					allcaps = false;
				word.push_back(input[i]);
				i++;
			}

			// process the word
			if(allcaps)
			{
				int j = 0;
				t.push_back(toupper(word[j++]));
					
				while(j < word.length())
				{
					t.push_back(' ');
					t.push_back(toupper(word[j++]));
				}
			}
			else
			{
				int j = 0;
				while(j < word.length())
					t.push_back(toupper(word[j++]));
			}

			word.clear();

		}
		else if(isdigit(input[i]))
		{
			while(i< len && isdigit(input[i]))
			{
				word.push_back(input[i]);
				i++;
			}
			vector<string> parts = convert(word);
			string al;
			int j = parts.size() - 1;
			for(j;j>=0;j--)
			{
				al = alphabetise(parts[j]);
				if(!al.empty())
				{
					if(!t.empty() && t[t.length()-1] != ' ')
						t.append(" ");
					t.append(al);
					if(j==1) t.append(" THOUSAND");
					if(j==2) t.append(" MILLION");
				}
			}
			word.clear();
		}
		else
		{
			while(i<len && !isdigit(input[i]) && !isalpha(input[i]))
				i++;
			t.push_back(' ');
		}
	}

	return t;
}

bool compare(listing a,listing b)
{
	if(a.transform < b.transform)
		return true;
	else
		return false;
}

int main()
{
	string number,name,line;
	vector<listing> output;

	while(getline(cin,line))
	{
		number = line.substr(0,7);
		number.insert(3,1,' ');
		name = line.substr(7);
		listing obj(number,name,transform(name));
		output.push_back(obj);
	}

	sort(output.begin(),output.end(),compare);
	vector<listing>::const_iterator iter = output.begin();
	while(iter != output.end())
	{
		cout.width(52);
		cout.setf(ios::left,cout.adjustfield);
		cout.fill(' ');
		cout << iter->name.substr(0,52);
		cout << "   ";
		cout.width(8);
		cout << iter->number << "\n";
		iter++;
	}
	
	return 0;
}

Post Reply

Return to “Volume 8 (800-899)”