Tag Archives: project euler

Project Euler : Problem 27 in Ruby

I’ve taken ill for the last two days, so I’ve been working on a couple Project Euler problems in between trips to the bathroom.

Problem #27

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

Since you start with n = 0, you know that b always has to be prime in order to satisfy n = 0.

Next, if b must be prime, and all primes greater than 2 are odd, and we don’t care about expressions resulting in less than 3 consecutive primes (example expression has 40), then we know that all values of a must be odd in order to satisfy n = 1!

I also suspect that for the number of consecutive primes we need to ‘win’, that we only need to look at negative values of a, but I’m having a heck of a time trying to prove it.

027.rb

require 'prime_generator'

# pre-calculate primes
MAX     = 1_000
primer  = Prime_Generator.new MAX
primes  = primer.stack
product = 0
highest = 0

# a must be odd
(0..MAX).each do |i| 
  next if i & 1 == 0

  # b must be prime
  primes.each do |b|
    
    # a can be positive or negative
    [i,-i].each do |a|
      n = 0
      while n += 1 do
        break unless primer.is_prime?(n ** 2 + a * n + b)
      end

      if highest < n
        highest = n
        product = a * b
      end

    end
  end
end

puts product

And here’s the prime generator I’m using:

prime_generator.rb

class Prime_Generator

  attr_reader :stack

  def initialize max = 3
    @stack  = [1,2,3]
    fill_to max
  end

  def fill_to max	
    n = 1
    while true do
      n += 4
      return @stack if n > max
      @stack << n if is_prime? n
  
      n += 2
      return @stack if n > max
      @stack << n if is_prime? n          
    end
  end
  
  def is_prime? n
    return false if n <= 0
    max = Math.sqrt(n).floor
    fill_to(max + 1) if max > @stack.last
  
    @stack.each do |i|
      next if i == 1
      return true if i > max
      return false if n % i == 0
    end
  
    true
  end

end

You can find more Project Euler solutions here: https://svn2.assembla.com/svn/joe-zack-personal/projects/euler/ruby/

Delving into C#

This year I’ve decided to really get into C#. My .NET experience is shall at best so aiming to rectify, I picked up C# in Depth and commenced skimming!

Now, I’ve made my fair share of M$ snide asides, but I’m having a hard time coming to gripes with C#. Everything I run into either “just works” or exceeds my expectations. And the cool features are in fact, quite cool! Color me impressed!

Noob!

Noob!


For fun I rewrote a few of my Project Euler Solutions to buff up on the syntax. After I got the semi-colons and brackets all figured out, I moved on to something a little bigger.

I wanted a simple program to run and benchmark my solutions, so I wouldn’t have to do as much leg work every time I converted a problem. I figured this would be a simple enough thing to do, and it would provide a good foundation for a future gui application and beginning unit testing.

I wanted to share some particulars that I thought were pretty cool, you can grab the code I’m talking about from the google code repository, and follow along…or something.

Generics, Delegates and Lambdas
Generic Collections provide a data structure that I can access and use just like an array, but also provides methods for dealing with delegates.

Delegates are very similar to closures, blocks, procs, and lambdas like I’ve worked with in other languages, so the transition was smooth. The lambda syntax was particularly reminiscent of pythonic list comprehensions.

Thanks to delegates, I can turn this:

