Linux console games

Though these linux console games would not offer high-end graphics or flexible controls, they do attract the geek with in you. Here is a list of some interesting console games (compiled from other forums and sites :P):
  • bastet : Also known as "Bastard Tetris", it will irritate you by not giving you the piece you desperately require to complete a bunch of lines. (My favourite)
  • zangband : A role-playing game with a motive of surviving and completing quests. (I would say its the Skyrim on console)
  • moon-buggy : Just need to make a buggy jump over craters.
  • ninvaders : Destroy aliens with your spaceship. (But controls suck)
  • greed : Clear the numbers on the board, with your moves being controlled by the same numbers.
Yet to rty out the below ones!!
  • nethack 
  • empire
Enjoy!!!!

If  you find any new game, do mention it in the comments.

DATAC: Miller Rabin

{ DATAC: desperate attempt to add content } 

This and perhaps many of my next few posts will be my desperate attempts to put up some content on the blog. This time I am putting up a code for Miller Rabin, a probabilistic algorithm to check whether a number is prime. It's a complete implementation and would run if the code is directly copy pasted.

#include <cstdio>
#include <cstdlib>
#include <iostream>

using namespace std;

/*Auxiliary function to compute gcd of two numbers */
long long gcd(long long a, long long b){
        return b==0?a:gcd(b, a%b);
}

/*Auxiliary function to compute (a^b)%mod */
long long power(long long a, long long b, long long mod){
        if(b==0)
                return 1;
        long long x = power(a, b/2, mod);
        x = (x*x)%mod;
        if(b%2==1)
                x=(x*a)%mod;
        return x;
}

/*Function to check primality of num against seed*/
bool checkprime(long long num, long long seed){
        if(num%2==0)
                return false;
        long long gc = gcd(num, seed);
        if(gc>1)
                return false;
        int s;
        long long t;
        s=0; t=num-1;
        while(t%2==0){
                s++;
                t/=2;
        }
        long long a0 = power(seed, t, num);
        if(a0==1 || a0==num-1){
                return true;
        }
        while(s-1>0){
                s--;
                a0 = power(a0,2, num);
                if(a0==num-1){
                        return true;
                }
        }
        return false;
}

bool isprime(long long num){
        srand( time(NULL));
        if(num<=1)
                return false;
        if(num == 2)
                return true;
/* 50 in below line defines the accuracy, which means the algorithm will declare
a composite number to be prime with a probability of (1/(2^50)), which is quite low.
A paranoid fellow can increase it to higher value, for some more satisfaction. */
        for(int i=0;i<50; i++){
                int random = rand()%num;
                while(random<2)
                        random = rand()%num;
                bool val = checkprime(num, random);
                if(!val){
                        return false;
                }
        }
        return true;
}

int main(){
        long long num = 31815;
        int cnt=0;
        cin >> num ;
        if(isprime(num)){
               cout << num << endl;
        }
        return 0;
}

But to quote my professor Dr. Kannan Srinathan, the probability of the above code to fail is less than the probability that you hit a wall of bricks and safely go through it (without breaking the wall :P).

Selecting the code and then copy-pasting can lead to addition of stray characters in the code. To remove them, run the command:
tr -cd '\0-\176' < input > output.cpp

The program is ready to run.

Never knew C++ sort can give a Segmentation Fault

I never knew such a thing could happen, and I learnt it the hard way.

I was trying my luck at the Facebook Hacker Cup, completed a question, ran the given sample test case (which was so long that had to scroll down a lot of times) and the output turned out to be fine. I decided to download the final test case (For the ones unaware of the hacker cup format, I would say that its different from the usual judges. You code, then download the test case and within 6 minutes you need to upload the test case output). The timer started and as soon as I ran my code on the file....BANG!!! seg fault. It took me a few seconds to figure out the reason for it and I realized it was at the C++ sort function call. With no idea in mind I desperately tried to correct it, but could not do so. The timer expired and so did my enthusiasm for doing any further questions. And believe me if such a thing happens while coding at 4:00 am, it hurts!!!.

Finally it turned out, the mistake was my poorly coded sort comparator function. It made a situation of kind: a<b, b<c, c<a, possible.

Fool, ain't I.