How to Start Competitive Programming

If you've ever thought about competitive coding, all you've got to do is start now. Doesn't matter which class or branch you are in. Everyone can code and everyone can be competitive. Basically, all you've got to have is the right mindset and the right skill set.

Let's talk about the mindset first. Competitive programming requires a drastically different mindset when compared to "normal" (or developmental) programming. While in developmental programming you have to concentrate on writing quality code that is manageable, competitive programming generally involves writing code that "just works". This is because you'll probably never even look at your code again, once you get an AC (accepted) result from the grader. This does not mean that you should write sloppy code since that would just make it hard to debug (and this can be a real pain in the a** in a competitive setting, with the added pressure of time running out). All it means is that the code need not have extensive documentation (just some inter-spread comments to help out when debugging are enough) or modularity/objects/classes (just write it in logically separate functions to make life easier).

What about the skill set? Basically, the only requirement is that you should be able to write in the language that the grader accepts without having to look at the documentation for the basics. Since almost all graders support C++ (I haven't found any that don't, except in some "special language contests" etc), and C++ has a massively powerful library called STL (standard template library), C++ is the natural choice for most competitive coders. However, if Java is your mother tongue, a fairly large number of graders accept this as well, but do note that Java is known to be slightly slower and more cumbersome to write in a pressured setting. Java does have one major advantage over C++ and this lies in its BigInteger library. However, this is so rarely used that it isn't worth the hassle of doing everything in Java just for this. Most coders use C++ for everything except for when the question requires large integers (larger than 10^18 or so).

I've put together a small set of FAQs below and this should help. If you do have any more questions, do ask in the comments below.

Q: Which language should I use?
A: C++ (Read above for why)

