885 - Telephone Directory Alphabetization

[little joey]

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]

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

[little joey]

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

[..]

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

[little joey]

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

I made a typo: "FOURTY" in stead of "FORTY"

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.

[..]

Hm~~
It sounds strange, if I add assert to check for tie, my program still gets AC.

[stubbscroll]

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.

[little joey]

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

[Margarita]

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]

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!

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?

[tgoulart]

Ouch, "12 people"... I could have gone to bed without this one...

[baodog]

Finally AC, ... spelling error....

[jimm1909]

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!

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

[brianfry713]

tgoulart your I/O matches my AC code.

[mathgirl]

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