Project Euler Problem 11

Yet another problem, this is the one I’ve had the most fun on so far. I swear it is IMPOSSIBLE to make this readable! The inspiration for the solution came from the UK TV show “catchphrase”, believe it or not 🙂 I basically slam a kernel/matrix type thingy around the grid doing Roy Walker impressions until I find the highest product. Here it is anyway, but abandon hope all ye who proceed beyond this point…

def problem11  
  grid = []
  kernel_size = 4
  max_product = 0

  File.readlines("numbers.txt").each do |line|
    grid < max_product

      left_diagonal_total = 1
      right_diagonal_total = 1
      (0..3).each {|matrix_counter|
        left_diagonal_total *= grid[row+matrix_counter][col+matrix_counter].to_i
        right_diagonal_total *= grid[row+matrix_counter][col+((kernel_size-1)-matrix_counter)].to_i  
      max_diagonal = [left_diagonal_total,right_diagonal_total].max
      max_product = max_diagonal if max_diagonal > max_product      

  puts max_product


Project Euler Problem 22

Another solution, this one is of note because it involves reading from a file and involved the discovery of the “each_with_index” method. This is also the first problem where I learned, the hard way, to “read the sodding question properly” 🙂

def problem22
  names_array = []"names.txt").each_line do 
    |s| names_array = s.scan(/\w+/).sort
  score = 0

  names_array.each_with_index do |name, index| 
    score += name.alphabet_score * (index+1)
  puts score

