Project Euler – Problem # 22 – Solved with Go

What is the total of all the name scores in the file of first names?

Using names.txt (right click and ‘Save Link/Target As…’), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 * 53 = 49714.

What is the total of all the name scores in the file?

**********

To solve this problem, I had help with reading the file and making it ready for the program from a stackoverflow question I asked – http://stackoverflow.com/questions/11462879/strings-split-in-golang

One Possible Solution: Go

package main

import "fmt"
import "io/ioutil"
import "strings"
import "sort"

func main() {
	fData, err := ioutil.ReadFile("names.txt")	// read in the external file
	if err != nil {
		fmt.Println("Err is ", err)	// print any error
	}
	strbuffer := string(fData)	// convert read in file to a string

	names := strings.Split(strbuffer, ",")

	for i, val := range names {
		names[i] = strings.Trim(val, "\"")
	}

	sort.Strings(names)

	total := 0

	for i := range names {
		name := names[i]
		letters := strings.Split(name, "")

		x2 := 0
		y := 0

		for m := range letters {
			letter := letters[m]
			x1 := letter_counter(letter)
			x2 += x1
		}
		y = x2 * (i + 1)
		total += y

	}
	fmt.Println(total)

}

func letter_counter(letter string) (lc int) {
	letv := make(map[string]int)

	letv["A"] = 1
	letv["B"] = 2
	letv["C"] = 3
	letv["D"] = 4
	letv["E"] = 5
	letv["F"] = 6
	letv["G"] = 7
	letv["H"] = 8
	letv["I"] = 9
	letv["J"] = 10
	letv["K"] = 11
	letv["L"] = 12
	letv["M"] = 13
	letv["N"] = 14
	letv["O"] = 15
	letv["P"] = 16
	letv["Q"] = 17
	letv["R"] = 18
	letv["S"] = 19
	letv["T"] = 20
	letv["U"] = 21
	letv["V"] = 22
	letv["W"] = 23
	letv["X"] = 24
	letv["Y"] = 25
	letv["Z"] = 26

	lc = letv[letter]

	return lc
}
Advertisements

Project Euler – Problem # 21 – Solved with Go

Problem:

Evaluate the sum of all amicable pairs under 10000.

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a != b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

One Possible Solution: Go

package main

import "fmt"

func main() {
	fmt.Println("Hello, playground")
	tally := 0
	for y := 1; y <= 10000; y++ {
		x := factors(y)
		x1 := get_total(x)
		x3 := factors(x1)
		x4 := get_total(x3)
		if y == x4 && y != x1 {
			tally += y
		}
	}
	fmt.Println(tally)
}

func get_total(factors []int) (number int) {
	total := 0
	for i := 0; i < len(factors); i++ {
		total += factors[i]
	}
	return total
}

func factors(number int) (factors []int) {
	L := make([]int, number)
	counter := 0
	for i := 1; i < ((number / 2) + 1); i++ {
		if number%i == 0 {
			L[counter] = i
			counter += 1
		}
	}
	return L[:counter]

}

Project Euler – Problem # 20 – Solved with Go

Find the sum of digits in 100!

n! means n * (n – 1) * … * 3 * 2 * 1

For example, 10! = 10 * 9 * … * 3 * 2 * 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!

['9332621544394415268169923885626670049071596826438162146859296389521759999
32299156089414639761565182862536979208272237582511852109168640000000000000
00000000000']

So 100! gives you a long number, what the question is asking is to sum each digit in that long number.

package main

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

func main() {

	n := big.NewInt(100)

	result := factorial(n)
	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)
}

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 # 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
}

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 # 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 # 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 # 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 # 13 – Solved with Go

Find the first ten digits of the sum of one-hundred 50-digit numbers.

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

**********

I had to ask two questions on stackoverflow.com to help me solve this problem in Go. Question # 1 was about reading in the external file and getting it into a useable form (string). Question # 2 was about the “math/big” package. For numbers greater than 2147483647, the big package is needed.

One Possible Solution: Go

package main

import "fmt"
import "io/ioutil"
import "strings"
import "math/big"

func main() {
	fData, err := ioutil.ReadFile("one-hundred_50.txt")	// read in the external file
	if err != nil {
		fmt.Println("Err is ", err) 	// print any error
	}
	strbuffer := string(fData)	// convert read in file to a string
	lines := strings.Split(strbuffer, "\n") // split the string into lines
	tally := big.NewInt(0)		// declare and initialise big number tally
	for _, line := range lines {	// loop through each line in lines - 100 of them
		bi := big.NewInt(0)	// declare and  initialise big number bi
		bi.SetString(line, 10) 	// convert line to a big integer (base 10)
		tally.Add(tally, bi)   	// add bi to the tally
	}
	fmt.Println(tally) 	// print tally and use the first 10 digits for the answer
}

Project Euler – Problem # 12 – Solved with Go

What is the value of the first triangle number to have over five hundred divisors?

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Let us list the factors of the first seven triangle numbers:

  • 1: 1
  • 3: 1,3
  • 6: 1,2,3,6
  • 10: 1,2,5,10
  • 15: 1,3,5,15
  • 21: 1,3,7,21
  • 28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

One Possible Solution: Go

package main

import "fmt"
import "math"

func main() {
	counter := 0
	TriangleNumber := 0
	Switch := 1
	for Switch >= 1 {
		counter++
		TriangleNumber += counter
		if factors(TriangleNumber) > 500 {
			fmt.Println(TriangleNumber)
			Switch = 0
		}
	}
}

func factors(n int) (facCount int) {
	facCounter := 0
	k := int(math.Sqrt(float64(n)))
	for i := 1; i < k+1; i++ {
		if n%i == 0 {
			facCounter++
		}
	}
	return facCounter * 2

}