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: