Google Code Jam 2014 Round 1A

shota.rb

require 'scanf'

def flip(mask, os)
  os.map { |o| mask ^ o }
end

Infinity = 1.0/0

def solve(n, l, flows, required_flows)
  outlets = flows.split(" ").map { |f| f.to_i(2) }
  outlet = outlets.first
  required_outlets = required_flows.split(" ").map { |f| f.to_i(2) }

  flips_done = required_outlets.reduce(Infinity) do |best_flips, possible_outlet|
    flips = outlet ^ possible_outlet

    left = flip(flips, outlets) - required_outlets

    if left.empty?
      new_flips_count = flips.to_s(2).scan(/\d/).select { |d| d == "1" }.size

      if new_flips_count.zero? # best result possible
        return 0
      else
        new_flips_count < best_flips ? new_flips_count : best_flips
      end
    else
      best_flips
    end
  end

  flips_done == Infinity ? "NOT POSSIBLE" : flips_done
end

input = ARGF.each_line.to_a

cases = input.shift.to_i

cases.times do |i|
  n, l = input.shift.scanf("%d %d")
  flow = input.shift
  required_flow = input.shift

  puts "Case ##{i+1}: #{solve(n, l, flow, required_flow)}"
end

# ruby shota.rb < input.in > output.in