Project Euler – Problem # 15 – Solved with Java

Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?

Starting in the top left corner of a 2 x 2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20 x 20 grid?

**********

After doing a bit of research on this problem, it seems as though a simple Combinations formula will provide the answer. We know that any path will have 40 moves (20 right + 20 down), so for C(n,r) – n will equal 40 and r (the number of right moves) will equal 20 – C(40,20). Then we just plug the numbers into the formula – the ! means ‘factorial’. I posted 2 versions of the solution: 1 without recursion – uses a for loop, and one with recursion – the factorial function calls itself.

                 n!
C(n,r) =   ———-
             r!*(n-r)!

The number of how many good routes we have can be found by finding how
many combinations of 20 R’s we can have in our 40 moves, so we want to
calculate:

                    40!
C(40,20) =   ———-
                20!*(40-20)!

Helpful Links:

One Possible Solution: Java – without recursion – (uses a for loop)

import java.math.BigInteger;

public class Problem_15 {
	public static void main(String args[]){
		int n = 40;		// The total number of moves for any one path (right + down)
		int r = 20;		// The total number of right moves for any one path
		
		System.out.println(factorial(n).divide(factorial(r).multiply(factorial(n - r))));
	}
	public static BigInteger factorial( int n1 )
    {
		BigInteger n = BigInteger.ONE;
		for (int i = 1; i <= n1; i ++) {
			n = n.multiply(BigInteger.valueOf(i));			
		}
		return n;
    }

}

One Possible Solution: Java – uses recursion (the factorial method calls itself)

import java.math.BigInteger;


public class Problem_15a {
	public static void main(String args[]){
		BigInteger n = BigInteger.valueOf(40);		// The total number of moves for any one path (right + down)
		BigInteger r = BigInteger.valueOf(20);		// The total number of right moves for any one path
		
		System.out.println(factorial(n).divide(factorial(r).multiply(factorial(n.subtract(r)))));
	}
	
	public static BigInteger factorial( BigInteger n )
	{
			if ( n.compareTo(BigInteger.ZERO) <= 0 ) { // base case
				return BigInteger.ONE;
			}
			else  {  // general case
				return ( n.multiply(factorial ( n.subtract(BigInteger.ONE)) ) );
			}
	}
}
Advertisements

Project Euler – Problem # 15 – Solved with Python

Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?

Starting in the top left corner of a 2 x 2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20 x 20 grid?

**********

After doing a bit of research on this problem, it seems as though a simple Combinations formula will provide the answer. We know that any path will have 40 moves (20 right + 20 down), so for C(n,r) – n will equal 40 and r (the number of right moves) will equal 20 – C(40,20). Then we just plug the numbers into the formula – the ! means ‘factorial’ which is imported from the math class in python.

                 n!
C(n,r) =   ———-
             r!*(n-r)!

The number of how many good routes we have can be found by finding how
many combinations of 20 R’s we can have in our 40 moves, so we want to
calculate:

                    40!
C(40,20) =   ———-
                20!*(40-20)!

Helpful Links:

One Possible Solution: Python

# Python version = 2.7.2
# Platform = win32
# Elapsed Time: 20.9999084473 millisecs

from math import factorial
import time

def main():
    """Main Program"""
    start_time = time.time()

    n = 40      # The total number of moves for any one path (right + down)
    r = 20      # The total number of right moves for any one path

    print factorial(n) / (factorial(r) * factorial(n - r))
    print "Elapsed Time:", (time.time() - start_time) * 1000, "millisecs"

if __name__ == '__main__':
    main()

Project Euler – Problem # 14 – Solved with Go

Problem:

The following iterative sequence is defined for the set of positive integers:

n –> n/2 (n is even)

n –> 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

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

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

package main

import "fmt"

func main() {
	largest := 0
	longest_sequence := 0
	for n := 2; n < 1000000; n++ {

		var (
			Number int64 = 0
		)
		Number = int64(n)
		counter := 1
		for Number > 1 {
			if Number%2 == 0 {
				Number = Number / 2
			} else {
				Number = Number*3 + 1
			}
			counter += 1
		}

		if counter > longest_sequence {
			longest_sequence = counter
			largest = n
		}

	}
	fmt.Println("Answer = ", largest)
	fmt.Println("longest sequence = ", longest_sequence)

}

Project Euler – Problem # 14 – Solved with Java

Problem:

The following iterative sequence is defined for the set of positive integers:

n –> n/2 (n is even)

n –> 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

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

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.


public class Problem_14 {
	public static void main(String args[]){
		long start = System.currentTimeMillis();
		
		int largest = 0;
		int longest_sequence = 0;
		for(int n = 2; n < 1000001; n++){
			long Number = n;
			int counter = 1;
			while(Number > 1){
				if(Number % 2 == 0){
					Number = Number / 2;
				} else{
					Number = (Number * 3) + 1;
				}
				counter += 1;
			}
			
			if(counter > longest_sequence){
				longest_sequence = counter;
				largest = n;
			}
		}
	
		System.out.format("Answer = %d", largest);
		System.out.println();
		System.out.format("longest_sequence = %d ", longest_sequence);
		System.out.println();
		long stop = System.currentTimeMillis();
		System.out.println("Run time = " + (stop - start) + " milliseconds");
	}

}