Just another tech blog.

A blog abt GNU/Linux, programming, hacking, and my life.

Archive for the ‘Programming’ Category

Tips about programming, mostly dealing with solving algorithmic problems and programming contests.

My Digital Signatures :)

Posted by ajay on May 8, 2008

One evening I didn’t have much work to do and I had a look at this page. After seeing the Quote there, I thought why not create one such signature for myself :). And here it is ->

i;double r[]={175297239055116917538816e2,591298870944180608}
;main(){150-i++?*r*+8.,1[r]*=2.,main():printf(r)^puts(r+1);}

Just a little note: You need to compile it using gcc ( g++ wont work ) in Linux.

PS 1: Many thanks to Maruti Borker for helping me in creating the signature.

PS 2: I’ve become foosball addict. For more details check out Maruti Borker’s recent post.

Advertisements

Posted in Programming | 13 Comments »

I love sudoku puzzles

Posted by ajay on January 16, 2007

I am writing a post again after a long time. Didn’t write one primarily due to the fact that I was very much busy these days due to Hectic schedule at college and ofcourse some other things ;). Anyway In vecations I wrote a kind of interesting c++ program to solve sudoku puzzles given in daily news papers. The program uses backtracking and thats why It’s complexity is exponential in general. But still on most of the puzzles that I tried; It works very fast ( almost negligable run time). You can download it or have a look at it here. If you find input puzzles where it doesn’t work ( bugs ) or you have better ideas to solve a sudoku puzzle ( in terms of run time ofcourse ), then please post it as a comment.

PS 1: The program is primarily written to solve puzzles of size 9 x 9. but can be easily modified to solve a bigger puzzle.

PS 2: I have been trying to solve this problem. But my idea doesn’t seem to run in time :(. If anybody solves it, please post a comment about the idea used to solve the problem.  ).

Posted in Programming | 14 Comments »

Setting up new keywords for programmes in vim

Posted by ajay on September 8, 2006

Recently I was working on my operating systems assignment and I noticed that all the primitive system types like pid_t , mode_t , dev_t , nlink_t  etc do not come colored in vim editor like basic data types such as int float etc.  I thought it would be nice to have those words colored as we have int and stuff .

all the keywords are related to syntax, so for creating new keywords. First of all we have to create a class of words. For that we use the syntax command. For example suppose for a C program you want to highlight some words I mentioned above as datatypes, then you should  go to the vim configuration file specific to C programs ( Previously I told how to have specific configuration files for specific file types in vim here ) and add the following code –

syntax keywod cSysvar pid_t mode_t something_t x_t

highlight link cSysvar Type

now here cSysvar is the name of the class which you want to create. You can have as many of these classes as you want but the class name should begin with the file type you want to edit (the same class in a cpp file will be named cppSysvar) and the next character should be capital to distinguish the extention from the class name.  All the words written after cSysvar in the first line are the elements in the class cSysvar.  The second line tell vim to recognize all the elements of class cSysvar as they are the members of class ”Type’ (Type is used to recognize datatypes).

some other alternatives of type are as follows  –

Type -> datatype

Comment -> comment

Error -> syntax with errors.

Number -> the color used for displaying numbers.

Character -> used to represent single characters.

Some other class names include Identifier, Underlined, Ignored, Delimiter, Statement, Preproc (preprocessor directives) and more. You can change the last word in second line of the snippet to have variation in the color used to display those particular words.

I hope this will make Vim more beautiful.

Happy Viming ..

Bytheway .. I recently got through in the Qualification round of Google Code Jam 2006 and the next stage will held on 14th of september :).  looking forward for that as well as Topcoder Collegiate Challange.

Posted in Programming, vim | 13 Comments »

Some good looking codes and interesting problems

Posted by ajay on July 21, 2006

I recently came across some awesome piece of codes. I dont understand any of them, but I find it worth sharing here.

1. A c program to solve The Tower of Hanoi problem without using functions,  stack etc. and does the task in 6 lines. Moreover, the code looks like a tower as well :).

