Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 18 of 18

Thread: How To Use Linear Search

  1. #1
    Junior Member
    Join Date
    Apr 2013
    Location
    San Francisco, CA
    Posts
    16
    Thanks
    1
    Thanked 1 Time in 1 Post

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


  2. #2
    Super Moderator jps's Avatar
    Join Date
    Jul 2012
    Posts
    2,642
    My Mood
    Daring
    Thanks
    90
    Thanked 262 Times in 231 Posts

    Default Re: How To Use Linear Search

                   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.

  3. #3
    Junior Member
    Join Date
    Apr 2013
    Location
    San Francisco, CA
    Posts
    16
    Thanks
    1
    Thanked 1 Time in 1 Post

    Default Re: How To Use Linear Search

    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!

  4. #4
    Super Moderator jps's Avatar
    Join Date
    Jul 2012
    Posts
    2,642
    My Mood
    Daring
    Thanks
    90
    Thanked 262 Times in 231 Posts

    Default Re: How To Use Linear Search

    Quote Originally Posted by Semion View Post
    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?

  5. #5
    Junior Member
    Join Date
    Apr 2013
    Location
    San Francisco, CA
    Posts
    16
    Thanks
    1
    Thanked 1 Time in 1 Post

    Default Re: How To Use Linear Search

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

  6. #6
    Member
    Join Date
    May 2013
    Posts
    33
    Thanks
    0
    Thanked 9 Times in 9 Posts

    Default Re: How To Use Linear Search

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

  7. #7
    Junior Member
    Join Date
    Apr 2013
    Location
    San Francisco, CA
    Posts
    16
    Thanks
    1
    Thanked 1 Time in 1 Post

    Default Re: How To Use Linear Search

    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!

  8. #8
    Member
    Join Date
    May 2013
    Posts
    33
    Thanks
    0
    Thanked 9 Times in 9 Posts

    Default Re: How To Use Linear Search

    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

  9. #9
    Junior Member
    Join Date
    Apr 2013
    Location
    San Francisco, CA
    Posts
    16
    Thanks
    1
    Thanked 1 Time in 1 Post

    Default Re: How To Use Linear Search

    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!

  10. #10
    Member
    Join Date
    May 2013
    Posts
    33
    Thanks
    0
    Thanked 9 Times in 9 Posts

    Default Re: How To Use Linear Search

    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

  11. #11
    Junior Member
    Join Date
    Apr 2013
    Location
    San Francisco, CA
    Posts
    16
    Thanks
    1
    Thanked 1 Time in 1 Post

    Default Re: How To Use Linear Search

    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.

  12. #12
    Member
    Join Date
    May 2013
    Posts
    33
    Thanks
    0
    Thanked 9 Times in 9 Posts

    Default Re: How To Use Linear Search

    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)

  13. #13
    Junior Member
    Join Date
    Apr 2013
    Location
    San Francisco, CA
    Posts
    16
    Thanks
    1
    Thanked 1 Time in 1 Post

    Default Re: How To Use Linear Search

    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?

  14. #14
    Super Moderator jps's Avatar
    Join Date
    Jul 2012
    Posts
    2,642
    My Mood
    Daring
    Thanks
    90
    Thanked 262 Times in 231 Posts

    Default Re: How To Use Linear Search

    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

  15. #15
    Junior Member
    Join Date
    Apr 2013
    Location
    San Francisco, CA
    Posts
    16
    Thanks
    1
    Thanked 1 Time in 1 Post

    Default Re: How To Use Linear Search

    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?

  16. #16
    Super Moderator jps's Avatar
    Join Date
    Jul 2012
    Posts
    2,642
    My Mood
    Daring
    Thanks
    90
    Thanked 262 Times in 231 Posts

    Default Re: How To Use Linear Search

    Quote Originally Posted by jps View Post
    ... 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

  17. #17
    Junior Member
    Join Date
    Apr 2013
    Location
    San Francisco, CA
    Posts
    16
    Thanks
    1
    Thanked 1 Time in 1 Post

    Default Re: How To Use Linear Search

    How do you unbox?

  18. #18
    Super Moderator jps's Avatar
    Join Date
    Jul 2012
    Posts
    2,642
    My Mood
    Daring
    Thanks
    90
    Thanked 262 Times in 231 Posts

    Default Re: How To Use Linear Search

    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.

Similar Threads

  1. Linear Search / Index Location of Strings
    By xJavaLover in forum What's Wrong With My Code?
    Replies: 7
    Last Post: February 8th, 2013, 06:11 AM
  2. Code for Linear & Binary Search using ArrayLists
    By JavaBeginner12 in forum Java Theory & Questions
    Replies: 2
    Last Post: December 11th, 2012, 08:22 AM
  3. [SOLVED] Linear array search(without Arraylist)
    By Usoda in forum What's Wrong With My Code?
    Replies: 9
    Last Post: November 18th, 2011, 12:12 AM
  4. [SOLVED] Help with array of Strings...Linear Search?
    By Stockholm Syndrome in forum Collections and Generics
    Replies: 4
    Last Post: March 22nd, 2011, 03:31 PM
  5. Linear Equation Help !!!
    By thangavel in forum Algorithms & Recursion
    Replies: 1
    Last Post: January 13th, 2011, 05:32 AM