batch_bisect.rb

require 'set'

# Invokes the block, passing in all or some of the input. If the block throws, the block will be invoked
# repeatedly for a progressively smaller subset of the batch until all elements are either processed or
# failed. Elements contained in sub-batches which succeed are never re-tried. Returns two Arrays, the first
# contains all items which succeeded and the second contains all elements which failed.
#
# This can be useful when a batch API will throw when it receies one or more malformed items, but doesn't
# tell you which input items were at fault.
#
# @param input [Enumerable, #to_ary] Elements to process as a batch
# @return [Array] Two Arrays. First contains inpt elements which succeeded. Second contains failures.
def batch_bisect( input, &blk )
  input = Array input
  return [[], []] if input.empty?
  blk.call(input)
  [input, []]
rescue
  return [[], input] unless input.size > 1
  half = input.size / 2
  good1, bad1 = batch_bisect input.take(half), &blk
  good2, bad2 = batch_bisect input[half..-1],  &blk
  [good1 + good2, bad1 + bad2]
end

def test( pool, errors, debug_on = false )
  problems = Array(1..pool).sample(errors).to_set
  puts "Problems: #{problems.inspect}" if debug_on
  attempts = 0
  batch_bisect(1..pool){ |batch|
    attempts += 1
    if batch.none?{ |n| problems.include? n }
      puts 'Pass: %s' % batch.inspect if debug_on
      next
    end
    puts 'Fail: %s' % batch.inspect if debug_on
    fail
  }.tap{
    puts "Attempts: #{attempts}"
  }
end

test 16, 1, true

# Problems: #<Set: {9}>
# Fail: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
# Pass: [1, 2, 3, 4, 5, 6, 7, 8]
# Fail: [9, 10, 11, 12, 13, 14, 15, 16]
# Fail: [9, 10, 11, 12]
# Fail: [9, 10]
# Fail: [9]
# Pass: [10]
# Pass: [11, 12]
# Pass: [13, 14, 15, 16]
# Attempts: 9