Skip to content

Instantly share code, notes, and snippets.

@mezcel

mezcel/.gitattributes

Last active December 26, 2020 01:20
Show Gist options
  • Save mezcel/22682a865a4e9d8a2c02877cf1cb7374 to your computer and use it in GitHub Desktop.
Save mezcel/22682a865a4e9d8a2c02877cf1cb7374 to your computer and use it in GitHub Desktop.
Download ZIP
ProjectEuler.net notes
Raw
.gitattributes
## win10 line endins
*.bat eol=crlf
*.ps1 eol=crlf
## Linux/Posix line endins
*.go eol=lf
*.sh eol=lf
*.source eol=lf
Makefile eol=lf
Raw
.gitignore
## ignore vscode settings
.vscode
## ignore builds
*.exe
*.out
main
Raw
README.md

Project Euler

About:

This is my scratch pad and progress bookmark for ProjectEuler.net problems.

  • I am using this to practice and learn Golang. I will look up and implement golang functionalities as I encounter a programming needs.
  • This is fun because after one solves the challenge, one can view the alternative solutions and learn "other ways to skin a cat".

Spoilers !!!

About Project Euler:

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve.

"Project Euler exists to encourage, challenge, and develop the skills and enjoyment of anyone with an interest in the fascinating world of mathematics."

Problems

  • Problems: projecteuler.net/archives

  • Offline copy:

    • Enclosed is golang script which will scrape the probles off the projecteuler.net website for offline use.

    Special math notations (Matlab/LaTex style notations) formatting may not get rendered properly onto the output text file.

Go

For me, this is an exercise in Golang. It is an interesting language because despite it being easier with faster rapid deployment than other mainstream languages, it is slower than others in peculiar areas. Something to do with "parallels and concurrency".

  • play.golang.org
  • run scripts 
    •   ## demo problem 1 solution
  go run problem-01.go
  • make-template.go will generate a blank starter template
    • it will attempt to web scrape the problem statement
    • dependency go get github.com/PuerkitoBio/goquery
  • Go math library: include "math"
    • I initially tried to avoid using it, but it makes more sence to use it.

"Solved" so far

Solutions for the first 100. The site asks users to not publicly share solutions beyond 100 outside of projecteuler.net.

10 20 30 40 50 60 70 80 90 100
1 11
2 12
3
4
5 15
6
7
8
9
10
  • For the problems whose calulations are slow or which have memory constraints, there is also a C equivalent.
    • I am thinking of making multiple language version for the slow ones

Notes

Definitions:

prime numbers

A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers.

natural numbers

positive discrete whole integer numbers, including zero

Pythagorean triples

A Pythagorean triple consists of three positive integers a, b, and c, such that a2 + b2 = c2.

Fibonacci

sequence, such that each number is the sum of the two preceding ones

Misc

Vim notes

  • copy highlighted text to system wide clipboard
    • paste outside of vim
    " highlight and yank the desired chars
