Month: May 2014

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