Algo and DS implementations in Ruby

binary_tree.rb

class BinaryTreeNode
  attr_accessor :left, :right, :data
  def initialize(data)
    @data = data
  end
end


class TreeQueue

  def initialize
    @q = []
  end

  def enq(v)
    @q.push(v)
  end

  def deq
    @q.shift
  end

  def empty?
    @q.empty?
  end
end

def print_k_last(head, k)
  q = TreeQueue.new
  q.enq(head)
  q.enq(nil)

  while !q.empty?
    count = 1
    temp = q.deq

    while !temp.nil?
      q.enq(temp.right) if !temp.nil? && !temp.right.nil?
      q.enq(temp.left) if !temp.nil? && !temp.left.nil?
      temp = q.deq
      count = count + 1

      if temp.nil? && !q.empty?
        q.enq(nil)
        break
      end

      if count == k
        puts "Node: #{temp.data}"
      end
    end
  end
end

def print_by_level_last(head)
  q = TreeQueue.new
  q.enq(head)
  q.enq(nil)
  level = 1

  while !q.empty?
    count = 1
    temp = q.deq

    while !temp.nil?
      q.enq(temp.right) if !temp.nil? && !temp.right.nil?
      q.enq(temp.left) if !temp.nil? && !temp.left.nil?
      temp = q.deq
      count = count + 1

      if temp.nil? && !q.empty?
        q.enq(nil)
        level = level + 1
        break
      end

      if count == level
        puts "Node: #{temp.data}"
      end
    end
  end
end

n = BinaryTreeNode.new(1)
n1 = BinaryTreeNode.new(2)
n2 = BinaryTreeNode.new(3)
n3 = BinaryTreeNode.new(4)
n4 = BinaryTreeNode.new(5)
n5 = BinaryTreeNode.new(6)
n6 = BinaryTreeNode.new(7)
n7 = BinaryTreeNode.new(8)
n8 = BinaryTreeNode.new(9)
n9 = BinaryTreeNode.new(10)
n10 = BinaryTreeNode.new(11)
n11 = BinaryTreeNode.new(12)
n12 = BinaryTreeNode.new(13)
n13 = BinaryTreeNode.new(14)
n14 = BinaryTreeNode.new(15)

n.left = n1
n.right = n2

n1.left = n3
n1.right = n4

n2.left = n5
n2.right = n6

n3.left = n7
n3.right = n8

n4.left = n9
n4.right = n10

n5.left = n11
n5.right = n12

n6.left = n13
n6.right = n14

print_k_last(n, 2)

link_list.rb

# mostly reverse operations!
class Node
  attr_accessor :data, :next_value
  def initialize(data)
    @data = data
  end
end

def reverse(head)
  return if head.nil?
  prev       = nil
  current    = head
  next_value = nil

  while (!current.nil?)
    next_value = current.next_value
    current.next_value  = prev
    prev       = current
    current    = next_value
  end

  return prev
end

def reverse_in_k_size(head, k)
  current    = head
  prev       = nil
  next_value = nil
  count      = 0

  while (!current.nil? && count < k)
    next_value         = current.next_value
    current.next_value = prev
    prev               = current
    current            = next_value
    count              = count + 1
  end

  if !current.nil?
    head.next_value = reverse_in_k_size(current, k)
  end

  return prev
end

def alternate_reverse(head, k)
  prev       = nil
  current    = head
  next_value = nil
  count = 0

  while (!current.nil? && count < k)
    next_value         = current.next_value
    current.next_value = prev
    prev               = current
    current            = next_value
    count              = count + 1
  end

  while !current.nil? && count != 0
    next_value = head.next_value
    head.next_value = current
    head = head.next_value
    current = current.next_value
    count = count - 1
  end

  head.next_value = next_value

  if !current.nil?
    head.next_value = alternate_reverse(current, k)
  end

  return prev
end


n = Node.new(1)
n1 = Node.new(2)
n2 = Node.new(3)
n3 = Node.new(4)
n4 = Node.new(5)
n5 = Node.new(6)
n6 = Node.new(7)
n7 = Node.new(8)
n8 = Node.new(9)
n9 = Node.new(10)

n.next_value = n1
n1.next_value = n2
n2.next_value = n3
n3.next_value = n4
n4.next_value = n5
n5.next_value = n6
n6.next_value = n7
n7.next_value = n8
n8.next_value = n9


# node = reverse(n)
node = alternate_reverse(n, 2)
# node = reverse_in_k_size(n, 2)

# puts node.inspect

while !node.nil?
  puts node.data
  node = node.next_value
end

merge_sort.rb

@array = [2, 4, 1, 6, 5, 3]

def merge_sort(array, low, high)
  return array[low..high] if low == high
  pivot = low + (high - low)/2

  l1 = merge_sort(array, low, pivot)
  l2 = merge_sort(array, pivot+1, high)

  merge(l1, l2)
end

def merge(a, b)
  c = []
  while !a.empty? && !b.empty?
    if a[0] > b[0]
      c << b[0]
      b.delete(b[0])
    else
      c << a[0]
      a.delete(a[0])
    end
  end

  while !a.empty?
    c << a[0]
    a.delete(a[0])
  end

  while !b.empty?
    c << b[0]
    b.delete(b[0])
  end

  c
end

p merge_sort(@array, 0, @array.size - 1)

my_flatten.rb

class Array
  def my_flatten(level = nil)
    rb_flatten(self, [], level)
  end

  private
  # apply recursion based on the level
  # when no level provided, then produce a complete flatten array
  # when level is given, then produce a flatten array flattened till that certain level
  def rb_flatten(array, result, level)
    array.each do |value|
      if ((value.is_a? Array) && (level.nil? || (level && level > 0)))
        rb_flatten(value, result, (level.nil? ? level : ((level || 0 ) - 1)))
      else
        result << value
      end
    end
    return result
  end
end

# arr = [[1,[2, [55, 6]],[3]],4]

# p arr.my_flatten    #=> [1, 2, 55, 6, 3, 4]
# p arr.my_flatten(1) #=> [1, [2, [55, 6]], [3], 4]
# p arr.my_flatten(2) #=> [1, 2, [55, 6], 3, 4]
# p arr               #=> [[1,[2, [55, 6]],[3]],4]


# test cases
require File.expand_path('../array_flatten', __FILE__)
require 'minitest/autorun'

class ArrayFlattenTest < MiniTest::Unit::TestCase
  def setup
    @arr = [[1,[2, [55, 6]],[3]],4]
  end

  def test_my_flatten
    flatted_array = @arr.flatten
    my_flatted_array = @arr.my_flatten
    assert_equal flatted_array, my_flatted_array
  end

  def test_my_flatten_with_one_level
    flatted_array = @arr.flatten(1)
    my_flatted_array = @arr.my_flatten(1)
    
    assert_equal flatted_array, my_flatted_array
  end

  def test_my_flatten_with_two_level
    flatted_array = @arr.flatten(2)
    my_flatted_array = @arr.my_flatten(2)
    
    assert_equal flatted_array, my_flatted_array
  end
end

quick_sort.rb

@array = [2, 4, 1, 6, 5, 3]

def partition(left_index, right_index, pivot)
  puts "left_index: #{left_index}, right_index: #{right_index}"
  leftPointer  = left_index
  rightPointer = right_index - 1

  while true do
    while (@array[leftPointer] < pivot)
      leftPointer = leftPointer + 1
    end

    while (@array[rightPointer] > pivot && rightPointer > 0)
      rightPointer = rightPointer - 1
    end

    if (leftPointer >= rightPointer)
      break
    else
      puts "items swapped: #{@array[leftPointer]}, #{@array[rightPointer]}"
      swap(leftPointer, rightPointer)
    end
  end

  puts "pivots swapped: #{@array[leftPointer]}, #{@array[right_index]}"
  swap(leftPointer, right_index)
  puts "updated array: #{@array.inspect}"
  leftPointer
end

def swap(left, right)
  temp          = @array[left]
  @array[left]  = @array[right]
  @array[right] = temp
end

def quick_sort(left, right)
  if (right - left) <= 0
    return
  else
    pivot = @array[right]
    partition_point = partition(left, right, pivot)
    quick_sort(left, partition_point - 1)
    quick_sort(partition_point+1, right)
  end
end

quick_sort(0, @array.length - 1)
p @array

substring_palindrome.rb

# check the number of substring palindromes in a string
# usage: $ ruby palindrome.rb aabba

string = ARGV[0] || "aabbaa"

result = []
def check_palindaromes(result, string, mid_pointer_left, mid_pointer_right)
  while (mid_pointer_left >= 0 && mid_pointer_right < string.length && string[mid_pointer_left] == string[mid_pointer_right])
    substring = string[mid_pointer_left..mid_pointer_right]
    result << substring if substring.length > 1
    mid_pointer_left = mid_pointer_left - 1
    mid_pointer_right = mid_pointer_right + 1
  end
end

0.upto(string.length) do |i|
  check_palindaromes(result, string, i, i+1);
  check_palindaromes(result, string, i, i);
end

p result #=> ["aa", "bb", "abba", "aabbaa", "aa"]