:call system("xclip -selection clipboard", @")

"then paste to web browser or text editor
  • mathschallenge.net
Raw
install_goquery.bat
go get github.com/PuerkitoBio/goquery
Raw
install_goquery.sh
#!/bin/bash
go get github.com/PuerkitoBio/goquery
Raw
make-template.go
/*
make-template.go
This is a script which will generate a template Golang script.
It will also attempt to scrape the problem from https://projecteuler.net/problem
You can run it and follow the prompt, or you can enter the new file name as an argument.
Example:
There are 723 problems
If you are starting problem 1, then enter the following.
go run make-template.go -p=01
*/
package main
import (
"flag"
"fmt"
"log"
"net/http"
"os"
"strconv"
"github.com/PuerkitoBio/goquery"
)
func FileExists(filePath string) bool {
if _, err := os.Stat(filePath); err != nil {
if os.IsNotExist(err) {
return false
}
}
return true
}
// Write/Append string to file
func WriteGoFile(goScript string, filePath string) {
f, err := os.OpenFile(filePath,
os.O_CREATE|os.O_WRONLY, 0644)
if err != nil {
log.Println(err)
}
defer f.Close()
if _, err := f.WriteString(goScript); err != nil {
log.Println(err)
}
}
func UserPrompt() string {
var input string
fmt.Println("\nMake a template Golang file.\nThis is a prompt, but the file name can also be inputted as an argument.")
fmt.Println("\tExample Usecase:\n\t\tInput:\tgo run make-template.go -p=7\n\t\tOutput:\tproblem-7.go")
fmt.Print("This will make a Go script template.\n\t Enter problem number [1 - 723]: ")
fmt.Scanln(&input)
return input
}
func GolangScript(projecteulerUrl string, problemFileName string) string {
Projects, err := GetProjectScrape(projecteulerUrl)
if err != nil {
log.Println(err)
}
var goScript string
// template Golang script
goScript = "/*\n\t" + problemFileName
goScript += "\n\tProblem Url: " + projecteulerUrl
goScript += "\n" + Projects + "*/"
goScript += "\n\npackage main\n\n"
goScript += "\nimport (\n\t\"fmt\"\n)\n"
goScript += "\nfunc main() {\n\tvar (\n\t\n\t)\n"
goScript += "\n\tfmt.Println(\"Done.\")\n}"
return goScript
}
// Scrape problems from web page
func GetProjectScrape(url string) (string, error) {
// Get the HTML
resp, err := http.Get(url)
if err != nil {
return "", err
}
// Convert HTML into goquery document
doc, err := goquery.NewDocumentFromReader(resp.Body)
if err != nil {
return "", err
}
// Save each .post-title as a list
problemInfo := ""
problemContent := ""
/*doc.Find(".post-title").Each(func(i int, s *goquery.Selection) {
titles += "- " + s.Text() + "\n"
})*/
doc.Find("#problem_info").Each(func(i int, s *goquery.Selection) {
problemInfo = s.Text()
})
doc.Find(".problem_content").Each(func(i int, s *goquery.Selection) {
problemContent = s.Text()
})
output := "===\n" + problemInfo + ":\n---" + problemContent
return output, nil
}
func IsNumber(input string) bool {
var valid bool = false
if input == "" {
// no input
valid = false
} else {
// some kind of input
if _, err := strconv.Atoi(input); err == nil {
// is a number
intNo, _ := strconv.Atoi(input)
if (intNo < 1) || (intNo > 723) {
// out of number range
valid = false
} else {
valid = true
}
} else {
// not a number
valid = false
}
}
return valid
}
func main() {
var (
problemFileName string
goScript string
projecteulerUrl string = "https://projecteuler.net/problem="
projectNumber string
)
wordPtr := flag.String("p", "", "")
flag.Parse()
projectNumber = *wordPtr
// Check if the input is a number string within range
for IsNumber(projectNumber) == false {
projectNumber = UserPrompt()
}
// new file name string
problemFileName = "problem-" + projectNumber + ".go"
projecteulerUrl = projecteulerUrl + projectNumber
fmt.Println("Web scraping", projecteulerUrl, "...")
goScript = GolangScript(projecteulerUrl, problemFileName)
fmt.Println("Create file", projecteulerUrl, "...")
if FileExists(problemFileName) == false {
fmt.Println("Writing", problemFileName, "...")
WriteGoFile(goScript, problemFileName)
} else {
fmt.Println("File", problemFileName, "already exists.")
}
fmt.Println("\nDone.")
}
Raw
problem-01.c
#include <stdio.h>
int main() {
int maxNo = 1000,
three = 3,
five = 5,
sum = 0,
multiple = 0;
for (int i = 0; i < maxNo; i++) {
multiple = i % three;
if (multiple == 0) {
sum += i;
continue;
}
multiple = i % five;
if (multiple == 0) {
sum += i;
}
}
printf("Sum of all the multiples of 3 or 5 below 1000.: %d", sum);
return 0;
}
Raw
problem-01.go
/*
https://projecteuler.net/problem=1
Multiples of 3 and 5
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
*/
// Golang Script Solution
package main
import (
"fmt"
)
func main() {
var ten int = 1000
var three int = 3
var five int = 5
var sum int = 0
for i := 1; i < ten; i++ {
if (i >= three) {
remainder := i % three
if (remainder == 0) {
// fmt.Println(i)
sum += i
continue
}
}
if (i >= five) {
remainder := i % five
if (remainder == 0) {
// fmt.Println(i)
sum += i
}
}
}
fmt.Println("Sum of all the multiples of 3 or 5 below 1000.:", sum)
}
Raw
problem-01v2.go
/*
https://projecteuler.net/problem=1
Multiples of 3 and 5
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
*/
// Golang Script Solution
package main
import (
"fmt"
)
// "math" //https://golang.org/pkg/math/
func main() {
var (
multiple int
maxNo int = 1000
three int = 3
five int = 5
sum int
)
for i := 0; i < maxNo; i++ {
multiple = i % three
if multiple == 0 {
sum += i
continue
}
multiple = i % five
if multiple == 0 {
sum += i
}
}
fmt.Println("Sum of all the multiples of 3 or 5 below 1000.:", sum)
}
Raw
problem-02.go
/*
https://projecteuler.net/problem=2
Even Fibonacci numbers
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
*/
package main
import "fmt"
func main() {
var fourMillion int = 4000000
var lastNumber int = 0
var thisNumber int = 0
var nextNumber int = 0
var sum int = 0
var isEven int = 0 // where 0 means true
thisNumber++
//sum := 0
for lastNumber <= fourMillion {
nextNumber = lastNumber + thisNumber
lastNumber = thisNumber
thisNumber = nextNumber
fmt.Println(lastNumber, thisNumber, nextNumber)
isEven = nextNumber % 2
if (isEven == 0) {
sum += nextNumber
fmt.Printf("\tSum of even numbers so far: %d\n", sum)
}
}
fmt.Println("Sum of even-valued terms whose values do not exceed four million:", sum)
}
Raw
problem-03.go
/*
https://projecteuler.net/problem=3
Largest prime factor
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
*/
package main
import (
"fmt"
)
// Get all prime factors of a given number n
func PrimeFactors(n int64) int64 {
// inspired by https://play.golang.org/p/Qedc4S_INB
// other answers https://projecteuler.net/thread=3
// The largest possible factor is n/2
// Largest factor that can not be evenly halved
for n%2 == 0 {
n = n / 2
}
// Check for odd division
// starting at 3
var i int64
for i = 3; i^2 <= n; i += 2 {
// Largest odd factor
for n%i == 0 {
n = n / i
}
}
return n
}
func main() {
fmt.Println(PrimeFactors(600851475143))
}
Raw
problem-04.go
/*
https://projecteuler.net/problem=4
Largest palindrome product
Show HTML problem content
Problem 4
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
*/
package main
import (
"fmt"
//"math"
)
func DigitCount(n int) int {
count := 0
for n != 0 {
n /= 10
count++
}
return count
}
func FirstHalf(n int, l int) int {
var tens int = 1
for i := 0; i < l; i++ {
tens *= 10
}
out := n / tens
return out
}
func LastHalf(n int, l int) int {
var tens int = 1
for i := 0; i < l; i++ {
tens *= 10
}
out := n % tens
return out
}
func Reverse(n int) int {
newInt := 0
for n > 0 {
remainder := n % 10
newInt *= 10
newInt += remainder
n /= 10
}
return newInt
}
func main() {
var (
firstHalf int = 0
lastHalf int = 0
revFirstHalf int = 0
revLastHalf int = 0
sum int = 0
digitCount int = 0
)
sum = 0
for i := 999; i >= 100; i-- {
for j := 100; j <= 999; j++ {
sum = i * j
digitCount = DigitCount(sum)
if digitCount%2 == 0 {
firstHalf = FirstHalf(sum, digitCount/2)
revFirstHalf = Reverse(firstHalf)
lastHalf = LastHalf(sum, digitCount/2)
revLastHalf = Reverse(lastHalf)
if (revFirstHalf == lastHalf) || (firstHalf == revLastHalf) {
// Display numbers starting with 9
if FirstHalf(sum, digitCount-1) == 9 {
fmt.Println("i:", i, "j:", j, "= ", i*j)
}
}
}
}
}
}
Raw
problem-05.c
/*
https://projecteuler.net/problem=5
Smallest multiple
Show HTML problem content
Problem 5
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
*/
#include <stdio.h>
#define ulong unsigned long
int main(void)
{
const ulong val = 10;
ulong x;
ulong y;
for(x = val ; ; x += val)
{
for(y = val-1 ; y ; y--)
{
if(x % y != 0)
{
break;
}
}
if(y == 0)
{
printf("Answer = %u \n", x);
break;
}
}
return 0;
}
Raw
problem-05.go
/*
https://projecteuler.net/problem=5
Smallest multiple
Show HTML problem content
Problem 5
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
*/
package main
import "fmt"
func main() {
var (
j int64 = 20
i int64 = 1
pass int = 0
count int = 0
)
for pass < 1 {
j++
for i = 1; i <= 20; i++ {
if (j%i != 0 ) {
// fail
pass = 0
count = 0
break
//continue
}
count++
if (count == 20) {
pass = 2
fmt.Println("Smallest multiple:", j)
//return
}
}
}
}
Raw
problem-06.go
/*
https://projecteuler.net/problem=6
Sum square difference
Problem 6
The sum of the squares of the first ten natural numbers is,
1^2+2^2+...+10^2=385
The square of the sum of the first ten natural numbers is,
(1+2+...+10)^2=55^2=3025
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025−385=2640
.
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
*/
package main
import "fmt"
func main() {
var (
sos int64 = 0
sonl int64 = 0
max int64 = 100
diffSum int64 = 0
i int64 = 0
)
for i < max {
i++
sos += (i * i)
sonl += i
// fmt.Println(sos, sonl, i) // debug
}
sonl = (sonl * sonl)
diffSum = sonl - sos
fmt.Println(sonl, "-", sos, "=", diffSum)
}
Raw
problem-07.c
#include <stdio.h>
#include <math.h>
#define ulong unsigned long
int main(void)
{
ulong x;
ulong y;
ulong z;
ulong cnt = 1;
printf("Prime %5d = %6d \n", 1, 2);
for (x = 3 ; cnt <= 10001 ; x++)
{
z = 0;
for (y = 2 ; y <= sqrt(x) ; y++)
{
if ((x % y) == 0)
{
z++;
break;
}
}
if (z == 0)
{
cnt++;
if(cnt == 10001)
{
printf("Prime %5d = %6d \n", cnt, x);
}
}
}
return 0;
}
Raw
problem-07.go
/*
problem url: https://projecteuler.net/problem=7
title: 10001st prime
problem number: 7
problem:
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
Prime number = no other whole numbers multiply together to make it
List of confirmed primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, ...
What is the 10,001 st prime number?
*/
package main
import (
"fmt"
)
// Return number of factors
// Primes = 2, it will have 1 and it's self
// A prime will be an odd number
func NoOfFactors(n int64) int64 {
var count int64 = 0
var start int64 = 3
var largestFactor int64 = n / 2
// check all numbers less than it
for i := start; i < largestFactor; i += 2 {
if n%i == 0 {
if count > 1 {
break
}
count++
}
}
return count
}
func main() {
var (
maxPrimeCount int64 = 10001
primeCounter int64 = 1 // pre count the number 2
primeNo int64 = 2 // the 1st even number is a prime
oddCounter int64 = 1 // initialize odd counter
factorCount int64 = 0
)
for primeCounter < maxPrimeCount {
// check odd numbers
oddCounter += 2
factorCount = NoOfFactors(oddCounter)
if factorCount < 1 {
primeCounter++
primeNo = oddCounter
// fmt.Println(primeCounter, primeNo, "\tfactorCount:", factorCount) // debug
}
}
fmt.Println("\nThe", primeCounter, "prime is", primeNo) // 104743
// 13th = 41
// 20th = 71
}
Raw
problem-08.go
/*
Problem Url: https://projecteuler.net/problem=08
Title: Largest product in a series
Problem number: 8
Problem:
The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?
*/
package main
import (
"fmt"
"strconv"
)
// Return the product of a number string
// inputs a string number and outputs an int number
func SegmentProduct(strSegment string) int {
var (
length int = len(strSegment)
strDigit string
intDigit int
segProd int = 1
nextDigit int
)
for i := 0; i < length; i++ {
nextDigit = 1 + i
strDigit = strSegment[i:nextDigit]
intDigit, _ = strconv.Atoi(strDigit)
segProd *= intDigit
}
return segProd
}
func main() {
var (
strNumber string = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450" // 1000 digit number
//segmentLength int = 4 // from question demo
segmentLength int = 13
segmentRange int // segmentLength in respect to position
segmentString string // a string of segmentLength chars
wordProduct int // product of segmentLength adjacent digits
largestProduct int // largest wordProduct
noIitterations int // number of loops
)
noIitterations = len(strNumber) - segmentLength // 1000 - segmentLength
for i := 0; i < noIitterations; i++ {
segmentRange = segmentLength + i
segmentString = strNumber[i:segmentRange]
wordProduct = SegmentProduct(segmentString)
if wordProduct > largestProduct {
largestProduct = wordProduct
}
}
fmt.Println("\nLargest product of a", segmentLength, "number sequence =", largestProduct, "\nDone.") // 23514624000
}
Raw
problem-09.go
/*
problem-9.go
Problem Url: https://projecteuler.net/problem=9
===
Problem 9:
---
A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a2 + b2 = c2
For example, 32 + 42 = 9 + 16 = 25 = 52.
There exists exactly one Pythagorean triplet for which a + b + c = 1000.Find the product abc.
*/
package main
import (
"fmt"
)
func IsPythagoreanTriple(a int, b int, c int) bool {
pass := false
aSqt := a * a
bSqt := b * b
cSqt := c * c
if aSqt+bSqt == cSqt {
pass = true
}
return pass
}
func main() {
var (
a int
b int
c int
abcSum int
maxSum int = 1000
abcProduct int
maxNaturalNo int = 500
pass bool = false
)
for a = 1; a < maxNaturalNo; a++ {
for b = 1; b < maxNaturalNo; b++ {
for c = 1; c < maxNaturalNo; c++ {
pass = IsPythagoreanTriple(a, b, c)
if pass == true {
abcSum = a + b + c
if abcSum == maxSum {
abcProduct = a * b * c
fmt.Println("a =", a, ", b =", b, ", c =", c)
fmt.Println("a^2 =", (a * a), ", b^2 =", (b * b), ", c^2 =", (c * c))
fmt.Println("Sum of ( a + b + c ) =", abcSum)
fmt.Println("Product of ( a * b * c ) =", abcProduct)
return
}
}
}
}
}
fmt.Println("Done.")
}
Raw
problem-10-v2.go
package main
/*
problem-10.go
Problem Url: https://projecteuler.net/problem=10
===
Problem 10:
---
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
*/
/*
Better faster version taken from https://projecteuler.net/thread=10;page=7
*/
import (
"fmt"
"math"
)
func primeTest(n int) bool {
for i := 2; i <= int(math.Sqrt(float64(n))); i++ {
if n%i == 0 {
return false
}
}
return true
}
func main() {
sum := 0
for k := 2; k < 2000000; k++ {
if primeTest(k) {
sum += k
}
}
fmt.Println(sum)
}
Raw
problem-10.go
package main
/*
problem-10.go
Problem Url: https://projecteuler.net/problem=10
===
Problem 10:
---
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
*/
import (
"fmt"
)
func IsPrime(n int64) bool {
var i int64
var min int64 = n / 2
var isPrime bool = true
if n%2 == 0 {
isPrime = false
if n == 2 {
isPrime = true
}
} else {
for i = 3; i < min; i++ {
if n%i == 0 {
isPrime = false
break
}
}
}
return isPrime
}
func main() {
var (
maxNum int64 = 2000000
i int64
accumulator int64 = 1 // imply 2 is a prime
)
for i = 1; i < maxNum; i += 2 {
if IsPrime(i) == true {
accumulator += i
}
}
fmt.Println("Sum of all the primes below two million:", accumulator)
fmt.Println("Done.")
}
Raw
problem-11.go
/*
problem-11.go
Problem Url: https://projecteuler.net/problem=11
===
Problem 11:
---
In the 20×20 grid below, four numbers along a diagonal line have been marked in red.
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 (26) 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 (63) 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 (78) 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 (14) 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
The product of these numbers is 26 × 63 × 78 × 14 = 1788696.
What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?
*/
package main
import (
"fmt"
)
func main() {
var (
intMatrix = [20][20]int{
{8, 2, 22, 97, 38, 15, 0, 4, 0, 75, 4, 5, 7, 78, 52, 12, 5, 77, 91, 8},
{49, 49, 99, 4, 17, 81, 18, 57, 6, 87, 17, 4, 98, 43, 69, 48, 4, 56, 62},
{81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 4, 67, 53, 88, 3, 3, 49, 13, 36, 65},
{52, 7, 95, 23, 4, 6, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 36, 91},
{22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 4, 4, 28, 66, 33, 13, 8},
{24, 47, 32, 6, 99, 3, 45, 2, 44, 75, 33, 53, 78, 36, 84, 2, 35, 17, 12, 5},
{32, 98, 81, 28, 64, 23, 67, 1, 26, 38, 4, 67, 59, 54, 7, 66, 18, 38, 64, 7},
{67, 26, 2, 68, 2, 62, 12, 2, 95, 63, 94, 39, 63, 8, 4, 91, 66, 49, 94, 21},
{24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72},
{21, 36, 23, 9, 75, 0, 76, 44, 2, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95},
{78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 8, 4, 62, 16, 14, 9, 53, 56, 92},
{16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57},
{86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 6, 21, 58, 51, 54, 17, 58},
{19, 8, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 4},
{4, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66},
{88, 36, 68, 87, 57, 62, 2, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69},
{4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 4, 62, 76, 36},
{2, 69, 36, 41, 72, 3, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 4, 36, 16},
{2, 73, 35, 29, 78, 31, 9, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54},
{1, 7, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48}}
xWidth int = 19 // 0-19
yHeight int = 19 // 0-19
x int
y int
xMax int
yMax int
first int
second int
third int
fourth int
product int64 = 0
ans int64 = 0
)
y = 0
yMax = yHeight - 3
x = 0
xMax = xWidth - 3
// forward diagonal
for y = 0; y <= yMax; y++ {
for x = 0; x <= xMax; x++ {
// fwd diag
first = intMatrix[x][y]
second = intMatrix[x+1][y+1]
third = intMatrix[x+2][y+2]
fourth = intMatrix[x+3][y+3]
product = int64(first * second * third * fourth)
if (product > ans ){
ans = product
}
// back diag
first = intMatrix[x+3][y]
second = intMatrix[x+2][y+1]
third = intMatrix[x+1][y+2]
fourth = intMatrix[x][y+3]
product = int64(first * second * third * fourth)
if (product > ans ){
ans = product
}
// horiz
first = intMatrix[x][y]
second = intMatrix[x+1][y]
third = intMatrix[x+2][y]
fourth = intMatrix[x+3][y]
product = int64(first * second * third * fourth)
if (product > ans ){
ans = product
}
// vert
first = intMatrix[x][y]
second = intMatrix[x+1][y]
third = intMatrix[x+2][y]
fourth = intMatrix[x+3][y]
product = int64(first * second * third * fourth)
if (product > ans ){
ans = product
}
}
}
fmt.Println("Sum of 4 digit sequence in any direction: ", ans)
}
Raw
problem-12.c
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char **argv) {
unsigned long long sum = 0;
unsigned long long counter = 1;
while(1) {
sum+=counter;
counter++;
int num=0;
unsigned long long i=1;
while( i * i <= sum) {
if( sum%i==0 ) {
num+=2;
}
i++;
}
if( num >= 500 ) {
break;
}
}
printf("%llu\n",sum);
}
Raw
problem-12.go
/*
problem-12.go
Problem Url: https://projecteuler.net/problem=12
===
Problem 12:
---
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?
*/
package main
import (
"fmt"
)
func DotsInTriangle(n int64) int64 {
var dots int64 = n * (n + 1) / 2
return dots
}
func main() {
var (
i int64 = 0
j int64 = 1
n int64 = 0
divCount int = 0
maxDiv int = 500
)
fmt.Println("\nProcessing ...\n\tthis will take a while.")
for divCount <= maxDiv {
i++
n += i
divCount = 0
for j = 1; j <= n; j++ {
if n%j == 0 {
divCount++
}
}
}
fmt.Println("Done\n\t", n)
fmt.Println("\nDone.")
}
Raw
problem-12.py
## stolen from https://projecteuler.net/thread=12;page=2
a=0; c=0; max=0;
while max<=500:
c+=1; a+=c; d=0; b=0; x=1
while a/x != b:
if a%x==0:
if x*x==a:
d+=1
break
b=x
d+=2
x+=1
if d>max:
max=d
print (d,a)
Raw
problem-15.c
/*
problem-15.c
Problem Url: https://projecteuler.net/problem=15
===
Problem 15:
---
Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
How many such routes are there through a 20×20 grid?
Notes:
Binomial coefficient ( https://en.wikipedia.org/wiki/Binomial_coefficient )
Commonly, a binomial coefficient is indexed by a pair of integers n ≥ k ≥ 0 and is written: n! / k!(n-k)!
Combinations and NE lattice paths ( https://en.wikipedia.org/wiki/Lattice_path )
Online calc: ( https://www.dcode.fr/lattice-path )
20x20=137846528820
Pascal's triangle:( https://en.wikipedia.org/wiki/Pascal%27s_triangle )
Pascal's triangle determines the coefficients which arise in binomial expansions.
Counting Lattice Paths( https://www.robertdickau.com/lattices.html )
1x1 = 2
2x2 = 6
3x3 = 20
4x4 = 70
ProjectEuloer solution: ( https://projecteuler.net/thread=15 )
Solution: 40 choice 20, or 40C20
*/
#include <stdio.h>
// Prototypes
unsigned long long factorial( unsigned long long n );
unsigned long long BinomialCoefficient( unsigned long long square );
unsigned long long PascalTriangle( unsigned long long square );
// Functions
unsigned long long factorial( unsigned long long n ) {
int i;
unsigned long long fact = 1;
// shows error if the user enters a negative integer
if (n < 0)
//printf("Error! Factorial of a negative number doesn't exist.");
return 1;
else {
for (i = 1; i <= n; ++i) {
fact *= i;
}
//printf("Factorial of %d = %llu", n, fact);
}
return fact;
}
unsigned long long BinomialCoefficient( unsigned long long square ) {
unsigned long long n;
unsigned long long k;
unsigned long long coefficient;
unsigned long long numerator;
unsigned long long denominator;
n = square + square;
k = square;
numerator = factorial( n );
denominator = factorial( k ) * factorial( n - k );
coefficient = numerator / denominator;
if (numerator < denominator) {
printf( "\t\t\t%llu / %llu\t%llu! square dimentions are too big to calculate in memory.\n", numerator, denominator, square );
}
return coefficient;
}
unsigned long long PascalTriangle( unsigned long long square ) {
unsigned long long x; //, xPrevious = 0;
unsigned long long y, yPrevious = 0;
unsigned long long sum = 1;
printf( "\n====================\nDimentions %llux%llu\n", square, square );
// Nudge the refference size up one. I need the next position to be based on previous position
square++;
// Square 2D matrix Variable
unsigned long long array[21][21] = {0};
// Populate array
// Initialize 2D matrix
for ( y = 1; y <= square; y++ ) {
array[1][y] = 0;
for ( x = 1; x <= square; x++ ) {
array[x][1] = 0;
}
}
// Manually fill 1st row and 1 col with 1's
for ( x = 0; x <= square; x++ ) {
array[x][0] = 1;
}
for ( y = 0; y <= square; y++ ) {
array[0][y] = 1;
}
// Display initialized matrix (Before screenshot)
printf( "\n--- Display Inititial 2D Block Dimentions Without Plotted Latice Paths ---\n" );
for (y = 0; y < square; y++) {
for (x = 0; x < square; x++) {
printf( "| (%llu,%llu) %llu ", x, y, array[x][y] );
}
printf( "\n" );
}
printf( "\n" );
// Populate 2D block
for ( y = 1; y < square; y++ ) {
sum = 1;
x = 0;
yPrevious = y - 1;
for ( x = 1; x < square; x++ ) {
//xPrevious = x-1;
sum += array[x][yPrevious];
array[x][y] = sum;
}
}
// Display populated matrix (After screenshot)
printf( "\n--- Display Plotted 2D Block Dimentions With Plotted Latice Paths ---\n" );
for ( y = 0; y < square; y++ ) {
for ( x = 0; x < square; x++ ) {
printf( "| (%llu,%llu) %llu ", x, y, array[x][y] );
}
printf( "\n" );
}
// reset refference size beack to original
square--;
printf( "\nNumber of Latis Paths in a %llux%llu Matrix is: %llu \n", square, square, array[square][square] );
return 0;
}
int main( void ) {
/*
// The BinomialCoefficient method works for less than 10 squares. Large factorials are too big for single variable memory.
unsigned long long square;
square = 20;
//printf( "BinomialCoefficient = %llu\n", BinomialCoefficient(square) );
printf( "\nSquare Size\tBinomialCoefficient\n");
printf( "-----------\t-------------------\n");
for (square = 1; square <= 20; square++) {
printf( "%llu \t\tBinomialCoefficient = %llu\n", square, BinomialCoefficient(square) );
}
*/
PascalTriangle(2); // 6
// PascalTriangle(3); // 20
// PascalTriangle(4); // 70
PascalTriangle(20); // 137846528820
return 0;
}
Raw
problem-15.go
/*
problem-15.go
Problem Url: https://projecteuler.net/problem=15
===
Problem 15:
---
Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
How many such routes are there through a 20×20 grid?
Notes:
Binomial coefficient ( https://en.wikipedia.org/wiki/Binomial_coefficient )
Commonly, a binomial coefficient is indexed by a pair of integers n ≥ k ≥ 0 and is written: n! / k!(n-k)!
Combinations and NE lattice paths ( https://en.wikipedia.org/wiki/Lattice_path )
Online calc: ( https://www.dcode.fr/lattice-path )
20x20=137846528820
Pascal's triangle:( https://en.wikipedia.org/wiki/Pascal%27s_triangle )
Pascal's triangle determines the coefficients which arise in binomial expansions.
Counting Lattice Paths( https://www.robertdickau.com/lattices.html )
1x1 = 2
2x2 = 6
3x3 = 20
4x4 = 70
ProjectEuloer solution: ( https://projecteuler.net/thread=15 )
Solution: 40 choice 20, or 40C20
*/
package main
import (
"fmt"
"math/big"
)
func PascalTriangle(square int64) {
var (
x int64 = 0
//xPrevious int64 = 0
y int64 = 0
yPrevious int64 = 0
sum int64 = 1
array [21][21]int64
)
square++
// Initialize 2D matrix
for y = 1; y <= square; y++ {
array[1][y] = 0
for x = 1; x <= square; x++ {
array[x][1] = 0
}
}
// Manually fill 1st row and 1 col with 1's
for x = 0; x <= square; x++ {
array[x][0] = 1
}
for y = 0; y <= square; y++ {
array[0][y] = 1
}
fmt.Printf("\n--- Display Initial 2D Block Dimensions Without Plotted Latice Paths ---\n")
for y = 0; y < square; y++ {
for x = 0; x < square; x++ {
fmt.Printf("| (%d,%d) %d ", x, y, array[x][y])
}
fmt.Printf("\n")
}
fmt.Printf("\n")
// Populate 2D block
for y = 1; y < square; y++ {
sum = 1
x = 0
yPrevious = y - 1
for x = 1; x < square; x++ {
//xPrevious = x - 1
sum += array[x][yPrevious]
array[x][y] = sum
}
}
// Display populated matrix (After screenshot)
fmt.Printf("\n--- Display Plotted 2D Block Dimensions With Plotted Latice Paths ---\n")
for y = 0; y < square; y++ {
for x = 0; x < square; x++ {
fmt.Printf("| (%d,%d) %d ", x, y, array[x][y])
}
fmt.Printf("\n")
}
fmt.Printf("\nNumber of Latis Paths in a %dx%d Matrix is: %d \n", square, square, array[square-1][square-1])
}
func BinomialCoefficient( squareSize int64) {
c := big.NewInt(1)
var n int64 = squareSize + squareSize
var k int64 = squareSize
fmt.Println("\n---\nBinomial Coefficient Latis path of a", squareSize, "x",squareSize, "grid: ", c.Binomial( n, k ), "\n" )
}
func main() {
// does not work for decimal numbers greater than int54
PascalTriangle(4)
// Big Math library
BinomialCoefficient(20)
fmt.Println("Done.")
}
Raw
problem-16.go
/*
problem-16.go
Problem Url: https://projecteuler.net/problem=16
===
Problem 16:
---
2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 2^1000?
*/
package main
import (
"fmt"
"math/big"
)
func PowBig(base, exponent int) *big.Int {
tmp := big.NewInt(int64(base))
res := big.NewInt(1)
for exponent > 0 {
temp := new(big.Int)
if exponent%2 == 1 {
temp.Mul(res, tmp)
res = temp
}
temp = new(big.Int)
temp.Mul(tmp, tmp)
tmp = temp
exponent /= 2
}
return res
}
func FloatToBigInt(val float64) *big.Int {
bigval := new(big.Float)
bigval.SetFloat64(val)
// Set precision if required.
// bigval.SetPrec(64)
coin := new(big.Float)
coin.SetInt(big.NewInt(1000000000000000000))
bigval.Mul(bigval, coin)
result := new(big.Int)
bigval.Int(result) // store converted number in result
return result
}
func BigSumDigits(number *big.Int) *big.Int {
var remainder *big.Int = big.NewInt(1)
var sumResult *big.Int = big.NewInt(1)
var zero *big.Int = big.NewInt(0)
var ten *big.Int = big.NewInt(10)
//var tmpFloat *big.Float = new(big.Float)
for number != zero {
//remainder = number % ten
remainder = remainder.Mod(number, ten)
//sumResult = sumResult + remainder
sumResult = remainder.Add(sumResult, remainder)
//number = number / ten
//sumResult = new(big.Int).Quo(number, ten)
sumResult = new(big.Int).Quo(ten, number)
}
return sumResult
}
func main() {
var (
base int = 2
exponent int = 15
power *big.Int = big.NewInt(1)
answer *big.Int = big.NewInt(1)
)
power = PowBig(base, exponent) //32768
fmt.Println(base, exponent, power)
//sumResult := new(big.Int).Quo(big.NewInt(10), big.NewInt(2))
//fmt.Println(sumResult )
answer = BigSumDigits(power)
fmt.Println("BigSumDigits", answer)
}
Raw
scrape-proj-euler.go
/*
This Golang script will scrape problems off the projecteuler.net website and output the problem to a text file.
Special math notations (Matlab/LaTex style notations) may not get rendered properly to text file format.
The scraping package is "github.com/PuerkitoBio/goquery"
Install goquery:
go get github.com/PuerkitoBio/goquery
*/
package main
import (
"fmt"
"io"
"log"
"net/http"
"os"
"strconv"
"github.com/PuerkitoBio/goquery"
)
func main() {
var (
projecteulerUrl string = "https://projecteuler.net/problem="
scrapeString string
textFileName string
headerString string
)
// Max problem range
intialProblemNo := 1
finalProblemNo := 713 // Max: 713
// Scrape iteration
for i := intialProblemNo; i < finalProblemNo; i++ {
Projects, err := GetProjectScrape(projecteulerUrl + strconv.Itoa(i))
if err != nil {
log.Println(err)
}
// Print Problem string to terminal
//fmt.Printf(Projects)
// Append Problem to string
scrapeString += Projects
// Write text files listing a max of 50 problems
if (i%50 == 0) || (i == finalProblemNo) {
// Generate name of an output file
textFileName = GenerateFileName(intialProblemNo, i)
// Prepend a file header to the text file continent
headerString = HeaderString(intialProblemNo, i)
scrapeString = headerString + scrapeString
// Write Problems to text file
AppendTextFile(scrapeString, textFileName)
// set a new initial number
intialProblemNo = i
// Wrote file message
fmt.Println("\nWrote: " + textFileName + "\n continuing to scrape ...")
}
fmt.Println("Finished scrape iteration loop.")
}
fmt.Println("\nApp Done.")
}
// Scrape problems from web page
func GetProjectScrape(url string) (string, error) {
// Get the HTML
resp, err := http.Get(url)
if err != nil {
return "", err
}
// Convert HTML into goquery document
doc, err := goquery.NewDocumentFromReader(resp.Body)
if err != nil {
return "", err
}
// Save each .post-title as a list
problemInfo := ""
problemContent := ""
/*doc.Find(".post-title").Each(func(i int, s *goquery.Selection) {
titles += "- " + s.Text() + "\n"
})*/
doc.Find("#problem_info").Each(func(i int, s *goquery.Selection) {
problemInfo = s.Text()
})
doc.Find(".problem_content").Each(func(i int, s *goquery.Selection) {
problemContent = s.Text()
})
output := "===\n" + problemInfo + ":\n---" + problemContent + "\n"
return output, nil
}
func DownloadFile(filepath string, url string) error {
// Get the data
resp, err := http.Get(url)
if err != nil {
return err
}
defer resp.Body.Close()
// Create the file
out, err := os.Create(filepath)
if err != nil {
return err
}
defer out.Close()
// Write the body to file
_, err = io.Copy(out, resp.Body)
return err
}
// Generate a file name
func GenerateFileName(startNo int, endNo int) string {
var outString string = "problems(" + strconv.Itoa(startNo) + "To" + strconv.Itoa(endNo) + ").txt"
return outString
}
// Write a header string
func HeaderString(startNo int, endNo int) string {
var headerString string
var start string = strconv.Itoa(startNo)
var finish string = strconv.Itoa(endNo)
headerString = "-----------------------------------------------------\n"
headerString += "Project Euler .net\n\turl: https://projecteuler.net/archives\n"
headerString += "\tProblems ( " + start + " to " + finish + " )\n"
headerString += "-----------------------------------------------------\n\n"
return headerString
}
// Write/Append string to file
func AppendTextFile(scrapeString string, textFile string) {
f, err := os.OpenFile(textFile,
os.O_APPEND|os.O_CREATE|os.O_WRONLY, 0644)
if err != nil {
log.Println(err)
}
defer f.Close()
if _, err := f.WriteString(scrapeString); err != nil {
log.Println(err)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment