anagram.rb

def anagram?(s1, s2)
  hash = Hash.new(0)
  s1.each_char do |c|
    hash[c] += 1
  end
  s2.each_char do |c|
    hash[c] -= 1
  end
  hash.values.uniq == [0]
end

puts anagram?("hello", "llohe")
puts anagram?("foo", "bar")

balance.rb

#!/usr/bin/env ruby

$:.unshift(".")
require "node"

class Node
  def min_depth
    1 + [ left ? left.min_depth : 0, right ? left.min_depth : 0].min
  end

  def max_depth
    1 + [left ? left.max_depth : 0, right ? right.max_depth : 0].max
  end

  def balance?
    (max_depth - min_depth) <= 1
  end
end

data = [1,
        [2, [4], [5]],
        [3, [6], [7]]]

tree = Node.from_array(data)

puts tree.inspect

def min(tree)
  return 0 unless tree
  1 + [min(tree.left), min(tree.right)].min
end

def max(tree)
  return 0 unless tree
  1 + [max(tree.left), max(tree.right)].max
end

puts tree.min_depth
puts min(tree)
puts tree.max_depth
puts max(tree)
puts tree.balance?

binary-tree-from-sorted.rb

class NilClass
  def value
    " "
  end

  def left
  end

  def right
  end
end

class Node
  attr_accessor :value, :left, :right

  def min_depth
    1 + [ left ? left.min_depth : 0, right ? right.min_depth : 0 ].min
  end

  def max_depth
    1 + [ left ? left.max_depth : 0, right ? right.max_depth : 0 ].max
  end

  def balance?
    max_depth - min_depth <= 1
  end

  def inspect
    current = [self]
    nextlevel = []
    maxd  = max_depth
    depth = 0

    while !current.reject(&:!).empty?
      gap = 2 ** (maxd - depth) - 1
      prepend = gap / 2
      puts " " * prepend + current.map(&:value).join(" " * gap)
      for v in current
        nextlevel.push(v.left   ? v.left  : nil)
        nextlevel.push(v.right  ? v.right : nil)
      end
      current = nextlevel
      nextlevel = []
      depth += 1
    end
  end
end

def binarytree(array)
  return nil if array.length == 0
  m = array.length / 2
  tree = Node.new
  tree.value = array[m]
  tree.left  = binarytree(array[0...m])
  tree.right = binarytree(array[m+1...array.length])
  tree
end

array = [1,2,3,4,5,6,7,8,9]
puts binarytree(array).balance?
puts binarytree(array).inspect

binarysearch-rotated-sorted-array.rb

def search(array)
  l, h = 0, array.length - 1
  while l < h-1
    m = (l + h) / 2
    if array[l] > array[m]
      h = m
    else
      l = m
    end
  end
  [array[l], array[h]]
end

puts search([4,5,6,7,8,1,2,3]).inspect

binarysearch-sparse-array.rb

def search(array, string)
  l, h = 0, array.length - 1
  while l <= h
    m = (l + h) / 2

    while array[m] == ""
      m += 1
    end

    if array[m] > string
      h = m
    elsif array[m] < string
      l = m
    else
      return m
    end
  end
end
  
