## Posts

Showing posts from 2012

### Project Euler: Problems 18 and 67

- Get link
- Google+

Problem 18

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3

7 4

2 4 6

8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75

95 64

17 47 82

18 35 87 10

20 04 82 47 65

19 01 23 75 03 34

88 02 77 73 07 63 67

99 65 04 28 06 16 70 92

41 41 26 56 83 40 80 70 33

41 48 72 33 47 32 37 16 94 29

53 71 44 65 25 43 91 52 97 51 14

70 11 33 28 77 73 17 78 39 68 17 57

91 71 52 38 17 14 91 43 58 50 27 29 48

63 66 04 68 89 53 67 30 73 16 69 87 40 31

04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

Solution

By extension, this solves problem 67 as well.

This uses a tail-recursive function requiring the pyramid to be flattened into an array and…

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3

7 4

2 4 6

8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75

95 64

17 47 82

18 35 87 10

20 04 82 47 65

19 01 23 75 03 34

88 02 77 73 07 63 67

99 65 04 28 06 16 70 92

41 41 26 56 83 40 80 70 33

41 48 72 33 47 32 37 16 94 29

53 71 44 65 25 43 91 52 97 51 14

70 11 33 28 77 73 17 78 39 68 17 57

91 71 52 38 17 14 91 43 58 50 27 29 48

63 66 04 68 89 53 67 30 73 16 69 87 40 31

04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

Solution

By extension, this solves problem 67 as well.

This uses a tail-recursive function requiring the pyramid to be flattened into an array and…

### Project Euler - Problem 17 (Match-based Solution)

- Get link
- Google+

Problem

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.

Note

I have done two (2) solutions for this problem. The original in a prior post requires less code, but is 'ugly' and is less reusable that this match-based solution. This solution is based on smaller methods using the match function, with larger number functions able to call and reuse code from the functions for smaller numbers. Calling the method is much cleaner as well.

Solution (Match-Based)

let GetThousandthsLetters prefix fourth third second first =

match fourth with

…

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.

Note

I have done two (2) solutions for this problem. The original in a prior post requires less code, but is 'ugly' and is less reusable that this match-based solution. This solution is based on smaller methods using the match function, with larger number functions able to call and reuse code from the functions for smaller numbers. Calling the method is much cleaner as well.

Solution (Match-Based)

let GetThousandthsLetters prefix fourth third second first =

match fourth with

…

### Project Euler - Problem 17

- Get link
- Google+

Problem

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.

Solution

//this is a very ugly solution, which I will return to to properly factor to smaller recursive methods

let GetThousandsLetters num =

match num with

| 1 -> "one thousand"

| 2 -> "two thousand"

| 3 -> "three thousand"

| 4 -> "four thousand"

| 5 -> "five thousand"

| 6 -> "six thousand"

| 7 -> "seven thousand"

| 8 -> "eight th…

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.

Solution

//this is a very ugly solution, which I will return to to properly factor to smaller recursive methods

let GetThousandsLetters num =

match num with

| 1 -> "one thousand"

| 2 -> "two thousand"

| 3 -> "three thousand"

| 4 -> "four thousand"

| 5 -> "five thousand"

| 6 -> "six thousand"

| 7 -> "seven thousand"

| 8 -> "eight th…

### Project Euler - Problem 12

- Get link
- Google+

Description

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 (500) divisors?

Solution

//from rosetta code site

//code for finding the distinct factors of a number

let factors number = seq {

for divisor in 1 .. (float >> sqrt >> int) number do

if number % divisor = 0 then

yield divisor

yield number / divisor

}

//verification of factor code

let factorTest = Seq.toArray(factors 28)

//basic method for calculating the triangle number oin a recursive function

let rec generateTriangleNumber (priorValue:int) …

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 (500) divisors?

Solution

//from rosetta code site

//code for finding the distinct factors of a number

let factors number = seq {

for divisor in 1 .. (float >> sqrt >> int) number do

if number % divisor = 0 then

yield divisor

yield number / divisor

}

//verification of factor code

let factorTest = Seq.toArray(factors 28)

//basic method for calculating the triangle number oin a recursive function

let rec generateTriangleNumber (priorValue:int) …

### Project Euler - Problem 28

- Get link
- Google+

Description

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25

20 7 8 9 10

19 6 1 2 11

18 5 4 3 12

17 16 15 14 13