main(
){int
z,y,n
;scanf(“%d”,&n);
for(y=1;(1<<n)-y
;y<<=z-1,printf(
“disk %i from %i to %i.\n”/**/
,z,(y&y-1)%3,((y|y-1)+1)%3),y
++)for(z=1;!(y&1);z++,y>>=1);}

2. The queen of problems – N queens problem. If you are a computer science student, you must have heard about n queens problem and probably solved that as well.  This C program solves the problem very quickly, and for the rest – just have a look at the code.

int v,i,j,k,l,s,a[99];main(){for(scanf(“%d”,&s);*a-s;v=a[j*=v]-a[i],k=i<
s,j+=(v=j<s&&(!k&&!!printf(2+”\n\n%c”-(!l<<!j),” #Q”[l^v?(l^j)&1:2])&&++
l||a[i]<s&&v&&v-i+j&&v+i-j))&&!(l%=s),v||(i==j?a[i+=k]=0:++a[i])>=s*k&&
++a[–i]);printf(“\n\n”);}

3. Prints first 15000 digits of PI.

a[52514],b,c=52514,d,e,f=1e4,g,h;main(){for(;b=c-=14;h=printf(“%04d”,
e+d/f))for(e=d%=f;g=–b*2;d/=g)d=d*b+f*(h?a[b]:f/5),a[b]=d%–g;}

4.  An interesting problem –

what is the “condition” such that, this snippet of code prints HelloWorld!!

if condition

printf(“Hello);

else

print(“World!!);

my friend abhilash gave a nice solution for that ..

if ( printf(“Hello”)<0){

printf(“Hello”);

else

printf(“World!!);

5. Another interesting problem –

Write a small C program, which while compiling takes another program
from input terminal, and on running gives the result for the second
program. (NOTE: The key is, think UNIX).
Suppose, the program is answer.c
Then, while compiling
$ cc -o answer answer.c
int main()
{
printf(“Hello World\n”);
}
^D
$ ./answer

Hello World
$
if anybody can solve this problem please let me know by commenting over the post with the solution.

Happy coding.

Posted in Programming | 23 Comments »

Some Special Codes

Posted by ajay on July 16, 2006

I was solving problems some time ago and came to know some good facts about c and c++  and wrote some interesting codes.

1. A C program which can print the file name it is kept in ;).

#include<stdio.h>

main(){

printf(“the source file name is %s\n”,__FILE__);

}

actually __FILE__ is a macro which stands for the file name the programme is kept in and the compiler does the rest.

2. Usage of assignment suppression operator in scanf  – Suppose you have some crap input (the input is provided to you but that is not of any use to your program) then what normally we do is take a dummy variable and scan the input in that variable.  Example –

int dummy;

scanf(“%d”,&dummy);

but there is one more method which can save memory and time

what you do is

scanf(“%*d”);

In this method, we provide a character * to the scanf function and by doing that; scanf will scan the input from standard input but it wont assign it to any variable. This is scanned in a buffer of sufficient size and you dont have to worry about that.

3.  My source code for problem KAMIL on spoj

x=1;main(){for(;scanf(“%*[^DFLT\n]”)+1;x=getchar()<11?printf(“%d\n”,x),1:x*2);}

If anybody has a better idea on this problem then please do comment on the post.

4. Printing something with variable width  –

Suppose you are to print some formatted output in some program and for that sometime you require to print a variable in a fix width ..

for example if you have to pring an integar in width of 5 or more then you do

printf(“%5d”, var);

now if var is 10 it will append 2 leading spaces to complete the atleast 5 width rule.

now suppose you dont want leading spaces but leading zeroes, then here is another method to write the same –

printf(“%05d”,var);

now if var is 10 it will print 00010 and so on.

Another condition comes if the width in which we want to print the variable is not known at the compile time – suppose you want to print variable with a width which is contained in another variable, then we can use –

printf(“%*d”,x,var);

here x is the width length variable. Whenever we do this * operator .. then it looks for the next integar argument provided in the arguments and then  assumes that it is the width in which  the variable is to be printed.

Now if x = 2 then it will b the same as

printf(“%2d”,var); ..

this way we can work with this width thing pretty well.

If any of you guys know some nice facts about c or cpp language, then please post them as comments. Any gud suggestions related to things I posted are also welcome. Have Fun.

Posted in Programming | 46 Comments »

Programming freaks @ ug1

Posted by ajay on June 22, 2006

While doing C programming assignments .. We all used to CURSE the prof and all .. but after SMR and Uday Vishesh .delivered a lecture about topcoder and all .. many people were programming out of interest not due to enforcement by the prof .. first we people started on topcoder .. but after that started on ACM Valladoid Online Judge and Sphere Online Judge as well . Plus we started taking part on many online programming contests as well like bitwise, bytecode, ICPC, Google India Code Jam etc ..

some of the people from ug1 who are coding are

1. ACM Valladoid Online Judge ( acm.uva .. )

Name No. of Solved Problems Rank ( India ) Rank ( world )
Ajay Somani 108 39 2261
Kulbir Saini 38 85 5216
Sharatchandra Pinapati 13 10630
Atul Kumar Dwivedi 10 12313
Maruti Borker 06 15875

2. Sphere Online Judge ( SPOJ )

Name No. of Solved Problems Points World Rank
Ajay Somani 38 13.2 229
Abhilash I 32 11.8 244
Maruti Borker 23 6.8 354
Sharatchandra Pinapati 19 6.5 362
Sunil Soni 13 3.2 560
Kulbir Saini 7 .9 1064

3. Topcoder

Name No. of Competetions Rating School Rank Country Rank
Ajay Somani 1 1571 1 18
Shikha Aggrawal 2 931 381
Maruti Borker 3 632 23 827
Kulbir Saini 3 602 24 861
Atul Kumar Dwivedi 3 590 25 875
Vivek Prakash —- —–

If anybody from our batch if programming on these sites and his name is left out due to my mistake .. Plzz let me know about it

and Thanks to

1. SMR, Uday Vishesh, Vardhman and Manikandan sir for their motivation.

2. Turbo for his classical effort for this ranklist of top 100 Indian coders at ACM UVA.

Posted in Programming | 4 Comments »

SPOJ Methods to solve for beginners – part 1

Posted by ajay on June 4, 2006

From last 20-25 days I am solving problems on Sphere Online Judge . This site contains the best problemset I’ve seen (even better than acm) It contains a variety of problems and I thought to write my algorithms here so that some beginners like me can get help and improve their programming skills. So here is the first part containing some easy problems –

Disclaimer : I do not claim that my solutions are best in any means, as far as methods are concerned I always prefer simplicity rather then speed, and my methods are just a starting point for beginners. If you have better solutions please be generous to put them as comments along with the problem name.

so here we go –

1. Prime Generater – This question can be solved by applying sieve’s algorithm. What we do is make an array of prime numbers in the range of 1 to 32000 ( square root of 1000000000 ) .. now we have our initial setup ready .. for generating primes i used sieve’s algorithm which states that you make an boolean array of 32000 values and initialize it as true that means declare all of them as prime .. now start from 2 and if the current number is prime .. make all itz multiple in the apropriate range as composite ( i.e. set their index in the array as false .. ) .. this is the fastest method for generating prime numbers .. now we start taking the input from the user .. lets say he gives the numbers m and n as input ( m> n) now we apply sieve again .. first make an array of booleans of size m-n ….. now for all the prime numbers from 2 to the prime number next to the square root of m we make their multiples in the range n to m as composite ( i.e. set their array as false ) .. now after this procedure is over .. just a linear traversal in the second array .. and print whatever is prime .. ( i.e. flag is true .. ) . here we consider primes only till the square root of bigger number beacause of the fact that if any number is divisible by a number .. then either the diviser of x/y( x is the number and y is the diviser ) will b in the range of square root of x .. so it speeds up the simulation a lot .. 🙂

2. Transform the expression – This problem is very easy except you got check all the minor errors .. you can do it easily by a use of stack .. ( that is the method i was taught in my data structure course .. :p .. ) what you do is make a stack of operations .. ( char ) and a stack of operators ( char again .. ) .. now whenever an operator is pushed on to the stack if the the operator at the top of the stack has a priority higher than the operator to be pushed ( for example ‘+’ is to be pushed and ‘*’ is at the top of the stack .. ) we first pop out the higher

priority operator .. apply the operation on the char operands .. print the result and then push the current operator .. I am just telling the basic thought .. now you have to put a lot of conditions to get it working .. and ofcourse the special case for brackets .. because they are not the operators but have got the highest priority .. ) .. this algorithm is pretty much O(n) so will work fine ..

