Missing elements

It is Friday and Friday posts are allowed to be short. In this one, I just want to post a quick solution to the following problem: Given two arrays of non-negative integers, one of which is formed by shuffling the first array and removing one element, find the element that has been removed.

With Ruby, it is possible to use a zip method.

arr1 =     [1, 2, 3, 5, 65, 21, 34, 22, 87, 0, 3]
shuffled = [22, 87, 34, 0, 1, 3, 2, 5, 65, 21]



def find_missing(arr1, arr2)
    arr1.sort!
    arr2.sort!
    arr1.zip(arr2).each do |i, j|
        return i if i != j
    end
end



print find_missing(arr1, shuffled) #=>  3

Scraper analysis

As can be seen in the image below, a scraper is a flint tool that has been sharpened on one edge. Its purpose is generally to scrape animal hides, though a scraper can also be used to work wood, and shape bone and ivory into tools and art. Scraper is a general term, and many different types are recognized - for example, a side scraper, flake scraper, end scraper, blade scraper and others. This specimen is made out of obsidian and does not belong to any archaeological culture (it was freshly made a week ago). First tools, including scrapers, appeared approximately 2.6 million years ago.

Another type of scraper is a so-called web-scraper, as shown below. This is a very recent introduction to humanity's toolset - it barely covers a couple of dozen years if not less. Its purpose is to scrape websites for data and save the extracted data as needed. It can be argued that similar to the first type, its purpose is to shape something as well - by extracting desired data and leaving undesired data behind, a web-scraper assists in creating a new piece of information. However, unlike the first type, web-scrapers are non-destructive. While a flake scraper modifies the raw material, a web-scraper does not. All the data stays in the Internet no matter how much one scrapes it.

require "mechanize"

url = 'http://www.archaeologywordsmith.com/lookup.php?category=&where=headword&terms=Scraper'
fp = File.new("scraper_list.txt", "w")

agent = Mechanize.new

html = agent.get(url).body

html_doc = Nokogiri::HTML(html)

fp.write("Types of scrapers:\n\n")

list = html_doc.xpath("//dt[@class='results']")
list.each { |i| fp.write(i.text + "\n") }

Charting

For my SLPassist app I wanted to be able to create reports for each student. Additionally, I wanted to implement at least some simple graphs, for a quick and dirty visualization of a student's progress.

Following RailsCasts tutorials, I implemented a Highcharts graph showing a student's percentage of correct vs. incorrect responses per day. My graph was intended to be a stacked column graph like this:

Since I do not expect that the xAxis will have regularly spaced values (a student may use the app as often as once a month), it appeared reasonable to create xAxis values as an array of dates instead of using 'datetime' intervals like in the tutorial. However, it appeared to be problematic to pass a variable from a controller (a variable holding an array of dates) to a javascript function. Whenever a variable was passed, the categories were either rendered incorrectly (parenthesis and other marks were not properly escaped), or errors were raised.

Thanks to the wisdom of SO, the recommendation was to pass the variable as a JSON object. The final code looked like so (only showing the problematic line, cats):

<script type="text/javascript" charset="utf-8">

     var cats = <%= raw @student.dates.to_json %>;

        var chart = new Highcharts.Chart({
               ....
                xAxis: {
                    categories: cats
                },
              ....  
            });
</script>

Git hints

Yesterday I went to the East Bay Ruby meetup to listen to a presentation titled "You don't know git". The presenter broke his presentation into three parts: git for a simple flow (one user), git for advanced simple flow, and git for a team work.

I apparently fall into an 'advanced single user' category, as I try using branches when I work on experimental features. However, git for team work is a very different story. It certainly requires some practice with a team.

Some of the useful tips I could incorporate now is to customize most commonly used git commands in git config --global. The presenter suggested the following (although each person devises their own custom system):

a       = add .
au      = add -u
st      = status
ci      = commit -v
co      = checkout
br      = branch
unstage = reset HEAD --
last    = log -l HEAD


It takes some time getting used to it but in the long run it's faster to type git a instead of git add .

Another suggestion is to create bash aliases in order to shorten the commands even more. Thus, command git checkout or git co can be aliased as gco. This is 114% and 50% difference in the number of letters in the former and the latter cases, accordingly.

Guest users

I haven't touched my SLPapp for a while, as recently I've been mainly working on studying algorithms and solving various mathematical problems. It is amazing how easy it is to forget what you've been doing before. Just two weeks pass and you look at your own code and you ask yourself: who wrote it? What is it even all about?

Anyway, it is certainly time to get back to my SLPapp, as I would like to finish it soon. One of the new features I wanted to implement is creating a guest user with Devise.

