Jolly Jumpers

From CS371p

Jump to: navigation, search

Jolly Jumpers is a puzzler for CS371p. The puzzler is part of the ACM Online Judge, hosted at Baylor University.


Problem Description

Here is the problem description as stated by the UVA Online Judge

A sequence of n > 0 integers is called a jolly jumper if the absolute values of the difference between successive elements take on all the values 1 through n-1. For instance,

1 4 2 3

is a jolly jumper, because the absolutes differences are 3, 2, and 1 respectively. The definition implies that any sequence of a single integer is a jolly jumper. You are to write a program to determine whether or not each of a number of sequences is a jolly jumper. Each line of input contains an integer n <= 3000 followed by n integers representing the sequence. Output For each line of input, generate a line of output saying "Jolly" or "Not jolly". Sample Input

4 1 4 2 3 5 1 4 2 -1 6

Sample Output

Jolly Not jolly


Algorithm

What you are looking for is the complete sequence from 1 to n-1, in any order. No duplicates, 0 values, or values greater than n-1, should occur.

Knowing this, the solution is easier to arrive at if you change what you are looking for. Looking for Jolly Jumpers is not the easiest way to solve this puzzle. By looking for what is not a Jolly Jumper is the best solution. Assuming that you read the whole input with out breaking one of the conditions above, you will have found a Jolly Jumper. In effect you want to find not not a Jolly Jumper.

Here is the algorithm I used in pseudo code: 

 while(read n)
   get first value
   loop n times
      get second value
      x = Absolute Value(first - second)
      if x is 0 or x greater than n-1 or I have seen x before
          not a jolly jumper
      swap first and second

Make sure to reset any booleans or remove unnecessary inputs left on a line when the input is not a Jolly Jumper.


Final Thoughts

This was a fun puzzler. It was easy to do in a few hours, and get a great time on the scoreboard. Just remember to reset your variables and arrays.

Retrieved from "http://z.cs.utexas.edu/users/downing/cs371p/index.php/Jolly_Jumpers"
Personal tools
papers