Tuesday, June 29, 2004

Re: The C++ Source (C++ future)

Frankly, I can see why managed code is becoming such an ally to developers, but I think the most important thing to consider is the fact that there are millions and millions of lines of code in C++ already, where does that go?

As far as I can tell, I do see an eventual shift from C++ to managed code, but call me old fashioned I just love C++. But I, like most other people, want to do things in better ways than possible now, so the only question to answer is whether managed code will be better (now or in the near future), once that happens, no one's going to just want to stick to C++ because of tradition or because I love it.

As long as it proves to be a worthy successor, Managed Code is going to pave the new paths. But this will take time and no, I don't see C++ completely phasing out in the immediate future.

They are actually reconsidering the C++ Standard and I think in the next update the Boost library will be included, lets see how far they go to actually "compete" with the others (Java et al), if at all.

Dinesh.

Re The C++ Source (C++ future)

I know this question has been debated many many times before, but what do you feel about the future of C++? With the emergence of managed code in the form of Java and .NET, where productivity is noticably higher, do you think C++ is falling behind for desktop application development? This is it's forte, but is it still relevant? I doubt anyone uses it anymore for web applications. Atleast on Windows, Microsoft seems to be giving less attention to MFC and is encouranging all developers to move to .NET. You already have Java in the Unix world.

What makes this debate interesting is our varying background. Mohnish and I do have a managed code bias so it is very important to know what Dinesh and Hrishi feel.

Personally I feel managed code will be adopted even more in the future and at a later stage C++ will loose its hold on desktop applications. This will happen sooner in Windows especially after Longhorn. On linux this should take much more time, simply because of mistrust of Java, Sun.

Another question is much on dev on Win will be done using Java? Java 5.0 (formerly Java 1.5) is now in beta and has many new features and enhancements as shown here. Speed is claimed to have been increased drastically. More importantly "Many areas of the rich desktop client have been enhanced including an updated, more modern, cross-platform look and feel." So the ugly and slow java apps might be a bit less uglier and more faster. I cannot claim that Java will hurt .NET on Windows, but as Mohn pointed out, Java is being taught in lots of universities. Those guys might become comfortable with Java. So as we all are resilient to change, some dev on Windows might be done in Java. Also a lot of API's are being added to Java which will make it an alternative to .NET. Otherwise I suppose most C++ devs like Dinesh will jump on to .NET unless they really need platform independence which for desktop apps doesn't seem to be the biggest driver.

Ps: have yu guys seen maestro? The Nasa space rover simulation app.

Monday, June 28, 2004

Re: Tales from the server side

Those were some good 'enterprise' jokes.

Especially liked EJB persistence and The conspiracy.

Framework Lock-In occurs in the Java world when 'other's make API's for something lacking in the general Java API. There are also instances of API's being created which compete with standard Java API's.

Does such a situation ever occur in .NET?

Security: The root of the problem

A very nice article on software security issues over at Queue magazine.

This again leads to my previous post regarding the relevance of C++ as we move forward. One of the reasons most Universites (atleast in the US) are moving to Java, is that you are by default sheilded from memory management, which is the root of most security problems. There is a benefit from having a safety net below you. The less expected of the programmer, the better :-)

The C++ Source

Artima has started a site devoted to c++ entitled The C++ Source. Here's an intro. All the big guns seem to be in on it - Check out the advisory board.

I know this question has been debated many many times before, but what do you feel about the future of C++? With the emergence of managed code in the form of Java and .NET, where productivity is noticably higher, do you think C++ is falling behind for desktop application development? This is it's forte, but is it still relevant? I doubt anyone uses it anymore for web applications. Atleast on Windows, Microsoft seems to be giving less attention to MFC and is encouranging all developers to move to .NET. You already have Java in the Unix world.

Tales from the server side

Been a while since we've had some activity here. Time we get it going again.

http://www.theserverside.com/cartoons/TalesFromTheServerSide.tss

Saturday, June 12, 2004

Re: N-queens solution

I still haven't read Dinesh's 'Optimum' solution completely and am assuming i understood what i read. But another idea came to my mind. I don't know how much performance gain can be achieved if any at all. You be the judge.

The idea is to use Reflection.

Reflection allows Classes to be thought of as objects and it is possible to create instances of classes and use those to invoke methods etc of the Class. (just a intro for completeness). As mohn put it,(i think) Reflection is using meta-data of the Classes.

I am not sure if Reflection is possible in C++.

In Dinesh's 'Optimum' solution,
File ChessBoard.cpp, method void Search(int xpos), iteration is done at each step by these lines

ChessBoard* chess = new ChessBoard ( currSol,order);
chess->Search(g+1);

I guess creating 'new' instances for every row each time, is very costly. Hey.. Reflection is definitely costlier than 'new'. But could be used here.

If N instances of ChessBoard are created and stored in a List, these can be used for the solutions.

