An exercise from Eloquent JS

At the moment, I am at Chapter 5 of Eloquent Javascript. It's been a little while since I started slowly going through it, and recently I've decided to accelerate my reading. Attending Women Who Code JS study groups has helped quite a bit as well.

Previously, I was working through some Angular.js tutorials, yet it is definitely helpful to have a more solid understanding of Javascript fundamentals. Thanks to this resource, there are many more books to read, and I definitely feel that I need to work through several before I will feel comfortable with JS functions.

There are several exercises at the end of each chapter of Eloquent Javascript, and I am including a solution to the first one from Chapter 5. The exercise states: "Use the reduce method in combination with the concat method to "flatten" an array of arrays into a single array that has all the elements of the input arrays".

Chapter 5 provides a sample reduce function, however, I have slightly modified it. The final solution is as follows:

var arrays = [[1,2,3], [4,5], [6]];

function reduce(array, combine){
    var current = [];
    for (var i = 0; i < array.length; i++){
        current = combine(current,array[i]);
    }
    return current;
}

console.log(reduce(arrays, function(a, b){
    return a.concat(b);
}));

RailsBridge and iOS

Last week I attended a MobileBridge Workshop, where a lot of women participants had a change to enhance their iOS development skills. For me it was the first experience in iOS. We built a simple Tip Calculator and started on a Rotten Tomatoes API app. All tutorials covered Objective-C.

As always, many thanks to organizers and teachers!

SQL queries in Rails

Recently, I needed to write a SQL query that would make multiple selections using insensitive search. The query would be done in either raw SQL and/or using Rails helpers.

For this task, I needed to select users if they practiced certain type of law according to the search terms. As such, there are Users who have many Practices through Practice_Users, and Practices have many Users though Practice_Users. I wanted to select Users with Practices if search terms matched the Practices. However, there are several stop words to avoid: for example, if two records in the database list 'Family law' and 'Family', and I want to search for 'family', then both records should be returned.

My initial solution was the following:
scope :by_practice, -> (pract) {joins(:practice_users).where("practice_users.practice_id IN (SELECT id FROM practices where name IN (?))", pract )}

However, this solution would work if only the search terms matched the database records exactly. Thus, searching for 'family' would exclude 'Family law'.

The second solution was the following:
scope :by_practice, -> (pract) {joins(:practice_users).where("practice_users.practice_id IN (SELECT id FROM practices WHERE #{pract})")}

pract = practices.map { |e|  "name iLIKE '%#{e}%'"}.join(" or ")

However, this solution is vulnerable to SQL injection due to the use of #{} in sql string i.e., #{pract}.

The third and final solution was sort of a combination of the first two: it used ? substitution in Rails and a regex expression in Postgres:

scope :by_practice, -> (pract) {joins(:practice_users).where("practice_users.practice_id IN (SELECT id FROM practices WHERE name ~* ?)", pract)}

pract = practices.map {|e| "#{e}"}.join('|')

Coverage gem

Just a little note that I am quite enjoying working with the simplecov gem. It helps to determine which sections of the app are still to be tested - models, controllers etc. It provides a nice visual interface, where the covered lines are shown in green, and untested lines are highlighted in red. Very helpful.

Devise login with membership id

I am currently working on another small project, where Devise is used for authentication. The project requires that users log in with a membership id instead of an email and a password (these are default Devise settings). The project is set up in such a way that an admin creates users using their membership id, and then the users log in with the membership id. The users can't delete their account; only an admin can.

Based on Devise documentation and other research, it appeared that several things needed to be done. First, one needs to create a membership id in the User table, and to add this parameter to the list of permitted parameters. Second, the log in form needs to be modified so that it includes the membership id only.

However, adding the membership id to the list of permitted parameters was only a partial solution. It would allow me to register the user using the membership id but when I would try to log the user in, I would get an authorization error.

Since Devise uses Warden for authorization and the default settings include email and password, the solution was to add another Warden strategy, so that the membership id would be recognized as a legitimate choice.

In initializers directory I created a file named membership_strategy.rb:

require 'devise/strategies/authenticatable'

module Devise
  module Strategies
   class Membershipid < Authenticatable

     def valid?
       true
     end

     def authenticate!
       if !params[:user].nil?
         auth_params = {}
         auth_params[:membershipid] = params[:user][:membershipid]
         resource = mapping.to.find_for_authentication(auth_params)

         if validate(resource){ resource.find_for_database_authentication(auth_params) }
            success!(resource)
         else
            fail!(:invalid)
         end
       end
     end
   end
  end
end
Warden::Strategies.add(:membershipid, Devise::Strategies::Membershipid) 

In initializers/devise.rb the following line needs to be appended to the beginning:

config.warden do |manager|
   manager.default_strategies(:scope => :user).unshift :membershipid
end

First hackathon

It's been a little while since I wrote the last post, but some interesting events have happened. Last weekend I attended my first hackathon - DevelopHer, organized by LinkedIn. It was a 24-hour event for women developers, and it was a great experience. And big thanks to organizers who provided the space and opportunity for people to participate.

Our team worked on creating an app on farmers' markets and fruits and vegetables that would be available from a market. The idea was to allow a user to search for nearest farmer markets by zipcode, and to browse the goodies that the markets would offer. Other options would include the recipes of foods that could be made from fruits and vegetables. The app was built with Python and Django framework.

We didn't finish the app but our team plans on working on it. I expect the results to be awesome.

I did learn a lot from the hackathon. It was great to work with Django, since I've never used it before. I found that Rails experience helped me to catch on Django quickly. I have new friends and a team to work with on future projects. Certainly looking forward to more hackathons.

Yet another Chess

I really hope this is the last post on chess game! Once I was done with writing a version in Ruby, I have translated the major functionality into a Javascript game. The Ruby version was very hard to play since it is terminal-based; however, the Javascript version certainly makes it more visual.

It can be played here, though Github. The game currently supports determining checks only. Mate is being determined in some situations but not all. Still room to improve but I need to move onto other projects.

More on Chess

I've been working on my chess game (see previous post) for a while by now. Primarily because once I had the main logic in, I did quite a bit of refactoring of the design over and over. While it can be improved further, my current design is as follows.

There are nine classes: Game, Board, Piece, and 6 Piece subclasses (Pawn, King etc). There is also a module called Converter that assists in converting x and y coordinates of the Board into 1D array, and vice versa.

The Piece class has the majority of methods that subclasses inherit from. Its basic structure is as follows:

class Piece
    include Converter
    attr_accessor :id, :x, :y

    def initialize(color=:white,x=0,y=0)
    end

    def move_to(x,y)
    end

    # determines what cells a piece can theoretically go to
    # in parent class, this method checks the board boundaries 
    def can_piece_move?(to_x, to_y)
    end

    # determines whether a piece can move to a cell (e.g., if it is empty).
    # Also "captures" an enemy piece
    # if the destination cell is occupied by one.
    def valid_move?(board, to_x, to_y)
    end
end

All Piece subclasses inherit these methods and override them as needed. Thus, each Piece subclass naturally implements its own version of can_piece_move?(to_x, to_y). All Piece subclasses except for Pawn use the method valid_move?(board, to_x, to_y) as defined in the parent class. However, Pawn has its own implementation of the valid_move? method because Pawn can only move in one direction vertically and can only capture in one direction diagonally.

Additionally, the Pawn class implements a special method that allows to count how many times the Pawn was moved (as a reminder, a Pawn can be moved 1 or 2 steps at a first move, but only 1 step afterwards). The King class has a special method as well - this method loops through surrounding cells and returns an array of cells where the King can move to. This method is used in determining whether the King is in check.

The Board class is shown below. Instead of placing Pieces directly into the Board matrix, I have chosen to create a collection of pieces, where each Piece has an id calculated on the basis of x and y coordinates of the Board. All positions are thus calculated on the basis of this id. Accordingly, it is easy to find a Piece in a collection by its id or to remove a Piece from the collection once it's been captured.

class Board
    include Converter
    attr_accessor :board, :piece_collection, :destination

    def initialize
        @board = Array.new (Converter.rows) { |i| Array.new(Converter.cols) { |j| nil } }
        @piece_collection = []
        @king_collection = []
    end
   
    # places pieces into corresponding collections
    def setup_pieces
    end

    def remove_piece_from_collection(piece)
    end

    def find_piece_in_collection(pid)
    end
   
    # determines whether the king has any moves left
    def legal_moves_left?(king)
    end

    # determines if the king is in immediate danger
    def threatening_piece(king)
    end
   
    # determines if the path is free/blocked 
    def is_it_blocked?(from_x, from_y, to_x, to_y)
    end

    def display
    end
end

Finally, the Game class determines the sequence of events and checks for a winner. The sequence of events is quite straightforward: a player inputs an id of the Piece she wants to move, and an id of the location where to move the Piece to. If the move is valid, the Game updates x and y coordinates of the involved Pieces and calls a method to determine whether there is a winner. The winner method looks as follows:

def determine_winners(board)
    board.king_collection.each do |king|
       board.destination = king
       threat = board.threatening_piece(king)
       legal_moves = board.legal_moves_left?(king)

       if legal_moves == true && !threat.nil?
          puts "WINNING: #{threat.full_description} Check!"
          return true
       elsif legal_moves == false && !threat.nil?
          puts "WINNING: #{threat.full_description} Check & Mate!"
          @game = false
          return true
       elsif legal_moves == false && threat.nil?
          puts "WINNING: #{player_turn.upcase} StaleMate!"
          @game = false
          return true
       end
    end
    false
end

The full code is available at my Github. I still wonder how it is possible to improve the design. It appears that the Piece and Board are heavily dependent on each other and the same arguments (board, to_x, to_y) are constantly being passed around. As they said in BerkeleyX SaaS Engineering course, if a group of arguments keeps traveling around, they may have to be extracted into a separate class. I guess as I learn more about OO design (and Sandi Metz's book "Practical Object Oriented Design in Ruby" has been already a great help), I will find myself re-writing the game again.

Chess game

Last time I played chess I was in the 6th grade or so. Okay, I didn't actually _play_ it, I was sort of moving the figures according to the rules. Since I don't know how to play chess, I decided to implement my own game of chess in Ruby. I hope to find time to turn it into a web game later on. Currently, the game is played in the terminal and it is a bit hard on the eyes.

For now, I am still working on the logic. One of the challenges was to write a generalized method that would allow to move a piece in any direction and return an error if there was a block on the way. At first, I ended up writing 8 if statements - one for each direction - but that looked so, so ugly. However, I realized it was possible to specify vectors instead. In the end, the method looked as follows:

def is_it_blocked?(board, from_x, from_y, to_x, to_y)

        result = false
        direction_x = from_x > to_x ? 1 : -1
        direction_y = from_y > to_y ? 1 : -1

        row = (from_x - to_x).abs
        col = (from_y - to_y).abs

        if  row > col
            diff = row
        else
            diff = col
        end

        (1...diff).each do |i|
            if row > col
                cell = board.board[to_x+i*direction_x][to_y]
                result = true if !cell.nil?
            elsif col > row
                cell = board.board[to_x][to_y+i*direction_y]
                result = true if !cell.nil?
            else
                cell = board.board[to_x+i*direction_x][to_y+i*direction_y]
                result = true if !cell.nil?
            end
        end
        result
    end

Stacking arithmetic expressions

As I was reviewing linked list data structure, I came across a beautifully simple algorithm to evaluate an arithmetic expression, developed by E.W. Dijkstra. Say, you have an expression in a form like "(1+(2*3)+3)". Dijkstra's algorithm uses two stacks: one holds the values and the second one holds the operators. As you are iterating over the string, you push values and operators onto corresponding stack if you encounter an opening parenthesis. Once you encounter a closing parenthesis, you pop a value and an operator, perform an arithmetic operation and push an updated value to the value stack. This implementation requires that the expression has a complete set of opening and closing parentheses.

Instead of using Ruby's Array and corresponding pop() and push() methods, I decided to implement my own stack class as a singly linked list from scratch. By the way, the time complexity for stack operations are as follows: O(1) for push() and pop(). This makes sense since we are just accessing the top element. However, the search for an element would be slow (O(n)), since linked lists do not support indices, and one would have to traverse all the elements to get to the desired one.

class Stack

    attr_accessor :first

    def initialize
        @first = Node.new
        @len = 0
    end

    def push(item)
        oldfirst = @first
        @first = Node.new
        @first.item = item
        @first.next = oldfirst
        @len += 1
    end

    def peek
        return @first.item
    end

    def pop
        item = @first.item
        @first = @first.next
        @len -= 1
        item
    end

    def empty?
        return @len == 0
    end

    def len
        return @len
    end

    class Node
        attr_accessor :item, :next

        def initialize
            @item = nil
            @next = nil
        end
    end
end

def calculate(str)

    values = Stack.new
    operators = Stack.new

    str.split(" ").each do |i|
        if i == '('
            # just skip
        elsif i == '+'
            operators.push(i)
        elsif i == '-'
            operators.push(i)
        elsif i == '*'
            operators.push(i)
        elsif i == '/'
            operators.push(i)
        elsif i == 'sqrt'
            operators.push(i)
        elsif i == ')'
            operator = operators.pop
            value = values.pop
            if operator == '+'
                value = values.pop + value
            elsif operator == '-'
                value = values.pop - value
            elsif operator == '*'
                value = values.pop * value
            elsif operator == '/'
                value = values.pop / value
            elsif operator == 'sqrt'
                value = Math.sqrt(value)
            end
            values.push(value)
        else
            values.push(i.to_f)
        end
    end
    values.pop
end

str = "( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )"
puts calculate(str)
str2 = "( ( 1 + sqrt ( 5.0 ) ) / 2.0 )"
puts calculate(str2)

Operator precendence

In this post I would like to discuss the difference between Ruby's and / && and or / || operators. Based on prior experience with Java, I would usually use && instead of and (|| instead of or). However, I've seen code samples with and or operators, and so I was under impression that it might've been a more Ruby-ish, human friendly way of writing code. (Plus, I was used to using and (or) when programming in NetLogo).

The truth is that one needs to pay attention to operator precedence in Ruby, as defined in the docs. Thus, the following code snippets will be evaluated differently:

a = true and false      => a = true
b = true && false       => b = false

As described in the docs, = operator takes precedence over and operator, while && takes precedence over = operator.

Putting parenthesis around an expression when using and (or) can help to make sure you are getting the expected behavior. Thus, the following expression will be evaluated to false:

a = (true and false)    => a = false  

Me not knowing this little catch probably explains some of the funny behaviors I was getting in my code sometimes. But I am a big fan of using parenthesis to help me visually break the code into pieces, and this habit probably saved me from bigger troubles.

Testing Speechy

When I was developing Speechy app, I must admit I included only a handful of tests. This mainly happened because I would frequently change design requirements; plus I was learning a great deal of new information. 

I have recently started adding unit-tests to the app. So far I am following Everyday Rails Testing with RSpec, and I find it to be a good and useful read.

Another anagram

It's been a little while since I've practiced solving smaller problems with the idea of improving my coding skills. (For a couple of weeks I became an in-house dog-sitter for a small puppy; who knew small puppies are SO demanding of attention).

The problem asks to take a parent string and a child string as parameters, and return the count of how many times a child string appears in the parent string as is or as an anagram.

I first tried to create all the permutations within the parent string but realized it was a wrong approach (to begin with, it took forever).

My final solution involves sorting a child string first. While iterating a parent string, at each iteration I create a string of the length of the child and sort it as well. Then I compare the child to this newly created string and increment the counter if the two match.

def anagram_detection(parent, child)
    sorted_child = child.chars.sort.join
    char_parent = parent.chars
    counter = 0
    (0..char_parent.length - child.length).each do |i|
        word = char_parent[i...i+child.length].sort.join
        counter += 1 if sorted_child == word
    end
    counter
end

print anagram_detection('AdnBndAndBdaBn', 'dAn')
print anagram_detection('AbrAcadAbRa', 'cAda')

Weather app

In the latest RailsBridge class that I attended, we discussed how to incorporate apis in the app. This inspired me to create my own little weather app.

As I searched Programmable Web for something quick and not complicated for a small project, I came across a weather api provided by the 5DayWeather. I mimicked the original site to some point in order to display weather data for a selected city. Additionally, I've added a google map pointing to a selected city. The google map portion was taken after an awesome Sitepoint tutorial. The api calls are handled using Faraday gem.

Coursera quick-union

I have recently made another attempt at taking Coursera's Algorithms course. At the moment I am not in an urgent need to optimize my programs and estimate their efficiency as my programs are quite small, but the day will hopefully come and I will need this knowledge. Anyway, I tried taking this course some time ago but dropped out of due to the lack of time. Hence, attempt number 2.

I started a little late and only covered week 1 materials for now. Week 1 problems cover quick-union algorithms. Even though the course is taught in Java, I decided to re-write the weighted quick-union algorithm in Ruby (it didn't look that much different from the original). I further applied it to the following proposed problem: Given a social network containing N members and a log file containing M timestamps at which times pairs of members formed friendships, design an algorithm to determine the earliest time at which all members are connected (i.e., every member is a friend of a friend of a friend ... of a friend). Assume that the log file is sorted by timestamp and that friendship is an equivalence relation.

I interpret this problem such that we should determine how many friend groups are in there. If there is only one friend group, this means all people are connected to each other, and we return the timestamp associated with the last node.

We start with the total number of nodes equal to the number of connections, and as we loop through friend pairs and merge them into groups, we reduce the number of nodes by 1. At the end, we should be left with one node only.

sample input:
20141001 0 2
20141002 0 4
20141003 2 3
....

class WeightedQuickUnionUF

    attr_reader :total_roots

    def initialize(n)
        @id = (0...n).to_a
        @sz = (0...n).to_a
        @total_roots = n
    end

    def connected?(first, second)
        find(first) == find(second)
    end

    def friends_connected?
        @total_roots == 1
    end

    def union(first, second)
        i = find(first)
        j = find(second)

        return if i == j

        if @sz[i] < @sz[j]
            @id[i] = j
            @sz[j] += @sz[i]
        else
            @id[j] = i
            @sz[i] += @sz[j]
        end
        @total_roots -= 1
    end

    def show
        print "#{@id}\n"
    end

    def find(index)
        while index != @id[index]
            index = @id[index]
        end
        index
    end

end

test = WeightedQuickUnionUF.new(13)

f = File.open("links.txt", "r")
f.each_line do |line|
    l = line.split(' ')
    test.union(l[1].to_i,l[2].to_i)
    print "#{l[0]}: #{test.friends_connected?} #{test.total_roots}\n"
end
f.close

Algorithm performance chart

A nice article explaining Big-O notation here. I wish there was a second part. Meanwhile, here is a summary of growth and rate name, as put together by the author's blog:

Oh snake

As I am spending more time learning Javascript, the inevitable has occurred: building a Snake game (a part of the Odin Project).

Posting here some fruits of my labor (css and html are here). The game is fairly basic, though I tried to make it more fun by using little sprites.

$(function(){

    prepareGrid();

    $('#submitter').click(function(){
        initiateGame();
    });
});

function prepareGrid(){
    $(".grid").remove();
    $("#points").text(0);
    for (var i = 0; i < 30; i++){
        for (var g = 0; g < 40; g++){
            createDivs(18, i, g);
        }
    }
}

function createDivs(size,i,j){
    d = document.createElement('div');
    $(d).addClass("grid");
    $divgrid = $(d);
    var h = size.toString() + 'px';
    $divgrid.height(h);
    $divgrid.width(h);
    $divgrid.data("value", { row: i, col: j } );
    $divgrid.attr("col", j );
    $divgrid.attr("row", i );
    $('.wrapper').append($divgrid);
}

function initiateGame(){
    prepareGrid();
    snake = new Snake(20,20);
    $("div").find("[row="+snake.xx+"]"+"[col="+snake.yy+"]").addClass('snake');
    generateFood();
    runGame();
}

function Food(){
    this.xx = Math.floor(Math.random() * 29);
    this.yy = Math.floor(Math.random() * 39);
}

function generateFood(){
    $('div.food > img').remove();
    $("div").removeClass('food');
    food = new Food();
    $("div").find("[row="+food.xx+"]"+"[col="+food.yy+"]")
            .addClass('food').prepend('<img src="images/star.gif"/>');
}

function runGame(){
    var snake_head = [snake.xx, snake.yy];
    var snake_tail = snake.sbody.pop();
    var new_coords = snake.changeDirection(snake_head);

    snake.eatFood();
    snake.moveToXY(new_coords[0], new_coords[1]);

    if (new_coords[0] < 0 || new_coords[0] > 29 || new_coords[1] < 0 || new_coords[1] > 39 || snake.collision())
    {
        alert("Kaboom! You just crashed into a wall or\n\nYOURSELF. Eek. \n\nGame over!");
        location.reload();
        return;
    }

    repaintSnakeHead(new_coords[0], new_coords[1]);
    repaintSnakeBody(snake_tail);
    setTimeout(function(){ runGame() }, 50);
}

function Snake(xx,yy){
    this.xx = xx;
    this.yy = yy;
    this.sbody = [];
    this.direction = "up";
    this.sbody.push([this.xx, this.yy]);
}

Snake.prototype.changeDirection = function(snake_head){
    switch(this.direction){
        case 'up':
            var new_x = snake_head[0] - 1;
            var new_y = snake_head[1];
            break;
        case 'down':
            var new_x = snake_head[0] + 1;
            var new_y = snake_head[1];
            break;
        case 'right':
            var new_x = snake_head[0];
            var new_y = snake_head[1] + 1;
            break;
        case 'left':
            var new_x = snake_head[0];
            var new_y = snake_head[1] - 1;
            break;
    }
    return [new_x, new_y];
}

Snake.prototype.collision = function () {
    for(var i = 1; i < this.sbody.length; i++){
        if (this.xx === this.sbody[i][0] && this.yy === this.sbody[i][1]){
            return true;
        }
    }
    return false;
};

Snake.prototype.eatFood = function(){
    if (food.xx === this.xx && food.yy === this.yy){
        this.sbody.unshift([food.xx, food.yy]);
        $("#points").text(Number($("#points").text())+1);
        generateFood();
    }
}

Snake.prototype.moveToXY = function(xx,yy){
    this.xx = xx;
    this.yy = yy;
    this.sbody.unshift([this.xx,this.yy]);
}

function repaintSnakeHead(new_x, new_y){
    switch(snake.direction){
        case 'up':
            $("div").find("[row="+new_x+"]"+"[col="+new_y+"]").addClass('snake head_up');
            break;
        case 'down':
            $("div").find("[row="+new_x+"]"+"[col="+new_y+"]").addClass('snake head_down');
            break;
        case 'right':
            $("div").find("[row="+new_x+"]"+"[col="+new_y+"]").addClass('snake head_right');
            break;
        case 'left':
            $("div").find("[row="+new_x+"]"+"[col="+new_y+"]").addClass('snake head_left');
            break;
    }
}

function repaintSnakeBody(snake_tail){
    $('div.snake').each(function()
    {
        var cols = $(this).data("value").col;
        var rows = $(this).data("value").row;

        if (snake.xx === rows && snake.yy === cols){
            // do nothing
        }else{
            $(this).removeClass('head_up head_left head_right head_down');
            $(this).addClass('body_piece');
        }
    });

    $("div").find("[row="+snake_tail[0]+"]"+"[col="+snake_tail[1]+"]").removeClass('snake body_piece head_up head_left head_right head_down');
}

$(document).bind("keydown", function(key)
{
    switch(parseInt(key.which,10))
    {
            // Left arrow key pressed
        case 37:
            snake.direction = 'left';
            break;
            // Up Arrow Pressed
        case 38:
            snake.direction = 'up';
            break;
            // Right Arrow Pressed
        case 39:
            snake.direction = 'right';
            break;
            // Down Arrow Pressed
        case 40:
            snake.direction = 'down';
            break;
    }

});

Symbols and strings

There is a lot of discussion around symbols and strings in Ruby. I put together a little flashcard explaining the difference. So: a symbol sort of looks like a string, except it is not. A symbol is immutable and reusable; unlike strings, it references one object in memory. For this reason, it makes the lookup of symbols faster. However, symbols cannot be manipulated like strings (hence immutability), which makes them less useful in certain situations. Another problem is that symbols cause memory leaks, since they are not released from the memory. However, the good news is since Ruby 2.2 symbols will be garbage collectible. See this article here.

Monday joke

Funny article. I wonder how Ruby fits in? 

On coding linguistics

This is an older post by Sarah Mei about the relationship between programming and human languages, and I still love it.

Not to boast, but I've been what they call "natural" when it came to picking up grammar and spelling rules in my native language. In fact, I seemed to have had an innate knowledge of grammar (frankly, it must have come from my love of reading). Learning a foreign language was also easy - I would see similarities in how to apply grammar rules. I liked languages - when I was little, I created my own language inspired by Tolkien's Hobbit. I created the alphabet (the letters looked like ancient hieroglyphs) and the grammar. My friend and I then used this language to write notes to each other, so that no one else could understand them. That was the first code I created.

When I was learning the basics of programming, drawing on linguistics concepts helped me tremendously. There is a structure, and a 'sentence' is formed by following a set of rules. Yes, a programming language has a much more rigid structure than a human language. But in a sense, I think it makes it easier because in simple terms, it is easier to follow one set of rules rather than 55 sets plus 155 exceptions.

Just a note for today. As I said, the article was great.

Good reads

A couple of books have been sitting on my bookshelf for a some time, and I can't wait to go through them thoroughly.

The first one that I recently started reading is a well-known Practical Object-Oriented Design in Ruby by Sandi Metz. I am looking forward to improving my understanding of design, and this book comes highly recommended. Even though a lot of design principles were (re)introduced during the edX SaaS course, it was not enough. I fully expect to take as much as possible of Metz's book.

One more book that will have to wait a little is Metaprogramming Ruby by Paolo Perrotta. I can't say much about it yet but it appears to be recommended.

Finally, I've discovered a golden mine of Javascript-related resources here. I have started digging more deeply into Javascript, and the first one on the list is Eloquent Javascript by Marijn Haverbeke.

Lots of good reads, and many more are coming.

Find a unique character

It never hurts to get a little more practice with solving problems in Ruby. A simple problem that I came across is how to find the first unique element in a string.

This can be done using hashes and counting how many times an element appears in the string.

example = "Hhello, Mr. Doglet."

def find_first_unique(example)
    hsh = Hash.new(0)
    example.downcase.split("").each { |i| hsh[i] +=1 }
    hsh.each { |key, value| return key if value == 1 }
end

puts find_first_unique(example) #=> ,

Fixup Git

Looking back at my Git commit history, I realize it looks quite ugly. I frequently make very small commits - like fixing a typo, then fixing another typo (since the first one was not actually a typo), fixing it again etc etc. It really looks ugly.

I am finally learning the power of rebase and squash (fixup) in history management. While I have not applied it to my real projects yet (I've only experimented on a test project), I am really looking forward to using it in the future.

Basically, the rebase command allows you consolidate however many commits you want into one. To do that, one needs to call
git rebase -i HEAD~N, where N is the number of commits to consolidate, counting from the last one. For example, 4.

You then see a screen, which lists the commits to be rebased, for example:

pick aaaaa 'commit message1'
pick bbbb 'commit message2'
pick ccccc 'commit message3'
pick dddd 'commit message4'


There are also several options: pick, edit, squash and fixup. I tried squash and fixup - they are both the same, except that squash shows the commit logs and fixup doesn't. So I guess if it is necessary to hide some particularly bad commit logs, fixup is the choice.

Assuming we want to consolidate three commits with the first one, the command console will look like that:

pick aaaaa 'commit message1'
fixup bbbb 'commit message2'
fixup ccccc 'commit message3'
fixup dddd 'commit message4'


Once the changes have been applied, the project will only show one commit: that is, commit message1. And now the history looks much cleaner.

Now, I still need to learn how to fix any issues when the rebase command was applied incorrectly. So far, Git has been winning over in these situations (though not for long, I bet).
 
 

GeoRails

Yesterday I attended my first class at Railsschool. The topic of the discussion was how to create geospatial applications with Rails. As I've worked at lot with traditional GIS in the past (mainly ArcGIS), I was definitely interested in learning how to apply my geographic skills in the realm of web geography.

We covered the usage of the activerecord-postgis-adapter and rgeo gems. The rgeo gem relies of PostGIS extension for PostgreSQL, which is the recommended choice for working with spatial data.

I am not sure how many hiccups there would be along the way when working with complex datasets and applications (I am sure more than I can imagine), but creating a very simple tutorial-like application was fairly straightforward. The author of the gem wrote a series of blog posts back in 2011, which is still a great reference.

Some pain usually comes with installing PostGIS itself. However, I used a Postgres.app for OSX, which comes bundled with PostGIS and is very easy to install.

One thing to remember is that PostGIS extension needs to be enabled for each of the databases you intend to use. It is possible to do it either manually, that is connecting to the database via psql --dbname=yourdatabasename and running the following commands (taken from the website):

-- Enable PostGIS (includes raster)
CREATE EXTENSION postgis;
-- Enable Topology
CREATE EXTENSION postgis_topology;
-- fuzzy matching needed for Tiger
CREATE EXTENSION fuzzystrmatch;
-- Enable US Tiger Geocoder
CREATE EXTENSION postgis_tiger_geocoder;

However, in Rails environment it is easier to run the following command: rake db:gis:setup, which enables the PostGIS extension. As already mentioned, the blog referenced above as well as the  github pages for activerecord-postgis-adapter and rgeo gems provide a lot of instructions.
 

GoogleV3 geocoder

This weekend I was playing with GoogleV3 geocoder and Python, as I needed some geocoded data for one of the projects.

The script itself is essentially copy and paste of the example code. However, I added a timeout call to the function in order to prevent any crashes if the server is not responsive. Additionally, I added an if-else statement in order to check whether the geocoder returned a valid value before writing it to file (again, in order to prevent any crashes).

It was certainly pleasing to see that so hundreds of addresses can be geocoded to lat/long within seconds. The only limitation was that a public API allows only about 1,000 or so calls per 24 hours (presumably for a given IP address).

I also wonder how accurate the geocoder is - it would be nice to plot all the data on the map and check how well it corresponds to what's on the ground.

import os, sys,re, time, csv
from geopy.geocoders import GoogleV3

geolocator = GoogleV3()
resultFile = "output.txt"

fileWrite = open(resultFile,'w')
fileRead = open("input.csv")
fileRead.readline() # read the first line

for line in fileRead:
    theaddress = splitline[3] # array index of address in my sample data
    theaddress += (", San Francisco, CA")
    result = geolocator.geocode(theaddress, timeout=20)
    if result:
        address,(latitude, longitude) = result
    else:
        print("Error: geocode failed on input %s"%(theaddress))
    fileWrite.write(address,(latitude, longitude) + "\n")

fileRead.close()
fileWrite.close()
print("done")

Word cloud

D3 library provides a lot fun ways to visualize one's data. I came across a great word-cloud library by Jason Davies, and I wanted to implement this visualization in my Rails app.

In order to do that, you first need to add d3-rails gem to your Gemfile, and //=require d3 to application.js (I always forget to restart the server at this point, and the app complains it can't find D3). You should then add d3.layout.cloud.js (downloaded from here) to the vendor/assets/javascripts directory. Finally, don't forget to add //= require d3.layout.cloud in application.js as well.

If you copy and paste example code (provided with Davies' library), it should work straight away. However, I wanted to see if I could read a static JSON file with word data instead of using a word array like in the example.

This can be done by creating a file say 'word.json' and placing it in the public directory so Rails has access to it. D3.layout.cloud requires such attributes as text and size, so the JSON file should look like this:

[
  { "text":"word1", "size":1 },
  { "text":"word2", "size":2 },
  { "text":"word3", "size":3 },
   .....
]

The file and its data can then be accessed as follows:

d3.json("/word.json", function(data){

   d3.layout.cloud().size([200,200]).words(data)

   ..... 

});

Additionally, I implemented a function that would redraw the graph on window.resize event. However, getting JSON data like this resulted in a slow and delayed rendering. Not quite sure whether this behavior is to be expected or whether something should have been done differently. Until a better solution, I am placing my words in an array directly in the function similar to the example.

Ajax and partials

As I keep adding more jQuery options to Rails my app (renamed Speechy), I discover the need to pass parameters via Ajax requests. In the app, one of the pages has two tabs: a click on one of the tabs shows a list of emotions to be selected, and a click on the second tab shows the images selected accordingly. Data from the first click is supposed to be passed via Ajax click event, and the first tab is supposed to display selected images without reloading the entire page.

This is done as follows:

In show.html.erb I set up the tabs to be called. emotion-tabs renders contents_form partial with checkboxes for emotions. In test-tabs, blank_response partial will be replaced with selected images with the help of jQuery.

<div id="student-tabs">
    <ul>
        <li><a href="#test-tabs" class='test-tabs-button'>Test</a></li>
        <li> <a href ='#emotion-tabs'> Select emotions</a></li>
    </ul>

    <div id="test-tabs">
         <%= render 'blank_response' %>
    </div>

    <div id="emotion-tabs">
        <%= render 'contents_form' %>
    </div>
</div>

_contents_form partial with a remote:true link:

<h3> Selecting emotions </h3>
    <% tag_selection Content.select_tags(current_user.id) do |tag| %>
        <li>
            <%= check_box_tag "tag_ids[]", tag.id, false, class: 'submittable' %>
            <%= tag.tagname %>
        </li>
    <% end %>
    <br/>
    <%= link_to "Select", show_selected_path(@student),
          remote: true, class: "btn btn-primary btn-xs submitme" %>

show_selected_path(@student) is a custom route that belongs to a method in a controller (in my case Student controller). The method gets the passed params[:tag_ids]:

def show_selected
    @selected_contents = Content.joins(:tags).
        where(tags: { id: params[:tag_ids]}).belongs_to_user(current_user.id)
    respond_to do |format|
         format.js
    end
end

The submitme button collects data from selected checkboxes as an array of ids and passes it to the show_selected method in controller:

$('.submitme').on('click',function(){
    var tag_array = $('input:checked').valList().split(',');
    var pathname = window.location.pathname;
    $.ajax({
         type: "GET",
         url: pathname+'/show_selected',
         data: { tag_ids: tag_array },
         success: function()
         {
            // alert('Success occurred');
         },
         error: function(){
            alert('Error occurred');
         }
    });
    return false;
 }); 

Finally, the show_selected method takes a responds_to format.js block. Since format.js does not take any arguments, this means that the file to be called has the same name as the method:

show_selected.js.erb:

<% if @selected_contents.count <= 0 %>
    $("#test-tabs").html("<%= escape_javascript(render 'blank_response') %>");
<% else %>
    $("#test-tabs").html("<%= escape_javascript(render 'shared/selected_contents') %>");
<% end %>

Second RailsBridge event

On Saturday I attended another Front-End RailsBridge event. As always, it was a great event organized by great people.

My group first started working on implementing a calendar-like app with jQuery. The idea was to create a simple calendar (just the front end of it), where one would be able to choose a date and set an event for that date.

However, later a smaller group (including myself) has broken off and started working on a Wacky Painter app. Here, the idea was to create a bunch of grids and to change the grid color on a mouseenter event.

While I have done a similar application in the past, it was good to see other approaches. Additionally, I learned how to populate a dropdown menu with jQuery. Assuming you have an array of colors and a div named dropdowns, the function looks like so:

window.populateMenu = function(){
    $(".dropdowns").find('option').remove();
    $(".dropdowns").append('<option value="'+'random'+'">'+'random'+'</option>');
    for(i = 0; i < colors.length; i++){
        $(".dropdowns").append('<option value="'+colors[i]+'">'+colors[i]+'</option>');
    }
}

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.