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      
      
    end
  end

  puts max_product

end
Advertisements

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 = []
  File.open("names.txt").each_line do 
    |s| names_array = s.scan(/\w+/).sort
  end
  
  score = 0

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

module StringHelper

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

end


class String 
  include StringHelper
end

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: " + Time.now.to_s

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

    |index|
    
    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      

    end

  end
  
  puts total

  puts "Finish: " + Time.now.to_s
  
end

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
93496983520312774506326239578318016984801869478851843858615607
89112949495459501737958331952853208805511125406987471585238630
50715693290963295227443043557668966489504452445231617318564030
98711121722383113622298934233803081353362766142828064444866452
38749303589072962904915604407723907138105158593079608667017242
71218839987979087922749219016997208880937766572733300105336788
12202354218097512545405947522435258490771167055601360483958644
67063244157221553975369781797784617406495514929086256932197846
86224828397224137565705605749026140797296865241453510047482166
37048440319989000889524345065854122758866688116427171479924442
92823086346567481391912316282458617866458359124566529476545682
84891288314260769004224219022671055626321111109370544217506941
65896040807198403850962455444362981230987879927244284909188845
80156166097919133875499200524063689912560717606058861164671094
05077541002256983155200055935729725716362695618826704282524836
00823257530420752963450".scan(/\w/)

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
    
end

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
  end

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);
   Console.ReadKey();

   }
 }

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--;
                    continue;
                }

                return false;
            }
            return true;
        }

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