Long Division Coding Challenge

long_division.rb

### BEST SOLUTION I HAVE SO FAR (unrealistic to acheive on first try)

# SUPER DRY'd up way of testing both techniques
def divide(x, y, technique='multiply')
  sign = (x < 0 && y > 0 || x > 0 && y < 0) ? -1 : 1
  x, y = x.abs, y.abs
  return 0 if x == 0 || y == 0 || y > x
  return sign * 1 if x == y

  i = 1
  while y * next_quotient(i, technique) <= x do
    i = next_quotient(i, technique)
  end
  sign * (i + divide(x - (i * y), y))
end

# Gets next quotient using either power of two or bitshift technique
def next_quotient(i, technique)
  technique == 'bitshift' ? i << 1 : i * 2
end

### TESTING

# Testing assertion similar to minitest
def assert_divide(a, b, technique)
  result = divide(a, b, technique)
  if result != (b == 0 ? 0 : a / b)
    puts "false: expected value #{b} does not match received value #{a}"
    false
  else
    puts 'true'
    true
  end
end

# Tests
%w(multiply bitshift).each do |technique|
  assert_divide(8, 2, technique) # even / even no remainder
  assert_divide(8, 6, technique) # even / even with remainder
  assert_divide(9, 2, technique) # odd / even always has remainder
  assert_divide(8, 3, technique) # even / odd always has remainder
  assert_divide(9, 3, technique) # odd / odd no remainder
  assert_divide(9, 6, technique) # odd / odd has remainder


  assert_divide(0, 4, technique) # x == 0
  assert_divide(2, 4, technique) # x < y
  assert_divide(2, 0, technique) # y == 0
  assert_divide(2, 2, technique) # x == y
  assert_divide(4, 1, technique) # y == 1

  assert_divide(-8, 2, technique)  # negative x positive y
  assert_divide(8, -2, technique)  # positive x negative y
  assert_divide(-8, -2, technique) # negative x negative y

  assert_divide(3456789, 12345, technique)  # x and y are both large
  assert_divide(3456789, 13, technique)     # x is large, y is small

  assert_divide(12667285656990194193, 3874417256, technique)  # x and y are both very large
  assert_divide(12667285656990194193, 13, technique)          # x is very large, y is small
end

### OPTIMAL SOLUTIONS USING BINARY SEARCH

# ## BINARY SEARCH USING MULTIPLICATION
# def divide(x, y, _)
#   sign = (x < 0 && y > 0 || x > 0 && y < 0) ? -1 : 1
#   x, y = x.abs, y.abs
#   return 0 if x == 0 || y == 0 || y > x
#   return sign * 1 if x == y
#
#   i = 1
#   while y * (i * 2) <= x do
#     i *= 2
#   end
#
#   sign * (i + divide(x - (i * y), y))
# end

# ## BINARY SEARCH USING BITSHIFT
# def divide(x, y, _)
#   sign = (x < 0 && y > 0 || x > 0 && y < 0) ? -1 : 1
#   x, y = x.abs, y.abs
#   return 0 if x == 0 || y == 0 || y > x
#   return sign * 1 if x == y
#
#   i = 1
#   while y * (i << 1) <= x do
#     i = i << 1
#   end
#
#   sign * (i + divide(x - (i * y), y))
# end

### NAIVE SOLUTIONS

# ## USING MULTIPLICATION
# def divide(x, y, _)
#   sign = (x < 0 && y > 0 || x > 0 && y < 0) ? -1 : 1
#   x, y = x.abs, y.abs
#   return 0 if x == 0 || y == 0 || y > x
#   return sign * 1 if x == y
#
#   i = 0
#   while (i + 1) * y <= x do
#     i += 1
#   end
#
#   sign * i
# end

# ## USING ADDITION
# def divide(x, y, _)
#   sign = (x < 0 && y > 0 || x > 0 && y < 0) ? -1 : 1
#   x, y = x.abs, y.abs
#   return 0 if x == 0 || y == 0 || y > x
#   return sign * 1 if x == y
#
#   i = 0
#   total = 0
#   while total + y <= x do
#     total += y
#     i += 1
#   end
#
#   sign * i
# end