Solved

# Java Data Structures Homework Help!!!

Posted on 2012-09-12
729 Views
I hate to do this, but I tried everything and I can’t solve this problem.
The file attached “jj.txt” contains some sequences of numbers. A sequence is represented by a line of numbers.

A jump in a sequence of integers is the absolute value of the difference between two consecutive numbers. Given any integer n > 1, a sequence of n numbers is called a Jolly jumper of size n if the set of jumps in the sequence is the same as {1,2,…,n-1}. By definition, a single integer number is a Jolly jumper. For example, the sequence 1, 3, 2, -1, 3 is a Jolly jumper of size 5 because it has four jumps in { 2, 1, 3, 4}. However, the sequence 3, 2, -1, 3 is not a Jolly jumper of size 4 because it only has three jumps in {1, 3, 4}, where 2 is missing and 4 is too big (can't be greater than 4 - 1).

I attached a picture of what happens when I compile"Capture.PNG", but for reference, if I am correct, the first 8 sequences should be as following:

Sequence 1 is a Jolly Jumper of size 1.
Sequence 2 is a Jolly Jumper of size 1.
Sequence 3 is a Jolly Jumper of size 5.
Sequence 4 is not a Jolly Jumper.
Sequence 5 is a Jolly Jumper of size 10.
Sequence 6 is not a Jolly Jumper.
Sequence 7 is not a Jolly Jumper.
Sequence 8 is not a Jolly Jumper.

``````import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Jolly{
public static void main(String[] args){

StringTokenizer tokenizer;
int sequenceNumber= 1;

try{
File file = new File("jj.txt");
Scanner ins = new Scanner(file);

while (ins.hasNextLine()) {
ArrayList<Integer> sequence= new ArrayList<Integer>();
tokenizer = new StringTokenizer(ins.nextLine());
for (int i = 0; i < tokenizer.countTokens(); i++) {
}

boolean ans = isJollyJumper(sequence);
if(ans){
System.out.println("Sequence " + sequenceNumber + " is a Jolly Jumper of size " + sequence.size() + ".");
}else{
System.out.println("Sequence " + sequenceNumber + " is not a Jolly Jumper " + sequence.size() + ".");
}
sequenceNumber ++;
}ins.close();
}catch(FileNotFoundException e){
System.out.println("Can't find file");
}

}
public static boolean isJollyJumper(ArrayList<Integer> x){
ArrayList<Integer> difList = new ArrayList<Integer>();
int jumps = x.size()- 1;
int difResult = 0;

for(int i = 0; i < jumps; i++){
difResult = Math.abs(x.get(i)- x.get(i + 1));

if(x.size() == 1){
return true;
}
else if(difResult >= x.size()){
return false;
}else{
}
}
for(int i = difList.size(); i >= 1; i--){
if(!difList.contains(i)){
return false;
}
}
return true;
}
}
``````
jj.txt
Capture.PNG
0
Question by:JavaBeginner123

Author Comment

After debugging, I came up with the proper solution, and my code works flawlessly now.

``````import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Asg2{
public static void main(String[] args){

StringTokenizer tokenizer;
int sequenceNumber= 1;

try{
File file = new File("jj.txt");
Scanner ins = new Scanner(file);

while (ins.hasNextLine()) {
ArrayList<Integer> sequence= new ArrayList<Integer>();
tokenizer = new StringTokenizer(ins.nextLine());
while(tokenizer.hasMoreTokens()) {
}

boolean ans = isJollyJumper(sequence);
if(ans){
System.out.println("Sequence " + sequenceNumber + " is a Jolly Jumper of size " + sequence.size() + ".");
}else{
System.out.println("Sequence " + sequenceNumber + " is not a Jolly Jumper.");
}
sequenceNumber ++;
}ins.close();
}catch(FileNotFoundException e){
System.out.println("Can't find file");
}

}
public static boolean isJollyJumper(ArrayList<Integer> x){
ArrayList<Integer> difList = new ArrayList<Integer>();
int jumps = x.size()- 1;
int difResult = 0;

for(int i = 0; i < jumps; i++){
difResult = Math.abs(x.get(i)- x.get(i + 1));

if(x.size() == 1){
return true;
}
else if(difResult >= x.size()){
return false;
}else{
}
}
for(int i = difList.size(); i >= 1; i--){
if(!difList.contains(i)){
return false;
}
}
return true;
}
}
``````
My next question is that I want to increase the efficiency of my code...
``````for(int i = difList.size(); i >= 1; i--){
if(!difList.contains(i)){
return false; }
``````
How do I make this section more efficient?
0

LVL 35

Accepted Solution

Below is how I would implement the 'isJollyJumper' method. Normally I would be reluctant to post code for homework questions, however (unlike most homework questions on here) you have already made good effort and have something working and were able to use the debugger to get it working so I think that in this case it is ok. I am confident that you are the type of person that is NOT just after the quick answer and so will study the below code and get a good understanding as to why it works the way it does. Please reply back if you want any clarifications as to the workings of this code.

``````	public static boolean isJollyJumper(ArrayList<Integer> x) {
int jumps = x.size() - 1;
boolean[] difsArray = new boolean[jumps];
int difResult = 0;

for (int i = 0; i < jumps; i++) {
difResult = Math.abs(x.get(i) - x.get(i + 1));

if (difResult >= x.size() || difsArray[difResult - 1]) {
return false;
}
}
return true;
}
``````
0

Author Comment

What was your rational in creating the boolean array difsArray?
0

Author Comment

Ok, I see why you created the boolean array. To sum it up, once the calculation from the difResults is produce, it checks to see if the answer refers to an actual index of the boolean array. If that is false and the answer is greater than the index, the statement becomes false; thus, we return a false value as a result.

Thanks for helping me understand that part! I was having trouble following the logic, when  trying to come up with the unnecessary algorithm to create a more efficient solution.

PS. It was not a requirement to make the assignment as efficient as possible, but I previously talked with my professor and he confirmed me that it could be more efficient if I got rid of the loop.
0

Author Closing Comment

Great solution!! I really could follow the logic behind the solution as well.
0

LVL 35

Expert Comment

Sorry, I missed a line when cleaning up what I had done and I have also changed it so that it reads a little better...

``````	public static boolean isJollyJumper(ArrayList<Integer> x) {
int jumps = x.size() - 1;
boolean[] difsArray = new boolean[x.size()];
int difResult = 0;

for (int i = 0; i < jumps; i++) {
difResult = Math.abs(x.get(i) - x.get(i + 1));

if (difResult >= x.size() || difResult <= 0 || difsArray[difResult]) {
return false;
}
difsArray[difResult] = true;
}
return true;
}
``````
If the above hasn't answered your question already, the difsArray is basically acting tracking the set of differences, and which difference value has been encountered yet or not. So the array starts out with all elements of the array set to false, which is what we want because at the start the set of differences encountered is empty. Now taking for example the THIRD sequence, 2 6 3 4 6, the first difference is 4, which is less than the size of the sequence AND difsArray[4] == false at the moment, so everything is good. We now also set difsArray[4] = true, so that if we ever encounter another difference of 4 later in the sequence, difsArray[4] == true and the if statement above will make sure that we return false as this ISN'T a Jolly Jumper.

So the logic behind this is to make sure that there are never two or more of the same 'difference' values between any two elements of the sequence. The reason why this works is that it is another way of looking at the problem. In your code, you were getting the set of 'differences' and then checking if any were missing. I am getting the set and checking if any are duplicates. This works because of the constraints on the set; for an example sequence of 5 numbers, the set has to have 4 elements and the values have to be between 1 and 4 (I also added a check to make sure difResult is not 0). So by logic, the only way that a number in that set can be missing, is if another number is duplicated, ie. if {1, 2, 3, 4} is a 'good' set, then examples of sets with the 2 missing but that meet the constraints are {1, 1, 3, 4}, or {1, 3, 3, 4}, etc.

(Note: I just saw your later comments, and that you have accepted my answer, but just watch out for the changes that I made above. It looked like it was working but without line 12, it wasn't correctly applying the logic. In the first code I posted, nothing ever got populated into the array!)
0

## Featured Post

### Suggested Solutions

Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to a…
Since upgrading to Office 2013 or higher installing the Smart Indenter addin will fail. This article will explain how to install it so it will work regardless of the Office version installed.
Viewers will learn about the different types of variables in Java and how to declare them. Decide the type of variable desired: Put the keyword corresponding to the type of variable in front of the variable name: Use the equal sign to assign a v…
The viewer will learn how to implement Singleton Design Pattern in Java.