module Kata::Algorithms

Constants

VERSION

Public Class Methods

addition(a, b) click to toggle source

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
gcd_modulo(a, b) click to toggle source

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
gcd_recursive_modulo(a, b) click to toggle source

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
gcd_recursive_subtraction(a, b) click to toggle source

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(a, b) click to toggle source

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