Monthly Archives: February 2012

Euler Problem 18 … and 67

Posted on by
Reply

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:

  1. 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.
  2. 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))}"}

February self-portraits – assemblages, landscapes, graphic work and sketchbooks

Posted on by
Reply

February’s had some contrasts.

The month began positively with a personal assemblage work and a graphic derivation of it, which I hoped would shake things up a bit. Since then I’ve returned largely to mirror work of questionable quality.

So far this month there’s pencil, ink, pastel, impressed cardboard(5th), gouache(10th) and charcoal(13,14th) and frequent shifting of scale – from sheets of cartridge down to notebooks, sketchbooks and paper bags(8th).

For the non-visually-representative work the subject matter is becoming more personal, so finally there’s a landscape(15th) without figures. I thought I’d have found that route far earlier.

February 16th saw me correcting the prior composition and setting to match the particulars of the subject that’s been in mind for some time – I think there’s a painting coming together.

Euler Problem 10

Posted on by
Reply

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.

Day 33, Moo-cough and I

Posted on by
Reply
February 2nd

February 2nd


Only in discussion during today did I realise that yesterday’s ready-made was, when examined with or without prior knowledge of me, probably the most descriptive and personal work so far.

I’m happy that things are taking a turn, I’d hate to end the year with a majority output of still-looking sketches of varying quality. The range of media, and the developing themes I’m following are giving me lots to think about, much to enjoy and more to look forward to.

Continuing the slightly obscure theme, this is the first digital work of the project, Illustrator and a little Photoshop.

I do not smoke, I never have. I do own a pipe, and a plastic bull.