Skip to content

Instantly share code, notes, and snippets.

@danvalencia
Created May 3, 2012 02:41
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save danvalencia/2582632 to your computer and use it in GitHub Desktop.
Save danvalencia/2582632 to your computer and use it in GitHub Desktop.
Code kata two: karate chop
# Mixin module for enhancing the Array class
module KarateChopArray
def left_side
slice(0, self.size/2)
end
def right_side
slice(self.size/2, self.size-1)
end
def in_left_side?(num)
num < middle_number
end
def in_right_side(num)
num > middle_number
end
def middle_number
self[middle_index]
end
def middle_index
size/2
end
end
#include the mixin into the Array class
class Array
include KarateChopArray
end
def chop(n, arr)
return -1 unless arr.include?(n)
return 0 if arr.size == 1
offset = 0
chop_with_offset(n, arr, offset)
end
def chop_with_offset(n, arr, offset)
middle_number = arr.middle_number
if n == middle_number
#offset += arr.left_side.size
return arr.middle_index + offset
elsif arr.in_left_side?(n)
return chop_with_offset(n, arr.left_side, offset)
else
offset += arr.left_side.size
return chop_with_offset(n, arr.right_side, offset)
end
end
#
# inicio = 0
# fin_idx = arr.size
#[ 0 1 2 3 4 5 6 7 8]
#
# assert_equal(0, chop(1, [1, 3, 5]))
# n = 1
# start 0, end 2, mid = 1, mid_val 3,
# start 0, end 0
#
#assert_equal(1, chop(3, [1, 3, 5]))
# n = 3, start=0, end=2, mid=1, mid_val=3
#
#assert_equal(2, chop(5, [1, 3, 5, 7]))
# n = 5
# start=0, end = 3, mid = 1, mid_val=3
# start = 2, end=3
def chop(n, arr)
#debugger
return -1 if arr.empty?
return 0 if arr.size == 1 && arr[0] == n
starting_idx = 0
end_idx = arr.size - 1
while end_idx > starting_idx
middle_idx = (end_idx + starting_idx)/2
middle_value = arr[middle_idx]
return middle_idx if middle_value == n
if n < middle_value
end_idx = middle_idx - 1
else
starting_idx = middle_idx + 1
end
end
return end_idx if arr[end_idx] == n
return -1 # not found
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment