Euler Problem 18 … and 67

Posted on February 24, 2012 by Anthony

Euler problem 18 has taken me far longer to conquer than it should have, for the following reasons which I offer here as a guide to others:

I aimed low at first
I tried to write the ‘brute force’ version, thinking I’d learn something along the way and that it would be a good step I could later optimise.
It proved time consuming and didn’t help me derive my optimal solution.
I took my eyes off the prize
…and concentrated on reading the tree, and storing routes and visited nodes. I’d forgotten the question. Using TDD here might’ve saved me some time.

Ditching what I had ans following my instincts, the solution virtually wrote itself. In summary:

Start with the bottom 2 rows, and work up. Determine which of the two numbers on the lower row will produce the highest return when added to the single number in the row above.
Use the derived maximum value to overwrite the single number in the upper row.
Repeat until you cannot repeat any more.

I was thrilled to see this return very quickly for Problem 18, more so when it was just as fast for Problem 67.

Here’s my solution, in Ruby:

# Project Euler - solution to problems 18 and 67
triangles = []
triangles << [75,95,64,17,47,82,18,35,87,10,20,4,82,47,65,19,1,23,75,3,34,88,2,77,73,7,63,67,99,65,4,28,6,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,4,68,89,53,67,30,73,16,69,87,40,31,4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]

def makeTriangle(ar)
rowCount=0
$rowsArr=[]
while ar.size > 0
$rowsArr[rowCount] = []
reducer = rowCount+1
while reducer > 0
$rowsArr[rowCount].push(ar.shift)
reducer-=1
end
rowCount+=1
end
$rowsArr
end
def solveTriangle(triangle)
numRows = triangle.length()-1
while numRows > 0
$ar= Array.new
$rowsArr[numRows-1].each_index{|i|
sumFirstRoute = triangle[numRows-1][i]+triangle[numRows][i]
sumLastRoute = triangle[numRows-1][i]+triangle[numRows][i+1]
higher = sumFirstRoute>sumLastRoute ? sumFirstRoute : sumLastRoute
triangle[numRows-1][i]= higher
}
numRows-=1
end
triangle[0][0]
end
triangles.each{|tri| puts "Max attainable value from triangle\: #{solveTriangle( makeTriangle(tri))}"}

Euler Problem 10

Posted on February 3, 2012 by Anthony

Find the sum of all the primes below two million

I’d say this is the first of the problems Greg and I have tackled that would really benefit from the kind of optimisations we’ve both added to our previous solutions. The Ruby solution below would take an age to complete:

range = 1999999
sumofprimesbelowrange = 2
def isPrime(num)
i = 2
while i<num
if num%i == 0
return false
end
i=i+1
end
end
while range > 1
if isPrime(range) != false
sumofprimesbelowrange=sumofprimesbelowrange+range
end
range=range-1
end
puts "Sum of all primes below #{range}"
puts "is #{sumofprimesbelowrange}"

improvements

If a number A (in our range) can be divided to a whole by number B, then it stands that the result of that division will also fail. The next example still takes a long time to return:

range = 2000000
counter = 2
sumofprimesbelowrange = 2
def isPrime(num)
i = 2
while 2*i<num
if num%i == 0

return false
end
i=i+1
end
end
while counter < range
if isPrime(counter) != false
puts counter
sumofprimesbelowrange=sumofprimesbelowrange+counter
else

end
counter=counter+1
end
puts "Sum of all primes below #{counter}"
puts "is #{sumofprimesbelowrange}"

Odds

We also know that the 2 is the only even prime number, so we can ignore all even numbers above 2 completely:

def isPrime(num)
if num%2==0
return false;
end
i = 2
while 2*i<num
if num%i == 0

return false
end
i=i+1
end
end

After a little reading into primes, the method I’m using is known as trial division. A further available optimisation allows us to only examine any division up to the square root of the number we’re checking. So our routine can be amended such:

def isPrime(num)
if num%2==0
return false;
end
i = 2
while i*i<=num
if num%i == 0

return false
end
i=i+1
end
end

This small change has a big effect, reducing the running time of the script to a matter of a few minutes.

This weeks challenge has been the most interesting yet, I now have lots of additional reading to do on the other possible solutions.

Project Euler, problem 5

Posted on January 27, 2012 by Anthony

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?

This one needed some rambling thought before I settled down to an approach. I had thought that there should be a more effective method than simply counting upwards while testing each number in the range.

I settled on the simple approach when I realised that when checking the current highest number, you can skip all remaining items in the range should there be a single failure to evenly divide.

My brief, if inelegant solution – which I’ll hopefully refine in the next few days – is copied below (written in Ruby). I can’t help but think there are ways to:

cut down the number of division checks
increment the high number by greater degrees each time

So plenty still to examine with this one.