module StringHelper

  def alphabet_score
    total = 0
    self.each_byte { |char|
      total += (char - 64)


class String 
  include StringHelper

Project Euler Problem 10

Here follows the story of problem 10, an epic tale spanning two countries and involving my mother in law! In my ongoing attempts to master Ruby through the solving of Project Euler tasks, I had hit a little snag on this problem. “This problem sounds easy!” I thought, and I wrote the code out in a clean, readable style just as I promised, hit run and… oh.

One of the rules of Project Euler is that your code needs to finish in under a minute in order to count, and my code was still running after two. My original prime calculating code was clearly too inefficient to cut it under this level of complexity. It is at this point that I was forced to confront the fact that I am, in fact, shit at maths. All I knew about prime numbers is that they were real integers which are divisible by only 1 and themselves. That was, literally, it. I knew nothing of their inherrent properties beyond that. Was this to be the problem where my lack of mathematical knowledge stopped me in my tracks?

I was very keen to solve this on my own rather than googling, so I reasoned like this: If i can’t solve this with mathematical knowledge, maybe i can solve it by thinking like a programmer. My initial thoughts were;

* Iterating over large arrays is expensive
* Arithmetic, when done on a large scale, is expensive
* Comparisons are very cheap

I then started to work in any knowledge of maths I had into the solution: I knew that Ruby would very competently be able to handle an array of 2 million real numbers. The plan was to start with an array of all numbers up to 2 million, then “zero them” when i knew they weren’t prime. At the end, it would just be a case of adding up all of those numbers that weren’t zero. This would be more efficient than my existing prime method, which involved iterating through all numbers prior ot the one you’re calculating.

At this point I was still using my original prime method to do this, and I knew that this was computational overkill, so I started to think of other ways to do this. I know that all even numbers (with the exception of 2) are not prime. Therefore, when i initialize the array, I can get rid of the evens from the start. That’s half the problem solved, right?

Still not quick enough. It is at this point that I realized that my prime calculating method had got to go. I was all but ready to give up, but then had a bit of a brainwave during a long drive to Wales (hey, it’s inspiring country!). While I am iterating from 3 to 2m, I can also reason that any multiple of the number I am currently on (up to 2m) can also be zeroed. Then, as I iterated further, I could skip over those that were already zero with another nice cheap comparison. This would make the algoritm slow at first, but super-fast once it got going. When I eventually got to Wales I was so excited about it that I described the whole algorithm to my in-laws (who were also in Wales). In hindsight, they probably thought I was a total freak, but my mother in law did draw a comparison between the algorithm and the childrens game “Guess who”, which is an awesome comparison it has to be said!

I started coding as soon as I could, and my little netbook finally managed to calculate the sum of primes below 2 million in 32 seconds!

In an interesting epilogue to the story, once you solve a Project Euler problem you are invited to a forum thread to gaze in awe at other people’s solutions. Many of the other participants were talking about something called the Sieve of Eratosthenes, so I decided to google it. I was quite suprised to find that the solution I had come with on the drive to Wales was actually an implementation of this 2000 year old greek algorithm!

In retrospect, I nearly buckled and gave in a couple of times on this but I am so pleased that I didn’t. I am not really doing this to learn maths, I’m doing it to learn ruby, but if gaining a better understanding of mathematical algorithms is a happy side-effect then who am I to argue. The feeling of elation for having come up with this solution on my own is pretty phenominal, even if it did mean breaking my promise about writing readable code!

Incidentally, the plan is not to post every single problem solution that I come up with, only those I’m particularly proud of or that hold some kind of merit worth mentioning. Anyway, here is my solution, in all its unreadable glory 🙂 There is a commented puts in there which, if you uncomment, will show you how this algorithm builds speed as it closes off the multiples.

def problem10

  puts "start: " +

  # create array of numbers 1 - 2m
  two_million = 2000000
  #set up the array
  arr = []
  (1..two_million).each do 
    if ((num.even? and num != 2) or num == 1)
      arr << 0
      arr << num
  #start the iteration
  3.step(two_million, 2) do

    next if arr[index-1] == 0

    current_number = arr[index-1]
    total += current_number

    #uncomment next line to see the algorithm gaining momentum!
    #puts current_number

    multiplier = 3

    while true do

      result = arr[(multiplier*current_number)-1]

      break if result == nil

      arr[result-1] = 0

      multiplier += 2      


  puts total

  puts "Finish: " +

It is worth noting that there are further optimizations that can be done to the above. The array initialization, for example, only initially zeros even numbers. Knowing, for example, that all multiples of five are not prime, those numbers ending in 5 could also be eliminated at this stage (you’d have already gotten rid of the numbers ending in zero when you blat the evens). One such algorithm that reasons along the same lines is the Sieve of Atkin, for anyone who wants to check it out.

Project Euler Problem 8

Another ruby solution in my ongoing efforts to master this wonderful technology. This time, it’s for problem 8.

I’m focusing very much on the ability ruby gives you to write not only write *less* code, but to at the same time write code that is more readable, particularly to non-programmers. Half way through writing this solution, i came to the realization that I was basically writing English! I am going to try and do this to ridiculous levels for the remainder of the problems I solve 🙂

Anyway, onto the solution. I didn’t use my Math mixin this time, mainly because I became a little obsessed with making the code read like English half way through. So here is the solution;

#note: this first bit just gets the numbers into an array

the_numbers = "73167176531330624919225119674426574742355349194

highest_found = product_of the_numbers.last 5

999.times do
    the_numbers.pop      #note: this just gets rid of the last number
    product_of_last_five = product_of the_numbers.last 5

    highest_found = product_of_last_five if product_of_last_five > highest_found

print highest_found

I would be incredibly interested in hearing from anyone who has no coding experience at all, but who can still understand what the above does (or anyone who can’t, where did i go wrong?). Sometimes I guess developers can get a bit too close to the forest to see the trees and I am really striving for code readable by non-techies in all of this (will save me a LOT of headaches in my job if I can perfect it, believe me!)

I also used this helper method that will now go into the mixin.

  def product_of array
    total = 1
    array.each do |x| total = total * x.to_i end
    return total

Project Euler Problem 4

Have decided to try and get a few of these done every week just to keep the ol’ brain alive. Here’s my working for Project Euler problem 4 in C#.

class Program
 static void Main(string[] args)
 int biggest = 0;

 for (int i = 100; i < 999; i++)            
   for (int j = 100; j < 999; j++)
      int product = i * j;
      if (IsPalindromic(product))                      
        if (product > biggest)
          biggest = product;
   Console.WriteLine("Done!, biggest was " + biggest);


Where “IsPalindromic” is as follows…

        public static bool IsPalindromic(int number)
            string s = number.ToString();
            int frontCounter = 0;
            int backCounter = s.Length-1;

            while (frontCounter < backCounter)
                if (s[frontCounter] == s[backCounter])
                    frontCounter++; backCounter--;

                return false;
            return true;

brute force… but for something this trivial I don’t care 😛