Programming Challenges - JollyJumpers

[keeyon2]

Hey Guys, I have been coding this out for a while and I can't find a problem with my code, yet the online code judge says I give a wrong answer. Can you guys find out where my algorithm doesn't work? I have had a lot of troubles finding any problem

Here is the actual Programming Challenge:
http://www.programming-challenges.com/english/pdfs/110201.pdf

Here is My solution to it.
I am using a queue to store all the numbers
and a priority queue to store all the differences of numbers

I tried commenting my code well. let me know if something doesn't make sense.
Thanks in advance!

// JollyJumpers.cpp : Defines the entry point for the console application.
//
#include <iostream>
#include <string>
#include <queue>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
using namespace std;


int main()
{

	int incomingNumberAmount, incomingNumber, compare1, compare2;
	char input;
	
	priority_queue<int> differences;
	queue<int> numbers;
	
	
	while ( true )
	{
		
		input = (cin.get());

		//breaks out if receives an enter key
		if (isspace(input))
		{
			break;
		}


		//convert inputted string to int
		incomingNumberAmount = atoi (&input);

		//take care of case with 1 number
		if (incomingNumberAmount == 1)
		{
                        //inputs number after 1, whatever it may  be
			cin >> incomingNumberAmount;
			cout << "Jolly" << endl;

			//removes ending whitespace so while loop 
			//doesn't break on the next loop
			cin.ignore();
			continue;
		}

		//put all numbers on que
		for (int i = 0; i < incomingNumberAmount; i++)
		{
			cin >> incomingNumber;
			numbers.push(incomingNumber);
		}

		//put differences of numbers on priority que
		for (int i = 0; i < incomingNumberAmount-1; i++)
		{
			compare1 = numbers.front();
			numbers.pop();
			compare2 = numbers.front();
			differences.push(abs(compare1 - compare2));
		}

		//counts down from max value
		//remove elements from priority queue if it is correct value
		for (int i = differences.size(); i > 0; i--)
		{
			if (differences.top() == i)
			{
				differences.pop();
			}
		}

		//depending on if empty or not, print correct value
		if (differences.empty() == true)
		{
			cout << "Jolly" << endl;
		}

		else
		{
			cout << "Not jolly" << endl;
		}

		//removes ending whitespace so while loop doesn't 
                //exit on next loop

		cin.ignore();
                
               //clears both queues
		for (int i = 0; i < differences.size(); i++)
		{
			differences.pop();
		}

		for (int i = 0; i < numbers.size(); i++)
		{
			numbers.pop();
		}

	}

	return 0;
}

Thanks !

[ne555]

Each line of input contains an integer n < 3,000 followed by n integers representing the sequence.
To read the input http://cplusplus.com/forum/general/58394/#msg314772

By the way, there are some problems that are misjudged. You may want to try uva judge instead http://uva.onlinejudge.org/

[keeyon2]

ne555, thanks for the reply.
As for your first link. I am the one that posted to solution to that question there. haha small world.

I do use cin >> x for all of the inputs except for the first one. The reason the first input uses the cin.get() is that when you do cin >> x, if you click enter a bunch of times, nothing goes in, for cin ignores white space and enters. I thought I had to detect enters though, for if the person presses enter after one of the series, the program must exit, and with cin, the program wont exit. I could be wrong though and the program might not have to exit, but if it does have to, then my approach allows this.

And as for the uva, judge, I have not yet tried that out. I will try that out now.

Thanks again for your response, I appreciate it :)

[ne555]

I thought I had to detect enters though, for if the person presses enter after one of the series, the program must exit, and with cin, the program wont exit

Nope, ¿why do you think that?
The input ends when you reach eof.

input = (cin.get());
//convert inputted string to int
incomingNumberAmount = atoi (&input);

You are just reading 1 character.
And atoi expects a null terminated string

[keeyon2]

ne555, you have found a problem I didn't notice!! YES thank you.

You are exactly right with the reading 1 char, and that is when it would cause an error, for if they put in the number 23, my program would input it as the number 2. That is a definite problem and I'll get to fixing that now. Thanks a bunch ne555. I'll change that up and see if it works.

[keeyon2]

It now just says that my time limit was exceeded. Do you think it is because my program never exits? My program will output all of the correct solutions I believe, but when they are done giving me inputs and they just input another empty line, my program doesn't stop running. It is because my first import now uses cin >> x, and when the empty line is given, my program doesn't respond because cin >> x ignores white space and empty lines.

Do you think the time limit being exceeded has to do with me not actually having the program close, or does my algorithm actually runs too slow? Thanks in advice again. Here is my Updated Code

// JollyJumpers.cpp : Defines the entry point for the console application.
//

#include <iostream>
#include <string>
#include <queue>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
using namespace std;


int main()
{

	int incomingNumberAmount, incomingNumber, compare1, compare2;
	char input;
	
	priority_queue<int> differences;
	queue<int> numbers;
	
	
	while ( true )
	{
		cin >> incomingNumberAmount;

		//take care of case with 1 number
		if (incomingNumberAmount == 1)
		{
			cin >> incomingNumberAmount;
			cout << "Jolly" << endl;

			continue;
		}

		//put all numbers on que
		for (int i = 0; i < incomingNumberAmount; i++)
		{
			cin >> incomingNumber;
			numbers.push(incomingNumber);
		}

		//put differences of numbers on priority que
		for (int i = 0; i < incomingNumberAmount-1; i++)
		{
			compare1 = numbers.front();
			numbers.pop();
			compare2 = numbers.front();
			differences.push(abs(compare1 - compare2));
		}

		//counts down from max value
		//remove elements from priority queue if it is correct value
		for (int i = differences.size(); i > 0; i--)
		{
			if (differences.top() == i)
			{
				differences.pop();
			}
		}

		//depending on if empty or not, print correct value
		if (differences.empty() == true)
		{
			cout << "Jolly" << endl;
		}

		else
		{
			cout << "Not jolly" << endl;
		}


		//removes ending whitespace so while loop doesn't exit on next loop
		//cin.ignore();

		//clears both queues
		for (int i = 0; i < differences.size(); i++)
		{
			differences.pop();
		}

		for (int i = 0; i < numbers.size(); i++)
		{
			numbers.pop();
		}
	}

	return 0;
}

[naraku9333]

Have you tried the sample input? 41423 should (according to the page you linked) produce "Jolly", although I'm not sure why since n in this case is 5 so 4, 3, 2, 1 should be necessary for a "Jolly". Am I missing something?

[keeyon2]

Naraku, the first 4 indicates that there will be 4 numbers coming that you should evaluate,
so when it says 4 1 4 2 3, it means something like 4: 1 4 2 3. Where 1 4 2 3 are the 4 numbers that are to be evaluated. I hope my explanation makes sense, if not let me know.

I tried the sample inputs and my program gives the same outputs as the problem says it should.

Thanks again for your response. it is much appreciated.

[ne555]

Do you think it is because my program never exits?

Yep, that's the problem.

	while ( true )
	{
		cin >> incomingNumberAmount;

Change that to while ( cin>>incomingNumberAmount ){ so it will end when there is no more input (eof).

In order to test your program, you should use i/o redirection

$ ./program.bin < input.in

[keeyon2]

ne555 thank you for the intelligent response. I like that while loop, i think that will probably fix my program. I will test that out now and if it does Ill mark this as solved. Thanks to everyone that has responded so far, this has been a great learning experience. I will let you know how the changes do. Thanks again