Monday, April 5, 2010

10038 Jolly Jumper Solution

Here's my Jolly Jumper solution. It was accepted by UVA online judge. It may not be the best solution but at least its readable.

My Algorithm is designed to fail quickly. As it calculates each sequence number it checks against three simple rules

  1. The sequence(n) number cannot be 0
  2. The sequence(n) number cannot be equal or greater than the input(numbers in my code). If there are 4 numbers then the sequence should contain the numbers 1,2,3
  3. There cannot be duplicates.
My solutions took 0.304 seconds to execute. Compared to the best, my solution is rather slow. The best solutions were written in C++ and ANSI C. Their run time was a flat 0. It would be rather interesting to see if  I could get an even faster run time. The only problem is that I'm using Java which is going to be slow from the get go. On the bright side I am one of 9546 users that have solved this problem.

My solution came as a result of refactoring. My original solution did not fail early. Instead it gathered all sequence numbers, sorted a list and then checked that it had the correct numbers. My original solution had an execution time of about 0.36 well my new solution executed at about 0.304. Although my solution isn't the fastest's I do enjoy its readability.

The problem can be found here

4 comments:

Anonymous said...

Your program is slow because you are using find() with an ArrayList which takes linear time. It would be much better to use a HashMap or a TreeMap.

Anonymous said...

There's no need for sorting or resorting to searching in a dictionary in this program.
Here's my code for this problem. It has a runtime of 0.006 s.

Anonymous said...

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

typedef long long ll;
typedef vector vi;
typedef pair ii;
typedef vector vii;

int main() {
int N, i, numbers[3005], diff;
bool found[3005];
/*
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
*/
while(true) {
if(scanf("%d", &N) == EOF) break;
for(i=0; i 0 && diff < N && !found[diff]) found[diff] = true;
else break;
}

if(i == N) printf("Jolly\n");
else printf("Not jolly\n");
}
return 0;
}

Anonymous said...

Sorry, comment box messed up my code.