A simple formula to rapidly succeed

This is a well-known formula. Wanted to see how it looks in code. Only 5 lines, not bad!

Of course, you can force kill this infinite loop :), how far you go is up to you, though!

Cheers!
Braga

State of Rails Releases

I am dealing with multiple Rails applications at once some of which are funded right and some of which have ran into maintenance modes. I just wanted to have a pictorial representation of what is the state of each of the Rails versions, unfortunately, I cannot get one. So I spent half an hour trying to decode the Rails official releases page and came up with this.

If you closely observe, the Rails releases 3.0.x and 3.1.x are history (I don't even want to pull up data for releases before that). It is high time you plan to upgrade your stack to a minimum of Rails 4.2 before you loose all the goodness the Rails community has to offer. Yes, I know it is a herculean task for folks in 3.x in which case I recommend you to do a complete rewrite of your application piecemeal by piecemeal!

Data Source: http://weblog.rubyonrails.org/releases/

Cheers,

Braga

Hotel Automation Controller - Interview coding problem

This is one of the problems I got via a friend who recently faced a company called Sahaj Software a clone company to Thoughtworks.

Problem Statement:

Hotel Automation Controller Problem  Statement

A very prestigious chain of Hotels is facing a problem managing their electronic equipments. Their equipments, like lights, ACs, etc are currently controlled manually, by the hotel staff, using switches. They want to optimise the usage of Power and also ensure that there is no inconvenience caused to the guests and staff.

So the Hotel Management has installed sensors, like Motion Sensors, etc at appropriate places and have approached you to program a Controller which takes inputs from these sensors and controls the various equipments.

The way the hotel equipments are organised and the requirements for the Controller is below:

• A Hotel can have multiple floors
• Each floor can have multiple main corridors and sub corridors
• Both main corridor and sub corridor have one light each
• Both main and sub corridor lights consume 5 units of power when ON
• Both main and sub corridor have independently controllable ACs
• Both main and sub corridor ACs consume 10 units of power when ON
• All the lights in all the main corridors need to be switched ON between 6PM to 6AM, which is the Night time slot
• When a motion is detected in one of the sub corridors the corresponding lights need to be switched ON between 6PM to 6AM (Night time slot)
• When there is no motion for more than a minute the sub corridor lights should be switched OFF
• The total power consumption of all the ACs and lights combined should not exceed (Number of Main corridors * 15) + (Number of sub corridors * 10) units of per floor. Sub corridor AC could be switched OFF to ensure that the power consumption is not more than the specified maximum value
• When the power consumption goes below the specified maximum value the ACs that were switched OFF previously must be switched ON

Motion in sub corridors is input to the controller. Controller need to keep track and optimise the power consumption.

Write a program that takes input values for Floors, Main corridors, Sub corridors and takes different external inputs for motion in sub corridors and for each input prints out the state of all the lights and ACs in the hotel. For simplicity, assume that the controller is operating at the night time. Sample input and output below.

Initial input to the controller: Number of floors: 2

Main corridors per floor: 1

Sub corridors per floor: 2

Since the hotel management is trying this for the first time, they would be changing the requirements around which electronic equipments are controlled and the criteria based on which they are controlled, so the solution design should be flexible enough to absorb these requirement changes without significant change to the system.

The solution to this problem involves approaching in an object oriented manner. Also we need to see here that we should use a Command/Strategy Pattern given there could be changes in the behavior based on external factors. I have not included the timings from the problem but from on here it should be easily extensible.

Code below:

Cheers!
Braga

Cloning remote PG database and loading in Local environment

For projects involving small to medium sized databases one may require to copy the remote (or production) database onto local environment. I was earlier doing this for my production application using custom pg_dump and then restoring with pg_restore. It was relatively straightforward but still consumed good amount of time. I wanted to automate this using capistrano and this is how I did it

You should note that this is extremely fast because it executes the command on the VPS - usually EC2 which has amazing internet speeds. And then copies it over scp as a single file. You can also add a compression step using the --format option in the pg_dump.

Hope this was helpful!

Cheers!
Braga

Ransack namespace collision - The search method

I am a big fan of Ransack, the Rails gem for quickly building a quick and easy Search based on pure ActiveRecord queries. For projects that require some on the fly search without having to set up dedicated Search Engines like Elastic Search, SOLR, ThinkinSphinx - this is a very juicy alternative.

However I recently faced one problem when I introduced this to a project where there already was SOLR integrated. It was because of the collision of the search method.

This simply patch did the job for me. All you have to do is include it to your initializers folder say under config/initializers/ransack.rb

That's it, the Ransack library will no longer collide with your existing suite. As a matter of fact the method search deprecated already and the library itself wants us to use the Alias ransack

Cheers!
Braga

My first ruby gem horoscope is live

I wanted to write a rubygem on my own for a long time. Never had the time really to write one. However, recently I had some spare time during which I wrote this gem called horoscope. This gem will help drafting the horoscope of a person given the birth date, time and the place. Source is hosted at Github. As with every other open source project out there, feel free to fork it and add more to your liking

Screenshot at Github

Proud to release this and I am planning to add more features to this. Also, planning to release different gems. If you want something particular or specific, don't be shy, add it in the comments section and I would be more than happy to contribute!

Cheers!
Bragboy

Write a program to build a small knowledge base about top "N" movies listed at IMDB

This was an interesting problem that I came across with. This problem is like an open book exam and race against time. The problem had to be solved within an allocated amount of time with a technology stack that is limited only to Ruby/Python/Node.js/Perl.

Few googling here and there and with some knowledge about Ruby I was able to solve this problem within an hour.

Problem Statement:

Build a small knowledge base about top "N" movies listed at http://www.imdb.com/chart/top. Each movie should mention the cast written on the individual page of the movie.
Given the name of a cast member, you should be able to return the movies out of the top "N" movies he/she has acted in. "N" will be passed by the user.
The knowledge base should be built during the runtime and stored in a data structure of your choice.
Q1. For example, if N=3, then you should parse the first 3 movies' individual pages from that page (http://www.imdb.com/chart/top) and build the knowledge base of the cast (there are about 15-20 on every page). Upon querying for "Morgan Freeman", you should return "The Shawshank Redemption". Do not use any external api for this.
Use only Ruby/Python/Node.js/Perl.

Solution:


Cheers!
Braga

Rails script/generate model with an association

I know this blog has been dormant for quite some days now for no apparent reason. But I would like to share what I learnt today. This is going to be in Rails (2.3.x) and hardly interest anyone who already knows it. But it still was a learning to me. I use to hate working in command prompt and was an IDE freak, a real good one too. But I was cornered to learn more on the command line front as well. Why waste an extra feather in the cap?
Bulling the shit, here is what I learnt today.

Rails has a script/generate ready for many usual stuff that we do. One of them is the model generator. It is not that much, but I was wondering whether it is possible to create associations using it. And I found it is not.

I tried a stupid model generation something like (in fact exactly like this)

rails -d mysql playground
cd playground
script/generate model project name:string has_many:tasks

It reeked,

exists  app/models/
exists  test/unit/
exists  test/fixtures/
create  app/models/project.rb
create  test/unit/project_test.rb
create  test/fixtures/projects.yml
create  db/migrate
create  db/migrate/20120227204200_create_projects.rb

My stupid assumption was that it would actually create a couple of models called projects and tasks. But to my wonder, it did not. The highlight was this command did not even raise any error. Inspecting the database migration, I found

class CreateProjects < ActiveRecord::Migration
  def self.up
    create_table :projects do |t|
      t.string :name
      t.tasks :has_many

      t.timestamps
    end
  end

  def self.down
    drop_table :projects
  end
end

And I did a migration and it did migrate without any errors. It silently ignored the line t.tasks :has_many. Not usual right?! But this is rails, you got to adapt and adapt very well. One more learning probably I could share are the commands that come with the script/generate model is the --pretend. This is like a dry run, does not actually creates a physical file but tells what its going to do. Thats it for today.

Cheers!
Braga

Blocks in Ruby

Blocks are one of the coolest things to have when you are coming from a language like C++ or Java. Say you are writing a function and you want to have some functionality within it which should be handled totally by the caller. Well, blocks come for the rescue.

Say I have a method like this.

There is a sweet keyword in Ruby to replace the second line of the test_method called yield.


And you can now make a call like,


Would output,
start
From block
end

Nothing great if you already are a ruby nerd. But for Java blokes, blocks are something to think for.

Cheers!
Braga

Efficient way to calculate prime numbers

In several puzzles/coding competitions we may need to check for prime numbers and this is required to be done in considerable time to save precious run time. The traditional approach is,



This will however will loop through all elements below x to see if a factor exists. Example, for finding if 13 is prime, we check if its divisible by 2,3,4,....12. This can be optimized to loop through only half the elements since the highest factor is going to be num/2 as,


But by analysis you can see that for a number say 100, the factors are (1*100),(2*50),(4*25),(5*20),(10*10),(20*5),(25*4),(50*2),(100*1). For finding out if 100 is prime or not we just need to check if 100 is divisible by any number not greater than 10 i.e., it is sufficient to check from 2 to 10. The reason being if its divisible by 4, its also divisible by 25.

Hence the best approach to check if a number is prime or not will be



Final prime number program in Ruby (bonus)


This approach will check for factors in very minimized number of loops.

Cheers!!
Bragaadeesh

Project Euler : Considering natural numbers of the form, ab, finding the maximum digital sum.

Problem 56

A googol (10¹⁰⁰) is a massive number: one followed by one-hundred zeros; 100¹⁰⁰ is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.
Considering natural numbers of the form, a^b, where a, b < 100, what is the maximum digital sum?

Solution (in Ruby)

Nothing much to discuss about the solution, I've implemented it directly as given in the problem statement.

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : Evaluate the sum of all amicable pairs under 10000.

Problem 21

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a b, then a and b are an amicable pair and each of a and b are called amicable numbers.
For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.
Evaluate the sum of all the amicable numbers under 10000.

Solution (in Ruby)

For this problem, it is vital to write an efficient method to find the sum of divisors of a number. The divisor finding logic is same as the one stated in Problem 12. Rest is an as-is implementation of the problem statement.

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : How many letters would be needed to write all the numbers in words from 1 to 1000?

Problem 17

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.
If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

Solution (in Ruby)

We will have to first try to come out with the unique words that are present in the numbers. We start with the ones which are one, two upto nine. Then the elevens starting from eleven to nineteen. Then the tens, twenties upto nineties. We should also define a hundred and thousand. After that the logic is directly readable from the ruby code given below.


Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : Discover all the fractions with an unorthodox cancelling method.

Problem 33

The fraction ⁴⁹/₉₈ is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that ⁴⁹/₉₈ = ⁴/₈, which is correct, is obtained by cancelling the 9s.
We shall consider fractions like, ³⁰/₅₀ = ³/₅, to be trivial examples.
There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.
If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

Solution (in Ruby)

This problem unlike the other problems does not ask us to go to millions and trillions and the scope is such that this can be solved in the least running time. All this problem demands careful inspection of the problem statement itself. Its clear we need to iterate through numbers from 1 to 99. For the outer loop (numerator), its enough we run from 12 since its the first double digit number which does not end with a 0 or their digits being equal. We run upto 97 since the numerator cannot be greater than equal to denominator since the fraction should be less than 1
Same is the case for the inner loop. We should always continue to the next iteration if the last number of either numerator or denominator is 0, or if both digits or equal or if the numerator is greater than or equal to denominator. Rest of the solution is just a language specific implementation of finding whether the two different fractions are indeed equal.

Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : What is the value of the first triangle number to have over five hundred divisors?

Problem 12

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?

Solution (in Ruby)

The main aspect about this solution is finding an efficient way to calculate the number of divisors. Lets take a simple example. The number 6 has 4 divisors namely 1,2,3,6. For this number its enough we run upto the Square root of 6 which is integer floored value to be 2. 1 is divisible by 6 by 6 times, so 1 and 6 are divisors. 2 is divisble by 6 3 times, so 2 and 3 are divisors. So totally we have 4 divisors.
There is one more point to be noted here. For a square number such as 16, if we apply this formula, we will end up getting 6 divisors --> 1, 2, 4, 4, 8, 16. You may see we may calculate 4 twice. But it occurs only once for a square number. This special case is handled in the solution given below. The rest is an as-is implementation of the problem statement.

Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : Concealed Square

Problem 206

Find the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0,
where each “_” is a single digit.

Solution (in Ruby)

Before we look at the optimal solution, lets look at what brute force has to offer us. There are nine slots in the number which leaves us to iterate on 1000000000 times (1 trillion times). This is simply not doable, it will take years to run through this loop. So brute force is out of the equation. We need to find a digit or two to reduce the loop count.

So its wiser to look at some of the property of square numbers. Square number ending with zero, has to have the previous digit also 0, which leaves us with only 8 slots now. One more property is that the square root for this particular number has to start with 1. The reason is in finding the square root, we need pair numbers from the back and need to find the square root of the first hanging digit/pair. In this case its 1. Square root 1 is 1 and its enough to inspect only one digit. This leaves us 1 more slot less in our problem. And one final property is the ending digit. Here its 9. Only numbers that end with 3 and 7 produces 9. This leaves our permutation reduce by one more digit (since its enough for us to step 10 times every time in the loop). We need to find the lower bound of the number which is 10203040506070809. The square root of this number is 101010101. We shall end with either 3 or 7. And start with the maximum digit in that sequence which is 199999999. Thats it!! Now we've shortened the problem to be solved within seconds!!


Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : How many circular primes are there below one million?

Problem 35

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.
There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
How many circular primes are there below one million?

Solution (in Ruby)

The solution to this problem invovles one performance enhancement in finding the prime numbers. If you want to check whether the same number is prime more than once in your program, it is highly important to have a look on the running time. That is why I am using an array to store the number as the index itself. This would make sure that the number given is found to be prime or not in O(1) time. Rest of the solution did what the problem statement demands


Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : Find the sum of all numbers less than one million, which are palindromic in base 10 and base 2.

Problem 36

The decimal number, 585 = 1001001001₂ (binary), is palindromic in both bases.
Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

Solution (in Ruby)

The solution is one the simplest and straightforward when implemented in Ruby.

sum = 0
1.upto(1000000) do |num|
  sum+=num if num.to_s == num.to_s.reverse && num.to_s(base=2) == num.to_s(base=2).reverse
end
puts "Sum is #{sum}"

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : How many triangle words does the list of common English words contain?

Problem 42

The n^th term of the sequence of triangle numbers is given by, t_n = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t₁₀. If the word value is a triangle number then we shall call the word a triangle word.
Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

Solution (in Ruby)

The main place where we need to attack this problem involves in finding the roots of the quadratic equation. We know the roots of the quadratic equation

If you apply this equation to the simple formula to find the triangle numbers, we will find out that a = 1 and b = 1 and c will be twice the triangle number. There will be two roots possible, one will be positive and other will be negative. It is enough to find the positive root. If that root is a whole number, then that will be a proper triangle number.

names = File.new("/words.txt","r").gets.split(/,/)
count = 0
names.each do |n|
  value = n.gsub!(/^"(.*?)"$/,'\1').split(//).inject(0){|b,i| b+i[0]-64}
  positive_root = (-1+Math.sqrt(1+8*value))/2
  count+=1 if positive_root == positive_root.ceil
end
puts "The total number of words is #{count}"

Hover here to see the solution

Cheers!!
Bragaadeesh