April 2008 - Posts
A while ago, we had a discussion here at the office about nerdy t-shirts. We all know what I'm talking about: usually worn by a male geek/programmer with a neckbeard, a black shirt with a "witty" technical reference. Opinions about these shirts vary among SRT employees: some of us find them funny and even wear them on dates [no report on the results, though], some are skeptical. You might guess that I fall into the second camp. Here are the worst offenders in my book:
The geek love poem...
It's so bad it's good.
The worst one of all. Nearly ubiquitous in computer science buildings on campuses nationwide, but yet still considered brilliant and unique by the wearer.
And of course, I can't leave out geeky women's gear -- in some ways even more horrifying than the men's stuff. Evidence presented:
HTML tags -- get it?!
I have no words. Instead I'll leave you with ThinkGeek's description of these: "... we bring you HTTPanties
for the discriminating woman who would prefer a web-savvy and somewhat-direct
approach in the romance department. Feeling frisky? Well then don the black "200 OK" panties and see where they take
you. Alternatively, the white "403 Forbidden" style sends a very different
and hopefully clear message. We think "411 Length Required" and "413 Requested Entity Too Large" are pretty self-explanatory."
Find the largest palindrome made from the product of two 3-digit numbers.
-----
First, I defined a palindrome recursively: a number is one if its first and last digits are the same, and if the inside is also a palindrome.
def palindrome?(digitArr)
if digitArr.empty?
true
elsif digitArr.length == 1
true
else
(digitArr.first == digitArr.last && palindrome?(digitArr[1..-2]))
end
end
Note that in Ruby, methods can end with a question mark, a convention that really helps readability. Also note that the "else if" keyword is elsif, which is weird and unhelpful to me. I want that 20 minutes of staring at my code like "wtf?!" (before figuring that out) back.
Then we do a search of all the multiples of two three-digit numbers until we find the biggest palindrome:
def search(i,j)
maxPal=0
while i > 99 do
j=999
while j > 99 do
if palindrome?((i*j).to_s.split("")) then
if(i*j)> maxPal then maxPal = i*j
end
end
j-=1
end
i-=1
end
return maxPal
end
puts search(999,999)
There's probably a prettier way to do this.
What is the largest prime factor of the number 600851475143 ?
-----
I wrote this piece of disgusting, un-Rubylike Ruby to get the answer by creating a list of a number's prime factors:
def factor(composite)
i=1
flag=false
primefactors =[]
while (i < composite)
i=i+1
primefactors.each{|p| flag=true if (i%p).zero?}
if flag then flag=false
else # if it is a prime
primefactors.push(i) #add the prime (since it's a prime factor)
while (composite%i).zero? # as long as n is divisbible by the prime
composite /= i # divide n by the prime
end
end
end
primefactors
end
puts factor(600851475143).last
And then I learned that ruby has a prime number generator. All I need to do is:
require 'mathn'
n = 600851475143
factor = 0
primes = Prime.new
while n > 1
factor = primes.next
while (n % factor).zero?
n /= factor
end
end
puts factor
I am slightly ashamed.
The problem:
Find the sum of all the even-valued terms in the [Fibonacci] sequence which do not exceed four million.
Here's my fibonacci function:
def fib(limit =nil)
f1 = 0
f2 = 1
while (not limit or f2 <= limit)
yield f2
f1,f2 = f2, f1+f2
end
end
And here's how I use it to get the answer:
evens=[]
fib { |x| if x%2==0 : evens.push(x) end ; if x>4000000: break end}
puts evens.inject {|sum, n| sum+n}
I learned about the awesomeness of 'yield' by doing this problem, so it was totally worth it. yield let me calculate as many fibonacci terms as I needed, but not more, and without having to calculate any term more than once.
I'm taking Bill Wagner up on his Project Euler challenge, but in Ruby. I've secretly wanted to learn Ruby for a long time, and this looks like the perfect chance. So if my code makes your eyes bleed, it's cause I'm a total n00b. Without further ado (because the excitement was becoming unbearable... I agree, Ruby is sexy!), here's my code that prints the answer to Problem 1:
If we list all the natural numbers below 10 that are multiples of 3
or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.
answer = (0..999).select { |a| a%3 ==0 || a%5==0 }
puts answer.inject { |sum, n| sum+n }
I love the built-in ruby function inject, which is like foldl in some functional languages. (See a cute demo here.) Overall the code is very similar to Bill's C# version. I wonder if that'll still be the case as we get to the more complex problems.
[4/08/08: correction of a typo in the code]