module Kata::Algorithms
Constants
- VERSION
Public Class Methods
ADDITION OF INTEGERS WHEN REPRESENTED AS STRINGS
¶ ↑
E.g. “345” + “7890” = “8235”
Inspired by the book “Algorithms In a Nutshell - Chapter 2 - The Mathematics of Algorithms”
Assume that we have two integers represented as strings, For example:
a = "2382738"
(a.k.a. `a = “8”, a = “3”, … , a = “2”`)
and
b = "9891829"
(a.k.a. `b = “9”, b = “2”, …, b = “9”`)
Can we calculate their sum, without converting them to integers?
c = c[n+1]...c[1] = "12274567"
(a.k.a. `c = “7”, c = “6”, …, c = “2”, c = “1”`)
Or in other words, how one would do this addition on a piece of paper?
The primitive operations used in this ADDITION algorithm are as follows:
c[i] = (a[i] + b[i] + carry[i]) mod 10 carry[i+1] = (a[i] + b[i] + carry[i]) >= 10 ? 1 : 0
The above algorithm is implemented in this addition. However, there is an optimization, because “mod 10” is an expensive operation. So, we do not use it.
Also, we have implemented that so that it can work with operands of different length. So, “a” and 'b“ do not have to be of same length.
@param a [String] An integer represented as string, e.g. “123412” @param b [String] An integer represented as string, e.g. “3742834” @return [String] The string representation of a + b, e.g. “3866246”
# File lib/kata/algorithms.rb, line 49 def self.addition(a, b) a = a.split('').reverse b = b.split('').reverse carry = 0 i = 0 c = "" # while I have a digit I process it while !a[i].nil? || !b[i].nil? result_on_i = a[i].to_i + b[i].to_i + carry # .to_i on nil works perfect. returns 0 if result_on_i >= 10 c = "#{result_on_i - 10}#{c}" carry = 1 else c = "#{result_on_i}#{c}" carry = 0 end i += 1 end c = "1#{c}" if carry == 1 c == "" ? "0" : c end
GREATEST COMMON DIVISOR (implementation with modulo)
—————————-¶ ↑
We are using the Euclidean algorithm to calculate the GCD or Greatest Common Divisor. This is also called GCF (Greatest Common Factor) or HCF (Highest Common Factor).
The algorithm goes as follows:
a |- b => quotient and remainder if remainder == 0 then b is the GCD else a = b, b = r and repeat
# File lib/kata/algorithms.rb, line 194 def self.gcd_modulo(a, b) return b if a == 0 return a if b == 0 if b > a temp = b b = a a = temp end # now a >= b r = a % b while r > 0 a = b b = r r = a % b end b end
GREATEST COMMON DIVISOR (recursive implementation with modulo)
————————————–¶ ↑
We are using the Euclidean algorithm to calculate the GCD or Greatest Common Divisor. This is also called GCF (Greatest Common Factor) or HCF (Highest Common Factor).
The algorithm goes as follows:
gcd(a, 0) is a gcd(a, b) is equal to gcd(b, a mod b) - consider a >= b
We are going to use a recursive call to implement it.
# File lib/kata/algorithms.rb, line 148 def self.gcd_recursive_modulo(a, b) return b if a == 0 return a if b == 0 if a >= b gcd_recursive_modulo(b, a % b) else gcd_recursive_modulo(a, b % a) end end
GREATEST COMMON DIVISOR (recursive implementation with subtraction)
——————————————-¶ ↑
We are using the Euclidean algorithm to calculate the GCD or Greatest Common Divisor. This is also called GCF (Greatest Common Factor) or HCF (Highest Common Factor).
The algorithm goes as follows:
gcd(a, 0) is a gcd(a, b) is equal to gcd(a - b, b) - consider a >= b
We are going to use a recursive call to implement it.
# File lib/kata/algorithms.rb, line 171 def self.gcd_recursive_subtraction(a, b) return b if a == 0 return a if b == 0 if a >= b gcd_recursive_subtraction(a - b, b) else gcd_recursive_subtraction(b - a, a) end end
MULTIPLICATION OF INTEGERS WHEN REPRESENTED AS STRINGS
¶ ↑
E.g. “345” * “7890” = “2722050”
Inspired by the book “Algorithms In a Nutshell - Chapter 2 - The Mathematics of Algorithms”
Assume that we have two integers represented as strings, For example:
a = "2382738"
(a.k.a. `a = “8”, a = “3”, … , a = “2”`)
and
b = "9891829"
(a.k.a. `b = “9”, b = “2”, …, b = “9”`)
Can we calculate their multiplication, without converting them to integers?
c = c[k]...c[1] = "23569636847802"
(a.k.a. `c = “2”, c = “0”, …, c = “2”`)
This MULTIPLICAITON algorithm works, more or less, as follows:
assume A X B
n scans B from right to left m scans A from right to left, for each on of the digits of B result holds the intermediate and final results
initialize result to “0”
for each digit on B starting from least significant to most significant - scan with n
for each digit on A starting from least significant to most significant - scan with m result is increased by B[n] * A[m] * 10^(n+m)
at the end of the iterations, result will hold the correct answer
Note that we have not used the native addition operation. We have used the Algorithms.addition
to increase the results.
@param a [String] An integer represented as string, e.g. “123412” @param b [String] An integer represented as string, e.g. “3742834” @return [String] The string representation of a + b, e.g. “461910629608”
# File lib/kata/algorithms.rb, line 123 def self.multiplication(a, b) a = a.split('') b = b.split('') result = "0" (0..b.size-1).step do |n| (0..a.size-1).step do |m| result = Kata::Algorithms.addition(result, (b[b.size - 1 - n].to_i * a[a.size - 1 -m].to_i * 10 ** (n + m)).to_s) end end result end