Binary Search theory proved

guesser.rb

#!ruby

#--
# Copyright 2009 Wilker Lucio <wilkerlucio@gmail.com>
# 
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
# 
#     http://www.apache.org/licenses/LICENSE-2.0
# 
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
#++

# This program was created to demonstrate the binary search theory.
# By using the algoritm of binary search, this program will find
# any number that you guess in at max 20 tries.

# This script requires the gem highline:
# sudo gem install highline

require 'rubygems'
require 'highline/import'

tries = 0
l = 0
r = 1_000_000

puts %{
Hi! Think in a number between 0 and 1,000,000 I will guess your number in
at max 20 tries. When I guess your number, press + if you number is greater
than the number that I guessed, or - if your number is lesser. If I guess
correct, press .

}

ask ("Press any key to start") { |q| q.limit = 1 }

puts

loop do
  guess = ((r - l) / 2).floor + l
  tries += 1
  
  puts "I guess your number is #{guess}"
  
  input = ask("I'm correct?") { |q| q.in = %w{+ - .}; q.limit = 1 }
  
  case input
    when '+'
      l = guess + 1
    when '-'
      r = guess - 1
    when '.'
      break
  end
end

puts "I found your value with #{tries} tries!"