Project Euler#22: Names scores

Approach

• Read The File.
• Make a String Array and store the data in it.
• Sort using a custom algorithm or using the in-built library functions.
• Iterate through each element and multiply it’s sum value by it’s index.
• Sum those.

Code

		String[] mStringArray = TextFileReader.getText(22).replaceAll("\"|\n", "").split(",");
		Arrays.sort(mStringArray);
		long mTotalSum = 0;
		int mIndex = 0;
		for (String mWord : mStringArray) {
			++mIndex;
			char[] ch = mWord.toCharArray();
			int mNameSum = 0;
			for (char y : ch) {
				mNameSum += y - 'A' + 1;
			}
			mTotalSum += mNameSum * mIndex;
		}
		return mTotalSum;

Result: Answer is 871198282, Time taken 0.053 seconds

Project Euler#21: Amicable Numbers

Approach

We loop through all numbers and find and , we also implement a cache which works on the principle that amicable number occurs in pairs, so if a number is amicable it’s conjugate is also and we don’t need to check it again, therefore we add both the numbers only once and decrease running time. Also the amicable numbers can’t be primes obviously. Suppose a number can be written in the form of (where ‘s are prime numbers):

Then sum of its factors can be written as (Convince yourself that every product collected is actually a factor of x):

Code

		int mSum = 0;
		final int mLimit = 10000;
		sievePrimes(mLimit);
		boolean[] checked = new boolean[mLimit];
		for (int a = 220; a < 1E4; a++) {
			if (!checked[a] && !isPrime(a)) {
				int b = getDivisorSum(a)-a;
				if (b > mLimit)
					continue;
				checked[b] = true;
				int c = getDivisorSum(b)-b;
				if (c == a && a != b) {
					mSum += a + b;
				}
			}
		}
		return mSum;

		int num;
		int sum = 1;
		for (int i = 2; i <= n; i==2; i += ((i == 2) ? 1 : 2)) {
			if (isPrime(i)) {
				if (n % i == 0) {
					num = i * i;
					n = n / i;
					while (n % i == 0) {
						num = num * i;
						n = n / i;
					}
					sum *= (num - 1) / (i - 1);
				}
			}
		}
		return sum;

Result: Answer is  31626, Time taken 0.470 seconds

Project Euler#20: Factorial digit sum

Approach

Another use of BigInteger(s), pretty simple. Keep multiplying by its predecessor until we reach one.

Code

		BigInteger mNum = BigInteger.valueOf(100);
		BigInteger mFactorial = BigInteger.ONE;
		do {
			mFactorial = mFactorial.multiply(mNum);
			mNum = mNum.subtract(BigInteger.ONE);
		} while (mNum.compareTo(BigInteger.ONE) == 1);
		char[] mCharArray = mFactorial.toString().toCharArray();
		long mSum = 0;
		for (char a : mCharArray) {
			mSum += a - '0';
		}
		return mSum;

Result: Answer is  648, Time taken 0.002 seconds

Project Euler#19: Counting Sundays

Approach

Let me explain a short trick to get the day of the week from it’s date, wherever it falls very quickly.

Basic concepts:

• Odd Days: The number of days exceeding the complete number of weeks in a duration is the number of odd days during that duration.
• Ordinary Year: has 365 days.
• Leap Year: has 366 days. Two kinds of leap years are:
  • Every year divisible by 4. (for non century years) e.g. 1212,2016,etc.
  • Every year divisible by 400. (for century years) e.g. 1200,1600,etc.

Counting Of Odd Days:

Total days between a duration modulo 7 is equal to the odd days, some to-be-learnt facts are:

• Normal year: days.
• Leap year: days.
• 100 years: These are equivalent to 76 ordinary years and 24 leap years (The year 100 is not a leap year). So total odd days are .
• 200 years:  odd days.
• 300 years:  odd days.
• 400 years:  odd days. (1 is added for the leap year 400)
• In a normal year, Jan, Mar, May, July, Aug, Oct, Dec have days and rest have days, except Feb which has days. In a leap year, Feb has days.

Example:

Let’s calculate the day at 9-Jun-2015, the date on which the post was written.

• 
• (2015 is not a leap year).
• Total odd days are :
• Now Sunday corresponds to 0, Monday to 1 and so on. Thus the day would be Tuesday, and indeed it is.

Computer Optimized Approach

The above approach is meant for humans, but computers are indeed fast and rather than delving into too much complexity, computers can easily find the day using the approach (from Wikipedia: Determination of the day of the week).