puts search(["at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""], "ball")

binarysearch.rb

#!/usr/bin/env ruby

def search(array, x, l = 0, h = array.length - 1)
  while l <= h
    m = (l + h) / 2
    if x == array[m]
      return m
    elsif x < array[m]
      h = m - 1
    else
      l = m + 1
    end
  end
end

a = ["hello", "world", "shelling", "ford", "here"].sort
puts a.inspect
for str in a
  puts search(a, str)
end

combination-sum.rb

def dfs(current, tokens, target, result)
  sum = current.reduce(0, :+)
  if sum == target
    result.push(current)
  elsif sum < target
    rest = tokens.dup
    token, count = rest.shift, 0
    while token && (sum + token * count) <= target
      dfs(current + Array.new(count, token), rest, target, result)
      count += 1
    end
  end
end

def combination_sum(candidates, target)
  result = []
  dfs([], candidates, target, result)
  result
end

puts combination_sum([2,3,6,7], 7).inspect

count.rb

#!/usr/bin/env ruby
# 
# map a-z to 1-26
# given a string containing only digits
# count all combinatorics to present digits in a-z

def count(string)
  return 1 if string.length < 2
  if string[0] == "1"
    if string[1] == "0"
      count(string[2..-1])
    elsif ["1","2"].include?(string[1])
      2 * count(string[2..-1]) + count(string[1..-1])
    else
      2 * count(string[2..-1])
    end
  elsif string[0] == "2"
    if string[1] == "0"
      count(string[2..-1])
    elsif ["1","2"].include?(string[1])
      2 * count(string[2..-1]) + count(string[1..-1])
    elsif ["3","4","5","6"].include?(string[1])
      2 * count(string[2..-1])
    else
      count(string[2..-1])
    end
  else
    count(string[1..-1])
  end
end

puts count("1313")
puts count("101")
puts count("313")
puts count("20")
puts count("2627")

# 1313
# 13-13
# 1-3-13
# 13-1-3
# 1-3-1-3

countdup.rb

def countdup(string)
  array = Array.new(26)
  count = 0
  string.downcase.each_byte.map(&:ord).map { |c| c - 97 }.each do |i|
    count += 1 if array[i]
    array[i] = true
  end
  count
end

def countdup(string)
  count = 0
  string.downcase.each_char.with_index do |c, index|
    for i in 0...index
      if string[i] == c
        count += 1
        break
      end
    end
  end
  count
end

puts countdup("shelling")
puts countdup("ababab")
puts countdup("aaabbb")

generate-parenthesis.rb

def dfs(ans, current, l, r)
  ans.push(current) if l == 0 && r == 0
  dfs(ans, current + "(", l - 1, r) if l > 0
  dfs(ans, current + ")", l, r - 1) if r > l
end

result = []
dfs(result, "", 3, 3)
puts result.inspect

graph.rb

#!/usr/bin/env ruby

$:.unshift(".")
require "node"

class Graph
  attr_accessor :list, :marked

  def initialize(edges)
    @list = {}
    for v, w in edges
      list[v] ||= []
      list[w] ||= []
      list[v].push(w)
      list[w].push(v)
    end
  end

  def dfs(from, &block)
    marked  = {}
    stack   = []

    stack.push(from)

    while !stack.empty?
      v = stack.pop
      if !marked[v]
        block.call(v) if block
        marked[v] = true
        for adj in list[v].reverse
          stack.push(adj)
        end
      end
    end
  end

  def dfsr(from, visited = {}, &block)
    visited[from] = true
    block.call(from) if block
    for adj in list[from]
      if !visited[adj]
        visited[adj] = true
        dfsr(adj, visited, &block)
      end
    end
  end

  def bfs(from, &block)
    marked = {}
    queue  = []

    queue.push(from)

    while !queue.empty?
      v = queue.shift
      if !marked[v]
        block.call(v) if block
        marked[v] = true
        for adj in list[v]
          queue.push(adj)
        end
      end
    end
  end

  def bfsr(from, visited = {}, &block)
    queue = []

    for node in from
      visited[node] = true
      block.call(node) if block

      for adj in list[node]
        if !visited[adj]
          queue.push(adj)
        end
      end
    end

    bfsr(queue, visited, &block) unless queue.empty?
  end

end

data = [1,
        [2, [4], [5]],
        [3, [6], [7, [8], [9]]]]

g = Graph.new(Node.from_array(data).edges)
puts g.list

g.dfs(1) do |v|
  print "#{v} "
end
puts

g.dfsr(1) do |v|
  print "#{v} "
end
puts

g.bfs(1) do |v|
  print "#{v} "
end
puts

g.bfsr([1]) do |v|
  print "#{v} "
end
puts

heap.rb

#!/usr/bin/env ruby

class MaxHeap

  attr_accessor :heap

  def initialize(heap = [nil])
    @heap = heap
  end

  def size
    heap.length - 1
  end

  def insert(n)
    heap.push(n)
    swim(size)
  end
  
  def swim(k)
    while k > 1 && heap[k/2] < heap[k]
      heap[k/2], heap[k] = heap[k], heap[k/2]
      k = k/2
    end
  end

  def sink(k)
    while (j = 2*k) <= size
      j += 1 if j < size && heap[j] < heap[j+1]
      break unless heap[k] < heap[j]
      heap[k], heap[j] = heap[j], heap[k]
      k = j
    end
  end

  def pop
    max = heap[1]
    heap[1] = heap[size]
    heap.pop
    sink(1)
    return max
  end

  def to_s
    heap.to_s
  end
end

heap = MaxHeap.new

for i in 1..7
  heap.insert(i)
  puts heap
end

while heap.size > 0
  puts heap.pop
end

lca.rb

#!/usr/bin/env ruby

$:.unshift(".")
require "node"

data = [1,
        [2, [4], [5]],
        [3, [6], [7]]]

tree = Node.from_array(data)

puts tree.inspect

def lca(t, p, q)
  return nil unless t
  return t.data if t.data == p || t.data == q
  left = lca(t.left, p, q)
  right = lca(t.right, p, q)
  return t.data if left && right
  return left ? left : right
end

puts lca(tree, 4, 5)
puts lca(tree, 6, 7)
puts lca(tree, 4, 6)
puts lca(tree, 2, 3)
puts lca(tree, 2, 7)

levellist.rb

#!/usr/bin/env ruby

class Graph
  attr_accessor :list

  def initialize(edges)
    @list = {}
    for v, w in edges
      list[v] ||= []
      list[w] ||= []
      list[v].push(w)
      list[w].push(v)
    end
  end
end

def levellist(graph, uplevel)
  results = []

  marked  = {}
  queue   = []

  for node in uplevel
    marked[node] = true
  end

  while !uplevel.empty?
    results.push(uplevel)

    for node in uplevel
      for adj in graph[node]
        if !marked[adj]
          marked[adj] = true
          queue.push(adj)
        end
      end
    end

    uplevel = queue
    queue = []
  end

  results
end

edges = [
  [1,2],
  [1,3],
  [2,4],
  [2,5],
  [3,6],
  [3,7],
  [7,8],
  [7,9]
]

g = Graph.new(edges)
puts g.list.inspect

puts levellist(g.list, [1]).inspect

mark.rb

#!/usr/bin/env ruby

def mark(matrix, m, n)
  x, y = [], []

  for i in 0...m
    for j in 0...n
      if matrix[i][j] == 0
        x[i] = 0
        y[j] = 0
      end
    end
  end

  for i in 0...m
    for j in 0...n
      matrix[i][j] = 0 if x[i] == 0 || y[j] == 0
    end
  end
end

data = [
  (0..9).to_a,
  (10..19).to_a,
  (20..29).to_a,
  (30..39).to_a,
  (40..49).to_a,
  (50..59).to_a,
  (60..69).to_a,
  (70..79).to_a,
  (80..89).to_a,
  (90..99).to_a
]

data[5][5] = 0

mark(data, 10, 10)

for row in data
  puts row.inspect
end

merge-k-linked-list.rb

class ListNode
  attr_accessor :val, :next
  def initialize(val)
      @val, @next = val, nil
  end

  def inspect
    "#{@val} -> #{self.next.inspect}"
  end
end

class Array
  def to_list
    current = head = ListNode.new(self[0])
    self[1..-1].each do |e|
      current.next = ListNode.new(e)
      current = current.next
    end
    head
  end
end

def smallest(array)
  result, i = array[0], 0
  array.each.with_index do |list, index|
    result, i = list, index if list && result.val > list.val
  end
  [result, i]
end

def merge_k_linked_list(array)
  result, index = smallest(array)
  array[index] = result.next
  current = result
  while true
    list, index = smallest(array)
    break unless list
    array[index] = list.next
    current.next = list
    current = current.next
  end
  result
end

array = [
  (7.upto(9)).to_a.to_list,
  (4.upto(6)).to_a.to_list,
  (1.upto(3)).to_a.to_list,
]

puts merge_k_linked_list(array).inspect

merge-sort.rb

#!/usr/bin/env ruby


def merge(array, l, h)
  i = l
  mid = (l+h)/2
  j = 1 + mid

  aux = []
  for k in l..h
    aux[k] = array[k]
  end
  
  for k in l..h
    if i > mid
      array[k] = aux[j]; j+=1
    elsif j > h
      array[k] = aux[i]; i+=1
    elsif aux[j] < aux[i]
      array[k] = aux[j]; j+=1
    else
      array[k] = aux[i]; i+=1
    end
  end

  array
end

def sort(array, l = 0, h = array.length - 1)
  return if h <= l
  mid = (l + h) / 2
  sort(array, l, mid)
  sort(array, mid+1, h)
  merge(array, l, h)
end

puts merge([1,3,5,7,9,0,2,4,6,8], 0, 9).inspect
puts sort([9,8,7,6,5,4,3,2,1,0]).inspect

merge-sorted-array.rb

b = (0..5).to_a
a = (6..15).to_a + Array.new(b.length)

def merge(a, b)
  i = a.length - 1
  j = b.length - 1

  while a[i] == nil
    i -= 1
  end

  (a.length - 1).downto(0) do |p|
    if i < 0
      a[p] = b[j]; j -= 1; p -= 1;
    elsif j < 0
      a[p] = a[i]; i -= 1; p -= 1;
    elsif b[j] > a[i]
      a[p] = b[j]; j -= 1; p -= 1;
    else
      a[p] = a[i]; i -= 1; p -= 1;
    end
  end

  a
end

puts merge(a, b).inspect

multiply-string.rb

#!/usr/bin/env ruby

class String

def *(str)
  maxshift = self.length + str.length - 2

  results = Array.new(maxshift+1, 0)

  self.split(//).map(&:to_i).each_with_index do |i, at1|
    str.split(//).map(&:to_i).each_with_index do |j, at2|
      results[maxshift - at1 - at2] += i * j
    end
  end

  results.each_with_index do |i, shift|
    if i > 9
      results[shift+1] = results[shift+1].to_i + (i / 10)
      results[shift] = i % 10
    end
  end

  results.reverse.join
end

end

for i in 1..1000000
  a = (i.to_s * i.to_s).to_i
  b = i * i
  unless a == b
    puts a
    puts b
  end
end

node.rb

class Node
  attr_accessor :data, :left, :right

  def initialize(data, left = nil, right = nil)
    @data = data
    @left = left
    @right = right
  end

  def self.from_array(array)
    array ? self.new(array.shift, from_array(array.shift), from_array(array.shift)) : nil
  end

  def edges
    result = []
    if left
      result.push([data, left.data])
      result += left.edges
    end
    if right
      result.push([data, right.data])
      result += right.edges
    end
    result
  end

  def inspect
    "[#{data}, #{left.inspect}, #{right.inspect}]"
  end
end

palindrome.rb

def palindrome(string)
  hash = Hash.new(0)
  string.each_char do |c|
    hash[c] += 1
  end
  odd = hash.select { |k,v| v.odd? }
  return nil if odd.length > 1
  if k = odd.keys.first
    v = hash.delete(k)
    result = Array.new(v, k)
  else
    result = []
  end
  hash.each do |k,v|
    (v/2).times { result.push(k); result.unshift(k) }
  end
  result.join
end

puts palindrome("aaaab")
puts palindrome("aabcbcbbdcdcd")

parenthesis.rb

LEFT = ["(", "{", "[", "<"]

RIGHT = {
  ")" => "(",
  "}" => "{",
  "]" => "[",
  ">" => "<",
}

def balance?(string)
  stack = []

  string.split(//).each do |c|
    puts stack.inspect
    if LEFT.include?(c)
      stack.push(c)
    elsif RIGHT[c]
      if stack.last == RIGHT[c]
        stack.pop
      else
        return false
      end
    end
  end

  stack.empty? ? true : false
end

puts balance?("((<{}>)())")
puts balance?("()({(}))")

path-sum.rb

class TreeNode
  attr_accessor :val, :left, :right
  def initialize(val)
     @val = val
     @left, @right = nil, nil
  end
end

tree = TreeNode.new(1)
tree.right = TreeNode.new(2)
tree.right.right = TreeNode.new(3)
tree.right.right.right = TreeNode.new(4)
tree.right.right.right.right = TreeNode.new(5)

def path_sum(root, sum)
  return 0 unless root
  result = 0
  result += paths(root, sum)
  result += path_sum(root.left,  sum)
  result += path_sum(root.right, sum)
  result
end

def paths(tree, target)
  return 0 unless tree
  tmp = 0
  tmp += 1 if tree.val == target
  tmp += paths(tree.left,  target - tree.val)
  tmp += paths(tree.right, target - tree.val)
  tmp
end

puts path_sum(tree, 3)

path.rb

#!/usr/bin/env ruby

$:.unshift(".")
require "node"

data = [1,
        [2, [4], [5]],
        [3, [6], [7]]]

tree = Node.from_array(data)

puts tree.inspect

def path(tree, node)
  return nil unless tree
  return [node] if tree.data == node
  return (subpath = path(tree.left, node) || path(tree.right, node)) ? subpath.unshift(tree.data) : nil
end

puts path(tree, 6)

permutation.rb

def combination(element, target)
  (0..target.length).select { |index| target[index] != element }.map { |index| target[0...index] + [element] + target[index...target.length] }
end

def permutation(array)
  return [array] if array.length == 1
  head = array.shift
  permutation(array).map { |v| combination(head, v) }.reduce(:+)
end

puts permutation("aaa".split(//)).inspect

print-bugfix.rb

def list(n)
  hash = Hash.new("")
  1.upto(n/3) do |i|
    hash[i*3] += "bug"
  end
  1.upto(n/5) do |i|
    hash[i*5] += "fix"
  end
  hash.sort_by { |k,v| k }
end

list(30).each do |i, word|
  puts "#{i}\t#{word}"
end

def list(n)
  a, b = 3, 5
  i, j = 0, 0
  result = []
  while i + a <= n || j + b <= n
    if i + a == j + b
      i += a
      j += b
      result.push([i, "bugfix"])
    elsif i + a < j + b
      i += a
      result.push([i, "bug"])
    else
      j += b
      result.push([j, "fix"])
    end
  end
  result
end

list(30).each do |i, word|
  puts "#{i}\t#{word}"
end

quick-sort.rb

#!/usr/bin/env ruby

def sort(array, l = 0, h = array.length - 1)
  return if h <= l
  m = partition(array, l, h)
  sort(array, l, m-1)
  sort(array, m+1, h)
end

def partition(array, l, h)
  i = l
  j = h+1
  m = array[l]
  while true
    while array[i+=1] < m; break if i == h; end
    while array[j-=1] > m; break if j == l; end
    break if i>=j
    array[i], array[j] = array[j], array[i]
  end
  array[l], array[j] = array[j], array[l]
  j
end

a = [3,4,5,2,1]
sort(a)
puts a.inspect

b = [9,8,7,6,5,4,3,2,1]
sort(b)
puts b.inspect

remove-duplication.rb

def removedup(string)
  result = ""
  for i in 0...string.length
    exist = false
    for j in 0...i
      exist = true if result[j] == string[i]
    end
    result += string[i] unless exist
  end
  result
end

puts removedup("shelling")
puts removedup("aaabbb")
puts removedup("ababab")

def removedup(string)
  return if string.length < 2
  length = string.length

  tail = 1
  while true
    break if tail >= length
    for i in 0...tail
      if string[i] == string[tail]
        string[tail] = ""
        length -= 1
        break
      end
      tail += 1 if i == tail - 1
    end
  end

  string
end

puts removedup("shelling")
puts removedup("aaaaaa")
puts removedup("aaabbb")
puts removedup("ababab")

reverse-k-group-linked-list.rb

class ListNode
  attr_accessor :val, :next
  def initialize(val)
      @val, @next = val, nil
  end

  def inspect
    "#{@val} -> #{self.next.inspect}"
  end
end

class Array
  def to_list
    current = head = ListNode.new(self[0])
    self[1..-1].each do |e|
      current.next = ListNode.new(e)
      current = current.next
    end
    head
  end
end

puts [1,2,3,4,5,6,7].to_list.inspect

def reverse(head, c)
  return head unless head
  tail = head
  c.times { |i|
    if tail.next || i == c - 1
      tail = tail.next
    else
      return head
    end
  }
  pre = reverse(tail, c)
  current = head
  c.times {
    tmp = current.next
    current.next = pre
    pre = current
    current = tmp
  }
  pre
end

puts reverse((1..7).to_a.to_list, 2).inspect
puts reverse((1..3).to_a.to_list, 3).inspect
puts reverse((1..4).to_a.to_list, 3).inspect

reverse-linked-list.rb

class ListNode
  attr_accessor :val, :next
  def initialize(val)
      @val, @next = val, nil
  end

  def inspect
    "#{@val} -> #{self.next.inspect}"
  end
end

class Array
  def to_list
    current = head = ListNode.new(self[0])
    self[1..-1].each do |e|
      current.next = ListNode.new(e)
      current = current.next
    end
    head
  end
end

l = [2,3,4,5].to_list

def reverse(head, c)
  pre = head
  c.times { pre = pre.next }
  current = head
  c.times do
    tmp = current.next
    current.next = pre
    pre = current
    current = tmp
  end
  pre
end

puts reverse(l,4).inspect

def reverse_between(head, m, n)
  if m == 1
    return reverse(head, n - m + 1)
  else
    p = head
    (m-2).times { p = p.next }
    p.next = reverse(p.next, n-m+1)
    return head
  end
end

puts reverse_between([1,2,3,4,5].to_list, 2, 4).inspect

revserse-int.rb

#!/usr/bin/env ruby

def reverse(int)
  flag = int < 0
  int = int.abs

  result = 0

  while int > 0
    result = result * 10 + int % 10
    int /= 10
  end

  (flag ? -1 : 1) * result
end

puts reverse(321)
puts reverse(-100)

rotate.rb

#!/usr/bin/env ruby

def rotate(matrix, m)
  maxlevel = m / 2
  for layer in 0..(maxlevel-1)
    for i in layer..m-2-layer
      # top, left, bottom, right = left, bottom, right, top
      matrix[layer][i], matrix[m-i-1][layer], matrix[m-layer-1][m-i-1], matrix[i][m-layer-1] =
      matrix[m-i-1][layer], matrix[m-layer-1][m-i-1], matrix[i][m-layer-1], matrix[layer][i]
    end
  end
end

data = [
  [1,2,3,4],
  [5,6,7,8],
  [9,10,11,12],
  [13,14,15,16]
]

rotate(data, 4)

for row in data
  puts row.inspect
end

def rotate(matrix)
  result = []
  for j in 0...matrix.first.length
    row = []
    for i in 0...matrix.length
      row.unshift(matrix[i][j])
    end
    result.push(row)
  end
  result
end

data = [
  [1,2,3,4],
  [5,6,7,8],
  [9,10,11,12],
  [13,14,15,16]
]

for row in rotate(data)
  puts row.inspect
end

rotated-binary-search.rb

#!/usr/bin/env ruby

def search(array, x, l = 0, h = array.length - 1)
  while l <= h
    m = (l + h) / 2
    if x == array[m]
      return m
    elsif array[l] <= array[m] # sorted left
      if x < array[m] and x >= array[l]
        h = m - 1
      else
        l = m + 1
      end
    else # sorted right
      if x > array[m] and x <= array[h]
        l = m + 1
      else
        h = m - 1
      end
    end
  end
end

data = [15,16,19,20,25,1,3,4,5,7,10,14]

for i in data
  puts search(data, i)
end

data = [10,14,15,16,19,20,25,1,3,4,5,7]

for i in data
  puts search(data, i)
end

sorted-intersect.rb

#!/usr/bin/env ruby

def intersect(first, second)
  intersect = []
  while !first.empty? && !second.empty?
    if first[0] == second[0]
      intersect.push first.shift
      second.shift
    elsif first[0] > second[0]
      second.shift
    else
      first.shift
    end
  end
  intersect
end

puts intersect [  2,3,    6,7,  9,10],
               [1,2,3,4,5,6,7,8]

def bsearch(array, n)
  i = 0
  j = array.length - 1
  while i <= j
    mid = (i + j) / 2
    if n == array[mid]
      return n
    elsif n > array[mid]
      i = mid + 1
    else
      j = mid - 1
    end
  end
end

for n in [  2,3,    6,7,  9,10]
  if found = bsearch([1,2,3,4,5,6,7,8], n)
    puts found
  end
end

spiral-sequence.rb

def spiral(matrix)
  result = []

  left    = 0
  right   = matrix.first.length - 1
  top     = 0
  bottom  = matrix.length - 1

  while true
    left.upto(right) {|j| result.push(matrix[top][j]) }
    top += 1
    break if top > bottom || left > right

    top.upto(bottom) {|i| result.push(matrix[i][right]) }
    right -= 1
    break if top > bottom || left > right

    right.downto(left) {|j| result.push(matrix[bottom][j]) }
    bottom -= 1
    break if top > bottom || left > right

    bottom.downto(up) {|i| result.push(matrix[i][left]) }
    left += 1
    break if top > bottom || left > right
  end

  result
end

puts spiral([[1,2],[3,4]]).inspect

spiral.rb

n = 9
matrix = Array.new()
n.times { matrix.push(Array.new(n)) }

matrix.each { |row| puts row.inspect }; puts

Direction = {
  right:  :down,
  down:   :left,
  left:   :up,
  up:     :right,
}

def right(matrix, i, j)
  return [i, j] if matrix[i] && matrix[i][j+2] == "*"
  return [i, j] if j >= matrix.first.length-1
  matrix[i][j] = "*"
  return [i, j+1]
end

def down(matrix, i, j)
  return [i, j] if matrix[i+2] && matrix[i+2][j] == "*"
  return [i, j] if i >= matrix.length-1
  matrix[i][j] = "*"
  return [i+1, j]
end

def left(matrix, i, j)
  return [i, j] if j <= 0
  return [i, j] if matrix[i] && matrix[i][j-2] == "*" && j != 1
  matrix[i][j] = "*"
  return [i, j-1]
end

def up(matrix, i, j)
  return [i, j] if matrix[i-2] && matrix[i-2][j] == "*"
  return [i, j] if i <= 0
  matrix[i][j] = "*"
  return [i-1, j]
end

def move(direction, matrix, i, j)
  send(direction, matrix, i, j)
end

i, j = 0, 0
direction = :right

while true
  x, y = i, j
  i, j = move(direction, matrix, i, j)
  direction = Direction[direction.to_sym] if i == x && j == y
  if  direction == :right   &&
      matrix[i][j+2] == "*" &&
      matrix[i-2][j] == "*" &&
      matrix[i+2][j] == "*"
    matrix[i][j] = "*"
    break
  end
end

matrix.each { |row| puts row.inspect }

stack-sort.rb

class Stack < Array
  def sort
    result = []

    while !self.empty?
      if result.last && result.last > self.last
        tmp = self.pop
        while result.last && result.last > tmp
          self.push(result.pop)
        end
        result.push(tmp)
      else
        result.push(self.pop)
      end
    end

    result
  end
end

stack = Stack.new([9,8,7,6,5,4,3,2,1])
puts stack.sort.inspect

stack-with-min.rb

class StackWithMin < Array
  def initialize
    @mins = []
    super
  end

  def push(e)
    @mins.push(min ? [min, e].min : e)
    super(e)
  end

  def pop
    @mins.pop
    super
  end

  def min
    @mins.last
  end
end

s = StackWithMin.new
s.push(3); puts s.min
s.push(2); puts s.min
s.push(1); puts s.min
s.pop;     puts s.min
s.pop;     puts s.min
s.pop;     puts s.min

stackqueue.rb

class StackQueue
  attr_accessor :s1, :s2

  def initialize
    @s1 = []
    @s2 = []
  end

  def add(obj)
    @s1.push(obj)
    self
  end

  def pop
    if @s2.empty?
      while obj = @s1.pop
        @s2.push(obj)
      end
    end
    @s2.pop
  end

  def to_s
    s2.reverse.to_s + s1.to_s
  end
end

sq = StackQueue.new

sq.add(1).add(2).add(3)

puts sq
puts sq.pop
puts sq

subsets.rb

def subsets(set)
  return [set] if set.length == 1

  head = [set.shift]
  tail = subsets(set)

  return tail.map { |s| head + s } + [head] + tail
end

puts subsets([1,2,3]).inspect

def subsets(set)
  max = 2 ** set.length
  (1..max-1).map { |i| i.to_s(2).rjust(set.length, "0").split(//) }
            .map { |flags|
              flags.zip(set).select { |p| p[0] == "1" }.map { |p| p[1] }
            }
end

puts subsets([1,2,3]).inspect

def dfs(current, tokens, result)
  if tokens.empty?
    result.push(current.map { |k,v| Array.new(v, k) }.reduce(:+))
  else
    rest = tokens.dup
    char, count = rest.shift
    (0..count).each do |c|
      dfs(current.merge(char => c), rest, result)
    end
  end
end

def subsets(nums)
  hash = Hash.new(0)
  nums.each do |n|
    hash[n] += 1
  end

  result = []
  dfs({}, hash, result)
  result
end

puts subsets([1,2,2]).inspect

swap-vowel.rb

def vowel?(c)
  ["a", "e", "i", "o", "u"].include?(c)
end

def swap(string)
  i, j = 0, string.length - 1
  while true
    while !vowel?(string[i]); i+=1; end
    while !vowel?(string[j]); j-=1; end
    break if i >= j
    string[i], string[j] = string[j], string[i]
    i+=1
    j-=1
  end
  string
end

puts swap("apple")
puts swap("friend")

tracetree.rb

#!/usr/bin/env ruby

$:.unshift(".")
require "node"

data = [1,
        [2, [3], [5]],
        [4]]

tree = Node.from_array(data)

def tracetree(t)
  left, right = [], []
  while true
    left.push(t.data)
    right.push(t.right.data) if t.right
    break unless t = t.left
  end
  # left = [1,2,3]
  # right = [4,5]
  puts left.reverse
  puts right.reverse
end

tracetree(tree)

tree-level.rb

#!/usr/bin/env ruby

$:.unshift(".")
require "node"

data = [1,
        [2, [4], [5]],
        [3, [6], [7]]]

tree = Node.from_array(data)

def dfs_level(tree, level = 0, result = [])
  result[level] ||= []
  dfs_level(tree.left, level+1, result) if tree.left
  result[level].push(tree.data)
  dfs_level(tree.right, level+1, result) if tree.right
  result
end

puts dfs_level(tree).inspect

def bfs_level(current)
  return if current.empty?
  queue = []
  for node in current
    print node.data
    queue.push(node.left) if node.left
    queue.push(node.right) if node.right
  end
  puts
  bfs_level(queue)
end

bfs_level([tree])

uniqchar.rb

def uniqchar?(string)
  index = Array.new(26)
  string.split(//).map(&:downcase).map(&:ord).map { |c| c - 97 }.each do |i|
    return false if index[i]
    index[i] = true
  end
  return true
end

puts uniqchar?("shelling").inspect

def uniqchar?(string)
  for i in 0...string.length
    for j in i+1...string.length
      return false if string[i].downcase == string[j].downcase
    end
  end
  return true
end

puts uniqchar?("shelling").inspect

zeroend.rb

#!/usr/bin/env ruby

def zeroend(array)
  i = -1
  j = array.length
  while true
    while i += 1; break if array[i] == 0; end
    while j -= 1; break if array[j] != 0; end
    break if i >= j
    array[i], array[j] = array[j], array[i]
  end
  array[0..j]
end

puts zeroend([1,0,2,0,3,0,4,0,5,0,6,0]).inspect
puts zeroend([1,2,3,4,0,0,0,0,5,6,7,8,0,0,9]).inspect

zigzag.rb

def next_position(i, j, row)
  if (j % (row - 1) == 0) && (i < (row - 1))
    return [i+1, j]
  else
    return [i-1, j+1]
  end
end

def convert(string, row)
  matrix = []
  row.times { matrix.push([]) }

  i, j = 0, 0
  string.each_char do |c|
    matrix[i][j] = c
    i, j = next_position(i, j, row)
  end

  return matrix
end

result = convert("paypalishiring", 3)

for row in result
  for c in row
    if c
      print c + " "
    else
      print "  "
    end
  end
  puts
end