Q: How should I learn C++?
A: The tutorials on cplusplus.com are extremely useful (http://www.cplusplus.com/doc/tutorial/). Not to mention, their documentation is in depth and is useful later on also, when learning things like STL.

Q: Any specifics of the language that are more useful?
A: C++ is a very powerful language with a gazillion features (and more added with C++11), but a whole large chunk of them are not necessary whatsoever for competitive programming. Basically, you should be comfortable with variable types, I/O (using cin, cout - there are faster ways but those are usually not necessary unless a 0.001 second improvement is the only thing that's causing a TLE - usually, the algorithm can be improved instead), control statements (if, ?: operator), looping (for and while, break and continue), functions (call by reference and call by value), arrays, strings (as character arrays), struct. Once you're comfortable with these, learn how to use basics of STL (vector, sort() are most useful). Pointers and dynamic memory is usually a larger headache than anything in the pressures of a contest. See a further question for more. Also, classes and objects will usually not be used since your code usually depends heavily on algorithms and does not usually break down into a object-oriented way.

Q: What do I do for unknown sizes of memory? Is int x[n]; OK? Can I use pointers for this (using int *x = new int[n];)?
A: NO!!! int x[n]; is NOT OK. Arrays need to have a compile time constant size. n is not a constant at compile time. Pointers and dynamic memory is too much of a headache. Just declare an array that is of the size that is max allowed (based on question). If question says n is less than 10^6, then just declare int x[1000010];. The extra 10 is just to be safe :P. Oh, and put large arrays in global scope (declare outside the function) so that it doesn't cause stack overflow problems (can cause SIGSEGV on graders). And don't forget to initialize them using loops whenever necessary. If you really need a truly dynamic sized array, don't use pointers, use std::vector (http://www.cplusplus.com/reference/vector/vector/).

Q: Where do I learn algorithms from?
A: Best place I've found is the MIT OpenCoursware. It is a BTech level course (but usually understandable by most Indian school students too). Link: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/

Q: What if I prefer books instead of videos?
A: You might've heard of the book we fondly call "murder-weapon" due to it's size. CLRS (Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein) is like the bible of algorithms. If you have the guts to read this huge book, by all means, please do. However, if you want something smaller and more manageable, try the book by Skiena (The Algorithm Design Manual).

Q: Which sites should I practice on?
A: SPOJ has the largest collection of problems. CodeChef has a very nice classification of Easy, Medium, Hard problems. UVa has a large number of problems suitable for ICPC training. CodeForces holds extremely regular contests (and editorials are also regular). TopCoder has regular SRMs but has a very messy arena applet that you have to get used to (but tutorials on TopCoder are great). HackerRank has a nice set of problems divided by difficulty and topic. Finally, it is up to you. I currently use UVa and CodeForces the most, but would suggest CodeChef for beginners due to its classification.

Q: What to do if I get a TLE (Time Limit Exceeded)?
A: Usually your algorithm might not be good enough. Check if the number of elemental operations (like single element access or write or operation etc) totally stays bounded by 10^6 or 10^7. If so, it should run within a second. Otherwise, you're in trouble. Even an algorithm that takes 10^8 operations would be too slow. For example, on an array of size 10^5, a sort using bubble sort (requiring quadratic time) is too slow, but merge sort (requiring N log N time) runs within a second.

Q: What to do if I get a MLE (Memory Limit Exceeded)?
A: You really need to cut down on what memory you are using. Reuse memory space if possible. Usually this verdict from a grader is very very rare. I've got it only once or twice totally in my whole experience until now, and it was fixed by rethinking the usage of memory. A million sized array if integers takes up 4 MB of space, and million 'long long's take up 8 MB space, so this is usually not a problem at all.

Q: What to do if I get a WA (Wrong Answer)?
A: Check if you are missing any \n while outputting your answer. This is a common mistake that might happen even if code and algo is correct otherwise. If that isn't the problem, try running the algo on paper and see that it matches for all cases you can throw at it. If it still works, you haven't tried some corner cases (n=0,1, or very very large). Also, are you sure you are using the right data type? int stores max of ~10^9, long long stores ~10^18. Use it instead. Remember, intermediate calculations also should fit within the limit. If all else fails, try rethinking the algorithm.

Q: I cannot figure out the algorithm. What should I do?
A: If this is in a contest, there is usually not much you can do other than just think or move onto another question. However, if this is when practicing, try working out the example on paper first to make sure you've understood the question. If nothing yet, don't give up (or check online yet). Mentally take note of the question and go on with other work. The answer will strike at the most random time (in the shower for instance). If you still get nothing (after a few days/weeks/months depending on difficulty of question), search for an editorial for the question, or ask someone who's solved it. If it involves a new concept, learn it (don't just copy code without understanding). If it did not require anything new, then re learn whatever was needed. After that, try coding it in and getting an AC. Search for related concepts and questions and solve them.

Q: I know the algo, but cannot code it in. What should I do?
A: Isn't this obvious? Relearn the topics needed.

Q: Can you see my code for problem XXX from site YYY?
A: Nope. I do not have the time to do this individually. Also, competitive code is usually hard to read and difficult to find mistakes in. I usually cannot understand my own (competitive) code after a few days (developmental code is understandable even after years however, since it is written that way). You're on your own. However, if you write the algo in simple English (or pseudo code) then it might help for you to figure out what is wrong by yourself. Also online forums exist just for this. If nothing else, if you can find me a great question, I might just write an editorial on it (see example here).

Q: My question is not in this FAQ.
A: Write it in the comments below.

1000 Week Mark

Turns out, I was born exactly 1000 weeks before today. Next such round number happens in 2018 when I'd have lived for 200,000 hours on this hunk of rock that we call Earth. All this cool calculation is done very nicely using the Special Age Calculator on the website timeanddate.com.

Debugging code in a competitive setting, Part 1

Writing code in a competitive setting is an especially tiring and frustrating task, for a multitude of reasons. The rush of wanting to code fast prevents one from applying good coding standards and leads to trivial errors. Also, there is no time to set up a testing framework etc. How do you prevent (or at least find and correct) any errors in the code you write?

What I personally do is to use a combination of gdb and a custom debug message function.

The first part of this series of posts will explain the function

First, I always put the following code at the start of my programs:

#ifdef DEBUGIT
  #define DEBUG(X) cerr << ">>> DEBUG(" << __LINE__ << ") " << #X << " = " << X << endl
#else
  #define DEBUG(X) (void)0
#endif

Now, whenever there is a need to check the value of a variable (or expression), all that is left to be done is to call the DEBUG() function like so:

DEBUG(x); // debugging variable x
DEBUG((a<<3)+2); // debugging an expression

The way that the "function" (or macro, to be precise) is defined, whenever DEBUGIT is defined at compilation, debug statements are shown, and otherwise, they are just skipped.

Hence, whenever you want to look at the debug statements, use g++ -DDEBUGIT to compile instead of just g++.

Here's an example program and its output:

#include <iostream>

using namespace std;

#ifdef DEBUGIT
  #define DEBUG(X) cerr << ">>> DEBUG(" << __LINE__ << ") " << #X << " = " << X << endl
#else
  #define DEBUG(X) (void)0
#endif

int main() {
  int x = 5, y = 10;
  DEBUG(x);
  DEBUG(y);
  ++x += y++;
  DEBUG(y+1);
  cout << x << endl;
}

Output:

>>> DEBUG(13) x = 5
>>> DEBUG(14) y = 10
>>> DEBUG(16) y+1 = 12
16

The advantage with the DEBUGIT technique is that you can directly submit code (without any modifications) and the grader will not run the DEBUG statements at all.

I have added the following line to my .bashrc file:

alias d++='g++ -DDEBUGIT'

Hence, I can directly run d++ for compiling with the debug statements.

In my next post, I will explain how to use gdb to further make life easier.

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. :)

