Checks the number of iterations necessary to determine max # of inputs on a line with a fixed length

output.txt

Determining how many ip elements can sit on a line with a max length of 1000

     lower |   mid/test |      upper |        len | over/under
--------------------------------------------------------------
         1 |         50 |        100 |        840 |      under
        50 |         75 |        100 |       1240 |       over
        50 |         62 |         75 |       1032 |       over
        50 |         56 |         62 |        936 |      under
        56 |         59 |         62 |        984 |      under
        59 |         60 |         62 |       1000 |      under
        60 |         61 |         62 |       1016 |       over

Golden Ticket (under) = 60
7 iterations for 99 possible iterations (0.070707 efficiency)

ruby_binary_search.rb

require 'digest/sha1'

@k_len = Digest::SHA1.hexdigest('a').size     # 32
@ip_len = "255.255.255.255".size              # 15
@range = 1..100                               # starting range
@max_line_len = 1000                          # length to check against
@count = 0                                    # iteration counter

# Given a upper and lower boundary, determine if its
# middle value is over or under the given line length
# If over, use the lower boundary (lower..mid) for a recursive check,
# otherwise use upper boundary (mid..upper)
def check_boundary(lower, upper)
  # determine middle value
  mid = lower + ((upper-lower)/2)
  # Exit recursion if we've found the value
  throw(:found_value, mid) if (upper-lower) == 1

  # only increment iter count if we're checking the length
  @count += 1
  # Get the line length for the variable number of elements
  len = @k_len + (@ip_len*mid) + mid

  # Perform the test
  if len > @max_line_len
    puts_stats lower, mid, upper, len, :over
    # use the lower boundary
    check_boundary(lower, mid)
  else
    puts_stats lower, mid, upper, len, :under
    # use the upper boundary
    check_boundary(mid, upper)
  end
end

# Log method for values in a given test
def puts_stats lower, mid, upper, len, over_under
  puts '%10d | %10d | %10d | %10d | %10s' % [lower, mid, upper, len, over_under]
end

# Specify some information for readability
puts 'Determining how many ip elements can sit on a line with a max length of %d' % @max_line_len
puts 
legend = '%10s | %10s | %10s | %10s | %10s' % %w(lower mid/test upper len over/under)
puts legend
puts '-'*legend.size

# Run the recursive boundary checking
golden_ticket = catch(:found_value) do
  check_boundary(@range.first, @range.last)
end

# Output results
puts
puts 'Golden Ticket (under) = %s' % golden_ticket.to_s
possible_iterations = @[email protected]
efficiency = @count.to_f / possible_iterations.to_f
puts '%d iterations for %d possible iterations (%f efficiency)' % [@count, possible_iterations, efficiency]