It can be verified that the sum of the numbers on the diagonals is 101. What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

Solution

//calculates the sum for the level of the square

//each increase in level only requires calculating 4 new values, the corners

let levelValue (start:int) (side:int) =

let diffAtLevel = side - 1

let sum = (start + diffAtLevel) + (start + (diffAtLevel * 2)) + (start + (diffAtLevel * 3)) + (start + (diffAtLevel * 4))

sum

//recursively iterates from level 0, which is the center

//to the outer part of the array

//and for each level calculates the additional sum and sums that to running sum

let rec sumByPowers start priorLevelSquared level endSide sum =

if level > endSide then

sum

else

let newSum =…

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25

20 7 8 9 10

19 6 1 2 11

18 5 4 3 12

17 16 15 14 13

It can be verified that the sum of the numbers on the diagonals is 101. What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

Solution

//calculates the sum for the level of the square

//each increase in level only requires calculating 4 new values, the corners

let levelValue (start:int) (side:int) =

let diffAtLevel = side - 1

let sum = (start + diffAtLevel) + (start + (diffAtLevel * 2)) + (start + (diffAtLevel * 3)) + (start + (diffAtLevel * 4))

sum

//recursively iterates from level 0, which is the center

//to the outer part of the array

//and for each level calculates the additional sum and sums that to running sum

let rec sumByPowers start priorLevelSquared level endSide sum =

if level > endSide then

sum

else

let newSum =…

### Project Euler - Problem 30 Redux (using Parallel)

- Get link
- Google+

The original post Project Euler - Problem 30 was done some time ago, and I recently read about using parallel methods to improve performance, and in this case, Parallel reduces execution time by 33%.

Description

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits. Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

Solution (using Parallel)

open System

open System.Threading

open System.Threading.Tasks

let isNarcissistic num power =

let numAsString = num.ToString()

let arr = [for i=0 to (numAsString.Length - 1) do

yield (float(numAsString.Chars(i).ToString()))**power]

if num = int(List.sum arr) then

num

else

0

let GetAllNarcissistic2_Start = System.DateTime.UtcNow

let GetAllNarcissistic2 =

[|2..999999|]

|> Array.Parallel.map (fun x -> isNarcissistic x 5.0)

|> Array.sum

printfn "%f" ((System.DateTime.UtcNow).Subtract(GetAllNarcissi…

Description

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits. Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

Solution (using Parallel)

open System

open System.Threading

open System.Threading.Tasks

let isNarcissistic num power =

let numAsString = num.ToString()

let arr = [for i=0 to (numAsString.Length - 1) do

yield (float(numAsString.Chars(i).ToString()))**power]

if num = int(List.sum arr) then

num

else

0

let GetAllNarcissistic2_Start = System.DateTime.UtcNow

let GetAllNarcissistic2 =

[|2..999999|]

|> Array.Parallel.map (fun x -> isNarcissistic x 5.0)

|> Array.sum

printfn "%f" ((System.DateTime.UtcNow).Subtract(GetAllNarcissi…

### Project Euler - Problem 26 Redux (using Parallel)

- Get link
- Google+

The original post Project Euler - Problem 26 was done some time ago, and I recently read about using parallel methods to improve performance, and in this case, Parallel reduces execution time by 25%.

Description

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2 = 0.5

1/3 = 0.(3)

1/4 = 0.25

1/5 = 0.2

1/6 = 0.1(6)

1/7 = 0.(142857)

1/8 = 0.125

1/9 = 0.(1)

1/10 = 0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

Solution (using Parallel)

open System

open System.Threading

open System.Threading.Tasks

let rec remainders (num:int) (rem:int) (arr:list) =

let filteredList = arr |> List.filter (fun x -> x = num)

if filteredList.Length > 1 || num = 0 then

arr.Length - 1

elif (num*10) < rem then

remai…

Description

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2 = 0.5

1/3 = 0.(3)

1/4 = 0.25

1/5 = 0.2

1/6 = 0.1(6)

1/7 = 0.(142857)

1/8 = 0.125

1/9 = 0.(1)

1/10 = 0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

Solution (using Parallel)

open System

open System.Threading

open System.Threading.Tasks

let rec remainders (num:int) (rem:int) (arr:list) =

let filteredList = arr |> List.filter (fun x -> x = num)

if filteredList.Length > 1 || num = 0 then

arr.Length - 1

elif (num*10) < rem then

remai…