More practice

practice2.rb

#!/usr/bin/env ruby -w
# ✓ FizzBuzz
# ✓ Fibonacci
# ✓ Bubblesort
# ✓ Mergesort
# ✓ Search Tree
# ✓ Rotated minimum
# ✓ Prime factorization

def fizz_buzz n
  (1..n).each do |i|
    if i % 3 == 0 and i % 5 == 0
      puts "  FizzBuzz"
    elsif i % 5 == 0
      puts "  Buzz"
    elsif i % 3 == 0
      puts "  Fizz"
    end
  end
end


class Fib
  @@memo = { 1 => 1, 2 => 1 }

  attr_reader :val
  def initialize n
    raise ArgumentError if n <= 0
    if @@memo.has_key? n
      @val = @@memo[n]
    else
      @val = Fib.new(n-1).val + Fib.new(n-2).val
    end
  end
end

def fib n ; Fib.new(n).val end


def boring_fib n
  raise ArgumentError if n <= 0
  return 1 if n <= 2
  boring_fib(n-1) + boring_fib(n-2)
end


class Factorization
  @@memo = {}
  attr_reader :factors

  def initialize n
    orig_n = n - 1
    orig_n += 1
    raise ArgumentError if n < 2

    @factors = []

    if @@memo.has_key? n
      @factors = @@memo[n]
    else
      candidates = (2..Math.sqrt(n)).select do |i|
        n % i == 0
      end
      if candidates.empty? ; @factors = [n]
      else
        i = candidates.first
        @factors += Factorization.new(i).factors
        @factors += Factorization.new(n / i).factors
      end

      @@memo[n] = factors
    end
  end
end

def factorize n ; Factorization.new(n).factors end

def boring_factorize n
  factors = []

  candidates = (2..Math.sqrt(n)).select do |i|
    n % i == 0
  end
  if candidates.empty? ; factors = [n]
  else
    i = candidates.first
    factors += boring_factorize(i)
    factors += boring_factorize(n / i)
  end

  return factors
end


class Array
  def rot_min
    i, j = 0, length - 1

    while self[i] > self[j]
      k = i + (j - i) / 2
      if self[k] > self[j]
        i = k + 1 # Push lower bound
      else
        j = k     # Push upper bound
      end
    end

    return self[i]
  end

  def bubble_sort
    (length-1).times do |_|
      (length-1).times do |i|
        n, m = self[i], self[i+1]
        self[i], self[i+1] = m, n if n > m
      end
    end
    return self
  end

  def merge_with other
    res = []
    until self.empty? or other.empty?
      a = self.shift
      b = other.shift
      if a == b
        res << a
      elsif a < b
        res << a
        other.unshift b
      else # a > b
        res << b
        self.unshift a
      end
    end
    res += self + other
  end

  def merge_sort
    len = length
    if len < 2
      return self
    elsif len == 2
      return self[0] < self[1] ? self : reverse
    else
      half  = len / 2
      left  = slice 0, half
      right = slice half, len
      return left.merge_sort.merge_with right.merge_sort
    end
  end
end


class Tree
  attr_reader :value, :children

  def initialize value, children=[]
    @value    = value
    @children = children
  end

  def dfs term
    return self if term == value
    children.each do |c|
      res = c.dfs term
      return res unless res.nil?
    end
    return nil
  end

  def bfs term
    q = [self]
    until q.empty?
      t = q.shift
      return t if term == t.value
      q += t.children
    end
  end
end


class BinaryTree < Tree
  attr_reader :value, :left, :right

  def initialize value, left=nil, right=nil
    @value = value
    @left  = left
    @right = right
  end

  def children
    return []      if left.nil? and right.nil?
    return [left]  if right.nil?
    return [right] if left.nil?
    return [left, right]
  end

  def is_search_tree?
    left_okay, right_okay = true, true
    left_okay  = left.value < value and left.is_search_tree? unless left.nil?
    right_okay = right.value > value and right.is_search_tree? unless right.nil?
    return left_okay && right_okay
  end

  def search term
    raise ArgumentError unless is_search_tree?
    return self if term == value
    return left.search(term) if term < value
    return right.search(term)
  end