I first looked at the Devise wiki, whose approach is to create a guest user in a session. Unfortunately, the guest user would persist only as long as the browser session is open. For my purposes, I wanted the guest user to have almost the same functionality as a regular user. Specifically, I wanted the guest user to be able to create the same - or almost the same associations - as a regular user. In this case, it seemed appropriate to use an approach discussed in RailsCasts episode #393. The approach is as follows: create a guest user in a database, sign them in, and delete all guest users from the database using a rake task (for example, every 24 hours).

In ApplicationController:

    def create_guest_user
        u = User.new { |user| user.guest = true }
        u.email = "guest_#{Time.now.to_i}#{rand(100)}@example.com"
        u.save!(:validate => false)
        sign_in(:user, u)
        redirect_to root_path
    end

In routes.rb:

match '/sign_in_guest', to: "application#create_guest_user", via: 'get'

In a view:

<%= link_to "Guest Login", sign_in_guest_path %>

As a result, a user can click on a "Guest Login" link, and a unique guest user is generated and saved to the database automatically. The user can perform almost the same operations as a regular user. Currently, there is no option to save all the temp data if a guest user decides to sign up but I may reconsider this later.

Combinations + recursion

In the previous blog entry, I've posted two iterative solutions for creating combinations using NetLogo and Ruby. I then spent an entire weekend trying to conquer recursion and to re-write this function using recursive methods. I think I am still a bit away from being truly conformable with implementing recursion: each time I think I understand its implementation, I find that I still do not understand it. I guess, it is a recursive process in itself; I just need to get a proper base case.

Anyway, this blog post has tremendously helped me to get a firmer grasp of both the concept and implementation details. I particularly liked different examples ranging from simple to complex. I then implemented the fill algorithm trying my hardest not to look for hints.

Below are the fruits of my weekend fight with combinations:

def combinations(str)
    return [str] if str.length == 1
    combos = combinations(str[1..-1])
    current = [str[0]]
    combos.each {|combo| current += [str[0] + combo] }
    return (current + combos)
end  

Creating combinations

I've been looking through some of my old NetLogo code (perhaps, feeling nostalgic) and I've discovered a method I wrote some time ago in order to create combinations of variable names. For example, using a string 'abc' one can create the following combinations: a, b, c, ab, ac, bc, abc.

For practice, I re-wrote this method in Ruby. The implementation is both cases is the same (iterating over an array using a nested loop), but it is interesting to compare the grammar of two languages. For example, NetLogo requires initializing an empty array prior to performing any further actions. It also has an interesting way of adding an element to an array (line 10). I also love the use of [?], which refers to the input in the task ordered by number . 

NetLogo:

to-report comparison [strings]
  let results []
  foreach n-values length strings [?]
  [  
    let current item ? strings    
    foreach n-values length results [?]
    [
      let next item ? results
      let combo sentence next current      
      set results lput combo results       
    ]     
    let combo []
    set combo lput current combo
    set results lput combo results
  ]
  report results
end

Ruby:

def combinatations_iterative(str)
    results = []
    (0...str.length).each do |i|
        (0...results.length).each do |j|
            results << results[j] + str[i]
        end
        results << str[i]
    end
    return results
end

Anagram problem

In this post, I would like to share my solution for an anagram problem. The problems is stated as follows: Write a method to sort an array of strings so that all the anagrams are next to each other.

The problem doesn't state any special conditions (e.g., whether it is necessary to sort the groups of anagrams), so I assume a simple approach. For example, if the input is alert, acre, pool, race, care, loop, alter, later, then the output could be something like acre, race, care, alert, alter, later, pool, loop.

This problem could be solved using hashes. Example is below with the comments.

def anagrams(input)

    hash = Hash.new

    n = 0

    # iterate over the array

    while n < input.length()

        # convert each string into characters and sort

        word = input[n].chars.sort

        # create a new key value if it doesn't exist

        hash[word] ||= []

        # iterate over the remaining words in the array

        (n...input.length).each do |i|

            # compare each word in the remaining array with the first word

            # and add it to hash if it doesn't exist yet

            if word == input[i].chars.sort

                hash[word] << input[i] if !hash[word].include?(input[i])

            end

        end

        n += 1

    end

    # return only values of the hash converted into an array

    hash.values.flatten

end
 
input = ['alert', 'acre', 'pool', 'race', 'care', 'loop', 'alter', 'later']
print anagrams(input)

The output is ["alert", "alter", "later", "acre", "race", "care", "pool", "loop"].

The complexity of this solution seems to be O(n^2) (or very close to it) since we are iterating over each element twice - the outer loop picks an element, and then the inner loop goes over the remaining elements to find all matches; then the process repeats. I would like to think about a better approach in the future.

Customizing Devise

As I use Devise gem for user authentication, sometimes I run into situations when it is necessary to customize devise's controllers. The simplest case is when I want to add an extra field to be passed through the form during the registration. For example, I want to add a user's name.

So what to do:

1. Create your own RegistrationsController which inherits from Devise::RegistrationsController and modify the update_sanitized_params with the value you want to pass (for example, name).

class RegistrationsController < Devise::RegistrationsController
    before_filter :update_sanitized_params, if: :devise_controller?

    def update_sanitized_params
        devise_parameter_sanitizer.for(:sign_up) {|u| u.permit(:name, :organization_name, :email, :password, :password_confirmation,
                :name)}
    end
end

2. Update the routes.rb like so:

devise_for :users, :controllers => { registrations: 'registrations' }

3. Update the app/views/devise/registrations/new.html.erb form accordingly, so you can pass the name parameter.

4. Do a little dance if the above works.

Sorting bubbles

Once upon a time ago, I needed to merge data from two text files: one file had household data, where each household had a unique id assigned to it; and another one had household members data, where each member was associated with its household through that unique id. Both files were big (over 2 million households and however many household members) but sorted, so it should have been easy. However, back in the days my naive approach and weak understanding of how to keep track of indices in a loop resulted in some hanging processes. A kind soul suggested that I used a binary search algorithm (since my data was sorted) but back then I have not even heard of it. (There was a happy end to the story).

So the lesson to be learned is you need to know your algorithms. As such, I am starting to review at least some basic ones and how they are different.

Bubble sort is usually taught as one of the first algorithms. It works by comparing two adjacent elements and swapping them if the first element is larger than the second (assuming we want to sort from lowest to highest). The example is below:

def bubble_sort(array)
    n = array.length
    begin
        (n...array.length-1).each do |i|
            if (array[i] > array[i+1])
                swap(array,i)
            end
        end
        n = n - 1
    end while n >= 0
    array
end

def swap(a,i)
    a[i], a[i+1] = a[i+1], a[i]
end 

In terms of Big O Notation, bubble sort's performance is described as having O(n^2) or quadratic runtime in the average and worst cases, and O(n) or linear runtime in the best case. Performance is determined by the number of swaps and comparisons to be made.

The best case is when the array is already sorted or nearly sorted. In this case, bubble sort just makes one iteration over the array and then stops. For example, we have an array like [1,2,3,4,5]. It compares 1 and 2 and finds that 1 and 2 are already sorted and do not need to be swapped, then moves onto comparing 2 and 3, 3 and 4, 4 and 5. Since all the elements are in a proper order, only one iteration of the array over n elements is needed, no swaps are needed and the number of comparisons to be made is equal to (n-1).

The worst case is when the smallest element is at the very end of the array; for example [2,3,4,5,1]. In this case, the smallest element will be changing its place once per each iteration until it is placed in a proper location:

[2,3,4,5,1]
[2,3,4,1,5]
[2,3,1,4,5]
[2,1,3,4,5]
[1,2,3,4,5]


As a result, in the worst case this requires one comparison and one swap per each iteration.

It also helps to see some real numbers for the visual purposes. Thus, I created two arrays with a length of 10,000 elements: both were sorted but in the second array the smallest element was placed at the end. Using the Benchmark library for Ruby, I got the following results:

array1: 2.3600000000000003 millisecs
array2: 4900.736           millisecs

That's quite a difference. Bubble sort doesn't perform well on large datasets, but it is quite efficient on small datasets and the nearly sorted ones.

Dancing with RVM

At some point something must have gone wrong with my installation of RVM - Ruby Version Manager. Specifically, something must have happened with permissions, as I was being forced to use sudo more and more often when I wanted to install a gem or even do bundle install!

At some point it became ridiculous, as I couldn't do anything without sudo anymore - even saving a Sublime file when working on an app. I tried to reinstall, but still no luck. Later, it turned out that my installation of RVM was probably system-wide instead of user-specific and my user name was not added to it.

Other than reinstalling, the following steps should help to fix the nightmare:

• in terminal, type id and see if there is a group called 'rvm' in the list of the results;


• if not, create a group by typing rvm group create rvm


• add yourself as a user by typing rvm group add rvm your_user_name


• fix permissions by typing rvm fix-permissions


• make sure you have a stable version: rvm get stable


• restart, as it might be required for the changes to take effect.

I'm writing this up in case if something goes wrong again, there is a complete list of instructions. Hopefully, no more dancing with RVM.

jQuery and Ajax weekend

This weekend I worked on how to submit a modal form in Rails using Ajax request. This goes back to my SLP (speech language pathologist) Assistant app that I am working on most of the time these days.

