Algorithm Practice with Ruby
Aug 13, 2015
The Magic of Ruby Hash - Wood Chuck Puzzle
Find the most common word in the sentence.
"First off hi back at ya, in My neck of the woods (Northern Michigan) the NA tribes used wood wood wood both snapping turtle neck skin and wood chuck hide. The woodchuck hide was and is looks pretty cool. Here's a pic of a Potawatomi bow with the original is string....it's from the Peabody Museum. Sorta looks like one big string silencer to me, the eh? we we we we we"
There are bunch of ways to solve this problem. First in my mind was set variable frequency and then loop through whole array bunch of times to change the frequency value as it find the same word. This works but expensive program. The cost of this operation is n power over n. Instead we can use powerful ruby Hash class.
We all know that Hash (or Map in Python) is the answer for most of algorithm solution. It's because of their handy methods and easy lookup. By definition, A Hash is a collection of key-value pairs. It is similar to an Array, except that indexing is done via arbitrary keys of any object type, not an integer index. Hashes enumerate their values in the order that the corresponding keys were inserted.
def frequent_word(sentence)
sentence_array = sentence.split(" ")
word_hash = Hash.new(0) //there is a reason we put '0' as an arg
sentence_array.each do |word|
word_hash[word]+=1
end
max_value = word_hash.values.max
word_hash.select {|key, value| p key if value == max }
end
Let's break down. There are several key Hash functions in this problem. Hash.new(0), hash[key] += 1, max and select.
hash = Hash.new(0) =>This means that new hash will have default value of '0' if there is no value given to the key. For instance,
h['a'] = 17
h['c'] #this will return 0
So initiate the hash with default value of '0' make it no ncessary to set another variable like counter.
hash[word] += 1
Under the hood, this function will set up the key as a 'word' and then create the new key-value pair.
While it is in the each loop, if it finds the same key, instead of create new key-value pair, it will increate the value.
{"First"=>1, "off"=>1, "hi"=>1, "back"=>1, "at"=>1, "ya,"=>1, "in"=>1, "My"=>1, "neck"=>1,
"of"=>1, "the"=>2, "woods"=>1, "(Northern"=>1, "Michigan)"=>1}
{"First"=>1, "off"=>1, "hi"=>1, "back"=>1, "at"=>1, "ya,"=>1, "in"=>1, "My"=>1, "neck"=>1,
"of"=>1, "the"=>2, "woods"=>1, "(Northern"=>1, "Michigan)"=>1, "NA"=>1}
{"First"=>1, "off"=>1, "hi"=>1, "back"=>1, "at"=>1, "ya,"=>1, "in"=>1, "My"=>1, "neck"=>1,
"of"=>1, "the"=>2, "woods"=>1, "(Northern"=>1, "Michigan)"=>1, "NA"=>1, "tribes"=>1}
{"First"=>1, "off"=>1, "hi"=>1, "back"=>1, "at"=>1, "ya,"=>1, "in"=>1, "My"=>1, "neck"=>1, "of"=>1, "the"=>2, "woods"=>1, "(Northern"=>1, "Michigan)"=>1, "NA"=>1, "tribes"=>1,
"used"=>1}
{"First"=>1, "off"=>1, "hi"=>1, "back"=>1, "at"=>1, "ya,"=>1, "in"=>1, "My"=>1, "neck"=>1,
"of"=>1, "the"=>2, "woods"=>1, "(Northern"=>1, "Michigan)"=>1, "NA"=>1, "tribes"=>1,
"used"=>1, "wood"=>1}
.max
.max will return the max of the value. If max function isn't available, another loop function to find out the max value.
.select
I was initially throught that:
return hash.key(max)
will return the key if value == max. and it did. Only problem is that it will NOT return all the keys which as max value but the first instance and stop running.
So it was necessary to select all keys from the hash and then return it.
'.select' function will return any key or value (or both) if it meets the condition.
.key(value)
It is also notable that .key method will not return anything unless argument(value) is passed.
Common Array Question - Find, Arrange, Rearrange Array Element
Given an array of positive integers, write a function which returns all the unique pairs which add (equal) up to 100.
ample_data = [0, 1, 100, 99, 0, 10, 90, 30, 55, 33, 55, 75, 50, 51, 49, 50, 51, 49, 51]
sample_output = [[1,99], [0,100], [10,90], [51,49], [50,50]]
This problem can be solved by many different ways. The brute force way is n(O2) notation, using two loops.
def make_100(arr)
result_arr = []
for i in 0..arr.length-1
for j in 0..arr.length-1
if i != j and arr[i] + arr[j] == 100
result_arr.push(arr[i], arr[j]].sort)
end
end
end
return result_arr
end
The briliant part of this method is that you can push the two elements from the arr by using [arr[i], arr[j]] and then '.sort' will guarantee that the array is unique. This way works perfectly. It is just expensive. As always, using Hash gives you same result with cheaper(faster).
def make_100(arr)
hash = Hash.new
arr.each do |element|
pair = 100 - element
hash[element] = pair if arr != pair and arr.include?(pair)
end
return hash
end
With hash, I don't have to push to another arry and sort it again. The issue with this problem is that it becomes little complicated to deal with '50'. When pair == element, it must have both pair and element in the array.