Ruby

compressor function

given: “aaabbcca”
return: “a3b2c2a1”

def compressor(string)
	# initialize
	compressed = ''
	count = 0
	i = 0

	size = string.size

	string.each_char do |s|
		
		i += 1

		if compressed[-1].nil?
			count = 1
			compressed = s
			next
		end

		# when c[-1] = a, s = a
		if compressed[-1] == s 
			count += 1
			# last character
			if i == size
				compressed << count.to_s
			end
			next
		end

		# when c[-1] = a, s = b
		if compressed[-1] !=s
			compressed << count.to_s << s
			count = 1
			next
		end

	end
	compressed
end

Find all prime numbers between x & y

I was watching this today… Learn Ruby Programming – Day 17 – Find Prime Numbers

well almost half way through before I decided to run it myself
note: it’s not an exact copy but the core is the same

def find_prime(x,y)
  prime = []
  while (x <= y)
    prime_flag = true
    i = 2
    while (i <= x/2)
      if x%i == 0 
        prime_flag = false
        break
      end
      i +=1
    end
    if prime_flag
      prime << x
    end
    x+=1
  end
  prime
end

and someone suggested to use #find

def prime_between(x,y)
  prime = []
  while x <= y
    result = (2..x).find{|i| x%i == 0}
    prime << x if result == x
    x +=1
  end
  prime
end

Yep #prime_between is definitely much neater than #find_prime, but how about the time?

t = Time.now
10.times{find_prime(7,100)}
puts "#find_prime: #{Time.now - t}"

t = Time.now
10.times{prime_between(7,100)}
puts "#prime_between: #{Time.now - t}"

#and in case you wanna see benchmark

require "benchmark"
time = Benchmark.measure do
  find_prime(7,100)
end
puts time

time1 = Benchmark.measure do
  prime_between(7,100)
end
puts time1

————- result

time 1: 0.000462
time 2: 0.001452
——————-
0.000000 0.000000 0.000000 ( 0.000052)
0.000000 0.000000 0.000000 ( 0.000167)

So even though #prime_between is neater, it’s slower… noted that #find_prime goes up to x/2

#...
while (i <= x/2)

whereas #prime_between goes up to x

#...
result = (2..x).find{|i| x%i == 0}

so in worst case scenario, #prime_between is obviously going to run longer…

so I updated #prime_between

def prime_between(x,y)
  prime = []
  while x <= y
    result = (2..x/2).find{|i| x%i == 0}
    prime << x if result.nil?
    x +=1
  end
  prime
end

updated benchmark:
#find_prime: 0.000463
#prime_between: 0.001015
——————-
0.000000 0.000000 0.000000 ( 0.000052)
0.000000 0.000000 0.000000 ( 0.000127)

Hmmm… yep a little faster than the previous #prime_between but still slower than #find_prime.

Anyway, here’s another one inspired by Sieve of Eratosthenes

def sieve_prime(x,y)
  prime = (x..y).to_a
  while (x<=y)
    (2..Math.sqrt(x)).each do |i|
      if x%i == 0
        prime -= [x]
        break
      end
    end
    x +=1
  end
  prime
end

ways to use #inject

sum an array

[0,1,2,3].inject(0){|sum, i| sum+i}
#=> 6

——————>>>>>>——————

linear array into hash

["apple", "orange", "pineapple"].inject({}){|k, v| k[v]=1; k} 
#=> {"apple"=>1, "orange"=>1, "pineapple"=>1} 

k: {}
v: apple
k: {“apple”=>1}
v: orange
k: {“apple”=>1, “orange”=>1}
v: pineapple
=> {“apple”=>1, “orange”=>1, “pineapple”=>1}

check this out

fruits = ["apple", "orange", "pineapple", "apple"]
fruits.inject(Hash.new(0)){|k, v| k[v]+=1; k} 
 #=> {"apple"=>2, "orange"=>1, "pineapple"=>1} 

or use #update

[0,1,2,3].inject({}) {|result, i| result.update(i => i+1)}
#=> {0=>1, 1=>2, 2=>3, 3=>4} 

k: {}
v: 0
k: {0=>1}
v: 1
k: {0=>1, 1=>2}
v: 2
k: {0=>1, 1=>2, 2=>3}
v: 3
=> {0=>1, 1=>2, 2=>3, 3=>4}

notice the difference in these two and the importance- make sure a hash is returned.

——————>>>>>>——————

arrays into hash

 def array_to_hash(array)
   array.inject({}) do |result, element|
     result[element.first] = element.last
     result
   end
 end