3. The next palindrome .. :- this method I used to solve the problem is pretty much a non standard method .. I mean just specific to the problem .. there is no specific theorum to proove that the method is correct or not .. anyways .. what we do is .. we have a boolean variable isincreased ( which at any time specifies that after all the manipulations we have done till then is the resultant number greater than the input number or not .. ) now make it initially as false then first we travel starting from the starting digit and the ending digit .. ( make one pointer as low and other one as high .. based on your choice .. ) now we keep moving both the pointers towards the center of the number untill high<low comes .. once it comes we make high equal to low and make the isincreased flag to true .. if it does not than we will stop our traversal once we reach the center .. now we will move outside i mean towards the corners of the number .. we again have a high .. ( pointer on the right side .. ) .. and low so we can have 3 conditions at a time ..

1.high < low .. => we make high equal to low and forget about it ..

2. high=low => we do nothing and keep moving

3. low<=high => we increase digit low by 1 and and then make high equal to low ( that means if we have low = 1 and high = 8 we make low as 2 and high as 2 ( ofcourse we have to make them equal at any stage because the resultant number is a palindrome .. ) . and then make all of the digits between low and high as 0 ( becauze since low is increased so even we make all of them as 0 the isincreased flag will still be fine .. )

now the special case is if we have the digits as 9 and their is no chance of increasing the digits .. frm the beginning ( the number is all 9 ) the isincreased flag continues to be false and finally if that is the case when we finish it up .. we simply print 1 than some 0’s then again 1 .. ) ..

