Results 1 to 7 of 7
Like Tree1Likes
  • 1 Post By Fubarable

Thread: Question on memorization......SOS, gonna die >.<

  1. #1
    Join Date
    Aug 2011
    Posts
    16
    Rep Power
    0

    Default Question on memorization......SOS, gonna die >.<

    Hi guys, I'm totally stucked in this question just as I was about to reach the solution....
    Here goes the question:

    Given a positive integer n, prints out the sum of the lengths of the Syracuse sequences starting in the range of 1 to n inclusive. So, for example, the call:
    lengths(3)
    will return the the combined length of the sequences:
    1
    2 1
    3 10 5 16 8 4 2 1
    which is the value: 11. lengths must throw an IllegalArgumentException if its input value is less than one.

    It will usually take a long time to calculate the sum of lengths of the syracuse sequence when its input value n is greater than 500 000. To make it faster we can take advantage of the fact that there is considerable overlap between many sequences.
    For example: if we have already calculated lengths(3) then we must have computed the sequence:
    3 10 5 16 8 4 2 1

    and would, threfore, also have had access to answers to lengths(10),lengths(5), lengths(16),lengths(8),lengths(4),lengths(2), and lengths(1). If we can store at least some of these temporary solutions as we go, and then use them, when possible, then the speed of lengths is greatly increased.
    In a file called SyraLengthsEfficient.java write a new version of lengths that behaves the same way as the lengths from question two above, but is able to work much faster for large numbers by
    memorising some partial solutions.

    This new syraLength and it's encapsulating class must contain the code necessary to remember and recall the values of some intermediate lengths.


    My solution :
    Java Code:
      
    
    
    
    
    
    
    
    
    import java.util.HashMap;
    import java.util.Map;
    import java.util.TreeMap;
    
    public class SyraLengthsEfficient {
    
         HashMap<Integer, Integer> memory = new HashMap<Integer, Integer>();
        // Map<Integer, Integer> memory = new TreeMap<Integer, Integer>();
         public int lengths(int n)throws IllegalArgumentException
        {
            int lengthSum = 0;
            // If n is less than 1, throw an IllegalArgumentException
            if(n < 1)
            {
                throw new IllegalArgumentException();
            }else{
            // Otherwise, call the helper method, syra
                for(int i=0;i<=n;i++)
                {
                    if(memory.get(n)==null)
                    {
                        memory.put(n,syra(n,1)).intValue();
                        lengthSum+=memory.get(n).intValue();
                    } else {
                        lengthSum+=memory.get(n).intValue();
                    }
                }
                return lengthSum;
            }
    
        }
    
        private int syra(int n, int length)
        {
            // If n becomes 1, return the length of the Syracuse sequence.
            if(n==1)
            {
                return length;
            // If n is even, return syra(n/2, ++length)
            } else if(n%2 == 0){
                return syra(n/2, ++length);
             // If n is odd, return syra(n/2, ++length)
            } else {
                return syra((n*3)+1, ++length);
            }
    
        }
    
    }
    I used a combination of for-loop and addition to try to retrieve the values from my hashmap and add the previous computed length onto my lengthSum, so I used .intValue() to convert Integer to int but I still get NullPointerException
    Last edited by FiasseKrystella; 01-29-2012 at 02:46 PM.

  2. #2
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,306
    Rep Power
    25

    Default Re: Question on memorization......SOS, gonna die >.<

    I still get NullPointerException
    Post the full text of the error message if you need help fixing the problem.

  3. #3
    Join Date
    Aug 2011
    Posts
    16
    Rep Power
    0

    Default Re: Question on memorization......SOS, gonna die >.<

    The test code I ran and the output:

    public class Q3Test {

    public static void main(String []args)
    {
    SyraLengthsEfficient s1= new SyraLengthsEfficient();
    System.out.println(s1.lengths(3));
    System.out.println(s1.lengths(5));
    }


    }
    Exception in thread "main" java.lang.NullPointerException
    at SyraLengthsEfficient.lengths(SyraLengthsEfficient. java:30)
    at Q3Test.main(Q3Test.java:15)

    Process completed.

  4. #4
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,306
    Rep Power
    25

    Default Re: Question on memorization......SOS, gonna die >.<

    at SyraLengthsEfficient.lengths(SyraLengthsEfficient. java:30)
    What variable at line 30 in SyraLengthsEfficient is null? Look at that line in the code. If you can't see which variable is null, add a println to print out the values of all the variables used on that line.
    When you find the variable, backtrack in the code to see why it does not have a valid value.

  5. #5
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

    Default Re: Question on memorization......SOS, gonna die >.<

    Have a look here:

    Java Code:
                    if(memory.get(n)==null)  // (A)
                    {
                        memory.put(n,syra(n,1)).intValue(); // (B)
                        lengthSum+=memory.get(n).intValue();
                    } else {
                        lengthSum+=memory.get(n).intValue();
                    }
    If line (A) is true, then your HashMap, memory, has no value assigned to n at the beginning of this block, and so the if block will be entered.

    At line (b), you call put on memory to place a value for the key n, but you also for some unknown reason call .intValue() on that which is returned by the put() method. So what does put return in this case? Let's look at the API:

    the previous value associated with key, or null if there was no mapping for key. (A null return can also indicate that the map previously associated null with key.)
    So since the previous value was null, put returns null, and you're trying to call a method on a null value.

    But why even call this method here when you're just discarding the result? Get rid of that method call .intValue() on that line (B).
    FiasseKrystella likes this.

  6. #6
    Join Date
    Aug 2011
    Posts
    16
    Rep Power
    0

    Default Re: Question on memorization......SOS, gonna die >.<

    Yes it was a careless mistake as I thought the Integer needed to be converted to primitive int. This is my first time using hashmap and I'm quite confused.

    Gonna do more testing now thank you guys =)
    Last edited by FiasseKrystella; 01-29-2012 at 04:16 PM.

  7. #7
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

    Default Re: Question on memorization......SOS, gonna die >.<

    You're welcome!

Similar Threads

  1. Java Question [Beginner Question]
    By joker760 in forum New To Java
    Replies: 3
    Last Post: 12-13-2011, 04:01 PM
  2. question posted by indissa: library question.
    By Fubarable in forum New To Java
    Replies: 2
    Last Post: 11-18-2011, 01:14 AM
  3. Question concerning question marks and colons
    By jim01 in forum New To Java
    Replies: 17
    Last Post: 01-14-2011, 12:05 AM
  4. Question mark colon operator question
    By orchid in forum Advanced Java
    Replies: 9
    Last Post: 12-19-2010, 08:49 AM
  5. Question!
    By anjogomez in forum Java Applets
    Replies: 2
    Last Post: 02-21-2009, 03:24 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •