Re: [QUIZ] Long Division (#180)

=20

-----Original Message-----
From: Matthew Moss [mailto:[e-mail]]=20

## Long Division (#180)

Your task this week is to perform and display long division.
Here's a solution. I checked it with quite a few combinations, seems
like its robust.
A define and use an object called "Slot" which takes a number and puts
each digit
in a "slot".

Comments welcome.


Run this like

$ ruby longdiv.rb 5002101 201

      24886  R 15
   +-------
201|5002101
    402
    ---
     982
     804
     ---
     1781
     1608
     ----
      1730
      1608
      ----
       1221
       1206
       ----
         15

Checked answer ! Correct



=3D=3D=3D CODE follows =3D=3D=3D
# An abstraction where a number is modeled
# such that each digit sits in a "slot"
# Eg : 345 =3D=3D> |3|4|5| (internally stored in an array)
# Makes it easy to left shift
class Slot
	def initialize(num)
		@x =3D []
		if (num =3D=3D 0) then
			@x << 0
		else
			while (num > 0)
				@x <<  num % 10
				num =3D num / 10
			end
			@x.reverse!
		end
	end

	def zero?
		(@x =3D=3D "0" * @x.length)=20
	end

	def show
		@x.each {|f| print f}
		puts
	end

	def length
		return @x.length
	end

	def int
		return 0 if self.zero?
		y =3D @x.reverse
		val =3D 0
		(0 .. (y.length - 1)).each {|i| val +=3D y[i]*(10 ** i)}
		return val
	end

	# left shift
	def lshift(p=3D1)
		return if @x.empty?
		val =3D 0
		(p-1).downto(0) do |i|
			val +=3D @x.shift * (10 ** (i))
		end
		return Slot.new(val)
	end

	def div(a)
		return Slot.new(0) if self.zero?
		x =3D self.int
		y =3D a.int
		return Slot.new(x/y)
	end

	def mod(a)
		return Slot.new(0) if self.zero?
		x =3D self.int
		y =3D a.int
		return Slot.new(x % y)
	end

	def concat(p)
		return self if p =3D=3D nil
		s =3D p.clone
		s.length.times do |i|
			@x << s.lshift.int
		end
		return self
	end

	def clone
		return Slot.new(self.int)
	end

	def to_s
		@x.to_s
	end
end

def spc(x)
	" " * x.to_i
end

#
# MAIN
# Programmer: Shourya Sarcar
# ruby log_div.rb <dividend> <divisor>
#

# Get the dividend followed by the divisor
b =3D Slot.new(ARGV.shift.to_i)
a =3D Slot.new(ARGV.shift.to_i)

# Some initialisation
al =3D a.length
q =3D b.clone
steps, anss, rems, ds =3D [], [], [], [] # Arrays to store numbers at
various stages
init_gaps =3D 0
first_line =3D true
rem =3D q.lshift

# That magic loop of long division
# This is where the calculation is performed
while (q.length > 0) do
	d =3D rem
	while (d.int < a.int && (q.length > 0)) do=20
		d.concat(q.lshift)
		anss << d.div(a).int if (d.int < a.int)
		init_gaps +=3D 1 if (first_line)
	end
	first_line =3D false
	ans =3D d.div(a)
	step =3D Slot.new(a.int * ans.int)
	rem =3D d.mod(a)
	#puts "Divide " + d.to_s + " by " + a.to_s +  " =3D=3D> " + ans.to_s
+ " Step " + step.to_s + " , R " + rem.to_s
	ds << d
	steps << step
	anss << ans.int if (ans.int > 0)
end

# Print the hard-earned results
lm =3D spc(al + 1) # left margin
while (anss[0] =3D=3D 0) do anss.shift end # spit leading zeroes if any
ansline =3D lm + spc(init_gaps) + anss.to_s=20
ansline +=3D "  R " + rem.to_s if (rem.int !=3D 0)
puts ansline
puts spc(al) +  "+" + "-" * b.length
mainline =3D a.to_s + "|" + b.to_s
puts mainline
pre_line =3D lm
d =3D ds.shift
steps.each do |s|
	puts pre_line + spc(d.length - s.length)+ s.to_s
	puts pre_line + "-" * d.length
	pre_line +=3D spc(d.length - Slot.new(d.int - s.int).length)
	d =3D ds.shift
	if (d!=3Dnil) then
		puts pre_line + d.to_s
	else
		puts pre_line + rem.to_s
	end
end


# Check results
puts
if (a.int * anss.to_s.to_i + rem.int =3D=3D b.int) then
	puts "Checked answer ! Correct"
else
	puts "Problem in calculation :-(. Answer is not correct"
end



=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=

Shourya Sarcar
http://blog.shouryalive.com