$greatestNumber = 1
def checkHigh()
rangeLow = 1
rangeHigh = 20
i = rangeHigh
singleNumbersNonRemainDivCount = 0
while i >= rangeLow
if ($greatestNumber % i) > 0
singleNumbersNonRemainDivCount=0
$greatestNumber = $greatestNumber+1
i = rangeHigh
else
singleNumbersNonRemainDivCount=singleNumbersNonRemainDivCount+1
if singleNumbersNonRemainDivCount == rangeHigh
puts "Highest number: #{$greatestNumber}"
$greatestNumber = $greatestNumber-1
end
i=i-1
end
end
end
checkHigh()

Project Euler problem 8

Posted on January 20, 2012 by Anthony

The latest in a series of paired-up problem workings with Greg Bowie. This week we’re looking at Problem 8:

Discover the largest product of five consecutive digits in a the [provided] 1000-digit number

Here’s my response, longhand:

I’ll need a variable to store the (current) value of the greatest product
I’ll need to iterate through the 1000-digit number, reading 5 digits at a time working out the product of each sequence, stepping one digit on with every iteration.
The routine will begin from the 1st digit. The process will stop 5 digits of the final digit
Using variables to store the length of the 1000-digit number and the number of digits we’re deriving the product of would make the solution more adaptable for other numbers and sequences
Each product retrieved from every sequence of 5 digits must be compared to the current greatest product. If this exceeds the current greatest product, we set this as the new greatest product

This should solve the problem, but why stop now?

Refinements

The presence of zeros in the 1000-digit number is notable – any zero encountered while examining the product of multiple digits will result in a zero product. So I’ll ignore them:

Create an array of smaller numbers by splitting the 1000-digit number by any zero digit – handling sequences of zeros so as to prevent empty array items
Iterate through each of these numbers, deriving the product of each set of 5 digits, and checking this against the current greatest product

Chances are this refinement will not improve the performance of this test on a single number, but as it reduces the number of product-derivation runs by 398 by it may scale well, depending on the language.

ratherLongNumber = 73167176531330624919225...
numDigits = ratherLongNumber.to_s.length
considerRange = 5
totalcomparisons = 0
$greatestProduct = 0
while totalcomparisons range = ratherLongNumber.to_s[totalcomparisons,5]
rangeproduct = range.split(//).map(&:to_i).inject(:*)
$greatestProduct = $greatestProduct>rangeproduct ? $greatestProduct:rangeproduct
totalcomparisons=totalcomparisons+1
end
puts "#{$greatestProduct}"

Refined version:

ratherLongNumber = 73167176531330624919225...
def getProductOfRange(inputNumber,considerRange)
# puts inputNumber
numberofcomparisons = 0
localGreatestRange = 0
while numberofcomparisons range = inputNumber.to_s[numberofcomparisons,5]
rangeproduct = range.split(//).map(&:to_i).inject(:*)
numberofcomparisons=numberofcomparisons+1
localGreatestRange = localGreatestRange>rangeproduct ? localGreatestRange:rangeproduct
end
return localGreatestRange ,numberofcomparisons
end
$greatestProduct = 0
arrayOfNumbers = ratherLongNumber.to_s.split(/0+/).map(&:to_i)
arrayOfNumbers.each{
|a|
tmp2,comparisons = getProductOfRange(a,5)
$greatestProduct = $greatestProduct>tmp2 ? $greatestProduct:tmp2
}
puts "#{$greatestProduct}"

here’s Greg’s response, posted simultaneously today.

update 23/01/2012:

Revisiting this afresh I realise there’re other ways to skip those pesky zeros, rather than drop them into an array, better to simply skip past any such sequence:

ratherLongNumber = 73167176531330624919225...
numDigits = ratherLongNumber.to_s.length
considerRange = 5
greatestProduct = 0
cursor = 0
skipped = 0
while cursor <= numDigits-considerRange
range = ratherLongNumber.to_s[cursor,considerRange]
if range.index('0')
cursor=(cursor+range.index('0'))+1
skipped=skipped+1
else
rangeproduct = range.split(//).map(&:to_i).inject(:*)
greatestProduct = greatestProduct>rangeproduct ? greatestProduct:rangeproduct
cursor=cursor+1
end
end
puts "Greatest Product: #{greatestProduct}"
puts "#{skipped} sequences with zero in the #{considerRange}-digit range skipped"

Project Euler problem 4

Posted on January 13, 2012 by Anthony

Here’s the first of my responses to the Euler problems I’m working through in parallel with ex-colleague and fellow code-charmer Greg Bowie.

Each week we’ll tackle one of the problems (in isolation) and post our respective responses each Friday – workloads permitting – at around 3pm. This week Greg chose Problem 4
Continue reading →

Pairing up for Project Euler