15 Mar 10 Project Euler : Problem 29 in Ruby
I spent some time playing around with a way to reduce calculations by constructing something akin to a sieve, (2^16 is the same as 4^8 and 16^4), but it turns out that the brute force solutions runs in under a second on my machine so it seemed silly to spend any more time with it.
Ruby even minds the big numbers for me, so the solution is quite trivial:
How many distinct terms are in the sequence generated by a^(b) for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?
MIN, MAX = 2,100
values = []
(MIN..MAX).each do |base|
(MIN..MAX).each do |power|
values << base**power
end
end
puts values.uniq.length
Tags: project euler, ruby
11 Mar 10 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.
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/
Tags: project euler, ruby
07 Jan 10 My First Forray into C#
This year I've decided to delve into C#. I haven't touched Visual Studio since before .NET. I don't know anything about the framework, the languages, or windows programming. 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!
Being a TOTAL noob, the first thing I did was rewrite 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
Tags: c#, meta-programming, project euler
22 Sep 09 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.
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
Tags: project euler, ruby
18 Aug 09 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.
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"]
Tags: project euler, ruby
