Binary Search Class in Ruby

binary_search.rb

module BinarySearchExtensions
  refine Array do
    def mean
      reduce(&:+) / length.to_f
    end
  end
end

class BinarySearch
  using BinarySearchExtensions

  attr_accessor :count
  attr_reader   :range

  def initialize(options={})
    @range = options.fetch(:range, 1..100)
    @target = options.fetch(:target, rand(range))
    @count  = 0
  end

  def zone_in(options={})
    array = options.fetch(:range, range).to_a
    index = array.mean.floor
    @count += 1
    if index == target
      { index: index, count: count }
    else
      zone_in({
        range: RangeSlicer.new({
          index: index, target: target, array: array
        }).slice
      })
    end
  end

  private
  attr_reader :target

end

class RangeSlicer
  attr_reader :index, :array

  def initialize(options)
    @index = options.fetch(:index)
    @target = options.fetch(:target)
    @array = options.fetch(:array)
  end

  def slice
    index > target ? slice_left(index, array) : slice_right(index, array)
  end

  private
  attr_reader :target
  
  def slice_left(index, array)
    (array.first..index.pred)
  end

  def slice_right(index, array)
    (index.succ..array.last)
  end
end

#~-~-~-~-~#

require 'minitest/autorun'

CONCURRENCY = 100
Minitest.parallel_executor = Minitest::Parallel::Executor.new(CONCURRENCY)
Minitest::Test.parallelize_me!

describe 'BinarySearch' do
  subject { BinarySearch.new(options) }
  let(:options) { {} }

  describe "#initialize" do
    it "should default to a range of 1..100" do
      assert_equal (1..100), subject.range
    end

    describe "can take a custom range" do
      let(:options) { { range: (50..100) } }

      it "should have a range of 50..100)" do
        assert_equal (50..100), subject.range
      end
    end

    it "creates a random target" do
      assert_equal true, subject.zone_in[:index].between?(1, 100)
    end

    # this is all the confidence I have in its randomness :(
    5.times do
      it "is hopefully quite random" do
        answer1 = BinarySearch.new({range:(1..1000)}).zone_in[:index]
        answer2 = BinarySearch.new({range:(1..1000)}).zone_in[:index]

        refute_equal answer1, answer2
      end
    end
  end

  describe "#zone_in" do
    # I thought this method was clever until I
    # had to try and work out how to test it

    it "guesses the number" do
      subject.stub :target, 1 do
        assert_equal subject.target, subject.zone_in[:index]
      end
    end

    describe "we can predict the exact number of guesses" do
      describe "the default range" do

        it "guesses the number" do
          subject.stub :target, 40 do
            assert_equal subject.target, subject.zone_in[:index]
          end
        end

        it "takes exactly 5 guesses" do
          subject.stub :target, 40 do
            assert_equal 5, subject.zone_in[:count]
          end
        end

        it "it takes no more than 7 guesses with a random number" do
          assert_operator subject.zone_in[:count], :<=, 7
        end
      end

      describe "the smallest range" do
        let(:options) { { range: (1..1) } }

        it "guesses the number" do
          assert_equal 1, subject.zone_in[:index]
        end

        it "takes exactly 1 guess" do
          subject.stub :target, 1 do
            assert_equal 1, subject.zone_in[:count]
          end
        end

        it "it takes no more than 1 guess with a random number" do
          assert_operator subject.zone_in[:count], :<=, 1
        end
      end

      describe "a small range" do
        let(:options) { { range: (1..5) } }

        it "guesses the number" do
          subject.stub :target, 4 do
            assert_equal subject.target, subject.zone_in[:index]
          end
        end

        it "it takes exactly 2 guesses to get it" do
          subject.stub :target, 4 do
            assert_equal 2, subject.zone_in[:count]
          end
        end

        it "it takes no more than 3 guesses with a random number" do
          assert_operator subject.zone_in[:count], :<=, 3
        end
      end

      describe "a slightly less small range" do
        let(:options) { { range: (1..5) } }

        it "guesses the number" do
          subject.stub :target, 4 do
            assert_equal subject.target, subject.zone_in[:index]
          end
        end

        it "takes exactly 2 guesses to get it" do
          subject.stub :target, 4 do
            assert_equal 2, subject.zone_in[:count]
          end
        end

        it "it takes no more than 3 guesses with a random number" do
          assert_operator subject.zone_in[:count], :<=, 3
        end
      end

      describe "getting a bit bigger now" do
        let(:options) { { range: (1..8) } }

        it "guesses the number" do
          subject.stub :target, 5 do
            assert_equal subject.target, subject.zone_in[:index]
          end
        end

        it "it takes exactly 3 guesses to get it" do
          subject.stub :target, 5 do
            assert_equal 3, subject.zone_in[:count]
          end
        end

        it "it takes no more than 4 guesses with a random number" do
          assert_operator subject.zone_in[:count], :<=, 4
        end
      end

      describe "a large range" do
        let(:options) { { range: (1..1024) } }

        it "guesses the number" do
          subject.stub :target, 93 do
            assert_equal subject.target, subject.zone_in[:index]
          end
        end

        it "it takes exactly 10 guesses to get it" do
          subject.stub :target, 93 do
            assert_equal 10, subject.zone_in[:count]
          end
        end

        it "it takes no more than 3 guesses with a random number" do
          assert_operator subject.zone_in[:count], :<=, 10
        end
      end

      describe "a range with a non-1 index" do
        let(:options) { { range: (50..150) } }

        it "guesses the number" do
          subject.stub :target, 73 do
            assert_equal subject.target, subject.zone_in[:index]
          end
        end

        it "takes exactly 7 guesses to get it" do
          subject.stub :target, 73 do
            assert_equal 7, subject.zone_in[:count]
          end
        end

        it "turns out 7 is the furthest you can get" do
          assert_operator subject.zone_in[:count], :<=, 7
        end
      end

      describe "a specified target" do
        subject { BinarySearch.new({target: 53}) }
        it "zone_ins the right number" do
          assert_equal 53, subject.zone_in[:index]
        end

        it "takes exactly 5 guesses to get it" do
          assert_equal 5, subject.zone_in[:count]
        end
      end
    end
  end

  describe "you can't access the target from the outside" do
    subject { BinarySearch.new }

    it "won't let you do it" do
      assert_raises(NoMethodError) { subject.target }
    end
  end

  describe "thread safe, I tells ya!" do
    (1..CONCURRENCY).each do |n|
      it "tests BinarySearch.new({target: #{n}}) is correct" do
        subject { BinarySearch.new({target: n}) }
        subject.stub :target, n do
          sleep 1/100
          assert_equal n, subject.zone_in[:index]
        end
      end
    end
  end
end

describe 'RangeSlicer' do
  subject { RangeSlicer.new(options) }

  describe "#slice" do
    describe "we can predict the slicing when the guess is too low" do
      let(:options) { {index: 2, target: 4, array: (1..10)} }

      it "it slices!" do
        assert_equal subject.slice, (3..10)
      end
    end

    describe "we can predict the slicing when the guess is too high" do
      let(:options) { {index: 74, target: 31, array: (1..192)} }

      it "it slices!" do
        assert_equal subject.slice, (1..73)
      end
    end

    describe "it will totally crap out if there are no options" do
      let(:options) { {} }
      it "goes beserk!" do
        assert_raises(KeyError) { subject }
      end
    end
  end

  describe "you can't access the target from the outside" do
    subject { RangeSlicer.new(options) }
    let(:options) { {index: 2, target: 4, array: (1..10)} }

    it "won't let you do it" do
      assert_raises(NoMethodError) { subject.target }
    end
  end
end


describe 'BinarySearchExtensions' do
  using BinarySearchExtensions

  it "should zone_in the mean average" do
    assert_equal      5    , (0..10).to_a.mean
    assert_equal      5.5  , (1..10).to_a.mean
    assert_equal     18    , (1..35).to_a.mean
    assert_equal 157098    , (1..314195).to_a.mean
  end
end