Project Euler – Problem # 19 – Solved with Go

How many Sundays fell on the first of the month during the twentieth century?

You are given the following information, but you may prefer to do some research for yourself.

  • 1 Jan 1900 was a Monday.
  • Thirty days has September,
    April, June and November.
    All the rest have thirty-one,
    Saving February alone,
    Which has twenty-eight, rain or shine.
    And on leap years, twenty-nine.
  • A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

Problem:

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

**********

To solve this problem, I just ported my python solution to Go.

One Possible Solution: Go

package main

import "fmt"

func main() {
	fmt.Println("Hello, playground")

	L := make(map[int]string)

	L[1] = "Sun"
	L[2] = "Mon"
	L[3] = "Tue"
	L[4] = "Wed"
	L[5] = "Thurs"
	L[6] = "Fri"
	L[7] = "Sat"

	// Start at Monday, 1st, 1900
	counter := 1
	tally := 0

	for yr := 1900; yr < 2001; yr++ {	// Year
		fmt.Printf("Year = %d\n", yr)

		for month := 1; month < 13; month++ {	//  Month
			y := find_days(month, yr)
			for month_days := 1; month_days <= y; month_days++ {	// Number of month days
				// Start at Monday, 1st, 1900
				counter += 1
				if month_days == 1 && L[counter] == "Sun" {
					fmt.Printf("month_days = %d L[counter] = %s\n", month_days, L[counter])
					tally += 1
				}
				if counter >= 7 {	// Days of the week
					counter = 0
				}
			}
		}
		fmt.Printf("\n")
	}
	// subtract 2 for the year 1900
	fmt.Println("Tally = ", tally-2)
}

func find_days(month int, yr int) int {
	d := 0
	if (month == 1) || (month == 3) || (month == 5) || (month == 7) || (month == 8) || (month == 10) || (month == 12) {
		d = 31
	} else if (month == 4) || (month == 6) || (month == 9) || (month == 11) {
		d = 30
	} else if month == 2 {
		if yr%4 == 0 {
			if yr%100 == 0 {
				if yr%400 == 0 {
					d = 29
				} else {
					d = 28
				}
			} else {
				d = 29
			}
		} else {
			d = 28
		}
	} else {
		fmt.Println("There has been an error")
	}
	return d
}
Advertisements

Project Euler – Problem # 19 – Solved with Java

How many Sundays fell on the first of the month during the twentieth century?

You are given the following information, but you may prefer to do some research for yourself.

  • 1 Jan 1900 was a Monday.
  • Thirty days has September,
    April, June and November.
    All the rest have thirty-one,
    Saving February alone,
    Which has twenty-eight, rain or shine.
    And on leap years, twenty-nine.
  • A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

Problem:

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

**********

To solve this problem, I just ported my python solution to java.

One Possible Solution: Java

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


public class Problem_19 {
	public static void main(String args[]){
		Map<Integer, String> L = new HashMap<Integer, String>();
		L.put(1, "Sun");
		L.put(2, "Mon");
		L.put(3, "Tue");
		L.put(4, "Wed");
		L.put(5, "Thurs");
		L.put(6, "Fri");
		L.put(7, "Sat");
		
		// Start at Monday, 1st, 1900
		int counter = 1;
		int tally = 0;
		
		// Year
		for (int yr = 1900; yr < 2001; yr ++)
		{
			System.out.println("Year = " + yr);
			// Month
			for (int month = 1; month < 13; month ++)
			{
				int y = find_days(month, yr);
				for (int month_days = 1; month_days <= y; month_days ++) // Number of month days
				{
					// Start at Monday, 1st, 1900
					counter += 1;
					if ((month_days == 1) && (L.get(counter) == "Sun"))
					{
						System.out.println("month_days = " + month_days);
						tally += 1;
					}
					// Days of the week
					if (counter >= 7)
					{
						counter = 0;
					}
				}
			}
			System.out.println();
		}
		// subtract 2 for the year 1900 - start counting at 1901
		System.out.println("tally = " + (tally - 2));
	}
	public static int find_days(int month, int yr){
		int d = 0;
		if ((month == 1) || (month == 3) || (month == 5) || (month == 7) ||
		(month == 8) || (month == 10) || (month == 12))
		{
			d = 31;
		}
		else if ((month == 4) || (month == 6) || (month == 9) || (month == 11))
		{
			d = 30;
		}
		else if ((month == 2))
		{
			if (yr % 4 == 0)
			{
				if (yr % 100 == 0)
				{
					if (yr % 400 == 0)
					{
						d = 29;
					}
					else
					{
						d = 28;
					}
				} 
				else
				{
					d = 29;
				}
			}
			else
			{
				d = 28;
			}
		}
		else
		{
			System.out.println("There has been an error");
		}
		return d;
	}
}

