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

[FiasseKrystella]

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 :

  








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

[Norm]

I still get NullPointerException

Post the full text of the error message if you need help fixing the problem.

[FiasseKrystella]

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.

[Norm]

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.

[Fubarable]

Have a look here:

                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]

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 =)

[Fubarable]

You're welcome!