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.

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

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.

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"]

Tags: project euler, ruby

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)

21 Jun 09 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

Tags: project euler, ruby

29 May 09 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

Tags: project euler, ruby