Project Euler – Problem # 17 – Solved with Go

How many letters would be needed to write all the numbers in words from 1 to 1000?

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of “and” when writing out numbers is in compliance with British usage.

**********

I basically just ported my python solution to Go.

One Possible Solution: Go

package main

import "fmt"
import "strconv"

func main() {
	fmt.Println("Hello, playground")

	number := make(map[int]string)

	number[1] = "one"
	number[2] = "two"
	number[3] = "three"
	number[4] = "four"
	number[5] = "five"
	number[6] = "six"
	number[7] = "seven"
	number[8] = "eight"
	number[9] = "nine"
	number[10] = "ten"
	number[11] = "eleven"
	number[12] = "twelve"
	number[13] = "thirteen"
	number[14] = "fourteen"
	number[15] = "fifteen"
	number[16] = "sixteen"
	number[17] = "seventeen"
	number[18] = "eighteen"
	number[19] = "nineteen"
	number[20] = "twenty"
	number[30] = "thirty"
	number[40] = "forty"
	number[50] = "fifty"
	number[60] = "sixty"
	number[70] = "seventy"
	number[80] = "eighty"
	number[90] = "ninety"
	number[100] = "hundred"
	number[1000] = "thousand"

	tally := 0
	k := 0

	for n := 1; n <= 1000; n++ {
		x := strconv.FormatInt(int64(n), 10)
		if len(x) == 1 {
			// The first 9 numbers are 1 digit -- in the dictionary
			k = len(number[n])
			fmt.Printf("n = %d k = %d\n", n, k)
		} else if len(x) == 2 {
			x1 := x[0:1]
			x2 := x[1:2]
			x2_i, _ := strconv.Atoi(x2)
			if n < 20 {
				k = len(number[n])
				fmt.Printf("n = %d k = %d\n", n, k)
			} else {
				if x2 == "0" {
					// The numbers under 100 and greater than 19 -- in the 
					// dictionary ending in '0', (20, 30, 40 ....)
					k = len(number[n])
					fmt.Printf("n = %d k = %d\n", n, k)
				} else {
					// The other numbers under 100 greater than 19
					x1a := x1 + "0"
					x1a_i, _ := strconv.Atoi(x1a)
					k = len(number[x1a_i]) + len(number[x2_i])
					fmt.Printf("n = %d k = %d\n", n, k)
				}
			}
		} else if len(x) == 3 {
			// add 3 for 'and' i.e. -- two-hundred and ten
			x1 := x[0:1]
			x2 := x[1:2]
			x3 := x[2:3]
			x1a := x2 + "0"
			x1aa := x2 + x3

			x1_i, _ := strconv.Atoi(x1)
			x3_i, _ := strconv.Atoi(x3)
			x1a_i, _ := strconv.Atoi(x1a)
			x1aa_i, _ := strconv.Atoi(x1aa)

			if x1 == "1" && x2 == "0" && x3 == "0" {
				// 100 -- in the dictionary
				k = len(number[1]) + len(number[100])
				fmt.Printf("n = %d k = %d\n", n, k)
			} else if x2 == "0" && x3 == "0" {
				// Consider 200, 300, 400, 500, 600, 700, 800, and 900
				k = len(number[x1_i]) + len(number[100])
				fmt.Printf("n = %d k = %d\n", n, k)
			} else if x2 == "0" && x3 != "0" {
				// Consider 101, 102 ... 109, 201, 202, ... 209 etc.
				k = 3 + len(number[x1_i]) + len(number[100]) + len(number[x3_i])
				fmt.Printf("n = %d k = %d\n", n, k)
			} else if x2 != "0" && x3 == "0" {
				// Consider 110, 120, ... 190, 210, 220, ... 290 etc.
				k = 3 + len(number[x1_i]) + len(number[100]) + len(number[x1a_i])
				fmt.Printf("n = %d k = %d\n", n, k)
			} else if x2 == "1" && x3 != "0" {
				// Consider the teens 111, 112, ... 119, 211, 212, ... 219 etc.
				k = 3 + len(number[x1_i]) + len(number[100]) + len(number[x1aa_i])
				fmt.Printf("n = %d k = %d\n", n, k)
			} else {
				// Consider all the other numbers
				k = 3 + len(number[x1_i]) + len(number[100]) + len(number[x1a_i]) + len(number[x3_i])
				fmt.Printf("n = %d k = %d\n", n, k)
			}

		} else {
			// 1000 -- two parts (one and thousand) -- in the dictionary
			k = len(number[1]) + len(number[1000])
			fmt.Printf("n = %d k = %d\n", n, k)
		}
		tally += k

	}
	fmt.Println(tally)
}

