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.