Monthly Archive for December, 2009

Problem number 14 of Project Euler gave a sequence.

n = n/2 if (n is even)

n = 3*n+1 (if n is odd)

It has been observed that all the numbers in this sequence do end up at 1, though this is yet to be proved! For example, if we consider the number 13, then the sequence pans out as

13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

The length of the sequence in this case is 9. The challenge was to find the largest starting number below 1 million which produces the maximum length sequence. Do note that intermediate numbers might cross the 1 million mark.

The first thing that struck me was the repetitive nature of the problem. Say we are checking the lengths for every number and we start from 1 upwards. So, by the time we get to 13, we would have already calculated the value of 10. If we remember this value, then the value for 13 effectively becomes 3 + value for 10. Thus memoization can be used to speed up the computation.

But if we remember all the values, we will require a very large array as the number greater than 1 million are bound to occur. An another interesting thing struck me. Consider the number 16. It has only 2 predecessors in the sequence, namely 5 and 32. No other number can land on 16 in one step. So, if I know the values for 5 and 32, I need not know the value for 16 anymore. Also note that we shall not miss the largest sequence value by removing keys like this because its predecessors will have a larger sequence length.

Using these two ideas I implemented a recursive solution to give me the answer. Well, I did get the answer but the time taken was large. It took 3845ms to get the answer.

The first modification was to replace the recursive function with an iterative one. This reduced the time taken to just 1907ms. However, the one drawback of moving from a recursive solution to an iterative one was that while in recursive I was able to store the path lengths for intermediate numbers too, in the iterative one I am able to store the results for the starting number only. I suppose if I have a stack of the numbers visited, then I might be able to add their values and consolidate the map so as to remove the unnecessary entries.

At this point, another thing came to my mind. I had used a hash map to remember the already computed values. I remembered Prasun telling me that the jvm allocates a default space to the map, which is as low as 11, if the initial size of the map is not specified. When the number of values being put into the map increases, the map size is readjusted. And since I had not specified any initial size, my map was undergoing all these extra operations. So I went ahead and specified a map of size 1 million. Voila! The time reduced to under 1500ms.

Another couple of observations I made was regarding the size of the map. If I do not optimize the map to contain only the essential entries, then the map is as large as 97000 entries. But with the optimization function that I have used, the size required reduces to 62000. A further modification of calculating the lengths for only odd numbers reduces the map size to just 48500, which is half of the original usage. And since the time invested in periodic optimization of the map contributes to only some 100ms, I think it is a good enough trade off to optimize the entries stored in the map.

All said and done, it is a brute force solution with memoization. I look to better the solution sometime. Below is the code that I have written.

import java.util.HashMap;
import java.util.Map;

import stopwatch.Stopwatch;

public class Problem_14 {
	private static long MAX_NUMBER = 1000000;
	private Map<Long, Integer> m_pathLengths = new HashMap<Long, Integer>((int) (2 * Problem_14.MAX_NUMBER));

	public long getLongestChainStartingNumber() {
		int maxLength = 0;
		long maxLengthStartNumber = -1;

		for (long i = 30001; i < Problem_14.MAX_NUMBER; i += 2) {
			int length = getPathLength(i);
			if (length > maxLength) {
				maxLength = length;
				maxLengthStartNumber = i;
			}
		}
		System.out.println(m_pathLengths.size());

		return maxLengthStartNumber;
	}

	private int getPathLength(Long val) {
		long value = val;
		int pathLength = 0;
		for (; val > 1; pathLength++) {
			if (m_pathLengths.containsKey(val)) {
				pathLength += m_pathLengths.get(val);
				break;
			}
			val = val % 2 == 0 ? val / 2 : 3 * val + 1;
		}
		m_pathLengths.put(value, pathLength);
		optimiseMap(value);

		return pathLength;
	}

	private void optimiseMap(long keyAdded) {
		if (keyAdded % 2 == 1) {
			// odd key added.
			// 5 -> 16, 16 can be reached from only 5 or 32
			// 7 -> 22, 22 can be reached from only 7 or 44
			long keyToBeChecked = 3 * keyAdded + 1;
			if (m_pathLengths.containsKey(2 * keyToBeChecked))
				m_pathLengths.remove(keyToBeChecked);
		} else {
			// even key added.
			// 32 -> 16, 16 can be reached from only 5 or 32
			// 18 -> 9, 9 can be reached from only 18
			long keyToBeChecked = keyAdded / 2;
			if ((keyToBeChecked - 1) % 3 == 0) {
				if (m_pathLengths.containsKey((keyToBeChecked - 1) / 3))
					m_pathLengths.remove(keyToBeChecked);
			} else
				m_pathLengths.remove(keyToBeChecked);
		}
	}

	public static void main(String[] args) {
		Stopwatch stopwatch = new Stopwatch();
		stopwatch.start();
		System.out.println(new Problem_14().getLongestChainStartingNumber());
		stopwatch.stop();
		System.out.println("The reading for operation is: " + stopwatch);
	}
}

Popularity: 13% [?]