class Group
  attr_reader :bound, :objs
  def initialize(s); @bound = s; @objs = [] end

  def intersect(hit, ray)
    len = bound.ray_sphere(ray)
    return hit if len >= hit.lambda
    @objs.inject(hit){ |h, ss| ss.intersect(h, ray) }
  end
end

class Hit
  attr_reader :lambda, :normal
  def initialize(l, n); @lambda, @normal = l, n end
end

class Ray
  attr_reader :orig, :dir
  def initialize(o, d); @orig, @dir = o, d end
end

class Sphere
  attr_reader :center, :radius
  def initialize(c, r); @center, @radius = c, r; end

  def ray_sphere(ray)
    vec = @center - ray.orig
    b = vec.dot(ray.dir)
    det = b * b - vec.dot(vec) + (@radius * @radius)
    return 1.0/0 if det < 0
    sqDet = Math.sqrt(det)
    t2 = b + sqDet
    return 1.0/0 if t2 < 0
    t1 = b - sqDet
    t1 > 0 ? t1 : t2
  end

  def intersect(hit, ray)
    len = ray_sphere(ray)
    return hit if len >= hit.lambda
    vec = ray.orig + ray.dir * len - @center
    Hit.new(len, vec.unitise)
  end
end

class Vec
  attr_reader :x, :y, :z
  def initialize(x, y, z); @x, @y, @z = x, y, z; end 
  def +(v); Vec.new(@x + v.x, @y + v.y, @z + v.z) end
  def -(v); Vec.new(@x - v.x, @y - v.y, @z - v.z) end
  def *(s); Vec.new(@x * s, @y * s, @z * s) end
  def dot(v); @x * v.x + @y * v.y + @z * v.z end
  def unitise; self * (1.0 / Math.sqrt(self.dot(self))) end
end

def create(level, position, radius)
  sphere = Sphere.new(position, radius)
  return sphere if level == 1
  group = Group.new(Sphere.new(position, 3.0 * radius))
  group.objs << sphere
  factor = 3.0 * radius / Math.sqrt(12)
  [-1, 1].each{ |dx| [-1, 1].each{ |dz|
    childPos = position + Vec.new(dx, 1, dz) * factor
    group.objs << create(level - 1, childPos, radius / 2.0)}}
  group
end

def ray_trace(light, camRay, scene)
  delta = Math.sqrt(2.22045e-16)
  infinity = 1.0/0
  zero_vec = Vec.new(0.0, 0.0, 0.0)
  hit = scene.intersect(Hit.new(infinity, zero_vec), camRay)
  return 0 if hit.lambda == infinity
  refPos = camRay.orig + camRay.dir * hit.lambda + hit.normal * delta
  spGai = light.dot(hit.normal)
  return 0 if spGai >= 0
  spRay = Ray.new(refPos, light * -1)
  spHit = scene.intersect(Hit.new(infinity, zero_vec), spRay)
  spHit.lambda == infinity ? -spGai : 0
end

def run(px, level)
  ss = 4
  scene = create(level, Vec.new(0.0, -1.0, 1.0), 1.0)
  File.open('image.pgm', 'wb'){ |out|
    out.write("P5\n#{px} #{px}\n255\n")
    (px - 1).downto(0){ |y| (0...px).each{ |x|
      gain = 0.0
      (0...ss).each{ |dx| (0...ss).each{ |dy|
        dir = Vec.new(x + (dx.to_f / ss) - (px / 2), y + (dy.to_f / ss) - (px / 2), px)
        eye = Ray.new(Vec.new(0.0, 0.0, -4.0), dir.unitise)
        gain = gain + ray_trace(Vec.new(-1.0, -3.0, 2.0).unitise, eye, scene)}}
      out.write([(255.0 * gain / (ss * ss)).round].pack("C"))}}}
end


run(ARGV[0].to_i, ARGV[1].to_i)