Skip to content

Instantly share code, notes, and snippets.

@alebian

alebian/pascal_math.rb

Last active Sep 7, 2019
Embed
What would you like to do?
Pascal's triangle implementation
require_relative 'pascal_triangle'
class PascalMath
def initialize
@triangle = PascalTriangle.new
end
def binomial_power(a, b, n)
coefficients = @triangle.get_file(n)
result = 0
coefficients.each_with_index do |coefficient, idx|
result += coefficient * a**(n - idx) * b**idx
end
result
end
def power_of_2(n)
coefficients = @triangle.get_file(n)
coefficients.sum
end
def power_of_11(param)
coefficients = @triangle.get_file(param)
if param <= 4
coefficients.join.to_i
else
coefficients_with_carry = [0]
coefficients.reverse_each.with_index do |coefficient, idx|
coefficient_with_carry = coefficient + coefficients_with_carry[idx]
if coefficient_with_carry < 10
coefficients_with_carry[idx] = coefficient_with_carry
coefficients_with_carry[idx + 1] = 0
else
coefficients_with_carry[idx] = coefficient_with_carry % 10
coefficients_with_carry[idx + 1] = (coefficient_with_carry / 10.0).floor
end
end
coefficients_with_carry.reverse.join.to_i
end
end
def fibonacci(n)
return 0 if n <= 1
return 1 if n == 2
result = 0
(0..n).reverse_each.with_index do |n, idx|
coefficients = @triangle.get_file(n - 2)
next unless coefficients[idx]
result += coefficients[idx]
end
result
end
def natural_numbers
NHedralSeries.new(@triangle, 2)
end
def n_hedral_series(n)
raise 'N must be greater than 2' if n < 3
NHedralSeries.new(@triangle, n)
end
def binomial_coefficient(n, k)
file = @triangle.get_file(n)
file[k]
end
def perfect_squares
PerfectSquaresSeries.new(@triangle)
end
private
class NHedralSeries
def initialize(triangle, n)
@triangle = triangle
@current_file = n - 1
@n = n
end
def next
file = @triangle.get_file(@current_file)
@current_file += 1
file[@n - 1]
end
end
class PerfectSquaresSeries
def initialize(triangle)
@triangle = triangle
@current_file = 3
end
def next
previous_file = @triangle.get_file(@current_file - 1)
file = @triangle.get_file(@current_file)
@current_file += 1
file[2] + previous_file[2]
end
end
end
require_relative '../pascal_math'
describe PascalMath do
subject(:pascal) { described_class.new }
describe '#binomial_power' do
let(:as) { [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] }
let(:bs) { [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] }
let(:powers) { [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] }
it 'returns the expected result' do
as.each do |a|
bs.each do |b|
powers.each do |n|
expect(pascal.binomial_power(a, b, n)).to eq((a + b)**n)
end
end
end
end
end
describe '#power_of_2' do
let(:powers) { [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] }
it 'returns the expected file' do
powers.each do |n|
expect(pascal.power_of_2(n)).to eq(2**n)
end
end
end
describe '#power_of_11' do
let(:powers) { [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] }
it 'returns the expected file' do
powers.each do |n, expected|
expect(pascal.power_of_11(n)).to eq(11**n)
end
end
end
describe '#fibonacci' do
let(:fibonacci_series) do
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]
end
it 'returns the expected result' do
fibonacci_series.each_with_index do |expected, n|
expect(pascal.fibonacci(n + 1)).to eq(expected)
end
end
end
describe '#natural_numbers' do
let(:series) { pascal.natural_numbers }
it 'returns the expected results' do
(1..10).each do |n|
expect(series.next).to eq(n)
end
end
end
describe '#n_hedral_series' do
context 'when n is 4' do
let(:series) { pascal.n_hedral_series(4) }
it 'returns the expected results' do
(1..10).each do |n|
expect(series.next).to eq(((1 / 6.0) * n * (n + 1) * (n + 2)).ceil)
end
end
end
end
describe '#perfect_squares' do
let(:series) { pascal.perfect_squares }
it 'returns the expected results' do
(2..10).each do |n|
expect(series.next).to eq(n**2)
end
end
end
describe '#binomial_coefficient' do
let(:ns) { [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] }
let(:ks) { [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] }
it 'returns the expected result' do
ns.each do |n|
ks.each do |k|
next unless k <= n
# Math.gamma(n + 1) == factorial(n)
expect(pascal.binomial_coefficient(n, k))
.to eq((Math.gamma(n + 1) / (Math.gamma(k + 1) * Math.gamma(n - k + 1))).ceil)
end
end
end
end
end
class PascalTriangle
def initialize
@triangle = [[1]]
end
def get_file(param)
return @triangle[param] if @triangle[param]
previous_file = get_file(param - 1)
@triangle << calculate_new(previous_file)
@triangle[param]
end
private
def calculate_new(previous_file)
current_file = [1]
(0..(previous_file.size - 1)).each do |idx|
next if idx == previous_file.size - 1
current_file << previous_file[idx] + previous_file[idx + 1]
end
current_file << 1
current_file
end
end
require_relative '../pascal_triangle'
describe PascalTriangle do
describe '#get_file' do
subject(:triangle) { described_class.new }
let(:expected_files) do
[
[0, [1]],
[1, [1, 1]],
[2, [1, 2, 1]],
[3, [1, 3, 3, 1]],
[4, [1, 4, 6, 4, 1]],
[5, [1, 5, 10, 10, 5, 1]],
[6, [1, 6, 15, 20, 15, 6, 1]],
[7, [1, 7, 21, 35, 35, 21, 7, 1]]
]
end
it 'returns the expected file' do
expected_files.each do |n, expected_file|
expect(subject.get_file(n)).to eq(expected_file)
end
end
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.