Code

		int sum = 0;
		for (int i = 1901; i <= 2000; i++) {
			for (int j = 1; j <= 12; j++) {
				sum += Helper.getDay(1, j, i) == 0 ? 1 : 0;
			}
		}
		return sum;

		public static Days getDay(int d, int m, int y) {
		d += (m < 3) ? y-- : y - 2;
		return [(23 * m / 9 + d + 4 + y / 4 - y / 100 + y / 400) % 7];
		}

Result: Answer is …

Project Euler#18: Maximum path sum I

Prerequisites/Approach

This problem made me implement some complex depth-first-search for the first time. This time my code is rather well explained. However the pseudocode for it is explained well at Wikipedia:

Recursive

1  procedure DFS(G,v):
2      label v as discovered
3      for all edges from v to w in G.adjacentEdges(v) do
4          if vertex w is not labeled as discovered then
5              recursively call DFS(G,w)

Non-Recursive

1  procedure DFS-iterative(G,v):
2      let S be a stack
3      S.push(v)
4      while S is not empty
5            v = S.pop() 
6            if v is not labeled as discovered:
7                label v as discovered
8                for all edges from v to w in G.adjacentEdges(v) do
9                    S.push(w)

Code

(to be updated with improved version, soon)

		String[] s = getText(18).split("s");
		int[] a = stringArraytoIntArray(s);
		Stack<Integer> stackOfindices = new Stack<Integer>();
		// stack of indices (actually the path of indices)
		final int maxdepth = 15;
		final int size = maxdepth * (maxdepth + 1) / 2;
		boolean[] treaded = new boolean[size];
		// treaded or not?
		Arrays.fill(treaded, false);// not travelled anywhere
		int max = 1;// maximum is greater than 1
		int depth = 0;// depth to which we have reached
		int sum = a[0];// present sum
		stackOfindices.push(0);// pushing the index 0
		treaded[0] = true;// travelled index 0
		boolean shouldadd = true;// used whether to return or whether add to sum
								 // the present number
		// loop:
		do {
			++depth;// enter a depth
			if (depth != maxdepth) {
				// choose an undiscovered branch and add to sum while pushing to
				// stack
				// two paths possible 0,+1
				for (int i = 0; i <= 2; i++) {// trying children
					if (i == 2) {// if last children
						if (stackOfindices.peek() == size) {
							return max;
						}
						// clearing mechanism which clears treaded array for
						// entries children since we would be reaching some of
						// these children maybe
						// later through different paths and we then want these
						// to be treated as untreaded
						for (int j = 0; j <= 1; j++) {// clear each index of
													  // children
							int clearindex = stackOfindices.peek() + depth + j;
							treaded[clearindex] = false;
						}
						depth -= 2;// now move 2 steps up (since we will dive a
								   // step at the start so total -1)
						sum -= a[stackOfindices.peek()];// subtract from sum
						stackOfindices.pop();// remove current index
						shouldadd = false;// do not add but return
						break;
					}
					int tryindex = stackOfindices.peek() + depth + i;
					// try these index if not the last one
					if (!treaded[tryindex]) {
						stackOfindices.push(tryindex);// push
						treaded[stackOfindices.peek()] = true;// traversed
						shouldadd = true;// add the number
						break;
						// if found a treadable branch exit checking for a new
						// index

					}

				}
				// add to sum
				if (shouldadd) {
					sum += a[stackOfindices.peek()];
				}

			} else {
				if (stackOfindices.peek() == (size - 1)) {
					break;
				}
				// when no further check with max
				if (sum > max) {
					// System.out.println("="+max);
					max = sum;
				}
				// step back and subtract
				depth -= 2;
				// since it is going to be increased by one at the start of loop
				sum -= a[stackOfindices.peek()];
				stackOfindices.pop();
			}
		} while (true);
		return max;

Result: Answer is  1074, Time taken 0.128 seconds

Project Euler#17: Number letter counts

Approach

In this problem, I thought I can make my own word speller, which might be useful later on to me. The logic is pretty simple and it uses recursion. It works in this way:

• For 1 to 19 we actually explicitly give number names.
• For 20 to 99, we split the spelling into two parts, e.g. for 23, we take 20 from already given value and recursively use spell for 3. We also make sure, if second part is empty, we don’t end up in Twenty zero, rather make no call.
• Similarly we can add more digits – hundreds, thousands and so on.

Code

	long mSum = 0;
	for (int i = 1; i <= 1000; i++) {
		String x = spell(i);
		x = x.replaceAll("s|-", "");
		mSum += x.length();
	}
	return mSum;

        public static String spell(int i) { // current limit 0-9999
		final String[] ones = { "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten", "eleven", "twelve",
				"thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen" };
		final String[] tens = { "twenty", "thirty", "fourty", "fifty", "sixty", "seventy", "eighty", "ninety" };
		if (0 <= i && i <= 19) {
			return ones[i];
		} else if (20 <= i && i <= 99) {
			return tens[(i / 10) - 2] + ((i % 10 == 0) ? "" : "-" + spell(i % 10));
		} else if (100 <= i && i <= 999) {
			return spell(i / 100) + " hundred" + ((i % 100 != 0) ? " and " + spell(i % 100) : "");
		} else if (1000 <= i && i <= 9999) {
			return spell(i / 1000) + " thousand " + ((i % 1000 != 0) ? spell(i % 1000) : "");
		}
		throw new IllegalArgumentException("Out Of Range");
	}

Result: Answer is 21124, Time taken 0.148 seconds

Project Euler#16: Power digit sum

Approach

Use the same data type you used to solve “Project Euler#13: Large sums“. It won’t take much time.

Code

		final int mBase = 2;
		final int mPower = 1000;
		BigInteger mNum = BigInteger.valueOf(mBase).pow(mPower);
		String mNumstring = String.valueOf(mNum);
		char[] mCharArray = mNumstring.toCharArray();
		int mSum = 0;
		for (char c : mCharArray) {
			mSum += c - '0';
		}
		return mSum;

Result: Answer is 1366, Time taken 0.010 seconds

Project Euler#15: Lattice Paths

Approach

This is pretty simple if you look at it mathematically. Starting with top left node we need to go to the bottom right node. The Manhattan distance is 40 units. At any point we can move right or we can move down. We denote right by R and down by D. The possible choices when joined together form a string like “RDRRDDD…” So we have a string of length 40 and we need to choose 20 places for R and 20 for D which can be easily done in this way:

Actually this is also the total number of ways of arranging 40 object in which 20 and 20 are identical (R and D). This is pretty basic to calculate:

Code

		final int mEdge = 20;
		long mResult = (long) Math.pow(2, 10);
		for (int i = 1; i <= 10; i++) {
			mResult *= ((mEdge - 1) + (2 * i));
			mResult /= i;
		}
		return mResult;

Result: Answer is 137846528820, Time taken 0.001 seconds

Project Euler#14: Longest Collatz sequence

Approach

The standard approach would be to loop through each number and in a do-while loop find how long is the chain length. But this can also be improved by using an cache, i.e. when the number in the current chain falls below the original number, add the length of the smaller number to current length and break off. Make sure to feed the chain lengths after each loop. Rest is pretty standard or simple programming.

Code

		int mMax = 1;
		int mMaximumChainLength = 1;
		final int mLimit = 1000000;
		int[] mCollatzLengthCache = new int[mLimit];

		for (int i = 2; i < mLimit; i++) {
			long j = i;//we don't wanna mess up i
			int mCollatzLength = 0;
			do {
				++mCollatzLength;
				if ((j & 1) == 0) {
					j >>= 1;
					if (j < i) {
						mCollatzLength += mCollatzLengthCache[(int) j];
						break;
					}
				} else {
					j = 3 * j + 1;
				}
			} while (true);
			mCollatzLengthCache[i] = mCollatzLength;
			if (mCollatzLength > mMax) {
				mMax = mCollatzLength;
				mMaximumChainLength = i;
			}
		}
		return mMaximumChainLength;

Result: Answer is 837799, Time taken 0.172 seconds

Project Euler#13: Large sum

Approach

Pretty simple, just do what you are told by using a suitable data type, or creating one of your own by using an array. Such a class would be useful in further problem too. Here are some of the useful ones:

• Java has “BigInteger”.
• High level languages like Python, already have such integrated.
• With C, we can use GNU BigNum Library.

Code

		BigInteger mResult = BigInteger.ZERO;
		String[] a = getText(13).split("s");
		for (int i = 0; i < a.length; i++) {
			mResult = mResult.add(new BigInteger(a[i]));
		}
		return Long.parseLong(String.valueOf(mResult).substring(0, 10));

Result: Answer is 5537376230, Time taken 0.105 seconds