Linux : Bash Script (Shell Script)

A very simple automatic judge:

All of you studying cse must have known what is an Onlinejudge and most of us don't know how it works. Btw, I'm not going to talk about that here. It's a simple Linux Shell Scripting example / tutorial which will show you how to handle other programs in Bash and how to access all the files in a specific folder not knowing exactly how many are there.

The following snippet works very simply. It takes a target [.cpp] file as a command line argument and compiles it using g++, generates output files for all the input files provided with. And last, it compares those files with original output files and checks whether your program generated all the outputs correctly. So you can use it for your own purposes by making proper modification. It's also very easy to understand.

Note:
The folder from where you run this script must have these in it:
1. in // it will contain the input files with [.in] extension.
2. pout // it will hold the output files generated by your program.
3. jout // it will contain the correct judge output files for testing.
4. The program you are checking for with obviously [.cpp] extension and it's name is to be passed by command line argument.
Unless you change them in the code as you like. It is always a good practice to experiment with codes. :)

# Author: Zobayer Hasan
# CSE DU - 22/10/2009

# Check whether target file is provided or exists
# If available, compile and make it executableclear

if [ $# != 1 ]; then
    echo "parameter missing"
    exit
elif [ ! -f "$1" ]; then
    echo "file not found"
    exit
else
    if [ -f PROG ]; then
        rm PROG
    fi

    g++ -o PROG "$1"

    if [ ! -f PROG ]; then
        echo "Compilation Error!"
        echo "Your program could not be compiled."
        echo ;
        exit
    fi

    chmod -c 777 PROG > log.txt
fi

# Run the executable for each file in the "in" directory
# And generate their output files in "pout" directory
# Then match with the correct files in "jout" directory

echo ;

N=0
values=$( ls ./in/*.in )

for LINE in $values
do
    ./PROG < "$LINE" > "./pout/$N.out"
    diff ./pout/$N.out ./jout/$N.out > log.txt

    if [ $? -eq 1 ]; then
        echo "Wrong Answer!"
        echo "For file $LINE. Check log file."
        echo ;
        exit
    fi

    N=$(( N + 1 ))
done

echo "Accepted!"
echo "All tests passed successfully."
echo ;

# End of script :)

Have fun with bash !!!

SPOJ Solve list comparison tool

Check this:

This is a tool for comparing solve list between two users in SPOJ... Of-course you can do that with your eyes, but that's no doubt tedious...

http://www.cise.ufl.edu/~mlpalii/spoj/head2head.pl?user1=<user_id_1>&user2=<user_id_2>

This is the address of the tool.... You just need to replace the <user_id_1> and <user_id_2> with your desired two spoj user ID.

Example: say, two users "zobayer" and "shiplu", their head2head comparison is here:
http://www.cise.ufl.edu/~mlpalii/spoj/head2head.pl?user1=zobayer&user2=shiplu

Also, this site is great :: https://www.otinn.com/spoj/comparer.php (thanks to Ridowan)

Segmented Sieve

Memory and time efficient :)

Problem Statement:

Your are given two integers a and b. You have to find all the primes within range a and b. Here, 1 ≤ a ≤ b ≤ 2³¹-1 and b - a ≤ 10⁵.

Note: You have to handle 1, 2 and even numbers for appropriate case of your own.

Solution:

#include <string.h>

#define MAX 46656
#define LMT 216
#define LEN 4830
#define RNG 100032

unsigned base[MAX/64], segment[RNG/64], primes[LEN];

#define sq(x) ((x)*(x))
#define mset(x,v) memset(x,v,sizeof(x))
#define chkC(x,n) (x[n>>6]&(1<<((n>>1)&31)))
#define setC(x,n) (x[n>>6]|=(1<<((n>>1)&31)))

/* Generates all the necessary prime numbers and marks them in base[]*/
void sieve()
{
    unsigned i, j, k;
    for(i=3; i<LMT; i+=2)
        if(!chkC(base, i))
            for(j=i*i, k=i<<1; j<MAX; j+=k)
                setC(base, j);
    for(i=3, j=0; i<MAX; i+=2)
        if(!chkC(base, i))
            primes[j++] = i;
}

/* Returns the prime-count within range [a,b] and marks them in segment[] */
int segmented_sieve(int a, int b)
{
    unsigned i, j, k, cnt = (a<=2 && 2<=b)? 1 : 0;
    if(b<2) return 0;
    if(a<3) a = 3;
    if(a%2==0) a++;
    mset(segment,0);
    for(i=0; sq(primes[i])<=b; i++)
    {
        j = primes[i] * ( (a+primes[i]-1) / primes[i] );
        if(j%2==0) j += primes[i];
        for(k=primes[i]<<1; j<=b; j+=k)
            if(j!=primes[i])
                setC(segment, (j-a));
    }
    for(i=0; i<=b-a; i+=2)
        if(!chkC(segment, i))
            cnt++;
    return cnt;
}

This is a sample program which demonstrates segmented sieve. Very fast and memory efficient version. 'base' is the array which holds the flags for all the primes upto √(2³¹-1), i.e. the square-root of the max limit, and all the primes are stored in the 'primes' array. Later, these primes are used to determine whether a number is a composite or not within a certain range in the segmented sieve. To avoid overflow and sign bit problems, unsigned type is used.

A little explanation:

First of what what these macros mean?
#define MAX 46656
#define LMT 216
#define LEN 4830
#define RNG 100032

MAX is the sqrt of maximum possible input, in case of here, the maximum is integer range sqrt of which is almost MAX used here. So, MAX is not maximum allowed input, it is just sqrt of maximum input which is pretty big as 2147483647 i.e. 32 bit signed integer maximum.
LMT is sqrt of MAX. We all know, we run sieve upto sqrt MAX
LEN is the maximum possible different primes that can be stored using this algorithm with specific range defined as RNG, on which the segmented sieve will run and collect the primes out of it.

Now the next two vital macros:
#define chkC(x,n) (x[n>>6]&(1<<((n>>1)&31)))
#define setC(x,n) (x[n>>6]|=(1<<((n>>1)&31)))
And why we divide by 64:

Ok, yes, it is clearly bit shifting. But you must know what we do in bitwise sieve first in order to get this. Instead of using a whole array position to store just one flag, we can use its each 32 bits to store one flag, which saves memory by a factor 1/32. So its very logical to capture memory upto MAX/32, but why MAX/64 and RNG/64 here?
Because, we really have no point of handling the even number as 2 is the only even prime and we can handle it manually, without any stress. So, if we do not consider the even numbers at all, the total numbers are again reduced by a factor 1/2, isn't it? So what we get total is MAX/32/2 = MAX/64, same for RNG.

Now, the two macros chkC and setC is pretty straight forward. chkC checks if a specific bitflag is 1 or 0, and setC sets a specific bitflag 1 to mark it as a composite. They work similarly, so I will explain only the chkC part.

In bitwise sieve, where is a specific value n located? Obviously (n/32)^th index, and on that index, (n%32)^th bit from LSB (right hand side). But we just said before, we are interested with only odd numbers, so we map n with n/2 as follows:

Actual numbers
 1   2   3   4   5   6   7   8   9 ...........   n     ;[n is odd]
 |   |   |   |   |   |   |   |   | ...........   |
 0   x   1   x   2   x   3   x   4 ........... (n/2)
Position on which they are represented in the bitstrings.

So, n is actually n/2, which implies the previous statement: n's (actually n/2 's) position is in index [n/2/32] = [n/64] = [n>>6] and on the bit position (n/2)%32 = (n>>1)&31 ;[ We know, modding with a power of 2 is same as ANDing with (same power of 2)-1 ]. The rest is, how we check / set this specific bit. I have another post explaining these operations: Bitwise operations in C: Part 3, and obviously you can google it :)