The form is a modal form, which looks like this:

<div class="modal-dialog modal-sm">
    <div class="modal-content">
        <div class="modal-header">
            <button type="button" class="close" data-dismiss="modal" aria-hidden="true">&times;</button>
            <h4 class="modal-title" align="center">Select tags</h4>
        </div>
            <div class="modal-body">
                <% select Content.select_tags do |tag| %>
                    <li>
                        <%= form_for tag, remote: true do  |f| %>
                            <%= f.check_box "selected" %>
                            <%= tag.tagname %>
                        <% end %>
                    </li>
                <% end %>
            </div>
        <div class="modal-footer">
            <div class="row text-center">
                <button type="button" class="btn btn-default btn-sm" data-dismiss="modal">Close</button>
                <button type="button" class="btn btn-primary btn-sm submitme">Select</button>
            </div>
        </div>
    </div>
</div>

The submit button is actually outside of the main form, so it doesn't do anything if it is used as is. However, it is possible to call it using jQuery:

$('.submitme').on('click',function(){
      var valuesToSubmit = $('.edit_tag').serialize();
      $.ajax({
           url: $('.edit_tag').attr('action'),
           data: valuesToSubmit
       }).success(function(data){
           $('.edit_tag').trigger('submit.rails');
       });
       return false;
)};

submitme is the button to be clicked, and edit_tag is the name of the form automatically generated by Rails. The serialize() method creates a text string in a standard URL-encoded notation and serializes controls within the form. attr('action') allows to select an appropriate url to which to send data.

Most interestingly, I've stumbled across an interesting way to actually trigger the event: $('yourform').trigger('submit.rails'). Thanks to Stack Overflow wisdom.

To Kill A Mocking Stub

This week is clearly dedicated to RSpec and testing, as I've been working on Connect Four game and testing it most of the week. One of the things I've long wanted to clarify for myself is how to create fake objects and methods while testing, and what the difference is in how these fakes are created.

Specifically, what is the difference between stubs and mocks? What does it mean if we are stubbing a method vs. mocking an object? Both are related to creating some fake data and expectations regarding how our code show behave. There is also some confusion regarding the terminology.

According to RSpec docs, a method stub is "an instruction to an object (real or test double) to return a known value in response to a message". A message expectation is "an expectation that an object should receive a specific message during the course of a code example".

The main difference lies in the message expectation part. Both stubs and mocks operate with test doubles, which are just like stunt doubles standing in for some celebrity. However, when a stub creates a test double for a method, it does not create an expectation that the method will be called. In other words, it just returns a specified result for the method without calling an actual method. On the opposite, a mock does create an expectation that the method will be called. As a result, stubs do not fail a test (because they do not trigger an actual method), but mocks can fail (if a triggered method does not return expected results or if a method is not called).

Here is a simplified and a bit artificial example from Connect Four game. Let's say we want to check whether a given color was placed in a given location at a board. Note that the set_color_to function is called twice on purpose:

def set_color_to(color)
    @color = color
end

def set_colors_at(x,y)
    @matrix[x][y] = set_color_to("blue") unless !@matrix[x][y].nil?
end

def iam_a_weird_function
    set_color_to("red")
    x,y = 1,2
    set_colors_at(x,y)
end

def get_color_at(x,y)
    @matrix[x][y]
end

And the tests look like so:

let(:board) { Board.new }

describe "stubs vs mocks" do

    it "uses a stub" do
        allow(board).to receive(:set_color_to).and_return("green")
        board.iam_a_weird_function
        expect(board.get_color_at(1,2)).to eql "green"
    end

    it "uses a mock" do
        # expect(board).to receive(:set_color_to).and_return("green")
        expect(board).to receive(:set_color_to).and_return("green").exactly(2).times
        board.iam_a_weird_function
        expect(board.get_color_at(1,2)).to eql "green"
    end

end

The first test passes because we stub the set_color_to function, which returns a predetermined value of green. Even though the set_color_to function is called twice in the actual code, it doesn't matter in the test because a stub doesn't require a method to be actually called.

The second test fails at line 12 and complains that it expected to receive a message once with any arguments; instead, a message was received twice. This is happening because a mock has an expectation that the set_color_to function will be called. Line 13 fixes this by adding exactly(2).times option, which specifies how many times we expect to receive a message.   

This example shows functional differences between stubs and mocks; what is the conceptual difference? Testing is based on the idea that each test should test a single behavior; using stubs and mocks helps to achieve this. Thus, a stub could be used to check if a correct view is being rendered in an application, but it wouldn't check if an appropriate method gets called. The latter should be tested in a separate function.