From: "Sarcar, Shourya C (GE Healthcare)" <shourya.sarcar@...>
Date: 2008-10-21T23:09:32+09:00
Subject: Re: [QUIZ] Long Division (#180)

 

-----Original Message-----
From: Matthew Moss [mailto:matt@moss.name] 

## 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



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

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

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

	def length
		return @x.length
	end

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

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

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

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

	def concat(p)
		return self if p == nil
		s = 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 = Slot.new(ARGV.shift.to_i)
a = Slot.new(ARGV.shift.to_i)

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

# That magic loop of long division
# This is where the calculation is performed
while (q.length > 0) do
	d = rem
	while (d.int < a.int && (q.length > 0)) do 
		d.concat(q.lshift)
		anss << d.div(a).int if (d.int < a.int)
		init_gaps += 1 if (first_line)
	end
	first_line = false
	ans = d.div(a)
	step = Slot.new(a.int * ans.int)
	rem = d.mod(a)
	#puts "Divide " + d.to_s + " by " + a.to_s +  " ==> " + 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 = spc(al + 1) # left margin
while (anss[0] == 0) do anss.shift end # spit leading zeroes if any
ansline = lm + spc(init_gaps) + anss.to_s 
ansline += "  R " + rem.to_s if (rem.int != 0)
puts ansline
puts spc(al) +  "+" + "-" * b.length
mainline = a.to_s + "|" + b.to_s
puts mainline
pre_line = lm
d = ds.shift
steps.each do |s|
	puts pre_line + spc(d.length - s.length)+ s.to_s
	puts pre_line + "-" * d.length
	pre_line += spc(d.length - Slot.new(d.int - s.int).length)
	d = ds.shift
	if (d!=nil) 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 == b.int) then
	puts "Checked answer ! Correct"
else
	puts "Problem in calculation :-(. Answer is not correct"
end



=========================
Shourya Sarcar
http://blog.shouryalive.com