Terminal based Spell Check

Here's a cool little script I wrote (added to my .bashrc) file in order to test spellings, or to generate them when I don't remember them.

function spelling {
if [ $((`grep -c "^$1$" /usr/share/dict/american-english`)) -gt 0 ]; then
   echo -e "Spelling of\e[1;32m" `grep -m 1 "^$1$" \
    /usr/share/dict/american-english` "\e[0mseems fine"
else 
   echo -e "\e[1;31mThere seems to be a mistake in spelling\e[0m"
fi
}

The script is run quite simply by saying "spelling word-to-be-checked". For example,

spelling look

would say

Spelling of look seems fine

but

spelling louk

would say

There seems to be a mistake in spelling

Where this is extremely useful is when you cannot remember some part of the spelling of a word. For example allitaration or alliteration. Here, I can just use a regex.

Running

spelling allit.ration

would say

Spelling of alliteration seems fine

thereby giving the right spelling.

Editorial for Blitzkreig "Lost Zucky"

A nice problem based on choosing a proper method to denote state and then implementing it correctly and efficiently.

Let's first look at the question:

  Problem Statement:

  Zucky wants to find his way out of a maze in minimum possible steps. 
  Zucky knows that he can get lost in the maze if he can't find the exit so 
  he decides to find a way by writing the code first. Now, he knows that 
  there are doors, keys and walls in the maze. Doors and keys can be of four 
  colors Red, Blue, Green, Yellow (RBGY) and red, blue, green, yellow (rbgy) 
  respectively. (Capital letters represent doors, lower case letters 
  represent keys). Every key can open the door of same color as its own. For 
  eg. r can open R, g can open G, etc. No one can get through the walls. 
  Now, being a busy person he can't write all the code. So, he turns to you 
  for help. Your task is to find minimum number of steps in which he can get 
  out of the maze.
  Note: Zucky can move only in horizontal and vertical direction.

  Input:
  The first line contains t, the number of test cases (1 ≤ t ≤ 5).
  The second line contanis two integers R, C (1 ≤ R, C ≤ 100)
  Then R lines follow. Every line contains C characters, which can be
  1) R, B, G, Y - doors,
  2) r, b, g, y - keys,
  3) # - wall,
  4) . - free space,
  5) * - start point,
  6) X - exit

  Output:
  Each line should contain number of steps required if a path exists and 
  "Trapped!" if there is no path.

  Example:

  Input:
  2
  1 10
  *...rRG..X

  2 5
  *gr##
  RG..X

  Output:
  Trapped!
  5

  Please note that there can be multiple exits, multiple keys/doors of the 
  same color, multiple walls, but only one start point. A key once collected 
  can be used to open as many number of doors.

Okay, now, how do we go about solving this?

Firstly, we notice that if we get rid of the RGBYrgby stuff, then all we have is a simple maze to solve (use a BFS on the implicit graph).
However, one can then notice that the coloured keys create nothing new, other than to multiply a factor of 2^4=16 to the number of states (i.e. for each key, whether it is picked up or not also needs to be added to the state). Noticing this, we have a very clear idea of how to implement a BFS on the implicit graph that is formed here. Each node in the graph is a state which contains row number, column number, and which keys have been picked up.

Putting all of this in a pair<pair<int,int>,pair<pair<bool,bool>,pair<bool,bool>>> might be fun to some, but to me, that's just taking it too far.
What I did instead is made a struct that stores the values and wrote hash, unhash functions in order to convert this struct to and from a long long. This makes it easier to use with STL map which I used to store which vertices were already visited.

Here's the state struct and hash,unhash functions:

  typedef long long ll;

  struct state {
    int row, col, r,g,b,y;
  };

  const ll MULT_BASE = 101;

  ll hash(const state &s) {
    ll ret = 0;
    ret *= MULT_BASE; ret += s.row;
    ret *= MULT_BASE; ret += s.col;
    ret *= MULT_BASE; ret += s.r;
    ret *= MULT_BASE; ret += s.g;
    ret *= MULT_BASE; ret += s.b;
    ret *= MULT_BASE; ret += s.y;
    return ret;
  }

  state unhash(ll h) {
    state ret;
    ret.y = h % MULT_BASE; h /= MULT_BASE;
    ret.b = h % MULT_BASE; h /= MULT_BASE;
    ret.g = h % MULT_BASE; h /= MULT_BASE;
    ret.r = h % MULT_BASE; h /= MULT_BASE;
    ret.col = h % MULT_BASE; h /= MULT_BASE;
    ret.row = h % MULT_BASE; h /= MULT_BASE;
    return ret;
  }

The maze itself is quite simply stored in a character array:

  char maze[101][101];
  int R, C;

Now, we have to figure out which states are accessible from where. Also, we want to update the new state if we end up picking up a key.

  bool should_move(const state &o, state &n) {
    if ( n.row < 0 || n.row >= R || n.col < 0 || n.col >= C )
      return false;
    char l = maze[n.row][n.col];
    if ( l == '.' || l == '*' || l == 'X' )
      return true;
    if ( l == '#' )
      return false;
    if ( l == 'r' )
      return (n.r=1,true);
    if ( l == 'g' )
      return (n.g=1,true);
    if ( l == 'b' )
      return (n.b=1,true);
    if ( l == 'y' )
      return (n.y=1,true);
    if ( l == 'R' )
      return (n.r>0);
    if ( l == 'G' )
      return (n.g>0);
    if ( l == 'B' )
      return (n.b>0);
    if ( l == 'Y' )
      return (n.y>0);
  }

Notice the code for picking up the keys. The syntax return (n.y=1,true); uses a very nice but underused feature of C/C++. The comma operator, used in an expression, executes the left side part, followed by the right side part and keeps the right side part for further evaluation. This basically makes the code do n.y=1; return true; but the code is much more cleaner using this comma notation since unnecessary curly braces are removed and also, the code has a smooth uniform look of returns based on conditions.

Now, we can just do a BFS starting from the first location. We exit out of the BFS the moment we find any exit; thus guaranteeing shortest path.

The BFS is implemented quite simply as follows:

  int bfs(int startrow, int startcol) {
  // returns -1 if not possible to exit 

    map<ll,int> dist;
    int ans = -1;
    state startstate;

    startstate.row = startrow; startstate.col = startcol;
    startstate.r = 0; startstate.g = 0;

    startstate.b = 0; startstate.y = 0;

    queue<pair<ll,int> > q;

    q.push(make_pair(hash(startstate),0));

    while (!q.empty()){
      ll curhash = q.front().first;
      state curstate = unhash(curhash), newstate;
      int curdist = q.front().second;
      q.pop();

      if ( dist.count(curhash) != 0 )
        continue;

      dist[curhash] = curdist;

      if ( maze[curstate.row][curstate.col] == 'X' ) {
        ans = curdist;
        break;
      }

      newstate = curstate; newstate.row += 1;
      if ( should_move(curstate,newstate) )
        q.push(make_pair(hash(newstate),curdist+1));

      newstate = curstate; newstate.row -= 1;
      if ( should_move(curstate,newstate) )
        q.push(make_pair(hash(newstate),curdist+1));

      newstate = curstate; newstate.col += 1;
      if ( should_move(curstate,newstate) )
        q.push(make_pair(hash(newstate),curdist+1));

      newstate = curstate; newstate.col -= 1;
      if ( should_move(curstate,newstate) )
        q.push(make_pair(hash(newstate),curdist+1));

    }

    return ans; 

 }

Let's take a look at what's happening in this (pretty long) code. We are keeping a list of distances to visited states in the dist map. As is done in a normal BFS, we push the first vertex into a queue and then start a loop. However, in this case, the distances matter, and so we put an integer tagged along with the state too which will store the distance (distance means number of steps needed to reach that state). As long as the queue is not empty, we keep taking off the front element and we put all its neighbours into the queue whenever the neighbours are accessible. As soon as we reach a final destination (exit) however, we break out of the loop and return out of the function.

All that remains now is to implement the necessary I/O routines and to call the right functions; and there it is - AC!!!

Any doubts/suggestions/criticisms? Please leave your comments below.

The Easiest Way Ever to Compare 2 Texts

Here's another reason to use Linux: You can use the beautiful terminal tool called wdiff (more useful when only certain words in a sentence may have changed, as opposed to whole sentences or code, in which case, diff is a better tool)

How do you use it? First, you'll have to install it (simple standard "
sudo apt-get install wdiff" is enough - HA! Let's see Windows install anything that easily!)

Then, just use this crazy little command whenever you need to compare two documents:

echo "Enter text1 (press Enter,Ctrl+D when done):"; cat > /tmp/1.txt; echo "Enter text2 (press Enter,Ctrl+D when done):"; cat > /tmp/2.txt; echo "Comparing..."; wdiff -n -w $'\033[1;31m' -x $'\033[0m' -y $'\033[1;32m' -z $'\033[0m' -s /tmp/1.txt /tmp/2.txt; rm /tmp/1.txt; rm /tmp/2.txt

Or, let's just make our lives easier and put all of that into a function (therefore, making it more nicely written and easier to understand too)

function 2compare {
  echo "Enter text1 (press Enter,Ctrl+D when done):"
  cat > /tmp/1.txt
  echo "Enter text2 (press Enter,Ctrl+D when done):"
  cat > /tmp/2.txt
  echo "Comparing..."
  wdiff -n -w $'\033[1;31m' -x $'\033[0m' -y $'\033[1;32m' -z $'\033[0m' -s /tmp/1.txt /tmp/2.txt
  rm /tmp/1.txt
  rm /tmp/2.txt
}
Now, all you have to do is call 2compare and you will be able to compare texts.

Well, let's break it down, shall we?

The echo parts just show useful messages on the screen.
The cat parts store the data taken as input into temporary locations /tmp/1.txt and /tmp/2.txt
The wdiff part is the scariest bit but is quite simple (as we shall see):

• -n is a short way of saying --avoid-wraps which means "do not extend fields through newlines"
• -w $'\033[1;31m' -x $'\033[0m' -y $'\033[1;32m' -z $'\033[0m' sets up colours to show the differences in a much more easy to see way. wdiff by default shows colourless output (and shows differences using brackets etc.)
• -s or --statistics causes wdiff to show how many words were added, deleted etc.
• /tmp/1.txt /tmp/2.txt just specifies the files to be compared

The rm parts remove the temporary files

But what if you don't want to keep rewriting that crazy long function each time you restart your terminal?
You can place it at the end of ~/.bashrc and then you'll be able to use 2compare directly from your terminal next time onwards.

This command is staying in my ~/.bashrc probably permanently from now on. Maybe I'll post some other useful stuff I have in there in later blog posts.

Do you know of any other ways of comparing files? Any new terminal tricks?
Leave your comments below.

Going Backwards

All the time, we are told to only keep going forwards - keep looking towards the bright future and to strive to achieve greater goals. How many times are we told that we sometimes need to move backwards?

Think about a scenario where you have to jump from one building to another - you'll never jump directly from the parapet; you'll definitely move a few steps backwards to be able to take a run up in order to make a successful long jump. This applies to real life as well (in a metaphorical sense, of course). Many a times, we really need to move backwards to reassess and rethink whatever we are doing in order to be able to do a whole lot better than before. These are times when we need to backtrack whatever we've been doing or working on and start afresh.

Backtracking is hard since it goes against the whole fiber of who we have been molded into by society itself. It is difficult to let go of whatever you've worked on for a helluva long time but sometimes, its just better to take a few steps back in order to be able to get a better run up and a better jump and just maybe reach a much greater goal and dream bigger.

What do you think about this metaphor? Leave your comments below.

Negabinary

Thought you knew all there is to know about number systems? Well, here's something new to that list - Negabinary numbers. These are numbers that are written to the base -2 (negative two). What's so great about these numbers? There is no need to put any + or - to denote whether it is a positive number or not. Let's check these numbers out.

The normal way a number is defined, works here as well. There are "b" number of digits in a number system of base "b". Here, we just have to change the definition to: there are "|b|" number of digits in a number system of base "b". The definition works perfectly after that. Then, we can just use the following equation:

Using this we can thus generate the first few numbers (0, 1, 2, 3, 4, 5...) in negabinary: 0, 1, 110, 111, 100, 101... (Sequence A039724 on Online Encyclopedia of Integer Sequences (OEIS)) where 0 and 1 have usual face values.

How do we convert a number to this base then? Write the number down in binary first. Then, going from right to left, at every odd place (i.e. x₁, x₃, x₅ ...), if the bit is one, propagate a carry to the next bit. Also, while moving from right to left, add all the carries.

For example:

To convert 15 to negabinary:

1. Convert 15 to binary
• 15_decimal=1111_binary
2. Propagate from right to left
• 1111
• 1111
• 1211
• 2011
• 2011
• 10011
• 10011
• 10011_negabinary
3. Done! (This is correct since 16-0+0-2+1 = 15)

Conversion to decimal (or any other base) just uses the original formula.

Addition is kinda done the way conversion is done, except that carries are propagated (one bit extra to the left, since 2_negabinary = 110).

We can similarly define the other operations as well.

Let's take this onto another level itself: how about a number system that takes care of complex numbers as well (as digit strings)? I leave that upto you to figure out and comment about.

Reaching the network's speed limit for file transfer

Are you tired of transferring files from one computer to another using pen-drives and their abysmally slow speeds? Ever long for something faster? Here's a nice way to transfer files insanely fast - as fast as the network would allow (Note: This is another cool reason to switch to Linux)

Here's what you do:

Let's say you want to send a folder called ABC from computer X to computer Y. Then, fire up terminal on computer Y first and type the following commands:

hostname -I 

nc -l 9898 | tar xv

"hostname -I" shows all IP addresses associated with the host Y. You'll need to note these down to be used on computer X. "nc" is a utility that allows for arbitrary TCP and UDP connections and listens. "-l 9898" is a flag for nc to open port 9898 and listen for connections. The "|" pipes the output of nc (i.e. whatever comes from the network) into the next command "tar" which is an archival utility. The "xv" part stands for extract verbose which means that the archive coming from nc is extracted and each file name is printed out as it is extracted.

Once you're done running the above command on Y, run the following command on X:

tar c ABC | nc IP 9898

The "tar c" part stands for "use tar to compress" ABC (the folder to be sent). IP is the IP address got from the "hostname -I" command on computer Y. "nc IP 9898" connects to computer Y on port 9898 and sends the data from the tar command to the other computer.

Since no extra data is transferred in this way, the data should be transferred at the maximum (theoretical) limit of your network. If your network is unstable, this might actually cause a problem since no error correction codes are sent; however, if your network is stable (or all you are sending is movies or the like) then it shouldn't matter much.

Do you know of any other fast ways to transfer data on the network? Leave a comment below. :)

Shellshock

A newly discovered bug seems to be taking the whole security and hacker communities into uproar. A huge number of posts and talks are going on in many channels. For those who haven't heard about it, it is the bash bug which affects basically almost all systems that the world depends on.

What is the bash bug? To answer that, first you need to know what bash is.

"bash" stands for "Bourne-Again SHell" and is the most common type of shell on any linux or mac or unix related system. This basically includes almost all servers, and can go on all the way to smart lighting (those crazy lightbulbs whose colour can be controlled by your smart phone). If you've ever seen anyone use a black screen with white text on it, chances are you've seen either the Windows Command Prompt or a shell. A shell basically allows you to type commands to execute programs on a computer.

The bash bug is basically a bug that has been found in this very commonly used shell. The bug was discovered by Stéphane Chazelas, a French IT manager working for a software maker in Scotland, and was first disclosed on 24th September 2014. It basically allows for arbitrary code execution. Turns out that this bug has existed since the very first version of bash (25 years ago!!!). The bug has been nicknamed "Shellshock" and is regarded to be severe since CGI scripts using bash can be vulnerable. It is caused due to

However, this is where the open source community comes into play. Within a very short time frame, a patch has been released already and many systems are no longer vulnerable to this bug. As of now, my system is no longer vulnerable only because I continuously keep updating my PC.

How to test if you're vulnerable?
Just run the following code in your terminal:

env x='() { :;}; echo vulnerable' bash -c "echo this is a test"

If your system is vulnerable, it'll tell you vulnerable, otherwise it will show an error message.

If you want to know more, visit the Wikipedia page on the bug at Shellshock

Just to mention this here: This is the only severe bug I've personally seen on linux that has such a massive impact, and even then, it got fixed almost instantly. I love the way the open source community works so quickly. :)