var matchingTypes = new List<Type>();
foreach(t in CurrentTypes) {
	if(t.IsSubclassOf(parentType) {
		matchingTypes.Add(t);
	}
}
return matchingTypes;

Into this:

return CurrentTypes.FindAll(
	delegate(Type t)
	{
		return t.IsSubclassOf(parentType);
	}
);

And finally, via lambda, to this!

return CurrentTypes.FindAll(
	t => t.IsSubclassOf(parentType)
);

Not too shabby, eh?

Reflection
Most of my programming has been in ColdFusion, JavaScript and Ruby. There’s been a little bit of this and a little bit of that peppered in there, particually C and Java while I was at UCF, but for the most part I’ve enjoyed working with dynamic and/or interpreted languages. Meta-programming is common in these types of languages, but I was surprised and impressed to read up on reflection. In this case, reflection allows me to dynamically detect and run my problems, which makes it easier (and cleaner) for me to add new solutions.

Here’s a simplified “ClassMaster” class I use to wrap my reflection calls for listing and creating classes, so you can see what I’m on about:

class ClassMaster
{
	private Assembly CurrentAssembly { get; set; }
	private List<Type> CurrentTypes { get; set; }

	public ClassMaster()
	{
		CurrentAssembly = Assembly.GetExecutingAssembly();
		CurrentTypes = new List<Type>(CurrentAssembly.GetTypes());
	}

	// should probably take arguments to pass thru...somehow
	public Object CreateClass(Type classType)
	{
		return CurrentAssembly.CreateInstance(classType.FullName);
	}

	public List<Type> getTypesByParentClass(Type parentType)
	{
		return CurrentTypes.FindAll(
			t => t.IsSubclassOf(parentType)
		);
	}
}

That’s it for now. I’ll be looking into LINQ and unit testing in the next couple weeks, and then I’m on to the gui. ASP, SilverLight, and WPF here I come!

Here are those links again:
Release
Latest Version

Project Euler: Problem 30 in Ruby

I realize this isn’t the fast solution, but the more I optimized, the uglier it got so I’m done playing with it. The hardest part was figuring out what the upper bound limit was.

Problem 30

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

power, total = 5, 0

(power * 9**power).times do |i|
  total += i if i == i.to_s.split('').inject(0) {
    |sum, n|
    sum + n.to_i**power
  }
end

puts total - 1

Project Euler: Problem 26 in Ruby

I knew I’d be implementing my own division algorithm for this problem, but I had a hard time figuring out a good way to detect the repeating sequence.

That’s all I have to say about that.

Problem #26

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

def divide n, d, repo = []
  return repo.size - repo.index(n) if repo.include? n
  divide 10 * (n - (n / d) * d), d, repo << n
end

highest = {"d" => 1, "count" => 1}

(1..499).each do |i|
  x     = i * 2 + 1
  count = divide 1, x
  if count > highest['count']
    highest = {"d" => x, "count" => count}
  end
end

puts highest["d"]

Project Euler: Problems 1 – 5 in JavaScript

I’ve been wanting to check out Rhino for a while, and I’ve been particularly interested in seeing how it compares to Ruby in terms of speed. The results have been a little varied, and it’s a deeply flawed comparison. But it’s something.

These scripts are just ports of my ruby solutions. There are a few places where I had to roll my own JavaScript functions instead of baked in Ruby methods, but other than that it was nearly line by line translation.

Problem 1Ruby solution

Add all the natural numbers below one thousand that are multiples of 3 or 5.

var total = 0;

for(var i = 0; i < 1000; i++) {
  if(i % 3 == 0 || i % 5 == 0) {
    total += i;
  }
}

print(total);

Problem 2Ruby solution

Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.

function fib(stack, n) {
  if(n == 0) {
    return 1;
  }
  if(n == 1) {
    return 2;
  }
  return stack[n - 1] + stack[n - 2];
}

var max   = 4000000;
var total = 0;
var stack = [];

for(var i = 0; i < max; i++) {
  stack[i] = fib(stack,i);
  if(stack[i] > max) {
    break;
  }
  if(stack[i] % 2 == 0) {
    total += stack[i]
  }
}

print(total);

Problem 3Ruby solution

Find the largest prime factor of a composite number.

function find_highest_prime_factor(n) {
  var max = Math.round(Math.sqrt(n));
  for(var i = max; i >= 2; i--) {
    if(n % i == 0 && find_highest_prime_factor(i) == 1) {
      return i;
    }
  }
  return 1;
}

var target = 600851475143;
print(find_highest_prime_factor(target));

Problem 4Ruby solution

Find the largest palindrome made from the product of two 3-digit numbers.

function get_highest_palindrome(high, low) {
  var highest = 0;
  for(var i = high; i >= low; i--) {
	for(var j = high; j >= low; j--) {
      sum = i * j;
      if(sum <= highest) {
        break;
	  }
      if(is_palindrome(sum.toString())) {
        highest = max(highest, sum);
	  }
    }
  }
  return highest;
}

function reverse(string) {
  var array = string.split('').reverse();
  var out   = '';
  for(key in array) {
	out += array[key];
  }
  return out;
}

function max(a,b) {
  if(a > b) {
	return a;
  }
  return b;
}

function is_palindrome(string) {
  return string == reverse(string);
}

print(get_highest_palindrome(999, 100));

Problem 5 - Ruby solution

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

function gcd(a,b) {
  var x = a;
  var y = b;
  var result;
  
  while (y != 0) {
	result = x % y;
    x      = y;
    y      = result;
  }
  return x;
}

function lcm(a,b) {
  return (a * b) / gcd(a, b);
}

var max = 20;
var min = 11;
var n   = min;

for(var i = min; i <= max; i++) {
  n = lcm(n,i);
}

print(n);

Project Euler: Problem 24 in Ruby

I could see that this problem was solvable by hand, but that’s no fun.

Instead I decided to implement it with a tree. Not the most efficient solution to be certain, especially the way I rolled it, but it was a fun exercise. I don’t get to play with trees often enough.

Problem #24

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

def nth_lexical_permutation values, key = "", chain = ""

  chain    = chain + key.to_s
  children = values.select { |i| i != key }

  $count -= 1 if children.size == 0
  return chain if $count == 0

  children.each do |i|
    result = nth_lexical_permutation children, i, chain
    return result if result.size > 0
  end
  ""
end

$count = 1_000_000
set    = (0..9).to_a

puts nth_lexical_permutation(set)

Yep, there’s a global in there. It just made things easier. There are actually quite a few things I don’t like about this program. But it’s late. And I’m tired.

Project Euler: Problem 23 in Ruby

Looks like I took a pretty common approach on this one. First I calculated all the abundant numbers and dropped the sums in a hash. Then I just summed up to the given upper bound of 28,124 excluding those abundant sums.

Ruby1.9 solves it on my computer in about 15 seconds. After reading through the forums, some people were using a much lower upper limit of 20,200 which brought my run time down to a much respectable 6 seconds.

Problem #23

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

def sum_proper_divisors n
  sum = 1
  (2..Math.sqrt(n)).each do |i|
    if n % i == 0
      result = n / i
      sum += result unless result == i
      sum += i
    end
  end
  sum
end

def next_abundant repo
  i = repo.last + 1
  while( sum_proper_divisors(i) <= i)
    i += 1
  end
  i
end

max   = 20_200
repo  = [12]
sums  = {24 => nil}
total = 0

while repo.last < max do
  repo << next_abundant(repo)
  repo.each do |i|
    sum = repo.last + i
    if sum > max
      break
    end
    sums.store sum, nil
  end
end

max.times do |i|
  total += i unless sums.include? i
end

puts total

Project Euler: Problem 19 in Ruby

Although it felt dirty, I used Ruby’s baked-in date class. I’d written some day-of-week code when I first started coding, before I knew better, and it’s annoying. Besides, this was my last problem to do before level 1. That’s right…

LEVEL 1!!!!

Bravo, thejoezack! Now that you have solved 25 problems you have achieved what 79.52% of members have failed to do and have advanced to level 1. Good luck as you continue.”

I’m proud. I found a few of the problems to be really hard and it feels really good to have finally hit a milestone. I’ve actually had a much easier time with the problems as I’ve gone on, as I’ve learned a lot about solving these problems and perhaps even problem solving in general. Kudos and thanks, Project Euler!

Oh yeah…and here’s my solution:

Problem #19

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

require 'date'

start = Date.new 1901, 1, 1
total = 0

(100 * 12 - 1).times do |i|
  total += 1 if (start >> i).wday == 0
end

puts total

Project Euler: Problem 22 in Ruby

Cake. I really hate hard-coding that ascii value in there, but it made it easier for me to get it working in different versions of Ruby.

Problem #22

What is the total of all the name scores in the file?

def convert word
  total = 0
  word.each_byte do |i|
    total += i - 64
  end
  total
end

file  = File.new("files/names.txt", "r")
names = eval("[" + file.gets + "]").sort
total = 0

file.close

names.each_with_index do |name, i|
  total += convert(name) * (i + 1)
end

puts total

Project Euler: Problem 21 in Ruby

Pretty standard Project Euler solution. You only need to check up to the square of each number, and you can cache each calculation as you go along.

Problem 21

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

Evaluate the sum of all the amicable numbers under 10000.

def d(n)
  total = 1
  (2..Math.sqrt(n)).each do |i|
    if n % i == 0
      total += n / i + i
    end
  end
  total
end

def amicable?(a, repo)
  repo[a] = b = d(a)
  a != b and a == repo[b]
end

repo  = {}
total = 0

10_000.times do |i|
  if amicable?(i, repo)
    total += (i + repo[i])
  end
end

puts total