kata_2_iterative_solution.rb

require 'test/unit'

def chop(target, input)
  puts "--------------------------------"
  puts "chop #{target}, #{input.inspect}"
  return -1 if input.empty? || target < 0 || target < input.first || target > input.last
  found = false
  @current_index = input.length / 2
  @current_array = input
  while !found do
    puts "current_index: #{@current_index}"
    return @current_index if target == input[@current_index]
    left, right = @current_array.split_on @current_index
    puts "#{left.inspect}, #{right.inspect}"
    if !left.empty? && target <= left.last
      go(:left, left)
    elsif !right.empty? && target >= right.first
      go(:right, right)
    else
      return -1
    end
  end
end

def go(direction, input)
  op = direction == :left ? "-" : "+"
  @current_index = @current_index.send(op, input.length / 2)
  @current_index = @current_index.send(op, 1) unless input.length.even?
  @current_array = input
end

class Fixnum
  def even?
    self % 2 == 0
  end
end

class Array
  def split_on(pos)
      [self[0...pos], self[pos + 1...length]]
  end
end

class TestChop < Test::Unit::TestCase
  def test_chop
    assert_equal(-1, chop(3, []))
    assert_equal(-1, chop(3, [1]))
    assert_equal(0,  chop(1, [1]))
    #
    assert_equal(0,  chop(1, [1, 3, 5]))
    assert_equal(1,  chop(3, [1, 3, 5]))
    assert_equal(2,  chop(5, [1, 3, 5]))
    assert_equal(-1, chop(0, [1, 3, 5]))
    assert_equal(-1, chop(2, [1, 3, 5]))
    assert_equal(-1, chop(4, [1, 3, 5]))
    assert_equal(-1, chop(6, [1, 3, 5]))
    #
    assert_equal(0,  chop(1, [1, 3, 5, 7]))
    assert_equal(1,  chop(3, [1, 3, 5, 7]))
    assert_equal(2,  chop(5, [1, 3, 5, 7]))
    assert_equal(3,  chop(7, [1, 3, 5, 7]))
    assert_equal(-1, chop(0, [1, 3, 5, 7]))
    assert_equal(-1, chop(2, [1, 3, 5, 7]))
    assert_equal(-1, chop(4, [1, 3, 5, 7]))
    assert_equal(-1, chop(6, [1, 3, 5, 7]))
    assert_equal(-1, chop(8, [1, 3, 5, 7]))
  end
end
# >> Loaded suite -
# >> Started
# >> --------------------------------
# >> chop 3, []
# >> --------------------------------
# >> chop 3, [1]
# >> --------------------------------
# >> chop 1, [1]
# >> current_index: 0
# >> --------------------------------
# >> chop 1, [1, 3, 5]
# >> current_index: 1
# >> [1], [5]
# >> current_index: 0
# >> --------------------------------
# >> chop 3, [1, 3, 5]
# >> current_index: 1
# >> --------------------------------
# >> chop 5, [1, 3, 5]
# >> current_index: 1
# >> [1], [5]
# >> current_index: 2
# >> --------------------------------
# >> chop 0, [1, 3, 5]
# >> --------------------------------
# >> chop 2, [1, 3, 5]
# >> current_index: 1
# >> [1], [5]
# >> --------------------------------
# >> chop 4, [1, 3, 5]
# >> current_index: 1
# >> [1], [5]
# >> --------------------------------
# >> chop 6, [1, 3, 5]
# >> --------------------------------
# >> chop 1, [1, 3, 5, 7]
# >> current_index: 2
# >> [1, 3], [7]
# >> current_index: 1
# >> [1], []
# >> current_index: 0
# >> --------------------------------
# >> chop 3, [1, 3, 5, 7]
# >> current_index: 2
# >> [1, 3], [7]
# >> current_index: 1
# >> --------------------------------
# >> chop 5, [1, 3, 5, 7]
# >> current_index: 2
# >> --------------------------------
# >> chop 7, [1, 3, 5, 7]
# >> current_index: 2
# >> [1, 3], [7]
# >> current_index: 3
# >> --------------------------------
# >> chop 0, [1, 3, 5, 7]
# >> --------------------------------
# >> chop 2, [1, 3, 5, 7]
# >> current_index: 2
# >> [1, 3], [7]
# >> current_index: 1
# >> [1], []
# >> --------------------------------
# >> chop 4, [1, 3, 5, 7]
# >> current_index: 2
# >> [1, 3], [7]
# >> --------------------------------
# >> chop 6, [1, 3, 5, 7]
# >> current_index: 2
# >> [1, 3], [7]
# >> --------------------------------
# >> chop 8, [1, 3, 5, 7]
# >> .
# >> Finished in 0.000834 seconds.
# >> 
# >> 1 tests, 19 assertions, 0 failures, 0 errors