k, a, b, a1, b1 = 2, 4, 1, 12, 4

while TRUE
  # Next approximation
  p, q, k = k*k, 2*k+1, k+1
  a, b, a1, b1 = a1, b1, p*a+q*a1, p*b+q*b1
  # Print common digits
  d = a / b
  d1 = a1 / b1
  while d == d1
    print d
    $stdout.flush
    a, a1 = 10*(a%b), 10*(a1%b1)
    d, d1 = a/b, a1/b1
  end
end

#
# From the paper "Un Unbounded Spigot Algorithm for the Digits of Pi"
# http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/spigot.pdf
#

def pi
  q, r, t, k = 1, 0, 1, 1
  loop do
    n = (3*q+r) / t
    if (4*q+r) / t == n then
      yield n
      q, r, t, k = 10*q, 10*(r-n*t), t, k
    else
      q, r, t, k = q*k, q*(4*k+2)+r*(2*k+1), t*(2*k+1), k+1
    end
  end
end

pi {|n| print n; $stdout.flush }

#
# $Id: binary_tree.rb,v 1.1 2001/10/07 11:58:07 michael Exp $
#
# BinaryTree by Michael Neumann 
#

class BinaryTree
  class Node
    attr_reader :value, :left, :right

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

    def insert( value )
      if value >= @value then
        # insert right
        if @right.nil?
          @right = Node.new( value )
        else
          @right.insert( value )
        end
      else
        # insert left
        if @left.nil?
          @left = Node.new( value )
        else
          @left.insert( value )
        end
      end
    end

    # depth first (from left to right)
    def traverse(&b)
      @left.traverse(&b) if @left
      b.call(self)
      @right.traverse(&b) if @right
    end
  end

  attr_reader :root

  def initialize
    @root = nil
  end

  def insert( value )
    if @root.nil?
      @root = Node.new( value )
    else
      @root.insert( value )
    end
  end

  def traverse(&b)
    return if @root.nil?
    @root.traverse(&b)
  end
end

def binary_sort( array )
  tree = BinaryTree.new

  # fill tree with array elements
  array.each do |e|
    tree.insert( e )
  end

  sorted_array = []
  tree.traverse do |node|
    sorted_array << node.value
  end

  return sorted_array
end

if __FILE__ == $0
  p binary_sort( [0,6,4,3,5,8,4,6] ) # => [0, 3, 4, 4, 5, 6, 6, 8]
end

def fac(n)
  if n < 2 then
    n
  else 
    n * fac(n-1)
  end
end


# Aufrufen
print fac(6)

def fac(n)n>1?n*fac(n-1):1 end

puts fac(6)

def fac(n, res=1)
  if n < 2 then
    res 
  else 
    fac(n-1, n*res)
  end
end


# Aufrufen
print fac(6)

#
# Größter Gemeinsamer Teiler
# 

def ggt(a, b)
   a,b = b,a if a < b
   a,b = b,a%b while a%b != 0
   return b
end

def hash1( txt, m = 101 )
   h = 0
   txt.each_byte { |i| h = ((h<<8) + i) % m}
   return h
end

#
# hashpjw, algorithm by P.J.Weinberg
#
# implemented by Michael Neumann
#

def hashpjw(txt, m=101)
   h = 0
   txt.each_byte {|i|
      h = (h << 4) + i
      g = h & 0xf0000000
      h ^= (g >> 24) ^ g if g
   }
   return h%m
end

#
# $Id: heapsort.rb,v 1.1 2001/10/06 18:48:30 michael Exp $
#
# in-place Heapsort by Michael Neumann 
#

class Array
  def heapsort!
    a = self
    n = a.size
    a.unshift nil    # add 0'th element  

    ##
    # (1) construct heap
    #
    2.upto(n) do | i |
      # insert element a[i] into heap a[1..i-1]
      cnode = i
      while cnode != 1 and a[cnode] > a[cnode/2] do
        a[cnode], a[cnode/2] = a[cnode/2], a[cnode]
        cnode /= 2
      end
    end

    ##
    # (2) remove elements from heap 
    #
    n.downto(2) do | i |
      a[1], a[i] = a[i], a[1]
      cnode = 1
      while cnode*2 < i do
        if cnode*2+1 >= i or a[cnode*2] > a[cnode*2+1]
          # no right node exist or left > right
          if a[cnode] < a[cnode*2]   # cnode < left
            a[cnode], a[cnode*2] = a[cnode*2], a[cnode]
            cnode *= 2
          else
            break
          end
        else
          # right > left
          if a[cnode] < a[cnode*2+1]   # cnode < right
            a[cnode], a[cnode*2+1] = a[cnode*2+1], a[cnode]
            cnode = cnode*2+1
          else
            break
          end
        end
      end # do
    end

    a.shift     # remove 0'th element
    return a
  end

  def heapsort
    self.dup.heapsort!
  end
end

if __FILE__ == $0
  a = [6, 3, 5, 3 ,8, 5, 3, 7, 4, 2, 3]
  p a.heapsort
end

# Hello World in Ruby

print "Hello World\n"

"Hello World\n".display

class Color
  attr_accessor :red, :green, :blue

  def initialize(red=0, green=0, blue=0)
    @red, @green, @blue = red, green, blue
  end
end

# no abstract classes in Ruby!
class Shape
  attr_accessor :x, :y, :color

  def initialize(x, y, color)
    @x, @y, @color = x, y, color
  end

  def draw
    raise "abstract method"
  end

  def getArea
    raise "abstract method"
  end

  def move(x, y)
    @x += x
    @y += y
  end
end

class Circle < Shape
  attr_accessor :radius

  def initialize(x, y, radius, color)
    super(x, y, color)
    @radius = radius
  end

  def draw
    # do something here
  end

  def getArea
    Integer(Math::PI * radius)
  end
end

class Rectangle < Shape
  attr_accessor :width, :height

  def initialize(x, y, width, height, color)
    super(x, y, color)
    @width, @height = width, height
  end

  def draw
    # do something here
  end

  def getArea
    @width * @height
  end
end

## Test the Classes ##

BLACK  = Color.new
WHITE  = Color.new(255, 255, 255)

circle = Circle.new(100, 100, 50, BLACK)
rect   = Rectangle.new(20, 20, 5, 5, WHITE)

circle.move(10, 10)

circle.x = 50
circle.radius = 5

p circle.getArea     # => 15
p rect.getArea       # => 25

p rect.width         # => 5
rect.width = 10
p rect.width         # => 10 

circle.draw
rect.draw

def quicksort( arr )
   return arr if arr.size <= 1
   m = arr[0]
   return quicksort( arr.select { |i| i < m } ) + 
          arr.select { |i| i == m } + 
          quicksort( arr.select { |i| i > m } )
end


# Aufruf
print quicksort( [5, 99, 2, 45, 12, 234, 29, 0] ).join( " " )

s, j, k = (0..255).to_a, 0, (ARGV[0]*256)[0,256].unpack('C*')
(0..255).each{|x| j = (j + s[x] + k[x]) % 256; s[x], s[j] = s[j], s[x] }
i = j = 0; $stdin.each_byte{|b| i = (i + 1) % 256; j = (j + s[i]) % 256
s[i], s[j] = s[j], s[i]; $stdout<<(b ^ s[(s[i] + s[j])%256]).chr }

# $Id: prime.rb,v 1.2 2001/10/16 11:00:12 michael Exp $

class Primes
  def initialize(n = 10_000)
    @n = n
    @primes = 0

    # Sieve of Eratosthenes
    k = 2
    while k < Math.sqrt(@n)
      if @primes[k] == 0
        j = 2*k
        while j <= @n
          @primes |= (1 << j)
          j += k
        end
      end
      k += 1
    end
  end

  def is_prime?( number )
    if number > @n
      raise "number to big"
    else
      @primes[number] == 0
    end
  end

  alias prime? is_prime?
end

if __FILE__ == $0
  x = Primes.new(10_000)
  p x.prime?(77)   # => false
  p x.prime?(13)   # => true
  p x.prime?(100)  # => false
end

for i in 1..10 do
   print i*i, " "
end

(1..10).each { |i| print i*i, " " }

1.upto(10) do |i| puts i**2 end

i = 1
until i > 10 do
  puts i**2
  i += 1
end