kalyanchakravarthy.net – Kalyan’s Weblog, Rantings, Projects, Designs….and more blah


About

I am a 25 year old human, on a quest to discover self. Developer by trade, Designer and a Photographer by passion. I am also an amateur world traveller.

Read more »

Posts

Longest palindromic substring

  January 14th, 2014 | In Ramblings | No Comments »

The simplest naive solution, of looping through each character as the centre of palindrome, to finding longest palindromic substring, in a string, has O(n^2) time complexity. This can be improved to be solvable in linear time or O(N) complexity – and there are many ways to do it – one being creating a suffix tree of all prefixes and another being Manachers algorithm.

Manacher’s algorithm works pretty much the same way naive solution works, except, it tries to use the properties of palindromes i.e reflection around a centre to its advantage. After a long time trying to understand this algorithm, I managed to implement it.

Here is a simple solution in python

"""Manacher's algorithm implementation in python"""
import sys
# convert the string to have odd number of characters
# by inserting a token char between every character of the string
s = ("matata")
ps = ['#']
for c in list(s):
	ps.append(c)
	ps.append('#')

# ata -> becoms -> #a#t#a#
print ps

P = [0] * len(ps)
center = 0
right = 0

for i in range(len(ps)):
	mirror = 2 * center - 1;
	# the P[i] should be what its reflection is
	# or in case there is a mismatch in the initial set
	# it should be distance to right edge of known palindromes
	if i < right :
		P[i] = min( P[mirror], right - i )

	# attempt to expand palindrome at the center i
	# use previous computation 
	while( (i+1+P[i]) right:
		center = i
		right = i + P[1]

# P simply contains the maximum length of all palindromes at each center
# Figuring out the actual string is a trivial problem
# so I leave thee here
print P

Test run

pogobook(20:36):python $ python manacher.py 
['#', 'm', '#', 'a', '#', 't', '#', 'a', '#', 't', '#', 'a', '#']
[0, 1, 0, 1, 0, 3, 0, 5, 0, 3, 0, 1, 0]

Trust & Credibility

  August 7th, 2013 | In Ramblings | No Comments »

Smartness does not imply one will get things done. Competence does not imply accountability and which in turn does not imply smartness. These attributes are neither inter-related nor do they all go hand in hand.

Respect is what you gain when you show one of the attributes. Trust & Credibility are what you gain when you exhibit positive levels of all of them. Its easy to mistake for them to be universal (i.e trust at one thing is trust everwhere), but to realise otherwise, it takes experience.

I used to believe in the complete opposite and I was never more wrong. This has been one of the biggest eye openers for me in the recent times. Time, projects, money and ideas can be saved from reckless abandon and be taken to completion in the company of right people. I wish I had known this earlier.

In all fairness, it is possible that the naive version of me, may have hindered other people and their ideas, either when they were in the works or when they pitched to involve me and that makes me cringe at myself in disbelief.

This happens more often than one might think and is not necessarily specific to IT.

Inverted Snakes

  October 16th, 2012 | In Games, JavaScript, Projects | 1 Comment »

Everyone has played classic snake, be it on mobile, online, gameboy, whatever. If you have not, drop everything, I mean everything, including your heartbeat if possible and get on and play it.

Invertes snakes is a Javascript/Canvas implementation of Classic Snake with a twist – There are 2 snakes Red and Blue – You only control one snake, the 2nd one just mirrors your movement. The food for snakes alternate between Red & Blue, each snake only eats its colored food.

Rules are simple

  • You don’t die by crashing. You die on timeout
  • Red snake eats red food. Blue Snake eats Blue Food.
  • You always control RED snake.
  • You start with 30 seconds
  • Food gets you +10 seconds & +100 points.
  • Post your scores in the comments below :)

Demo & Javascript Source

 

Note: Some of Chrome’s plugins may cause <space> to not star the game. Try playing the game in another browser or disable your plugins.

  Tags : , ,

Tetris in Javascript and Canvas

  February 14th, 2012 | In Games, JavaScript, Programming | No Comments »

I love tetris. I have never written tetris before and I have always wanted to. Attempted it once but couldn’t figure out heads and tails of it and then left at it. I wanted to get over it.

So i wrote it, in less than 4 hours (bragging rights) in JavaScript using canvas. Feel free to browse the source or Play it here

http://kalyanchakravarthy.net/projects/fun/jstris/

 

During the process I learnt how to use the javascript “with()”. Despite all the cliches around it, I feel its a pretty awesome and useful language feature. It logically made sense to use it to group statements together, especially the drawing functions.

with( stage.ctx ) {
	fillStyle = "#fff";
	fillRect( theX+1, theY+1, stage.cellSize-2, stage.cellSize-2 );
	fill();
}

Ain’t that neater than this?

stage.ctx.fillStyle = "#fff";
stage.ctx.fillRect( theX+1, theY+1, stage.cellSize-2, stage.cellSize-2 );
stage.ctx.fill();

Imagine doing it for 20-30 statements.

  Tags : , , ,

Anonymous functions in Javascript

  February 14th, 2012 | In JavaScript, Programming | No Comments »

We all know the usual way to create anonymous functions is to write something like this

(function() {
 alert('hello');
})();

I recently learnt this works too (#1)

!function() {
 alert('hello');
}(); 

But interestingly enough that same code, without the !, throws a syntax error. (#2)

function() {
 alert('hello'); 
}(); 

This had me stoked for a while until I realized why and it was obvious all along.

In the first case the “!” makes the function be treated as an anonymous function object and then negating it to result false after it has executed. But in the #2, the absence of an expression and starting of the statement with ‘function’ keyword makes the interpreter look for a named function, which it wouldn’t qualify for due to the absence of a name, thereby resulting in syntax error.

The same piece of code in the context of an expression, works just fine

> x = function() { return 10; }(); 
> x
 10 

So, will naming work? Yes.

//Naming works too
> x = function xyz() { return 15; }(); 
> x
 15 

Can we call it outside an expression without grouping? No. That would throw an error, as after consuming a fully formed function, the interpreter tries to consider the empty anonymous parenthesis as a different statement.

> function xyz() { return 15; }();  //error
> ();  //error

Make the empty parenthesis a valid statement, and it works

> function xyz() { return 15; }(1);

How do we know its an independent statement?

> function xyz() { return 15; }(console.log(20));
> 20

But then how do we call it ? By Grouping.

> (function xyz() { return 15; })(console.log(20));
> 20  //console log
<- 15  //return

Why does it work? The function instead of being a simple statement, now is an object in an expression, which means can be evaluated and can take arguments.

But arguments need not be an expression and can be empty. That brings us back to the standard statement.

> (function xyz() { return 15; })();
<- 15  //return

Interesting language JavaScript is.

  Tags : , , ,

Detecting multiple arrow key strokes

  November 6th, 2011 | In Processing, Programming | No Comments »

Most games or applications which make use of arrow keys, sometimes require the use of multiple combinations like UP+RIGHT, LEFT+DOWN, etc also. I was trying to do the same for a 3d game I was trying to write in Processing. It might seem like a simple problem, which it is, surprisingly i couldn’t find anything on it. So after playing around with a little bit i figured it out.

Each key when pressed and released individually triggers a separate event, including for combinations of keys. Hence the way to test if both Up+Right keys are pressed, is to store the pressed status of individual keys, and clear their status individually when each key is released.

Here is the processing code. The logic should be applicable for any language and platform.


class KeyStateReader {
  //binary sequence for easy state storage
  static final int K_UP = 1;
  static final int K_RIGHT = 2;
  static final int K_DOWN = 4;
  static final int K_LEFT = 8;

  int keyState;

  //combine the key stats into single variable by logical |
  public void onKeyPress() {
    int kType = getK();
    keyState |= kType;
  }
  //on release clear individual bits
  public void onKeyRelease() {
    int kType = getK();
    keyState = keyState ^ kType;
  }
  // pass a key combo using logical or '|' ( UP | RIGHT ) to see if it exists. 
  public boolean isKey(int k) {
    return (k & keyState) != 0 ? true : false;
  }
  // do we have any at all ?
  public boolean hasAnyKey() {
    return keyState > 0;
  }

  public int getK() {
    switch(keyCode) {
      case UP: return K_UP;
      case DOWN: return K_DOWN;
      case LEFT: return K_LEFT;
      case RIGHT: return K_RIGHT;
    }
    return -1;
  }
}

KeyStateReader keyState = new KeyStateReader();
void keyPressed() {
  keyState.onKeyPress();
}
void keyReleased() {
  keyState.onKeyRelease();
}

To check for key combos you can now do this

void checkKeyCombo() {
  // for UP+RIGHT
  if( keyState.isKey( KeyStateReader.K_UP | KeyStateReader.K_RIGHT ) ) {
    do_something_up_right();
  }
  // You can even check them individually
  if( keyState.isKey( KeyStateReader.K_UP ) ) {
    do_something_up();
  }
  if( keyState.isKey( KeyStateReader.K_RIGHT ) ) {
    do_something_right();
  }
}

There are definitely other ways to do it too, like maintain an array with all the keyCodes and check if the key being tested is available in the array. That way you will be able to track multiple keys and you wouldn’t have to re-define key codes for each of them.

  Tags : , , ,

RSS Feed for Flickr Explore

  October 25th, 2011 | In Ramblings | 1 Comment »

Am a big fan of Google Reader and have subscribed to hundreds of RSS feeds. I love browsing through Flickr. I am addicted to it, especially to their explore section, where daily they come up with few hundred most interesting photos from flickr for that day.

So I wrote a PHP Script which generates an RSS feed of the 100 most interesting photos on Flickr’s explore, every single day via a cron job which uses Flickr API and a bit of cUrl magic. A 100 photos are published to the RSS Feed, every-single-day. The explore positions vary through out the day, but only those that appear to the script when it runs are considered.

Every single day I go through those photos, I am left inspired and mesmerized. There are so many amazing photographers out there, that simply watching their work is a delight. It just makes my day. Here is the Feed URL for you to subscribe for your photography delight.

Feed URLhttp://feeds.feedburner.com/Flickr-Daily-100-Interesting

You can use any Feed Reader you want. If you are not sure I would recommend Google Reader.

  Tags : , , , , , ,