[ruby] 40 stones - a brute-force solution

gistfile1.rb

# http://beust.com/weblog/2011/10/30/a-new-coding-challenge/

require 'set'

def cut(a, n)
  if a < n+1
    return nil
  elsif n <= 0
    return [[a]]
  elsif a == n+1
    return [ Array.new(a, 1) ]
  end
  Enumerator.new do |y|
    (1..a/2).each do |x|
      p = cut(a-x, n-1)
      next if p.nil?
      if p.is_a? Array and p.size == 1
        y << p[0].push(x)
      else
        p.each do |xx|
          y << xx.push(x)
        end
      end
    end
  end
end

def perm(n, arr)
  a = arr.size
  Enumerator.new do |y|
    (a**n).times do |i|
      y << n.times.map do |j|
        arr[(i / a**j) % a]
      end
    end
  end
end

def sats(arr, s, ps)
  ps.each do |p|
    s.delete arr.zip(p).inject(0) { |r, (a, w)|
      w == 0 ? r : (w == 1 ? r + a : r - a)
    }
  end
  s.empty?
end

def solve40
  perms = perm(4, [-1, 0, 1])
  weights = (1..40).to_set
  cut(40, 3).each do |c|
    if sats(c, weights.clone, perms)
      puts "found: #{c}"
      break
    end
  end
  nil
end