A new method, say flush(), to clear the state of the ChessBoard could be created.

Now instead of multiple 'new', the instances are created only once. Then Method objects can be created and invoked(). For each row, the Method of the element of the List can be called and after a search, all the List elements are 'flush()'ed for a new search...

Thursday, June 10, 2004

Re: N-queens solution

Explanation of N-queens

I will assume the 4-queens problem for sake of simplicity. 4-queens has 2 solutions.

The Optimal Solution (without notDuplicate() and other functions)

The objective of the program is to generate the positions on a 4x4 chess board such that when queens are placed on those postions, they do not attack each other.

The mobility of the queen sets the rules by which the other queens can be placed on the board.

This is how my program goes. The main() enters a loop to go through the first row of the chess board. So in the first iteration of the loop list< Solution > holds a single point (0,0) and this is used to construct the first chessBoard object,through a pointer "chess". The constructor for ChessBoard takes "candidate Solution list" and size of the board (in this case 4x4, hence n=4). Next, in the loop chess->Search() is exceuted. Search() represents the main algorithm which does most of the work in the program. Search() takes an argument which is the row number where the child has to be searched. If you notice, in this version, I'm feeding forward, as in, since my first point is (0,0), I search for a child in row 1.

Now I'll break down Search() for initial point of (0,0). The first step in Search() is to check whether the list currSol's size equals the size of of n. This case is possible only when a solution is found and hence here an "if" statement checks for that and on being true, Search() prints the Solution, increments the no. of solutions found and then returns.

Now if the size is not equal to n, that means the list still has to grow to find a solution. Hence the next step is to Map the chess board, i.e. to setup the unsafe positions on the board. This is achieved by the function setAttForEach(). For (0,0), the resultant board layout is:

Print currSol
Position on board is: 0 , 0

Print Board
1 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0

Now once the board has been setup, the main loop of the Search() function starts. xpos sets which row has to be searched to find a new safe position. The loop starts iterating through through that row (namely row 1) and the "if" statement checks whether the board position is safe or not. This is the critical part, If a safe position is found, first the new Point is appended to the currSol list and after that a new object of ChessBoard is created giving currSol to the new object's constructor and then chess->Search(g+1) is called, i.e Search() is called on the new object - for the next row (namely row 2).

Now again Search() executes for the new object, first checking if solution is found (which fails) and then Mapping the board of the new object according to it's currSol, which has the Points (0,0) and (1,2), the board now has the following setup:

Print currSol
Position on board is: 0 , 0
Position on board is: 1 , 2

Print Board
1 0 0 0
0 0 1 0
0 0 0 0
0 1 0 0

As you can notice when Search() goes through row 2, it finds no 1's hence the search on this object returns. Returns to where? Returns to the first object's Search(). See Search(), there is a "delete chess", hence the first object (the one with (0,0))deletes the new object (the one with (0,0) & (1,2)), and then does a currSol.pop_back(), which means that (1,2) is removed from the first object's currSol (remember we had pushed it in before creating new object, hence we pop it back out, since there is not solution to be found from that). The next line (setAttForEach) is redundant and is not needed, hence you can delete it. Now the first object's currSol has only (0,0) and it continues with the loop, i.e. it continues to search through row 1. It now finds (1,3) to be a probable child and in this way the search continues for all possible safe positions in row 1. But 4-queens doesn't have any solutions with (0,0), so this object search finally returns back to main(), where again the object is deleted and the main's loop continues, so now a new ChessBoard is created for the initial point of (0,1). This does find a solution:

Print currSol
Position on board is: 0 , 1
Position on board is: 1 , 3
Position on board is: 2 , 0
Position on board is: 3 , 2
Solutions: 1

And the second solution found is

Print currSol
Position on board is: 0 , 2
Position on board is: 1 , 0
Position on board is: 2 , 3
Position on board is: 3 , 1
Solutions: 2

Actually these also are similar, these two are basically what you call reflections of each other (try swapping the x,y values in first and re-order, you get the second solution). So the First is the "Unique" solution.

So this was the explanation, hope it made sense to you'll. This may not be the most efficient way to solve this problem, but my aim was to brush up with c++, which I achieved. So all in all, I'm pretty happy with the product!

Dinesh.

Wednesday, June 09, 2004

Re: N-queens solution

Ok, my favourite part when I was doing this was when I tried to make my own version of the standard library function mem_fun_ref_t. You'll will know it as mem_fun_ref, which is basically an adapter for the first!

Now what I was trying to do was to get for_each() working in this way,

for_each(currSol.begin(),currSol.end(),setatt)

But it would let me, saying that address of setatt couldn't be taken. Then I tried

for_each(currSol.begin(),currSol.end(),mem_fun_ref, (&ChessBoard::setatt))

This was really bad, cause as I later found out, my whole idea of what the adapters mem_fun and mem_fun_ref did was wrong.

Mohnish, this is especially for you, man try reading the source for stl_function.h !! You'll learn an awful lot about the way things work! try stl_algorithm.h too! But it's not for the faint-hearted!! :):) I thought I knew exactly what it did, but I was a bit wrong! It was time well spent trying to read it!!

I tried making my own version of mem_fun_ref, but there were problems and I wasn't able to get it right, yet!!

If you guys want I'll post explanations of mem_fun & mem_fun_ref! Tell me if you want it! Atleast I'll try, I'm still figuring out :)

Dinesh.

Re: N-queens solution

Revo of course the thing will work!!! I was really stupid, I should have given your'll this solution rather than the duplicate one. Remember I had said, I had written a program before also on 8-queens using brute search rather than "back-tracking", well that incorporated this idea.

This was at the back of my mind, but just forgot to use it for optimization! I'm sorry, I can get pretty dumb like this at times!! Thanks Revo!!

My aim for this thing was brushing up with C++, hence it's a little more complex than it should be. But I had a lot of fun with it.

I did the whole duplicate thing because I wanted to see what happened if I started say for an initial position on (0,0), I appended the nth-level queen to it. I wanted to see if the path taken was any different. But the nature of the problem is still such that, even if I append an nth-level queen all it gives me is a duplicate of the original solution! This is really a cool problem!

So I wanted to make a multi-level search and see what I found rather than just making a single-level search. For me the most interesting thing was the tree structure that was getting created.

You can find the optimized source here: Windows & Linux

Dinesh.

Re: N-queens solution

Firstly i would like to clarify that I have not read Dinesh's solution yet. Too lazy to read and C++ is not the easiest language.

I got thinking of the problem and may have a solution. I think its different cause I did not feel the need for a duplicate() or the need to set many attack conditions. Maybe the soln's might be same. And it's almost 3:30 AM so I'll just present an algo, which if different, I'll try coding later.

My basic principle is that each queen on the chess board will occupy only one row. There are 8 queens, q0, q1,.. q7 where qn will be placed in the n th row.

The methods are

[ ] getSafePositions()........//returns all safe column positions for a queen in a row
setAttackBelow()..............//set all positions below current position as unsafe
setAttackDiagonalLeft()...//set all positions diagonally left of current position as unsafe
setAttackDiagonalRight()..//set all positions diagonally right of current position as unsafe

.[ ] q0.getSafePositions()
.if [ ] == null, {reset board & continue};
.for each in [ ]
....q0.setAttack()
....[ ] q1.getSafePositions()
....for each in [ ]
.... ..
.... ..
...// and iterate for each lower row.
...// finally
.......[ ]q7.getSafePositions()
...........if [ ] != null
.............else {we have a soln}


Here q0 is the queen placed anywhere in the first row, q1 in the second row and so on. if q7 is also placed on the board, then thats a solution.

Now the other attack combinations ( up of the current queen row ) are not required as the next queen just cannot be placed there. So those above positions can be neglected for setAttack and also for getSafePositions()

So is my solution different or did I make a fool out of myself not reading Dinesh's code??

I suggest Hrishi and Mohn also try some solutions. Should we try more problems like these? We'll get a million from sites like topcoder.com.

N-queens solution

Have you'll heard about the 8-queens problem, I think most CS guys are familiar with it. I was generally trying to brush up with C++, so I thought I'd try to generate the solutions to the 8-queens problem (there are 92 of them). Then I thought if I'm going for a solver might as well make it a generic one and so I wrote the following code to solve n-queens for any given n.

The source code can be found here : Windows & Linux

It was really a lot of fun!! For 8 queens, I got the execution time down from 435 seconds to 213 seconds to 20 seconds!!!

As far as I know, the code will generate solutions for any n, considering some critical resource doesn't get exhausted. I tested it for 9 queens which has 352 solutions, it generated all 352 of them! So it should work!!

Dinesh.

Saturday, June 05, 2004

some news

here are some good links i got

link here

desription
One way to think of Fast Infoset is as a GZIPed XML. It has the same property that you only need to know it is encoded to recover the original. The main difference is that Fast Infoset is customized for XML and leads to better encoding and decoding times.

link here

description
open source java

do you guys think java will be used in linux more if java is open sourced or will dev's stick to c/c++.

also what are your resources for computer related news?

Wednesday, June 02, 2004

Re: To be or not to be virtual

Even I personally like the C++ style. And I think you hit the nail on the head by talking about designer control. Java partially forces you to adhere to a particular style whereas C++ can fit quite a few roles.

As far as the Design of C++ is concerned Bjarne put it best "Simplicity was an important design criterion: where there was a choice between simplifying the language definition and simplifying the compiler, the former was chosen."

I think Java went too far with the above, this is just a personal opinion, but everytime I write code in Java, I feel that I'm being spoonfed and that ultimately it seems like the design fits the language rather than the language fitting the design.

Dinesh.