Exercises from Chapter 10
Rite of Passage: Sorting
How you could do it:
def sort arr |
rec_sort arr, [] |
end |
|
def rec_sort unsorted, sorted |
if unsorted.length <= 0 |
return sorted |
end |
|
# So if we got here, then it means we still |
# have work to do. |
smallest = unsorted.pop |
still_unsorted = [] |
|
unsorted.each do |tested_object| |
if tested_object < smallest |
still_unsorted.push smallest |
smallest = tested_object |
else |
still_unsorted.push tested_object |
end |
end |
|
# Now "smallest" really does point to the |
# smallest element that "unsorted" contained, |
# and all the rest of it is in "still_unsorted". |
|
sorted.push smallest |
|
rec_sort still_unsorted, sorted |
end |
|
puts(sort(['can','feel','singing','like','a','can'])) |
a |
can |
can |
feel |
like |
singing |
How I would do it (well, aside from just using the built-in sort method):
# The well-known quicksort algorithm. |
def sort arr |
return arr if arr.length <= 1 |
|
middle = arr.pop |
less = arr.select{|x| x < middle} |
more = arr.select{|x| x >= middle} |
|
sort(less) + [middle] + sort(more) |
end |
|
puts(sort(['can','feel','singing','like','a','can']).join(' ')) |
a can can feel like singing |
Shuffle
How you could do it:
def shuffle arr |
shuf = [] |
while arr.length > 0 |
# Randomly pick one element of the array. |
rand_index = rand(arr.length) |
|
# Now go through each item in the array, |
# putting them all into new_arr except for the |
# randomly chosen one, which goes into shuf. |
curr_index = 0 |
new_arr = [] |
|
arr.each do |item| |
if curr_index == rand_index |
shuf.push item |
else |
new_arr.push item |
end |
|
curr_index = curr_index + 1 |
end |
|
|
# Replace the original array with the new, |
# smaller array. |
arr = new_arr |
end |
|
shuf |
end |
|
puts(shuffle([1,2,3,4,5,6,7,8,9])) |
6 |
1 |
7 |
5 |
9 |
4 |
3 |
8 |
2 |
How I would do it:
def shuffle arr |
arr.sort_by{rand} |
end |
|
p(shuffle([1,2,3,4,5,6,7,8,9])) |
[1, 8, 7, 9, 5, 4, 3, 2, 6] |
Dictionary Sort
How you could do it:
def dictionary_sort arr |
rec_dict_sort arr, [] |
end |
def rec_dict_sort unsorted, sorted |
if unsorted.length <= 0 |
return sorted |
end |
# So if we got here, then it means we still |
# have work to do. |
smallest = unsorted.pop |
still_unsorted = [] |
|
unsorted.each do |tested_object| |
if tested_object.downcase < smallest.downcase |
still_unsorted.push smallest |
smallest = tested_object |
else |
still_unsorted.push tested_object |
end |
end |
|
# Now "smallest" really does point to the |
# smallest element that "unsorted" contained, |
# and all the rest of it is in "still_unsorted". |
sorted.push smallest |
|
rec_dict_sort still_unsorted, sorted |
end |
|
puts(dictionary_sort(['can','feel','singing.','like','A','can'])) |
A |
can |
can |
feel |
like |
singing. |
How I would do it:
# The well-known quicksort algorithm. |
def dictionary_sort arr |
return arr if arr.length <= 1 |
|
middle = arr.pop |
less = arr.select{|x| x.downcase < middle.downcase} |
more = arr.select{|x| x.downcase >= middle.downcase} |
|
dictionary_sort(less) + [middle] + dictionary_sort(more) |
end |
|
words = ['can','feel','singing.','like','A','can'] |
puts(dictionary_sort(words).join(' ')) |
A can can feel like singing. |
Expanded english_number
How you could do it:
def english_number number |
if number < 0 # No negative numbers. |
return 'Please enter a number that isn't negative.' |
end |
if number == 0 |
return 'zero' |
end |
|
# No more special cases! No more returns! |
num_string = '' # This is the string we will return. |
ones_place = ['one', 'two', 'three', |
'four', 'five', 'six', |
'seven', 'eight', 'nine'] |
tens_place = ['ten', 'twenty', 'thirty', |
'forty', 'fifty', 'sixty', |
'seventy', 'eighty', 'ninety'] |
teenagers = ['eleven', 'twelve', 'thirteen', |
'fourteen', 'fifteen', 'sixteen', |
'seventeen', 'eighteen', 'nineteen'] |
|
zillions = [['hundred', 2], |
['thousand', 3], |
['million', 6], |
['billion', 9], |
['trillion', 12], |
['quadrillion', 15], |
['quintillion', 18], |
['sextillion', 21], |
['septillion', 24], |
['octillion', 27], |
['nonillion', 30], |
['decillion', 33], |
['undecillion', 36], |
['duodecillion', 39], |
['tredecillion', 42], |
['quattuordecillion', 45], |
['quindecillion', 48], |
['sexdecillion', 51], |
['septendecillion', 54], |
['octodecillion', 57], |
['novemdecillion', 60], |
['vigintillion', 63], |
['googol', 100]] |
|
# "left" is how much of the number |
# we still have left to write out. |
# "write" is the part we are |
# writing out right now. |
# write and left...get it? :) |
left = number |
|
while zillions.length > 0 |
zil_pair = zillions.pop |
zil_name = zil_pair[0] |
zil_base = 10 ** zil_pair[1] |
write = left/zil_base # How many zillions left? |
left = left - write*zil_base # Subtract off those zillions. |
|
if write > 0 |
# Now here's the recursion: |
prefix = english_number write |
num_string = num_string + prefix + ' ' + zil_name |
|
if left > 0 |
# So we don't write 'two billionfifty-one'... |
num_string = num_string + ' ' |
end |
end |
end |
|
write = left/10 # How many tens left? |
left = left - write*10 # Subtract off those tens. |
|
if write > 0 |
if ((write == 1) and (left > 0)) |
# Since we can't write "tenty-two" instead of |
# "twelve", we have to make a special exception |
# for these. |
num_string = num_string + teenagers[left-1] |
# The "-1" is because teenagers[3] is |
# 'fourteen', not 'thirteen'. |
|
# Since we took care of the digit in the |
# ones place already, we have nothing left to write. |
left = 0 |
else |
num_string = num_string + tens_place[write-1] |
# The "-1" is because tens_place[3] is |
# 'forty', not 'thirty'. |
end |
|
if left > 0 |
# So we don't write 'sixtyfour'... |
num_string = num_string + '-' |
end |
end |
|
write = left # How many ones left to write out? |
left = 0 # Subtract off those ones. |
|
if write > 0 |
num_string = num_string + ones_place[write-1] |
# The "-1" is because ones_place[3] is |
# 'four', not 'three'. |
end |
|
# Now we just return "num_string"... |
num_string |
end |
|
puts english_number( 0) |
puts english_number( 9) |
puts english_number( 10) |
puts english_number( 11) |
puts english_number( 17) |
puts english_number( 32) |
puts english_number( 88) |
puts english_number( 99) |
puts english_number(100) |
puts english_number(101) |
puts english_number(234) |
puts english_number(3211) |
puts english_number(999999) |
puts english_number(1000000000000) |
puts english_number(109238745102938560129834709285360238475982374561034) |
zero |
nine |
ten |
eleven |
seventeen |
thirty-two |
eighty-eight |
ninety-nine |
one hundred |
one hundred one |
two hundred thirty-four |
three thousand two hundred eleven |
nine hundred ninety-nine thousand nine hundred ninety-nine |
one trillion |
one hundred nine quindecillion two hundred |
thirty-eight quattuordecillion seven hundred forty-five ... |
And that’s just about how I would do it, too.
Wedding Number
I told you I didn’t do this one. It was a joke! Move on!
“Ninety-nine Bottles of Beer on the Wall.”
How you could do it:
# english_number as above, plus this: |
num_at_start = 5 # change to 9999 if you want |
num_now = num_at_start |
while num_now > 2 |
puts english_number(num_now).capitalize + ' bottles of beer on the wall, ' + |
english_number(num_now) + ' bottles of beer!' |
num_now = num_now - 1 |
puts 'Take one down, pass it around, ' + |
english_number(num_now) + ' bottles of beer on the wall!' |
end |
|
puts "Two bottles of beer on the wall, two bottles of beer!" |
puts "Take one down, pass it around, one bottle of beer on the wall!" |
puts "One bottle of beer on the wall, one bottle of beer!" |
puts "Take one down, pass it around, no more bottles of beer on the wall!" |
Five bottles of beer on the wall, five bottles of beer! |
Take one down, pass it around, four bottles of beer on the wall! |
Four bottles of beer on the wall, four bottles of beer! |
Take one down, pass it around, three bottles of beer on the wall! |
Three bottles of beer on the wall, three bottles of beer! |
Take one down, pass it around, two bottles of beer on the wall! |
Two bottles of beer on the wall, two bottles of beer! |
Take one down, pass it around, one bottle of beer on the wall! |
One bottle of beer on the wall, one bottle of beer! |
Take one down, pass it around, no more bottles of beer on the wall! |
How I would do it:
# english_number as above, plus this: |
|
num_at_start = 5 # change to 9999 if you want |
|
num_bot = proc { |n| "#{english_number n} bottle#{n == 1 ? '' : 's'}" } |
|
num_at_start.downto(2) do |num| |
puts "#{num_bot[num]} of beer on the wall, #{num_bot[num]} of beer!".capitalize |
puts "Take one down, pass it around, #{num_bot[num-1]} of beer on the wall!" |
end |
puts "#{num_bot[1]} of beer on the wall, #{num_bot[1]} of beer!".capitalize |
puts "Take one down, pass it around, no more bottles of beer on the wall!" |
Five bottles of beer on the wall, five bottles of beer! |
Take one down, pass it around, four bottles of beer on the wall! |
Four bottles of beer on the wall, four bottles of beer! |
Take one down, pass it around, three bottles of beer on the wall! |
Three bottles of beer on the wall, three bottles of beer! |
Take one down, pass it around, two bottles of beer on the wall! |
Two bottles of beer on the wall, two bottles of beer! |
Take one down, pass it around, one bottle of beer on the wall! |
One bottle of beer on the wall, one bottle of beer! |
Take one down, pass it around, no more bottles of beer on the wall! |
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.