a = [[:fruit, "apple"],[:taste, "good"]]
array_to_hash(a)
#=> {:fruit=>"apple", :taste=>"good"} 

sidenote: or use Hash and group the arrays

Hash[*[[:fruit, "apple"],[:taste, "good"]].flatten]
#=> {:fruit=>"apple", :taste=>"good"} 

or this… dudh

[[:fruit, "apple"], [:taste, "good"]].to_h
#=> {:fruit=>"apple", :taste=>"good"} 

——————>>>>>>——————

turn hash into array

h = {0=>1, 1=>2, 2=>3, 3=>4}
h.inject([]){|result, i| p result; p i; result<<i}
#=> [[0, 1], [1, 2], [2, 3], [3, 4]] 

or this… dudh no.2

h.to_a
#=> [[0, 1], [1, 2], [2, 3], [3, 4]] 

——————>>>>>>——————

swap keys and values in hash

braces = {"[" => "]", "(" => ")", "{" => "}"}
braces.inject({}){|result, (k,v)| result[v]=k; result}
# => {"]"=>"[", ")"=>"(", "}"=>"{"} 

or invert

braces.invert
# => {"]"=>"[", ")"=>"(", "}"=>"{"} 

but both are lossy, if there’re multiple of the same values, then only the last value will be saved… this is where each_with_object comes in handy.

s = {:a=>1, :b=>2, :c=>2} 
s.each_with_object({}){|(k,v), result| result[v] ||=[]; result[v] << k }
# => {1=>[:a], 2=>[:b, :c]} 

these are only some basic usage, but hopefully you get the gist to use it to your advantages.

Enumerators and Enumerables

I just learned this via rubymonk

enum = [0, -1, 3, 2, 1, 3].each_with_index
p enum.select { |element, index| element < index }

# => [[-1, 1], [2, 3], [1, 4], [3, 5]]
oohh fancy, it returns both the element and the index

whereas not using enum…

n = [0, -1, 3, 2, 1, 3]
p n.select.each_with_index { |element, index| element < index }

# => [-1, 2, 1, 3]

more usage on enum

class Array
  def map_with_index(&block)
    self.each_with_index.map(&block)
  end
end

a = [0,1,2,3]
p a.map_with_index{|x| x+1}

#=> [1, 2, 3, 4]

just beautiful

Anagram?

Given: Two arrays of words in lowercase
Result: Print “True” if the pair of words in the same index is anagram, else print “False”

Example:
words_A = [“shots”, “name”, “app”, “lure”, “melon”]
words_B = [“hosts”, “mean”, “paa”, “rule”, “lemons”]
Result = true, true, false, true, false

When I first started coding the method, it was a huge mess…

def anagrams(first_words, second_words)
  
  first_words.each_with_index do |f, i|
    puts "#{f} vs #{second_words[i]}"
    f_size = f.size
    s_size = second_words[i].size
  
    #if the two words have different length, then for sure they're not anagrams
    if f_size != s_size
      puts false
      next
    end
    
    # compare the number of letters vs the number of letters in the other
    first_letters = f.scan(/[a-z]/).uniq
    second_letters = second_words[i].scan(/[a-z]/).uniq

    #key: letter, value: the amount of times the letter shows up in the word
    first_count = {}
    second_count = {}
    
    first_letters.each do |l|
      v = f.count l
      first_count[l] = v
    end
    
    second_letters.each do |l|
      v = second_words[i].count l
      second_count[l] = v
    end
    
    first_letters.each do |l|
      if first_count[l] != second_count[l]
        puts false
        break 
      end
    end
    
    puts true
  end
end

The silver lining of this is I learn the differences between break and next:
next: Jumps to next iteration of the most internal loop
break: Terminates the most internal loop.

Now after a few hours, I revisted the task, and reconquered it.

def anagrams_ii(first_words, second_words)
  first_word.each_with_index do |word, i|
    puts "#{word} vs #{second_word[i]}"
    first_sorted = word.split('').sort
    second_sorted = second_word[i].split('').sort
    unless first_sorted == second_sorted
      puts false
      next
    end
    puts true
  end
end

Sorting and then comparing, much cleaner.

Both prints out the following results:
shots vs hosts
true
name vs mean
true
app vs paa
false
lure vs rule
true
melon vs lemons
false

year, month, and day from a string

Given: “03/17/2014”
Get: Year = “2014”, Month = “03”, Day = “17”