otherwise after we reach the ends we are done and we simply print the string .. 🙂

4. Simple Arithmatics .. – this is question is as simple as it looks except the output formatting .. you will get it right but the only statement to be given attention is that horizontal line of hyphens is only as long so as to cover the line exactly above and below it .. and not all the output .. so if u take care about this you may get it right .. that was the mistake i did when i solved .. :p ..

5. Small Factorial .. – This is one of the easiest problems at spoj .. you just have to make a programme to multiply arbitrary large numbers . ( stored as strings .. ) and then run a loop from 1 to n to calculate the answer .. thats it .. at least that is what i did .. ( thr may b better methods ofcourse .. )

6. Bytlandian cryptographer .. act 2nd .. – This is again a very easy problem .. add 1 to a number isnt it easy !!!! .. but the problem is you have to write the code in Brainf*** yeah that language does not have even a multiplication and addition operators .. just 8 instructions and the language is over .. !!! 😦 .. but you can try the official documention of brainf*** language .. go through may be first page and thats it for this problem .. ( I used a trick to get around the solution .. which makes it almost 16 character programme .. !! .. ) ..so easy points once you go through this page ..

Posted in Programming | 29 Comments »

Size contest

Posted by ajay on June 1, 2006

Recently I was solving problems on Shpere online Judge and I found an interesting challange Size contest. The problems statement is that you are given a number n and a set of n integars, you have to calculate the sum of all the positive integars amongst those numbers. But the requirement is not to write the fast program but to write the shortest code for it. You might choose any language. Since I know only c/c++ and python so here is what i wrote in both of them respectively ..

# c++ code ..

#include<iostream>
main(){

int n,s=0,x;

for(std::cin>>n;n–;s+=x>0?x:0)

std::cin>>x;

std::cout<<s;

}

this code is 93  characters without spaces and newlines ..

now here is the python code ….

# python code ..

n=input()
y=0
for i in range(n):
z=input()
if z>0:
y=y+z
print y

this is 53 characters without spaces and new lines ..

can anybody help  me reduce it to 70 ( in c/c++) and 26( in python ) .. which are the best codes for respective languages there or if not to that level at least reduce the code size .. 🙂 ..

Posted in Programming | 10 Comments »