Project Euler – Problem # 17 – Solved with Java

How many letters would be needed to write all the numbers in words from 1 to 1000?

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of “and” when writing out numbers is in compliance with British usage.

**********

I basically just ported my python solution to java.

One Possible Solution: Java

Project Euler – Problem # 16 – Solved with Go

What is the sum of the digits of the number 21000?

215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 21000?

One Possible Solution: Go

package main

import "fmt"
import "math/big"
import "strings"
import "strconv"

func main() {

	x := big.NewInt(2)
	y := big.NewInt(1000)
	z := big.NewInt(0)

	result := new(big.Int).Exp(x, y, z)		// result is a 302 digit big.Int
	string_result := result.String()		// convert result to a string
	numbers := strings.Split(string_result, "")	// split the string

	Answer := 0
	for _, number := range numbers {	// enumerate thru the string of numbers
		x, _ := strconv.Atoi(number)	// convert string to an integer
		Answer += x			// add the individual integer to the Answer
	}

	fmt.Println(Answer)
}

Project Euler – Problem # 16 – Solved with Java

What is the sum of the digits of the number 21000?

215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 21000?

**********

Helpful Links:

One Possible Solution: Java

import java.math.BigInteger;


public class Problem_16 {
	public static void main(String args[])
	{
		BigInteger result = BigInteger.ZERO;
		BigInteger two = BigInteger.valueOf(2);
		BigInteger one_thousand = BigInteger.valueOf(1000);
		result = pow(two, one_thousand);
		String string_result = new String(result.toString());
		
		int Answer = 0;
		for (int i = 0; i < string_result.length(); i++)
		{
		    Character c = new Character(string_result.charAt(i));
		    String s = c.toString();
		    int n = Integer.parseInt(s);
		    Answer = Answer + n;
		}

		System.out.println(Answer);

	}
	
	public static BigInteger pow(BigInteger base, BigInteger exponent)
	{
		BigInteger result = BigInteger.ONE;
		while (exponent.signum() > 0)
		{
			if (exponent.testBit(0)) result = result.multiply(base);
		    base = base.multiply(base);
		    exponent = exponent.shiftRight(1);
		}
		  return result;
	}

}

Project Euler – Problem # 16 – Solved with Python

What is the sum of the digits of the number 21000?

215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 21000?

**********

Python makes this easy – there is no special handling for Big integers. In this problem, it is 302 digits long.

One Possible Solution: Python

# Python version = 2.7.2
# Platform = win32

def main():
    """Main Program"""
    result = 2 ** 1000
    string_result = str(result)

    Sum = 0
    for number in string_result:
        Sum = Sum + int(number)
        
    print Sum

if __name__ == '__main__':
    main()

Project Euler – Problem # 15 – Solved with Go

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’. In order to solve this problem, I asked a question about creating a big.Int factorial in go on Stackoverflow.

                 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: Go – uses recursion for the factorial function

package main

import "fmt"
import "math/big"

func main() {

	n := big.NewInt(40)	// The total number of moves for any one path (right + down)
	r := big.NewInt(20)	// The total number of right moves for any one path

	t := big.NewInt(0).Sub(n, r)				// Part of Denominator
	x := big.NewInt(0).Mul(factorial(r), factorial(t))	// The complete Denominator
	Answer := big.NewInt(0).Div(factorial(n), x)		// Divide the Numerator by the Denominator

	fmt.Println(Answer)

}

func factorial(n *big.Int) (result *big.Int) {
	// This function finds the factorial of a number. For example: 5! = 5 * 4 * 3 * 2 * 1 = 120

	b := big.NewInt(0)
	c := big.NewInt(1)

	if n.Cmp(b) == -1 {
		result = big.NewInt(1)
	}
	if n.Cmp(b) == 0 {
		result = big.NewInt(1)
	} else {
		result = new(big.Int)
		result.Set(n)
		result.Mul(result, factorial(n.Sub(n, c)))
	}
	return
}

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)) ) );
			}
	}
}

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