DS programs in ruby

Linked List

class Node
  attr_accessor :next
  attr_reader :value

  def initialize(value)
    @value = value
    @next = nil
  end

  def to_s
    "Node with value: #{@value}"
  end
end

class LinkedList
  attr_accessor :head

  def initialize
    @head = nil
  end

  def append(value)
    node = Node.new(value)
    if @head
      find_tail.next = node
    else
      @head = node
    end
  end

  def find_tail
    node = @head
    return node if !node.next
    while(node = node.next)
      return node if !node.next
    end
  end

  def append_after(target, value)
    node = find(target)
    return unless node
    old_next = node.next
    node.next = Node.new(value)
    node.next.next = old_next
  end

  def delete(value)
    if @head.value == value
      @head = @head.next
      return
    end
    node = find_before(value)
    node.next = node.next.next
  end

  def find(value)
    node = @head
    return false if !node.next
    return node if node.value == value
    while(node = node.next)
      return node if node.value == value
    end
  end

  def find_before(value)
    node = @head
    return false if !node.next
    return @head if @head.next.value == value
    while(node = node.next)
      return node if node.next && node.next.value == value
    end
  end

  def print
    node = @head
    to_be_printed = "#{node.value} "
    while(node = node.next)
      to_be_printed << "-> #{node.value}"
    end
    puts to_be_printed
  end
end

node = Node.new(1)
1.upto(99) do |i|
  eval("Node.last(node).next = Node.new(i + 1)")
end

puts Node.node_list node
puts Node.node_list Node.reverse(node)

Queue


class Queue
  def initialize(size)
    @size = size
    @store = Array.new(@size)
    @head, @tail = @store.length - 1, 0
  end

  def dequeue
    if empty?
      nil
    else
      @tail += 1
      dequeued = @store[@head]
      @store.unshift(nil)
      @store.pop
      dequeued
    end
  end

  def enqueue(element)
    if full? or element.nil?
      nil
    else
      @tail -= 1
      @store[@tail] = element
      self
    end
  end

  def size
    @size
  end

  def tail
    @store[@tail]
  end

  def head
    @store[@head]
  end

  private
  def empty?
    @head == -1 && @tail == 0
  end

  def full?
    @tail.abs == @size
  end
end

Stack


class Stack
  def initialize(size)
    @size = size
    @store = Array.new(@size)
    @top = -1
  end

  def pop
    if empty?
      raise 'StackUnderflow'
    else
      popped = @store[@top]
      @store[@top] = nil
      @top -= 1
      popped
    end
  end

  def push(element)
    if full? || element.nil?
      raise 'StackOverflow'
    else
      @top += 1
      @store[@top] = element
      self
    end
  end

  def size
    @size
  end

  def look
    @store[@top]
  end

  private
  def empty?
    @top == -1
  end

  def full?
    @top == @size - 1
  end
end

Searching


class Searching
  def initialize(array, element)
    @array = Sorting.new(array).bubble_sort
    @element = element
  end

  def binary_search(first = 0, last = @array.length - 1)
    # ---- Complexity ----- #
    # Worst Case Time Complexity [ Big-O ]: O(log n)
    # --------------------- #
    mid = (first + last) / 2
    if @element < @array[first] || @element > @array[last]
      'Element not found'
    else
      if @element < @array[mid]
        binary_search(first, @array[mid])
      elsif @element > @array[mid]
        binary_search(@array[mid], last)
      elsif @element == @array[mid]
        return mid
      end
    end
  end
end

Sorting


class Sorting
  def initialize(array)
    @original_array = array
    @array = array
  end

  def print
    puts '------ Unsorted Array ----'
    puts @original_array.to_s
    puts '------ Sorted Array ------'
    puts @array.to_s
    puts '--------------------------'
  end

  def bubble_sort
    # Start by comparing the first element with second, if its greater then swap both. And go on further.
    # ---- Complexity ----- #
    # (n-1) + (n-2) + (n-3) + ..... + 3 + 2 + 1
    # Sum = n(n-1)/2
    # i.e O(n2)
    # --------------------- #
    # Average Time Complexity [Big-theta]: O(n2)
    # Worst Case Time Complexity [ Big-O ]: O(n2)
    # Best Case Time Complexity [Big-omega]: O(n)
    # Space Complexity: O(1)
    (1..(@array.length - 2)).each do |num|
      swapped = false
      (0..(@array.length - num - 1)).each do |i|
        if @array[i] > @array[i + 1]
          swapped = true
          @array[i], @array[i + 1] = @array[i + 1], @array[i]
        end
      end
      break unless swapped
    end
    @array
  end
  def selection_sort
    # Find smallest element in array and swap with first element. And go on to sort further.
    # Worst Case Time Complexity [ Big-O ]: O(n2)
    # Best Case Time Complexity [Big-omega]: O(n2)
    # Average Time Complexity [Big-theta]: O(n2)
    # Space Complexity: O(1)
    (0..@array.length - 1).each do |num|
      smallest = num
      (num..@array.length - 1).each do |i|
        if @array[i] < @array[smallest]
          smallest = i
        end
      end
      @array[num], @array[smallest] = @array[smallest], @array[num]
    end
    @array
  end

  def insertion_sort
    # Worst Case Time Complexity [ Big-O ]: O(n2)
    # Best Case Time Complexity [Big-omega]: O(n)
    # Average Time Complexity [Big-theta]: O(n2)
    # Space Complexity: O(1)
    (1..@array.length - 1).each do |i|
      j = i
      while (j > 0) && (@array[j - 1] > @array[j])
        @array[j - 1], @array[j] = @array[j], @array[j - 1]
        j -= 1
      end
    end
    @array
  end

  def merge_sort(list = @array)
    # Divide and Conquer: Keep dividing array until solo elements are not present, then merge in sorted manner.
    # Worst Case Time Complexity [ Big-O ]: O(n*log n)
    # Best Case Time Complexity [Big-omega]: O(n*log n)
    # Average Time Complexity [Big-theta]: O(n*log n)
    # Space Complexity: O(n)
    return list if list.size <= 1
    mid = list.size / 2
    left = list.take(mid)
    right = list.drop(mid)
    merge(merge_sort(left), merge_sort(right))
  end

  private
  def merge(left, right)
    sorted = []
    until left.empty? || right.empty?
      if left.first <= right.first
        sorted << left.shift
      else
        sorted << right.shift
      end
    end
    @array = sorted.concat(left).concat(right)
  end
end

Triangle programs

class Figures
  attr_accessor :size

  def initialize(size)
    self.size = size
  end

  # ======================================== #
  def right_angle_triangle
    (1..self.size).each do |counter|
      counter.times.each do
        print "*"
      end
      puts
    end
  end

  # ======================================== #
  def equilateral_triangle
    (1..self.size).each do |counter|
      (self.size - counter).times do
        print " "
      end

      (2 * counter - 1).times.each do
        print "*"
      end

      puts
    end
  end

  # ======================================== #
  def facing_triangles
    (1..self.size).each do |counter|
      (counter).times do |count|
        print count + 1
      end
      (2 * (self.size - counter)).times do
        print " "
      end
      (counter).times do |count|
        print count + 1
      end
      puts
    end
  end

  # ======================================== #
  def mirror_image
    (1..self.size).each do |counter|
      counter.times do |count|
        print count + 1
      end
      (2 * (self.size - counter)).times do
        print " "
      end
      (counter).times do |count|
        print counter - count
      end
      puts
    end
  end
end
comments powered by Disqus