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
Advertisements

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

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 (:

Bubble Sort?

Happy new year! I am finally back with a new post on code… yay!

now I am not a cs major, but come on all engineers should know the basics of cs, right?

Given an unsorted list of numbers, a bubble sort

  1. repeatedly step through the list to be sorted
  2. compare each pair of adjacent items and swap them if they are in the wrong order
  3. repeat until no swaps are needed

Recently, I picked up O’Reilly’s <Computer Science Programming Basics in Ruby>, and their bubble sort method threw me off…

note: I modified it so that I have a rndm_grades method that generates grades for me, so it is not an exact copy from the book, but the core loop functions the same way.


def bubble_sort(n)
    grades = rndm_grades(n)

    compare = 0
    for i in (0..n-2)
      for j in ((i+1)..n-1)
        compare +=1
        if (grades[i] > grades[j])
          temp = grades[j]
          grades[j] = grades[i]
          grades[i] = temp
        end
      end
    end
end

————– Bubble Sort? ————–
grades: [96, 29, 27, 7, 15]
i 0
j 1
comparing 96 & 29
swap takes place…….
j 2
comparing 29 & 27
swap takes place…….
j 3
comparing 27 & 7
swap takes place…….
j 4
comparing 7 & 15
currently grades are [7, 96, 29, 27, 15]
i 1
j 2
comparing 96 & 29
swap takes place…….
j 3
comparing 29 & 27
swap takes place…….
j 4
comparing 27 & 15
swap takes place…….
currently grades are [7, 15, 96, 29, 27]
i 2
j 3
comparing 96 & 29
swap takes place…….
j 4
comparing 29 & 27
swap takes place…….
currently grades are [7, 15, 27, 96, 29]
i 3
j 4
comparing 96 & 29
swap takes place…….
currently grades are [7, 15, 27, 29, 96]
number of comparisons made 10

in other words, given [96, 29, 27, 7, 15], in the first round of comparing…
compare 96 & 29 >> [29, 96, 27, 7, 15]
compare 29 & 27 >> [27, 96, 29, 7, 15]
compare 27 & 7 >> [7, 96, 29, 27, 15]
compare 7 & 15 >> [7, 96, 29, 27, 15]
compare and swap with the first element
the first number is always in the right order (aka the smallest number).

Bam! I am old school or what? I was stuck in this mind set >>
compare 96 & 29 >> [29, 96, 27, 7, 15]
compare 96 & 27 >> [29, 27, 96, 7, 15]
compare 96 & 7 >> [29, 27, 7, 96, 15]
compare 96 & 15 >> [29, 27, 7, 15, 96]
compare and swap with the current element
the last number is always in the right order (aka the biggest number).

now is this method necessarily comparing two “adjacent” numbers? hmmm…
————– Bubble Sort? ————–
grades: [60, 45, 55, 86, 60]
comparing 60 & 45 >> [45, 60, 55, 86, 60]
comparing 45 & 55 >> [45, 60, 55, 86, 60]
comparing 45 & 86 >> [45, 60, 55, 86, 60] nope
comparing 45 & 60 >> [45, 60, 55, 86, 60] nope

so is this still considered a “bubble” sort? hmmm…

anyway here is my take on the “traditional” bubble sort

def old_bubble_sort(n)
    grades = rndm_grades(n)   

    compare = 0
    sorted = false
    until sorted
      sorted = true
      for i in (0..n-2)
        compare +=1
        if grades[i] > grades[i+1]
          grades[i], grades[i+1] = grades[i+1], grades[i]
          sorted = false
        end
      end
      n -=1
    end     
  end

————– Bubble Sort? ————–
grades: [67, 90, 17, 27, 80]
comparing 67 & 90 >> [67, 90, 17, 27, 80]
comparing 67 & 17 >> [17, 90, 67, 27, 80]
comparing 17 & 27 >> [17, 90, 67, 27, 80]
comparing 17 & 80 >> [17, 90, 67, 27, 80]
comparing 90 & 67 >> [17, 67, 90, 27, 80]
comparing 67 & 27 >> [17, 27, 90, 67, 80]
comparing 27 & 80 >> [17, 27, 90, 67, 80]
comparing 90 & 67 >> [17, 27, 67, 90, 80]
comparing 67 & 80 >> [17, 27, 67, 90, 80]
comparing 90 & 80 >> [17, 27, 67, 80, 90]
sorted grades are [17, 27, 67, 80, 90]
number of comparisons made: 10

————– “Traditional” Bubble Sort ————–
grades: [67, 90, 17, 27, 80]
compare 67 & 90 >> [67, 90, 17, 27, 80]
compare 90 & 17 >> [67, 17, 90, 27, 80]
compare 90 & 27 >> [67, 17, 27, 90, 80]
compare 90 & 80 >> [67, 17, 27, 80, 90]
compare 67 & 17 >> [17, 67, 27, 80, 90]
compare 67 & 27 >> [17, 27, 67, 80, 90]
compare 67 & 80 >> [17, 27, 67, 80, 90]
compare 17 & 27 >> [17, 27, 67, 80, 90]
compare 27 & 67 >> [17, 27, 67, 80, 90]
sorted grades are [17, 27, 67, 80, 90]
number of comparisons made: 9

lots of different ways to implement this… what’s your take?