There are numerous ways to get them, I’ll show you some easy ones and my favorite one (:

1st way:

  date = "03/17/2014"
  m = date[0..1]    # => "03"
  d = date[3..4]    # => "17" 
  y = date[6..10]   # => "2014" 

note: several ways to substring as well, for more info: http://www.ruby-doc.org/core-1.9.3/String.html#method-i-5B-5D

2nd way:

  m = "03/17/2014"[/(\d{2})\/(\d{2})\/(\d{4})/,1]    # => "03"
  d = "03/17/2014"[/(\d{2})\/(\d{2})\/(\d{4})/,2]    # => "17"
  y = "03/17/2014"[/(\d{2})\/(\d{2})\/(\d{4})/,3]    # => "2014"

3rd way (my fav):

"03/17/2014".scan(/(\d{2})\/(\d{2})\/(\d{4})/).flatten
 # => ["03", "17", "2014"] 

4th way:

data = "03/17/2014".match(/(\d{2})\/(\d{2})\/(\d{4})/)
 # => #<MatchData "03/17/2014" 1:"03" 2:"17" 3:"2014"> 
data.captures
 # => ["03", "17", "2014"] 

Radix Sort Methods

still on O’Reilly’s Computer Science Programming Basics in Ruby

radix sort: sort the list by each successive digit

Here’s their take on Radix Sort (it’s not an exact copy; there’re some modifications made but the core functions the same)

def radix_sort(n)
    grades = rndm_grades(n) #randomly generate grades
    puts "grades: #{grades}"
    
    max_length = 0

    grades.each_index do |i|
      grades[i] = grades[i].to_s
      len = grades[i].length
      if len > max_length
        max_length = len
      end
    end
    
    #add 0 padding so that all numbers have the same max length
    grades.each_index do |i|
      grades[i] = grades[i].rjust(max_length, "0")
    end
      
    for i in (0..max_length - 1)
      buckets = {}
      for j in 0..9
        buckets[j.to_s] = []
      end
      
      for j in 0..n-1
        num = grades[j]
        digit = num[max_length - 1 - i]
        buckets[digit].push(num)
      end
      
      grades = buckets.values.flatten
    
    end
    
  end

debug output:
grades: [69, 63, 10, 54, 6]
get the ones digits:
9
3
0
4
6
buckets: {“0″=>[“10”], “1”=>[], “2”=>[], “3”=>[“63”], “4”=>[“54”], “5”=>[], “6”=>[“06”], “7”=>[], “8”=>[], “9”=>[“69”]}
grades flattened — [“10”, “63”, “54”, “06”, “69”]
get the ones digits:
1
6
5
0
6
buckets: {“0″=>[“06”], “1”=>[“10”], “2”=>[], “3”=>[], “4”=>[], “5”=>[“54”], “6”=>[“63”, “69”], “7”=>[], “8”=>[], “9”=>[]}
grades flattened — [“06”, “10”, “54”, “63”, “69”]

inspired by rosetta code, which is absolutely beautiful (it even takes into account negative numbers and base numbers), here’s a radix sort that utilizes more advantages of ruby compared to the one above.

def radix_sort_ii(n)
    grades = rndm_grades(n)
    puts "grades: #{grades}"

    max_length = grades.max.to_s.length

    max_length.times do |i|
      bucket = Hash.new {|h,k| h[k] = []}
      grades.each do |g|
        digit = (g/10**i) % 10
        bucket[digit] << g
      end
      grades = bucket.values_at(*(0..10)).compact.flatten
    end

    puts "grades are sorted now: #{grades}"
  end

debug output:
————– Radix Sort ii ————–
grades: [49, 71, 77, 18, 32]
{9=>[49]}
{9=>[49], 1=>[71]}
{9=>[49], 1=>[71], 7=>[77]}
{9=>[49], 1=>[71], 7=>[77], 8=>[18]}
{9=>[49], 1=>[71], 7=>[77], 8=>[18], 2=>[32]}
{7=>[71]}
{7=>[71], 3=>[32]}
{7=>[71, 77], 3=>[32]}
{7=>[71, 77], 3=>[32], 1=>[18]}
{7=>[71, 77], 3=>[32], 1=>[18], 4=>[49]}
grades are sorted now: [18, 32, 49, 71, 77]

so how did the last step happen? the magic happens at line 13, check this out:

bucket = {9=>[90], 8=>[80], 6=>[67], 0=>[7], 2=>[27]}
bucket.values_at(*(0..10))
=> [[7], nil, [27], nil, nil, nil, [67], nil, [80], [90], nil]
bucket.values_at(*(0..10)).compact
=> [[7], [27], [67], [80], [90]]
bucket.values_at(*(0..10)).compact.flatten
=> [7, 27, 67, 80, 90]

don’t you just looovveee ruby? I do (: