[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 744
  • Last Modified:

Java Data Structures Homework Help!!!

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++) {
     		sequence.add(Integer.parseInt(tokenizer.nextToken()));
    	}    	
    	
    	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{
	difList.add(difResult);
}
}
	for(int i = difList.size(); i >= 1; i--){
		if(!difList.contains(i)){
			return false;
		}
}
	return true;
}
}

Open in new window

jj.txt
Capture.PNG
0
JavaBeginner123
Asked:
JavaBeginner123
  • 4
  • 2
1 Solution
 
JavaBeginner123Author Commented:
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()) {
     		sequence.add(Integer.parseInt(tokenizer.nextToken()));
    	}    	
    	
    	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{
	difList.add(difResult);
}
}
	for(int i = difList.size(); i >= 1; i--){
		if(!difList.contains(i)){
			return false;
		}
}
	return true;
}
}

Open in new window

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

Open in new window

How do I make this section more efficient?
0
 
mccarlIT Business Systems Analyst / Software DeveloperCommented:
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;
	}

Open in new window

0
 
JavaBeginner123Author Commented:
What was your rational in creating the boolean array difsArray?
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
JavaBeginner123Author Commented:
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
 
JavaBeginner123Author Commented:
Great solution!! I really could follow the logic behind the solution as well.
0
 
mccarlIT Business Systems Analyst / Software DeveloperCommented:
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;
	}

Open in new window

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

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

  • 4
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now