Dreams - A connection to a different time

Dr. A. P. J. Abdul Kalam once said "You have to dream before your dreams can come true." This started to make me think, what if it is not just applicable to thinking big and achieving what you want? What if just normal dreams too work this way? Think about it, has it not happened that you are in some place and you just realize that it all had happened in a dream before? Kind of like déjà vu but not quite the same.

Déjà vu, is the experience of thinking that a new situation has occurred before. I am not talking about this but am talking about the phenomenon where we know we’ve been through the same situation in a dream.

It is common to dream about the past and relive some of the emotional moments that we’ve had until now, but is there any sense in thinking about dreaming about the future? Do we really dream about what will happen in a day or week or year and does it really happen?

We all know that when we’re in a dream, we do not really know that we’re in that dream. It is thus quite possible that we’re thinking that we’ve already been in a place in a dream when we’re in a dream. But all this becomes too much like inception (the movie, of course). Let’s just stay away from the dream inside a dream inside a dream thing.

If we look at what is happening objectively, there are plenty of reasons why we may come across this phenomenon. One possible explanation is that we may just be thinking that we’ve been there in a dream whilst never having such a dream ever before. This is quite possible since our brains are quite unreliable in terms of memories, especially when it comes to dreams. It is quite well known that we cannot remember clearly what we dreamt about even just after waking up. We may just remember pieces of it and this too is fast fading. Is it not possible then, that the mind, when in some situations, can trigger partial recall and patch up pieces from different unrelated dreams into a dream coherent with the current reality?

This’d then mean that the phenomenon would just be a post hoc thing that the brain does and that predicting the future is not really possible.

However, consider the following scenario. You are late for work, and you know the boss is going to scream at you. It is no surprise then that s/he screams at you for being late. Your mind “predicted” the future. Is it not possible that the mind, in dreams, is doing something similar? It is known that the mind has quite a high amount of activity even when we sleep and this increases significantly during dreams. We can say that when awake, our conscious mind is in power, but when dreaming, it’s the unconscious.

The unconscious mind may, in fact, have the ability to think rationally when the conscious mind cannot. It thus may be able to piece together clues that the conscious mind may be ignorant of or may be ignoring and might be able to construct possible case scenarios. Showing the scenarios in dreams may be a way of the brain letting us prepare for what’s about to come. When we realize that a certain situation occurred in a dream, we may even realize what we did in the dream and be able to take the same course of action, if it was helpful, or take a different action if otherwise.

A third possibility exists, however. That the “real world” is affected in a much more powerful way by dreams. A dream may have the capacity to affect real world decisions to such an extent that we may not really have any free will. We may be forced to take decisions that’ll eventually lead us to fulfilling those dreams. A scary thought to those who have nightmares! Lazy people, however, would like this scenario since it’d mean that they’d just have to dream big to achieve big.

We may never know the true nature of dreams and whether they present windows to the future or affect it. However, we know that dreams present windows to another world that is sometimes filled with possibilities that may not be possible in reality.

Dreams are and continue to remain a fascinating, captivating, mesmerising and enchanting way to see the countless possibilities that exist in our universe and any others beyond. They continue to be a source of endless debates and a source of creative ideas for both art and the sciences. Just ask Kekulé who figured out that benzene must have a cyclic ring structure by dreaming of a snake biting its own tail!

The Square Root of Three by Dave Feinberg

I fear that I will always be
A lonely number like root three

A three is all that's good and right
Why must my three keep out of sight
Beneath a vicious square-root sign?
I wish instead I were a nine

For nine could thwart this evil trick
With just some quick arithmetic

I know I'll never see the sun
As one point seven three two one

Such is my reality
A sad irrationality

When, hark, just what is this I see?
Another square root of a three

Has quietly come waltzing by
Together now we multiply
To form a number we prefer
Rejoicing as an integer

We break free from our mortal bonds
And with a wave of magic wands

Our square-root signs become unglued
And love for me has been renewed

-- Dave Feinberg

Good vs. Bad

Whenever we do a good deed, we feel a sense of accomplishment or happiness. In the pursuit of chasing happiness, we try to maximise the number of good deeds we do and minimize the number of bad deeds. Not only religion, but the personal sense of satisfaction of doing a good thing is what drives most to do good things. But is this just an illusion? A façade? Many find pleasure in doing things that would be considered “wrong” by a common person. What makes psychopaths, murderers, rapists and general criminals do what they do? In which way are they different?

There seems to be a general belief that these kinds of people have their brains probably “wired wrong”. But then, why is it this way? Many theories suggest that the notion of good and bad/evil stems from beliefs and values that get ingrained and learnt since childhood or even infancy. A child learns from his/her parents that hurting someone else or breaking things is bad. As the child grows up, society (in the form of teachers and elders) teach the child that one needs to do “good things”. In a religious family, the concept of “heaven and hell” or something similar to that.

Over time, the child develops a very strong sense of right and wrong and this becomes so ingrained into the sub consciousness of the child that the brain starts to release the pleasure/happiness chemicals whenever doing something “good”.

However, what if the society/parents did not teach the child what is good or bad? Or what if the child had a traumatic experience that shocked the brain into perceiving the world different from normal? Turns out, a majority of psychopaths, murderers etc. seem to have undergone at least one such experience in their early childhood. Some of them are orphans, had abusive parents, or had a neighbourhood in which many “wrong” things were considered normal, such as selling drugs, carrying firearms etc.

Living in such a world, the child quickly tends to form a very protective shell around oneself and the only things considered “good” are ones which are to the direct benefit to the child or lead to its survival. No wonder, their consciences with respect to harming others are unaffected by doing anything.

This makes one wonder, do we feel emotions only because we have been told since infancy that we should? Is it actually a forced feature of the human mind?

Dexter, from the TV Series named after him, cannot feel emotions unless he kills. By the code of Harry, he only kills criminals who have escaped the justice system. The reason for this is because of an extremely traumatic incident that occurred even before he could remember anything. Acting like he can feel emotions is the only way he can survive in this world.

But what if all of us are only acting out emotions? What if none of us really feel anything but “feel” emotions only as a result of our subconscious remembering what is good or bad? These remain questions to be pondered about for a long time.

Life after Death

Till recent times, scientists have believed that there is no way to know what happens after death, and that after-life, even if it exists, could not be proven. In the recent past however, there has been an increase in the number of ways in which people have started to think about this pretty common question, “What happens once we die?”

Most religion profess of some form or the other of “heaven” and “hell”, and many religions profess of rebirth. While not much can be said, scientifically, of the heaven and hell theory, many scientists now believe that rebirth may not be a farfetched idea. In a universe which is truly infinite, anything that can happen, must happen at some point of time or another. If we assume consciousness to be a manifestation of the physical arrangement of atoms and molecules, then at some other point of time (maybe in the very distant future or past), the atoms of your body which have split apart after your death, come together in a very similar form leading to you becoming conscious again. Since in the time that you’re “dead”, you have no notion of time, when you’d just die and wake up in a similar world (which could be different in a very important aspect such as whether dinosaurs are still living or as negligible as what you had for breakfast in the morning).

A similar theory, however, assumes that the universe may as well be finite, but that any “choice” or “decision” taken (even in the quantum physical sense of the word) may lead to a split of the universe into a parallel one. Hence, if you die in “this” universe, you’d be alive in an infinite number of other universes. Since we only are conscious when we are alive, we never will experience death. We tend to continue in whichever universe we live in. (Though this’d mean that we’d never lose in Russian roulette)

Sci-fi fans, however, propose that life is merely a simulation being done by a more technologically advanced civilization. That civilization too may itself be virtual, hence, we may actually be a simulation in a simulation in a simulation (and so on). This was formalized and brought to the attention of the scientific community by Nick Bostrom in 2003, with a paper titled 'Are You Living in a Computer Simulation?'

Atheists, on the other hand, believe in the theory of “nothingness” which says that consciousness passes back into the oblivion that existed before birth.

Personally, I like the persistent illusion theory that Einstein supported. It says that linearity of time is but a mere persistent illusion; that past, present and future are merely states of the mind. If a person died before me in this world, it’s only my illusion of time that tells me this. Reality may be very different.

Which one of these theories are true? We probably will never know, but we may even probably never need to know. With advances in science and medicine, it may be possible to stop or even reverse aging. Fatal wounds or infections could be remedied instantly. In such a world, “death” may just become folklore or a myth. Will this happen in our lifetime? And what kind of consequences will this have? We do not know yet, but the answers to these sure will lead to many interesting new breakthroughs.