end


################################################################################
################################################################################
################################################################################

puts "fizz_buzz =>"
fizz_buzz(10)

puts "fib => %d" % fib(5)
puts "boring_fib => %d" % boring_fib(5)

puts "factorize => %s" % factorize(10).inspect
puts "factorize => %s" % factorize(20).inspect
puts "factorize => %s" % factorize(2 * 2 * 3 * 5 * 7).inspect
puts "factorize => %s" % factorize(1234567).inspect
puts "boring_factorize => %s" % boring_factorize(10).inspect
puts "boring_factorize => %s" % boring_factorize(20).inspect
puts "boring_factorize => %s" % boring_factorize(2 * 2 * 3 * 5 * 7).inspect
puts "boring_factorize => %s" % boring_factorize(1234567).inspect

puts "rot_min => %d" % [3, 4, 5, 1, 2].rot_min
puts "rot_min => %d" % [1, 2, 3, 4, 5].rot_min
puts "rot_min => %d" % [1, 2, 3, 4].rot_min
puts "rot_min => %d" % [2, 3, 4, 1].rot_min
puts "rot_min => %d" % [3, 4, 1, 2].rot_min
puts "rot_min => %d" % [4, 1, 2, 3].rot_min
puts "rot_min => %d" % [1, 2, 3].rot_min
puts "rot_min => %d" % [2, 3, 1].rot_min
puts "rot_min => %d" % [3, 1, 2].rot_min

ll = BinaryTree.new(-3)
lr = BinaryTree.new(-1)
l  = BinaryTree.new(-2, ll, lr)
rl = BinaryTree.new 1
rr = BinaryTree.new 3
r  = BinaryTree.new 2, rl, rr
t  = BinaryTree.new 0, l, r
puts "is_serach_tree? => %s" % l.is_search_tree?.inspect
puts "is_serach_tree? => %s" % r.is_search_tree?.inspect
puts "is_serach_tree? => %s" % t.is_search_tree?.inspect
puts "dfs    => %s" % t.dfs(-1)
puts "bfs    => %s" % t.bfs(-1)
puts "search => %s" % t.search(-1)

puts "bubble_sort => %s" % [1,2,3,4].bubble_sort.inspect
puts "bubble_sort => %s" % [4,3,2,1].bubble_sort.inspect

puts "merge_with => %s" % [1,2,3,4].merge_with([-1,2,5,10]).inspect
puts "merge_sort => %s" % [5,4,3,2,1].merge_sort.inspect

# Output:
#
#   fizz_buzz =>
#     Fizz
#     Buzz
#     Fizz
#     Fizz
#     Buzz
#   fib => 5
#   boring_fib => 5
#   factorize => [2, 5]
#   factorize => [2, 2, 5]
#   factorize => [2, 2, 3, 5, 7]
#   factorize => [127, 9721]
#   boring_factorize => [2, 5]
#   boring_factorize => [2, 2, 5]
#   boring_factorize => [2, 2, 3, 5, 7]
#   boring_factorize => [127, 9721]
#   rot_min => 1
#   rot_min => 1
#   rot_min => 1
#   rot_min => 1
#   rot_min => 1
#   rot_min => 1
#   rot_min => 1
#   rot_min => 1
#   rot_min => 1
#   is_serach_tree? => true
#   is_serach_tree? => true
#   is_serach_tree? => true
#   dfs    => #<BinaryTree:0x007f8a5311e4e8>
#   bfs    => #<BinaryTree:0x007f8a5311e4e8>
#   search => #<BinaryTree:0x007f8a5311e4e8>
#   bubble_sort => [1, 2, 3, 4]
#   bubble_sort => [1, 2, 3, 4]
#   merge_with => [-1, 1, 2, 3, 4, 5, 10]
#   merge_sort => [1, 2, 3, 4, 5]
#