I've been reading and working through the exercises in the excellent Programming Elixir when I came across a problem that seemed easy enough: given a number contained within a range, write a binary search to guess the number. I thought "sure, I've solved this problem [years] ago, this won't be bad at all." Haha, funny. I've definitely gotten rusty on this class of problem and after about 20 minutes trying to solve this functionally in Elixir I turned to Ruby to work through the challenge in more familiar territory.

My first solution used a loop (and was based on the Javascript in this post which has an excellent write up of applying this algorithm to dichotomic search):

 # guess.rb  
class Guess < Struct.new(:number, :range)  
  def initialize(number, range = 1..1000)
    super(number, range)
  end

  def start
    guess
  end

  private
  def guess
    min = range.min
    max = range.max
    g = 0
    while min < max do
      g = min + (((max - min - 1) / 2) + 1).ceil
      puts "Is it #{g}?"
      if number < g
        max = g - 1
      else
        min = g
      end
    end
    puts "It is #{g}"
  end

end

That works, so the next step is to make the code recursive so I can translate it easier to Elixir. Here's the recursive solution:

 # guess.rb  
class Guess < Struct.new(:number, :range)  
  def initialize(number, range = 1..1000)
    super(number, range)
  end

  def start
    guess range.max / 2, range
  end
  private
  def guess(g, current_range)
    if g == number
      puts "It is #{g}"
      exit
    end

    g = current_range.min + (((current_range.max - current_range.min - 1) / 2) + 1).ceil
    puts "Is it #{g}?"
    if number < g
      guess(g, current_range.min..(g-1))
    else
      guess(g, g..current_range.max)
    end
  end

end

Looking at the recursive solution its easy to see how to translate this into Elixir. First, the convergence (base solution) in Elixir is our entry guard clause, while the calculation line (current_range.min + (((current_range.max - current_range.min - 1) / 2) + 1).ceil becomes an input into a helper function. The if statement's branches become two helper functions. The solution ends up looking like this:

# chop.ex  
defmodule Chop do

  def guess(n), do: guess(n, 1..1000)

  def guess(n, b..e) when !(n in b..e), do: IO.puts "Unguessable"

  def guess(n, b..b) when b == n, do: IO.puts "It is #{n}"

  def guess(n, b..e) do
    g = b + div(e - b - 1, 2) + 1
    IO.puts "Is it #{g}?"
    _guess(n, g, b..e)
  end

  def _guess(n, g, b.._) when n < g, do: guess(n, b..g-1)

  def _guess(n, g, _..e), do: guess(n, g..e)

end