change.rb

change.rb

#!/usr/bin/env rspec

# Given an amount (a positive int) and a currency (a hash of {coin (a string)
# => value (an int)}), return how many of each coin is needed to make the
# amount as a hash {coin (a string) => count (an int)}. This method is useful
# for more than money, but money is a nicely concrete example of its utility.
#
# make_change assigns counts based on the iteration order of the currency you
# pass in. If you want optimal change, the currency you pass in must be sorted
# in descending order of value.
#
# Examples:
#   make_change(19, {'dime'=>10, 'nickel'=>5, 'penny'=>1})
#     => {"dime"=>1, "nickel"=>1, "penny"=>4}
#   make_change(19, {'X' => 10, 'V' => 5, 'I' => 1})
#     => {"X"=>1, "V"=>1, "I"=>4}
#   make_change(19, {'X' => 10, 'V' => 5, 'IV' => 4, 'I' => 1})
#     => {"X"=>1, "V"=>1, "IV"=>1}
#   make_change(19, {'I' => 1, 'V' => 5, 'X' => 10})
#     => {"I"=>19}
#
# Formally, make_change takes an integer number and a language of symbols
# mapped to integer values and returns the representation of the number in the
# language. We expect that:
#
#     make_change(x, y).map { |sym, count| y[sym] * count }.reduce(:+) == x
#
# for any integer x and any hash {string -> int} y, provided y contains at
# least one symbol which is a factor of x.
#
def make_change(amount, currency)
	if amount == 0
		# We can't divide by zero, so handle it specially.
		return {currency.key(0) => 1}
	end
	# Return a Hash constructed by looping over the currency
	Hash[currency.map do |coin, value|
		# We can't divide by zero. If there is a coin with the value 0 and the
		# amount is 0, then we would have returned above.
		if value != 0
			# divmod returns the result of division and the remainder.
			#   if we have: x, y = 10.divmod(3)
			#   then x = 3, y = 1
			count, amount = amount.divmod(value)
			if count != 0
				# The Hash constructor will convert this to coin => count
				[coin, count]
			else
				nil
			end
		end
	# .compact removes nil values.
	end.compact]
end
#
## make_change spec ##
#
if methods.include? :describe  # This block only runs if we're in Rspec
	describe 'make_change' do
		it 'should be correct' do
			(1..100_000).each do |i|
				expect(make_change(i, ROMAN_OLD).map do |sym, count|
					ROMAN_OLD[sym] * count
				end.reduce(:+)).to eq(i)
			end
		end
		it 'should not return symbols with count zero' do
			(1..100_000).each do |i|
				change = make_change(i, ROMAN_OLD)
				change.each do |coin, count|
					expect(count).to be > 0
				end
			end
		end
	end
end

# Takes change ({coin=>count}) and a currency ({coin=>value}), and returns the
# amount represented by the change. We expect that:
#
#    unmake_change(make_change(x, currency), curency) == x
#
# For any valid x and currency. For more details, see the docs for
# make_change.
#
def unmake_change(change, currency)
	change.map{ |coin, count| currency[coin] * count }.reduce(:+)
end
#
## unmake_change spec ##
#
if methods.include? :describe
	describe 'unmake_change' do
		it 'should reverse make_change' do
			(1..100_000).each do |i|
				expect(unmake_change(make_change(i, ROMAN), ROMAN)).to eq(i)
			end
		end
	end
end

# Given an amount and a currency, return a tally mark string, in which the
# symbol for each coin is repeated a number of times equal to its count (as
# determined by make_change).
#
# Examples:
#   tally(11, {'X' => 5, 'I' => 1})
#     => "XXI"
#   tally(11, {'I' => 1})
#     => "IIIIIIIIIII"
def tally(amount, currency)
	make_change(amount, currency).map{ |coin, count| coin * count }.join
end

# Takes a tally mark string (such as returned by tally) and a currency,
# and returns the value.
#
# Examples:
#  untally('XXI', {'X' => 5, 'I' => 1})
#    => 11
#  untally("IIIIIIIII", {'I' => 1})
#    => 9
#  untally(tally(134, c), c)
#    => 134
def untally(tally_str, currency)
	currency.sort_by { |coin, value| -coin.length }.map { |coin, value|
		count = tally_str.scan(coin).count
		tally_str = tally_str.gsub(coin, '')
		count * value		
	}.reduce(:+)
end

# Returns string representing int in US English.
def to_words_en(int)
	make_change(int, NUMBERS_EN_US).map do |coin, count|
		if NUMBERS_EN_US[coin] > 99
			[to_words_en(count), coin]
		else
			coin
		end
		# Otherwise, nil.
	end.flatten.compact.join(' ')
end
#
# to_words_en spec
#
if methods.include? :describe
	describe 'to_words_en' do
		it 'should work for edge cases' do
			expect(to_words_en(0)).to eq('zero')
			expect(to_words_en(1)).to eq('one')
			expect(to_words_en(100)).to eq('one hundred')
			expect(to_words_en(99)).to eq('ninety nine')
			expect(to_words_en(101)).to eq('one hundred one')
			expect(to_words_en(990)).to eq('nine hundred ninety')
			expect(to_words_en(999)).to eq('nine hundred ninety nine')
			expect(to_words_en(1000)).to eq('one thousand')
			expect(to_words_en(10_000)).to eq('ten thousand')
			expect(to_words_en(99_000)).to eq('ninety nine thousand')
		end
		it 'should work for various cases' do
			expect(to_words_en(12_934)).to eq('twelve thousand nine hundred thirty four')
			expect(to_words_en(122_823_332_349_938_220)).to eq('one hundred twenty two quadrillion eight hundred twenty three trillion three hundred thirty two billion three hundred forty nine million nine hundred thirty eight thousand two hundred twenty')
		end
	end
end

# Returns a string representing int in modern roman numerals.
def to_roman(int)
	tally(int, ROMAN)
end
#
# to_roman spec
#
if methods.include? :describe
	describe 'to_roman' do
		it 'should be correct' do
			(1..100_000).each do |i|
				expect(untally(to_roman(i), ROMAN)).to eq(i)
			end
		end
	end
end

# Returns a string representing int in old-style roman numerals.
def to_roman_old(int)
	tally(int, ROMAN_OLD)
end
#
# to_roman_old spec
#
if methods.include? :describe
	describe 'to_roman_old' do
		it 'should be correct' do
			(1..100_000).each do |i|
				expect(untally(to_roman_old(i), ROMAN_OLD)).to eq(i)
			end
		end
	end
end

#### Currencies ####

# Roman numerals (modern)
ROMAN = {
	'M' => 1000,
	'CM' => 900,
	'DCCC' => 800,
	'D' => 500,
	'CD' => 400,		
	'C' => 100,
	'XC' => 90,
	'L' => 50,
	'XL' => 40,	
	'X' => 10,
	'IX' => 9,
	'V' => 5,
	'IV' => 4,
	'I' => 1
}

# Roman numerals (old style, no IV, IX, etc...)
ROMAN_OLD = {
	'M' => 1000,
	'D' => 500,
	'C' => 100,
	'L' => 50,
	'X' => 10,
	'V' => 5,
	'I' => 1
}

# Currency (English, US)
CURRENCY_EN_US = {
	'dollars' => 100,
	'quarters' => 25,
	'dimes' => 10,
	'nickels' => 5,
	'pennies' => 1
}

# Numbers (English, US)
NUMBERS_EN_US = {
	'duodecillion' => 1e39.to_i,
	'tredecillion' => 1e42.to_i,
	'quattuordecillion' => 1e45.to_i,
	'quindecillion' => 1e48.to_i,
	'sexdecillion' => 1e51.to_i,
	'septendecillion' => 1e54.to_i,
	'octodecillion' => 1e57.to_i,
	'novemdecillion' => 1e60.to_i,
	'vigintillion' => 1e63.to_i,
	'centillion' => 1e303.to_i,
	'undecillion' => 1e36.to_i,
	'decillion' => 1e33.to_i,
	'nonillion' => 1e30.to_i,
	'octillion' => 1e27.to_i,
	'septillion' => 1e24.to_i,
	'sextillion' => 1e21.to_i,
	'quintillion' => 1e18.to_i,
	'quadrillion' => 1e15.to_i,
	'trillion' => 1e12.to_i,
	'billion' => 1e9.to_i,
	'million' => 1e6.to_i,
	'thousand' => 1e3.to_i,
	'hundred' => 100,
	'ninety' => 90,
	'eighty' => 80,
	'seventy' => 70,
	'sixty' => 60,
	'fifty' => 50,
	'forty' => 40,
	'thirty' => 30,
	'twenty' => 20,
	'nineteen' => 19,
	'eighteen' => 18,
	'seventeen' => 17,
	'sixteen' => 16,
	'fifteen' => 15,
	'fourteen' => 14,
	'thirteen' => 13,
	'twelve' => 12,
	'eleven' => 11,
	'ten' => 10,
	'nine' => 9,
	'eight' => 8,
	'seven' => 7,
	'six' => 6,
	'five' => 5,
	'four' => 4,
	'three' => 3,
	'two' => 2,
	'one' => 1,
	'zero' => 0	
}