Project Euler problem #28

p28.rb

#!/usr/bin/env ruby

class Spiral
  def initialize
    @diagonal_values = []
    @current = 0
    @spiral_count = 1
    recompute_diagonals
  end

  def step
    @current += 1
    if diagonal?
      @diagonal_values << @current
      if @current == area
        @spiral_count += 1
        recompute_diagonals
      end
    end
  end

  def total
    @diagonal_values.inject(0,:+)
  end

  private
  def area
    width**2
  end

  def width
    2 * @spiral_count - 1
  end

  def diagonal?
    @diagonals.include? @current
  end

  def recompute_diagonals
    @diagonals = [
      area,
      area + 1 - width,
      area + 2 * (1 - width),
      area + 3 * (1 - width)
    ]
  end
end

n = ARGV.first.to_i

s = Spiral.new

(n**2).times do
  s.step
end

puts s.total

Here's what I ended up with: https://gist.github.com/grumpit/6189510
the benchmark shows it ran in 0.002089, my built-in interpreter in TextMate said 0.01s

Am I doing it right? ;)

Hi. I'm Brian's colleague. I just gave him this minimal recursive solution:

def euler_28_min(n)
n.equal?(1) ? 1 : (((4_n__2)-(6_(n-1))) + euler_28_min(n-2))
end

I have a version that 'shows my homework', but where would be the fun in sharing that :)

I made it a little faster:

def build_spiral(spiral_size)
  total = 0
  spiral_size.step(1, -2) do |i|
    v1= i**2
    i -= 1
    # total += i == 0 ? 1 : [v1, v1-i, v1-2*i, v1-3*i].inject{ |sum,x| sum + x }
    total += i == 0 ? 1 : (v1 + (v1-i) + (v1-2*i) + (v1-3*i))
  end
  total
end

puts Benchmark.measure {build_spiral(1001)}
=> 0.000000   0.000000   0.000000 (  0.001300)

That conditional was driving me nuts. Much faster to start in the middle and not have to worry about 1 every time.

Got it to where I think this is the fastest possible solution without having to worry about stack overflow:

def build_spiral(spiral_size)
  return 1 if spiral_size == 1
  total = 1
  (3..spiral_size).step(2).to_a.each do |i|
    value = i**2
    i -= 1
    total += (value + (value-i) + (value-2*i) + (value-3*i))
  end
  total
end
puts Benchmark.measure {build_spiral(1001)}
=> 0.000000   0.000000   0.000000 (  0.000923)

And a wee bit more refined:

def build_spiral2(spiral_size)
  total = 1
  (3..spiral_size).step(2).to_a.each do |i|
    total += (4*i**2)-(6*(i-1))
  end
  total
end
puts Benchmark.measure {build_spiral2(1001)}
=> 0.000000   0.000000   0.000000 (  0.000545)