Mr.Nutty's Palace

Subtitle

Blog

view:  full / summary

A Boggle Solver

Posted by Dibash on February 11, 2012 at 10:50 PM Comments comments (0)

If you guys don't know what the game of boggle is, then take a look at the wiki at http://en.wikipedia.org/wiki/Boggle. I wanted to creat a fast program that given a boggle board and a dictionary, it outputs all possible creatable words. Thinking about the problem for a bit there was a couple of ways to do it. 


 

  • 1) Use a trie to store the dictionary and search through the tries for words
  • 2) Create a min-heap based solution by storing the current neighbors in a min-heap and recursivle DFS t through it while checking for proper prefix via binary search
  • 3) Just do a recursive DFS on the board and perform a binary prefix search on the dictionary for each prefix.

Option 1 is pretty slow, comparitively of course, because it takes a while to build a trie. Option 2 is a little tricky and more complicated than option 3. The advantage option 2 has over option 3 is that, it doesn't have to be sorted since the result will come out presorted already if implemented correctly. My choice was option 3. Its simple, easy, and damn fast. My current working solution is on the hub at https://github.com/dchhetri/Boggle-Solver" target="_blank" rel="nofollow">http://https://github.com/dchhetri/Boggle-Solver. On my mac, it solves a 4x4 in 0.083s with no optimization on. Anyways, I figured putting up the code would benifit someone on of these days. Its there for your cheating needs. If I have time, I might still try to optimize it mainly by taking advantage of the cache and making the code more cache friendly but I'll see what happens. That's all for now, Happy Coding!!

regards MrNutty

 

A conversation about the use of 'break' in a loop [C++]

Posted by Dibash on January 31, 2012 at 9:25 PM Comments comments (6)

So today, one of my friend asked me about the use of break in a for loop? He wanted to know whether to using break in a for loop if a good idea or not? Well let see...


Here is a typical code where one has a chance to use break( assume there isn't a library function for this )

1.)  int find(int target, const int * array, const size_t size){
2.)    int index = -1;
3.)    for(int i = 0; i < size; ++i){
4.)      if(array[i] == target){
5.)          index = i;
6.)          break;
7.)      }
8.)    }

9.)   return index;
10) }

 

Is the above readable and clear? Yes. That is because the function can be described in plain english. Here is one way to read the function:

  'find' is a function that takes a target value to find from a array which will not be changed or altered. It tries to find the target value by looping through the whole array until there is a match with the current array value with the target, and if there is a match, then we save the current index and break out of the loop, else we keep chugging through until the end of the array. If at the end of the array we do not find the target value, we return the variable index which was initialized to negative one and never changed.


Ok thats clear enough, but can it be done another way that doesn't use break? Why yes of course. Here is an example.

1.)  int find(int target, const int *array, const size_t size){
2.)   int index = -1;
3.)   bool found = false;
4.)   for(int i = 0; i < size && !found; ++i){
5.)       if(array[i] == target){
6.)          index = i;
7.)          found = true;
8.)       }
9.)   }

10.)  return index;
11.) }


Using a similar way of reading style, this too can also be read easily. But is this a better version that the pervious one? I don't know, what's your definition of better? But as for my opinion, I like option 1 better. Why? Well for the following reasons:

 

  • Option 1 does not use an extra boolean variable
  • Option 1 does not use a extra check on the for loop ( i.e doesn't use "!found" extra boolean check)
  • Option 1 follows the rule of using a variable in the tightest scope by simply not using a variable and using the keyword break in place of the variable :)
  • I've always used option 1 since I started programming so I'm biased, plus less typing lol

 

One could say there is still a way to not use break, and the boolean variable and instead just return when needed. This is ok, but however is not viable in the general case. For example, there might be a time where you don't want to return from the loop but simply break out of it.

Also note, that sometimes using break is not viable to break out of a loop, for example in the situation where you want to break out of the whole nested loop from the inner most loop, you cannot use a break statement( you could but it wont do the job you want). Instead a good way to break out of a nested loop from the inner most loop is to use a boolean variable.


But here is the deal, it all comes down to style. If you have been using one way and it has worked, then there is no need to change your style, unless there is a compelling reason to do so. For example, if your company uses style X and you use style Y, then my advice would be to use style X and keep it consistent. It all comes down to style and consistency. If you are consistent with your style and if its correct, then don't worry about other approaches for now, just keep coding. However, this does not rule out the drive to write better code. If someone shows you a better way to do it and proves that it is better without a doubt, then you might want to give that option a try as well. Hope you enjoyed the small talk! Be safe and take care!

reagards, MrNutty

Update Chess Game programm

Posted by Dibash on January 29, 2012 at 7:50 PM Comments comments (0)

Here is a picture of its current state.

 


The developement is going pretty smoothly.  I have added a few more features and logic to the game. Now there is a status bar to let user notify who's turn it is, or the current game state such as checkmate and such. I have also changed the imaged used as you can see. Another feature added was the promition picker. When a pawn gets to the other end, a small popup window shows up, giving the user a choice to pick one of the available pieces.  

Now all thats left to is implement a menu and possible AI. We'll see how that goes. If you guys are interested, you can checkout the code at my github accout,  https://github.com/dchhetri/SFML-Chess" target="_blank" rel="nofollow">http://https://github.com/dchhetri/SFML-Chess . 

On Smart Pointers

Posted by Dibash on January 18, 2012 at 9:45 PM Comments comments (0)

So in this chess game, I'm using boost::shared_ptr and I have to say wow. I love it! It makes pointer handling so much easier. I don't have to worry about any memory managent, expect possible circular reference. I just love it. Not only does it make things easier, but it's also more efficient; with its reference counting. I have a new appreciation for boost smart pointers and I thought I'd share that. So next time you are creating a program, don't hesitate to use boost's smart pointers and possibly its other boost's features such as boost::array. 

Chess Game Progress

Posted by Dibash on January 16, 2012 at 1:40 AM Comments comments (0)

So I started working on a chess game clone using C++ and SFML and OpenGL. As of right now the graphics are done purely in SFML but some OpenGL functions are being used. Plus later I might port it into a more visually appealing game.

 

As for progress, I've been working on this on/off for about a week or so, and right now I have gotton the all the chess movement and its logic implemented. The graphics are shitty right now, since my main focus is on the logic. But once all the logic has been implemented, I will try to enhance the graphics.

 

Here is a minor screen-shot.

 

The images are just dummies images for now. They will be replaced later with appropriate images. The orange square is the horse possible move location. I had clicked the horse at bottom right, which showed its possible move location. 

There is still more stuff/logic to implement, but I will start on that tomorrow, right now I'm too tired. Anyways thanks for the read!

 


Rss_feed