Using BFS to solve the minimum number moves problems

Often in various programming contests we find problems related to calculating minimum moves for some toy problems like "8-puzzle problem", where the step cost to move a block from 1 location to other is constant for every move (or analogous). Generally such problems can be tackled by BFS (it means Breadth First Search, for my friends who didn't know earlier) technique. Well, the concept is pretty simple for BFS. it refers to traversing a tree level wise, i.e. first level 0, then level 1, then 2, 3...
Eg.
1
/ \
2 3
/ \ / \
4 5 6 7
For a tree like the above, a BFS traversal guarantees the traversal order: 1->2->3->4->5->6->7
Though in a linked implementation of a tree, the BFS traversal is a bit trickier but for an array representation this is nothing but a straight traversal of the array sequentially.
Since in most of the programming problems, generally the tree is not known at the beginning, therefore the limit of the total number of nodes is uncertain. But, theres nothing to worry much, for the ArrayList in Java and vector classe in C++ are the way out. Well a generalized BFS traversal may look something like this, when the code to remove the repeated states is added to the main BFS logic:
(Note: its just a pseudo code)

fringe= a queue
closed= a set containing visited nodes
fringe.push(root_node_of_tree);
while( ! fringe.empty())
{
node n=fringe.pop();
if(goalTest(n)){
return solution(n);
}
if(!closed.contains(n)){
closed.add(n);
//add all children of n to fringe
}
}

Based on this below is my C++ implementation for finding out the minimum move sequence to solve the 8-puzzle problem. In this problem given a 3*3 matrix with numbers 1..8 filled in random 8 places among 9 in the matrix with 1 block empty. Our goal is to slide a block at a time in the empty place and finally arrange the puzzle back to sorted order, just like this
1 2 3
4 5 6
7 8 0
(Note: 0 indicates the empty block)

Here is my complete C++ implementation

Donate water

Dealing with a Strange Java Problem

Here is a strange problem encountered by me while experimenting with Java. Have a look at the following code sample:

interface test {

void fun();
}

public class Test implements test {

public void fun() {
System.out.println("Test.fun() called");
}

public static void main(String[] args) {
new Test().fun();
}
}



Can you find any problem with the above code sample? Well there really isn't any problem with the above code. Still when you try to run this on Windows systems the execution fails for Test class ( i.e. >java Test) throwing exceptions like:-

java.lang.NoClassDefFoundError: test (wrong name: Test)
at java.lang.ClassLoader.defineClass1(Native Method)
at java.security.AccessController.doPrivileged(Native Method)
at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:276)
at java.lang.ClassLoader.defineClass1(Native Method)
at java.security.AccessController.doPrivileged(Native Method)
at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:276)
Exception in thread "main"
Exception in thread "main" Java Result: 1


And adding to the surprise, this program runs absolutely fine on Linux and other Unix based systems!

Ok so lets try to dissect the program and figure out what the problem is with this. Here is the possible explaination which I came up with.
Observing it a little carefully you can observe that the name of the interface is 'test' and class is 'Test' this makes them differ only in case. But what difference does it make to us? java is of course case sensitive, so we are free to chose names like that!
Well the answer is that, although java is case sensitive the underlying OS ( Windows) is not. Therefore the compiler (even though it wanted) couldn't create two separate .class files (one for interface, and other for the implementing class), because the other class file over-writes the previous one. In short, this problem arises because after compiling the above code, two class files: test.class and Test.class map only to a single file on windows, not two unlike the unix systems.
So be careful while getting trapped in such of hard-to-find bugs!

Getting started with GNOME based OS (Linux)

Here is My Linux (Ubuntu9.04) Desktop's screenshot, to prove that theres nothing now which cannot be achieved in the world of Open-source. Linux now is no more limited to the community of computer geeks, but its increasingly becoming extremely user friendly proving it much suitable for the beginners as well. The time is gone when one needed to type long and cryptic commands in order to do anything they want on Linux & Unix systems. Though the command line alternatives are always there, leaving an entire world for the user to explore and learn! Everything is now offered in much more interactive and highly customizable GUI.
Thats the beauty of open-source- it can give you exactly what you want. Open-source products including Linux opens itself to change by anyone who uses it thereby giving the freedom and power to users. There are multiple Window Managers available for using with Linux. The most commonly used are -GNOME and KDE which generally comes integrated with most of the linux distributions.

Lets begin with our familiarisation with GNOME, Ubuntu9.04 Desktop ( but this might help you in other distros as well)
It displays a menu bar at the top containing menus for Application, Places and System on the left side of the bar along with the tray icons of the processes and a calendar, sound control and the Username being on the right side of the bar.
And a status bar at the bottom of the screen with the icon to Show the empty desktop minimizing all the currently opened windows, tabs of all the currently opened windows, a Desktop Switcher showing the available desktops and finally a Trash (where the deleted files reside giving option to restore back the accidently deleted files, until manually cleaned).

• Application Menu: It contains Set of the applications installed and currently configured to be displayed in the menu format in different categories. It comes packed with a range of open-source applications preinstalled, like firefox for web browsing, Evolution as the email client, Pidgin as the chatting messenger, Totem and Rythmboxfor audio/video playing, GIMP ( my favourite!) for Image editing and a set of GNOME games!
• Places Menu: It presents links to some of the predefined locations so as to reach there quickly.
• System Menu: It presents the system specific tasks and configurations

Application and System menu can be manually altered by right clicking-> Edit Menu option.

Any system related information about the running processes or the present system memory and network usage etc. can be found anytime in System->Administration->System Monitor.

Ubuntu presents with an exhaustive list of open-source software for anyone to download from anywhere in the world from its central repository. This can be done in either of the following ways:

• Applications->Add/Remove
• System->Administration->Synaptic Package Manager
• using command line utilities like apt-get :
• sudo apt-get install

Some of the other utilities in which you would be interested to install are:

• Opera (a web browser)
• Netbeans IDE ( for programming in JavaSE, JavaME, JavaEE, C, C++, Javascript etc )
• openssh ( for enabling remote login into the machine)
• Thunderbird ( another email client like Evolution)
• Avant Window Navigator ( enables a cool looking, highly customizable docking feature much like MAC )
• GVIM text editor ( a GUI based vim text editor, for the people who are addicted to the cool and simple, our beloved VIM ! )
  

Happy Linuxing!

Mother Nature

Here are the lines written by a 15 year school girl. It indeed reminds us of our long forgotten nature and provokes us to again ponder on our actions.

Mother Nature

The lap of soothing comforts for all
With selfless care for all
Where all worries vanish, with no blemish,
Where the delicate colours of the rainbow,
Stretch themselves in the sky,
Birds sing, high and higher they fly.
Trees bear sweet fruits of affection,
Rivers linger through cresses with anticipation
This, nature through its humble phase,
confers on man a graceful place.
Man today in his passionate greed,
cutting down trees without need,
The smoke looming high from chimneys,
Toxicants thrown into rivers by industries.
Exploring, exploiting, denuding, eroding...
Man is gradually destroying his own living.
Benumbing, choking the Mother Nature.
Forgetting all her cares and nurture.
Tomorrow someone will surely ask:
Who is Mother Nature?
The barren lands with no life?
Or the carcasses of early extinct animals?
Is it???
So, can't we be kinder to nature,
for all her care and nurture?
can't we strive today,
So that never comes this tomorrow.
So that Mother Nature never cease to grow.
Can't We???

--Anjali Sharma
( fortunately, who is my beloved sis )

GIMP (the GNU Image Manipulation Program) my favourite Open-Source Image Editor

This tutorial is meant to remove fears from the hearts of people who fear working on open-source tools. GIMP is an open-source Image manipulation tool used exhaustively, but not that much common with the students especially here at my college. It has an exhaustive set of tools to match any of your image editing needs, with and extremely intuitive interface and very easy to learn.

So lets get started. Here I present my first tutorial for building a cool name template with shiny table effect as shown below, to let them know how easy it is to work with GIMP for common requirements of students.

Here are the easy steps to create one-

1. Install and start GIMP editor in your favourite operating system. This is fairly easy in case of OpenSolaris and Linux flavours like Ubuntu, Fedora etc.

2. File -> New -> Choose desired size ( default 640*400 works fine for me ), and click OK
Now a white background is visible in the Image window.


3. Select Blend Tool and Gradient as FG to BG. Then keeping the CTRL key pressed drag a line from top to bottom on the image and you shall find something like this -->





4. Select the Text tool from Toolbar or press 'T' key shortcut. and drag a bounding rectangle on the image at the position you want to place the text. This will open a text box popup, type in the desired text here ( "I LOVE OPEN-SOURCE" in my case ). Check the "Use selected Font" option and select the desired font type ( Sans Bold in my case), size( 37 px in my case) and color ( Red in my case) from the drop down menu. This will create a new layer ( say Layer1 ), which will be listed in the Layers window and It will look like this now-->




5. Right click on the newly created layer with the name same as your text and select Duplicate Layer . This creates a duplicated layer ( say Layer2). Now with the original layer, Layer1 selected, go to
Filters -> Blur -> Gaussian Blur -> Select horizontal and vertical blur radius as anything between 12 px - 20px each. and click OK

6. Select Layer2 and choose Color as Green from the color chooser.



7. Select Filters-> Distorts -> Emboss -> select funtion as Emboss and Azimuth, Elevation and Depth to any suitable value ( 30, 45, 20 respectively in my case)
now this will look something like this->





8. Select Layer2 -> right click on it -> Duplicate Layer. This creates another duplicate layer of it ( say Layer3).

9. Now Select Layer3 -> Tools menu -> Transform Tools -> Flip Tool -> Select Flip type as Vertical and click on the text. This is invert the image.
Select the Move tool from the toolbar and position the vertically flipped text few pixels below the original text. It will look like this now--->






10. Select Layer3 -> right click on it -> Add Layer Mask -> select Transfer Layer's Alpha Channel -> click Add

11. Select Layer3 and then select Blend tool from the tool bar with Gradient as FG to transparent and using CTRL key draw a straight line from bottom to top anywhere in the image. This is make the reflection text only partially visible, like this->





12. Finally right click Layer3 -> Apply Layer Mask. This finishes our steps and we finally get the desired text, kept on a shiny table, and glowing in red light. Crop the image to remove unwanted space and thats all!

Hope you enjoyed the tutorial! Experiment and learn...

Yet another tremor shook the souls at Bhubaneswar.

Well it was around 2 o' clock night with most of the people deep in their sleep at KP3 hostel, when we were hit by yet another earth quake. Though it was mild here, but strong enough to shake awake few of my sleeping friends. I noticed about this major piece of action going on here, when two of my friends shook me with their full strength ( I guess it was no less than 10-12 on Richter scale ;) , which struck me when I was peacefully asleep ) , still not strong enough to make my nerves active. It took me another 10 minutes to realise what had happened. I could hear students shouting and yelling ( But this is not new to our hostel. We have full freedom of expression here :) ). But as the case with me, majority of us got to know about the event from the fellow mates, only after it was gone ( just like Indian Police! ). But whatever the case may be, this event triggered many hot talks and fuming discussions here among boys. I could listen to few words which popped up every now and then like -'earth-quake','tsunami' ( what ? TSUNAMI !!! I really am scared of it.. Can I make a boat out of my study table? or using bed would be better idea? :) )
These increasing terrorist activities, bomb blasts every now and then, and now earth-quakes, tsunami, drastic weather changes, global warming, pollution, Swine Flu! are they not signals by mother nature indicating something? It sounds like a threat to me. We all shall be wiped off from the crust if we continued our greedy actions..
But at such hard times, one deeply feels the need of the loved ones to stay next to us. It makes one realise the true worth of relationships.