Thread: How To Use Linear Search

Hi all,

I'm having a problem using a linear search to find a duplicate. Here's the details of my program:

I roll two dice continually and get random numbers, 1-6. If I roll two of the same numbers, i.e. a 2 and a 2, then I lose the game. Otherwise, I add the two dice together and store it into a variable called sum. I then store each sum into an array. I roll the dice again and compare the sum to the previous sum in the array for a duplicate number. If no duplicate, I roll the dice a third time and compare the current sum to the last two sums in the array. I continue this until I find a duplicate sum then I win and stop. It's a little like craps but slightly different.

My problem is that I don't know how to compare the current sum to all of the sums in the array. I can compare the current sum with a previous sum in the array, but I don't know how to traverse the whole array to search for a duplicate. Any idea of how to do this?

Here's the code:

public static void main(String[] args) {
 
 
		int a = 10;
		int[] sumArray = new int [a];
 
 
		for (int i = 0; i < a; i++) {
			int d1 = roll();
			int d2 = roll();
		    int sum = d1 + d2;
			sumArray[i] += sum;
			System.out.println("d1: " + d1 + " d2: " + d2);
			System.out.println("index is:    " + sumArray[i]);
 
 
 
            if (d1 == d2) {
				System.out.println("You lose!");
				break;
			}
 
               for (int j = 0; j < a-1; j++){
 
				if (sum == sumArray[j]){
					System.out.println("You win!");
					break;
				}
			}
 
 
            }
 
 
		}
 
		public static int roll() {
		int die = (int)(Math.random() * 6) + 1;
		return die;
	}
 
}

               for (int j = 0; j < a-1; j++){
 
				if (sum == sumArray[j]){
					System.out.println("You win!");
					break;
				}
			}

What is this doing?
Does the code compile and run? What seems to be the problem? You never really said what is not working or what is going on you want to change.

The code does compile and run. That particular module is what I thought was a linear search through the array. I used some println statement to see what's happening in the run. It looks like the sum is equal to the array index every time and prints out "You win!" for every iteration. I need every iteration of the current sum to check all previous indices for a duplicate.

i.e. roll a 2 and 4 = 6<---
roll a 3 and 7 = 10
roll a 4 and 5 = 9
roll a 5 and 1 = 6 <---6's match
You win!

OR
roll a 2 and 3 = 5
roll a 3 and 3<---rolling a double loses
You lose!

Here's what I'm getting now:

d1: 3 d2: 6
Sum is: 9
index is: 9
You won!
d1: 1 d2: 2
Sum is: 3
index is: 3
You won!
d1: 2 d2: 1
Sum is: 3
index is: 3
You won!
d1: 3 d2: 4
Sum is: 7
index is: 7
You won!
d1: 6 d2: 6
Sum is: 12
index is: 12
You lose!

Originally Posted by Semion

It looks like the sum is equal to the array index every time

System.out.println("index is: " + sumArray[i]);
i would be the index, sumArray[i] would be the value at index i within the array.
Or do I not understand you correctly?

You are correct. Forgive the confusing sentence. I meant that the value inside each index is equal to the sum.

for (int i = 0; i < sumArray.length; i++){
    for (int j = sumArray.length -1; j >= 0; j--){
        if (( i != j) && (sumArray[i] == sumArray[j])){
            System.out.println("You win!");
            break;
            }
         }
     }

Thanks for the reply. I tried this code but it still has the sum equal to the value in the index. I see where you're going here in the linear search going backwards. Great idea. Now I just need to figure out how to implement this correctly.

Here's the new code and output:

public static void main(String[] args) {
 
		int a = 10;
		int[] sumArray = new int [a];
 
		for (int i = 0; i < a; i++) {
			int d1 = roll();
			int d2 = roll();
		    int sum = d1 + d2;
			sumArray[i] += sum;
			System.out.println("d1: " + d1 + " d2: " + d2);
			System.out.println("Sum is:      " + sum);
			System.out.println("index is:    " + sumArray[i]);
 
		   if (d1 == d2) {
				System.out.println("You lose!");
				break;
			}
 
             for (int k = 0; k < sumArray.length; k++){
 
            	 for (int j = sumArray.length -1; j >= 0; j--){
 
            		 if (( i != j) && (sumArray[i] == sumArray[j])){
 
            			 System.out.println("You win!");
                        break;
                        }
                     }
                 }
 
		}
 
    }
 
		public static int roll() {
		int die = (int)(Math.random() * 6) + 1;
		return die;
	}
 
 
 
}

Output:

d1: 4 d2: 3
Sum is: 7
index is: 7
d1: 6 d2: 3
Sum is: 9
index is: 9
d1: 5 d2: 1
Sum is: 6
index is: 6
d1: 3 d2: 2
Sum is: 5
index is: 5
d1: 5 d2: 5
Sum is: 10
index is: 10
You lose!

instead of break, you could break out of the first loop by i = sumArray.length -1;

--- Update ---

Now that I think about it. It would be more efficient to make the second for loop

for (int j = sumArray.length - 1; i < j; j--)
    if (sumArray[i] == sumArray[j]) // you could take out the (i != j) 
// And it wouldn't check the same values over again

Still not working. I have:

for (int k = 0; k < sumArray.length; k++){
 
            	 for (int j = sumArray.length - 1; i < j; j--){
 
            		 if (sumArray[k] == sumArray[j]){
 
                         System.out.println("You win!");
            			 break;
                        }
                     }
                 }

And my output is:

d1: 3 d2: 6
Sum is: 9
index is: 9
You win!
You win!
You win!
You win!
You win!
You win!
You win!
You win!
You win!
d1: 5 d2: 2
Sum is: 7
index is: 7
You win!
You win!
You win!
You win!
You win!
You win!
You win!
You win!
d1: 6 d2: 5
Sum is: 11
index is: 11
You win!
You win!
You win!
You win!
You win!
You win!
You win!
d1: 4 d2: 5
Sum is: 9
index is: 9
You win!
You win!
You win!
You win!
You win!
You win!
d1: 6 d2: 5
Sum is: 11
index is: 11
You win!
You win!
You win!
You win!
You win!
d1: 6 d2: 6
Sum is: 12
index is: 12
You lose!

You are calling the index "System.out.println("index is: " + sumArray[i]);" that is the value you want i. Also, you have the check running everytime you fill the index so it is checking a bunch of 0 to other 0s. Need to close off the first initialization for loop, before going into the 2 for loops that check to see if values are the same.

--- Update ---

Also, if you include the if (d1 == d2) in the initial for loop, then call break. It is breaking out of the for loop, and leaving the rest as 0's.

--- Update ---

Rewriting those mistakes and changing a couple of things around... my output is

(sample)
d1: 2 d2: 5
Sum is: 7
index is: 0
d1: 2 d2: 1
Sum is: 3
index is: 1
d1: 6 d2: 4
Sum is: 10
index is: 2
d1: 6 d2: 5
Sum is: 11
index is: 3
d1: 3 d2: 4
Sum is: 7
index is: 4
d1: 4 d2: 2
Sum is: 6
index is: 5
d1: 2 d2: 3
Sum is: 5
index is: 6
d1: 3 d2: 2
Sum is: 5
index is: 7
d1: 4 d2: 6
Sum is: 10
index is: 8
d1: 3 d2: 4
Sum is: 7
index is: 9
These two indices match 0, 9
These two indices match 0, 4
These two indices match 2, 8
These two indices match 4, 9
These two indices match 6, 7
You win

I was thinking the same thing about closing off the first for loop. The way I have it, the for loop is checking the current sum against each previous sum for a match, except on the first roll there will be nothing to match to except itself. I need to figure out a way to start checking for a previous match starting on the second roll. Also, if I close off the first for loop before initializing the 2nd and 3rd for loop, won't that cause an error? Because I have to check all previous indices in the array before going into the next iteration of the loop. If I put the other for loops outside of the first for loop, they won't be able to check every iteration.

I was thinking the same thing about closing off the first for loop. The way I have it, the for loop is checking the current sum against each previous sum for a match, except on the first roll there will be nothing to match to except itself.

That is not correct. The initial values of the array are all 0's so it checks all 10 numbers to see if they match. Here is an example output after the first roll.

----------------
d1: 4
d2: 6
 
Sum is:      10
index is:    0
 
The following indices have values that match: 
1, 9     
1, 8     
1, 7     
1, 6     
1, 5     
1, 4     
1, 3     
1, 2     
2, 9     
2, 8     
2, 7     
2, 6     
2, 5     
2, 4     
2, 3     
3, 9     
3, 8     
3, 7     
3, 6     
3, 5     
3, 4     
4, 9     
4, 8     
4, 7     
4, 6     
4, 5     
5, 9     
5, 8     
5, 7     
5, 6     
6, 9     
6, 8     
6, 7     
7, 9     
7, 8     
8, 9

They all match cause they are all 0. If you want to start checking immediately, then you need a resizing array, or something similar. Vector<Integer> would work.

Vector<Integer> sumArray = new Vector<Integer>();
 
sumArray.add(sum);
.....
 
// You would need to replace the sumArray.length() with sumArray.size()
// And index values are retrieved by sumArray.get(k) or .get(j)

I tried using Vector<Integer> but I'm still having problems matching the sum to every value in the container.

public static void main(String[] args) {
 
 
	Vector<Integer> sumArray = new Vector<Integer>();
 
 
		for (int i = 0; i < 10; i++) {
			int d1 = roll();
			int d2 = roll();
		    int sum = d1 + d2;
		    sumArray.add(sum);
			System.out.println("d1: " + d1 + " d2: " + d2);
			System.out.println("Sum is:      " + sum);
 
 
			if (d1 == d2) {
				System.out.println("You lose!");
				break;
			}
			 else if (sumArray.equals(sum)){
 
				   System.out.println("You win!");
				   break;
 
			   }}}

Shouldn't my equals() method detect any duplicate in the container?

The .equals method checks to see if two objects are the same exact object (pointer to the same place in memory). This is not the same thing done by the == operator

I see. I'm looking at the API and I don't see any other method that can find a duplicate. Is there another way?

Originally Posted by jps

... the == operator

If I remember correctly you were using this the first time around. I have not been following this thread very closely, but aren't you trying to generate two integers (die roll) and compare the values? If you stored them as objects, (you did, they are boxed in the Integer class) you can unbox them to compare the values with the == method or you can use the compareTo method of the Integer class

How do you unbox?

Read the API for the Integer class. Search keywords java autoboxing.

I liked the way this program was looking when it was dealing with int[] rather than Vector<Integer>, but either way can work. If you are going to go with the Vector<Integer> route I suggest (again) you use the method suggested in post#16. If you are going to box them to store them and unbox them to compare them with ==, you might just as well store them as int[] instead. But I wouldn't mix the two ways.