Module: Kata::Algorithms

Defined in:
lib/kata/algorithms.rb,
lib/kata/algorithms/version.rb

Constant Summary collapse

VERSION = 
"0.2.0"

Class Method Summary collapse

Class Method Details

.addition(a, b) ⇒ String

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.

Parameters:

  • a (String) —

    An integer represented as string, e.g. “123412”

  • b (String) —

    An integer represented as string, e.g. “3742834”

Returns:

  • (String) —

    The string representation of a + b, e.g. “3866246”



48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
# File 'lib/kata/algorithms.rb', line 48

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) ⇒ Object

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



193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
 
# File 'lib/kata/algorithms.rb', line 193

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) ⇒ Object

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.



147
148
149
150
151
152
153
154
155
 
# File 'lib/kata/algorithms.rb', line 147

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) ⇒ Object

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.



170
171
172
173
174
175
176
177
178
 
# File 'lib/kata/algorithms.rb', line 170

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) ⇒ String

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.

Parameters:

  • a (String) —

    An integer represented as string, e.g. “123412”

  • b (String) —

    An integer represented as string, e.g. “3742834”

Returns:

  • (String) —

    The string representation of a + b, e.g. “461910629608”



122
123
124
125
126
127
128
129
130
131
132
 
# File 'lib/kata/algorithms.rb', line 122

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