Saturday, 31 December 2016

Anirudh

How I Spent the Christmas of 2016

     No comments
About a month ago, in November, just before the end-term exams, our batch was told that this winter, extra classes will be scheduled for us and the winter break (earlier scheduled from December 25th onwards) has been postponed till December 31st. Being a hosteler, this meant I had to stay in the college during the beautiful holiday season… The thought was disheartening.

A Charlie Brown Christmas Comic

Well, here is a brief account of how my days went by.

A Little Background

I did not want to miss the classes because they were to be taught by special instructors coming from IT companies, including Google! Actually, my college offers a special batch for Computer Science, known as the University Coding Academy (UCA), and I was selected for it. Special lectures on important subjects like Operating Systems, Data Structures and Algorithms are arranged for UCA, which are delivered by people having work experience in the industry. One of our instructors, Mr. Gaurav Kumar, was recently hired by tech giant Google!

Now these extra classes were to be on the Essentials of Operating Systems. We already had the Operating Systems course in our 5th semester, but to be taught OS by these guys was going to be different, I guessed. So I cancelled my train tickets (I said it was disheartening) and stayed for the adventure. The decision about me spending Christmas in the boring hostel room was taken.

The Christmas Eve

From 9th to 24th of December, I appeared in my exams. They went really well. The very next day (December 25th), I would have been in my home. But now, it was not to be. I had a day off for Christmas and then the classes from 26th to 30th. Usually, on Christmas I would go to Church with my mother, have great food and spend the day enjoying at home. And here I was, many a kilometer away from all of that.

All my roommates were already off to their homes. Being alone in a hostel room might sound dire, but I love it. I spent the evening of 24th watching a movie on my laptop. I also listened to a few Christmas songs! During all this time, I also worked on redesigning a website of mine (I love creating websites; I consider it an art and spend a lot of my spare time doing that). Later, at night, I walked into one of my friends and a great coder, Gurpreet, and had a brief discussion (lasting 2 hours!) on programming and stuff. I called home at midnight to wish my mom Merry Christmas. And went to sleep. Quiet, calm and peaceful.

Command Line Christmas

The Christmas Day

I woke up. It was Christmas! The weather was really cold and rainy. I had breakfast and came back into my room, having the whole day in front of me. Again, I opened my laptop (what more can you expect) and started playing some songs from classic Bollywood movies and from one of my favorite bands, SANAM. I also listened to songs by Pentatonix – Mary, Did You Know, O Holy Night, and others. I remember to continue designing that website throughout the day, taking some short breaks in between.

I found that somewhere deep down, I was quite happy inside. Though I am not a Christian by religion, I’ve always had a strong bond with this festival. I believe that the mere fact that it was Christmas Day was enough to make me jolly. So, it wouldn’t be wrong to say that during those short breaks, I actually danced frantically in the whole room! At night, I started a new drawing – Santa Claus sitting on a sofa, reading a book… The artwork is not yet finished because I am constantly procrastinating the coloring. The classes were going to start the next day and I had already resolved in my head that if I was going to take those classes instead of having fun at home, I was going to do it like never before – I was going to pay a lot of attention and try to grasp all of the concepts, like a proper “nerd” (although, I prefer “geek”). With all that in mind, I completed Christmas.

The Classes

The classes started. I really was attentive during the lectures and let me tell you, they were not boring. Some of my most messed-up concepts about Operating Systems were demystified. I was rather enjoying myself.

On the evening of 27th, I started off something new and fun that has been recommended to me by my friends ever since 1st year – I started watching the sitcom How I Met Your Mother, and it was legendary! :-D

I had its episodes by my side for the next couple of days. I completed nearly two seasons in three days! By the 30th of December, I had better knowledge of Operating Systems, some great notes and really peaceful holiday memories. The days did not actually go that bad. And now, I’m at the railway station, waiting for the train that will take me home.
Read More

Tuesday, 20 September 2016

Anirudh

10k Apart Contest 2016: Build a website under 10KB

     No comments
There is a very interesting web design contest going on online, called 10k Apart. It puts emphasis on creating a website, "optimizing every little byte like your life depends on it and ensuring your site can work, no matter what". The challenge is to build such an optimized site that your pages load under 10 KB size limit.
You can enter the contest till September 30th. (Visit their website for more information.)

I have also participated in the contest, and my entry is just as "random" as it gets - it is about randomness! It is a minimal site made with HTML5, CSS3 and some JavaScript and shows that a pretty site can be built with pretty simple code! It's got some optimization hacks too, like the optimized URLs, and using character entities as icons etc. Minimal amount of JS is used with fallback options. Total cost: 7.02 KB :)


Some noteworthy optimizations:

1. URLs
  • Used <a href=""> for current page/directory link instead of the complete <a href= "http://anirudhkhanna.github.io/10k-apart-2016">
  • Omitted the protocol name for external sites. For example, //github.com instead of the complete URL http://github.com
  • Used ../ instead of giving a full URL to the previous directory (i.e. anirudhkhanna.github.io).
  • URL shorteners were not used because although they could reduce the number of characters, they are not always considered safe.
2. Code Formatting
  • The formatting is a bit compact.
  • Especially in CSS, where the code format is like this:
    nav ul {margin:5px 0 0 0;}
nav ul li {display:inline; padding-right:50px;}
...
3. No superfluous tags
  • It was tried that unnecessary tags were cut down. For example,
    <span id="titlelink">
  <a>...</a>
</span>
    becomes:
    <a id="titlelink">...</a>
4. Minimum and optimized images
  • Images were avoided mostly. The images used (like the favicon) were really small and optimized.
5. Character entities for symbols
  • Only character entities (like ✎, ✉ etc.) were used as icons on the site wherever required.
6. Minimal JS used, with fallback options

7. Indentation with 2 spaces, not 4
Read More

Monday, 22 August 2016

Anirudh

Puzzle: Is a married person looking at an unmarried person?

     1 comment
There are three persons - Jack, Anne and George. Jack is looking at Anne, but Anne is looking at George. Jack is married, but George is not. Is a married person looking at an unmarried person?

A) Yes
B) No
C) Cannot be determined

Answer: Show answer
Yes. Because, if Anne is married, she's looking at George (who is unmarried).
And if Anne is unmarried, Jack (who is married) is looking at her.

Read More

Saturday, 20 August 2016

Anirudh

Puzzle: Rectify the equation

     No comments
Rectify the following equation: 101 - 102 = 1. You are allowed to move just one digit.

Answer: Show answer
Move the numeral 2 half a line up to achieve: 101 - 102 = 1.

Read More
Anirudh

Puzzle: The 5-digit number

     No comments
What 5-digit number has the following property: If we put numeral 1 before this number, we get a number three times smaller than the number we get if we put numeral 1 after this number.

Answer: Show answer
Using an easy equation, 3(x + 100000) = 10x + 1, we find out that the number is 42857.

Read More
Anirudh

Puzzle: Between 5 and 9

     No comments
What mathematical symbol can be placed between 5 and 9, to get a number greater than 5 and smaller than 9?

Answer: Show answer
Place a decimal point between them to get 5.9

Read More
Anirudh

Puzzle: Birthday mystery

     1 comment
The day before yesterday I was 25 and the next year I will be 28. This is true for only one day in a year. What day is my birthday?

Answer: Show answer
He was born on December 31st and spoke about it on January 1st.

Explanation:
The day before yesterday (December 30) he was 25.
He turned 26 on December 31 (his birthday).
And he talked about it on January 1 (which is in the next year of his recent birthday). That year he would turn 27, so "next year" he would turn 28.

Read More

Friday, 19 August 2016

Anirudh

Write a program to get the nth byte of an integer

     No comments
Problem statement: Given an integer, write a program to extract the nth byte from it.

Example: Let's take an integer in hexadecimal format, say 0x5510EF3A (a 32-bit integer). It has four bytes, given in hexadecimal as:
     Byte 0: 0x3A
     Byte 1: 0xEF
     Byte 2: 0x10
     Byte 3: 0x55
So, if we want to get byte #2, the result would be 0x10.

Solution: We can move the required byte to the rightmost position by right-shifting the number by (8 * required byte number). Now we only need the rightmost byte in our result (the last 8 bits), so we can mask it by doing bitwise AND with 0x000000FF, which is also written as just 0xFF, or 255 in decimal.

#include <stdio.h>

int getByte(int num, unsigned byteno)
{
    return (num >> (byteno * 8)) & 0xFF;    // Mask and return the required byte
}

int main()
{
    int num;
    unsigned byteno;

    printf("\nEnter a hex number: ");
    scanf("%x", &num);        // To take input number in hex, by using %x
    printf("\nEnter byte no to get (0 - 3): ");
    scanf("%u", &byteno);     // To take byte no in unsigned decimal, by using %u

    printf("\nByte no %u in hex representation: %x\n", byteno, getByte(num, byteno));

    return 0;
}
Read More
Anirudh

Check if two integers are equal without using any comparison operators

     No comments
Problem statement: Given two integers, you need to check if they are equal or not, without using any comparison operators.

Solution: An optimized solution can be given using bitwise XOR operator. The bitwise XOR of two numbers is 0 only if each corresponding bit in the two numbers is same, i.e. the numbers are equal.
int isUnequal(int a, int b)
{
    return a ^ b;    // Returns zero if the numbers are equal, else a non-zero value
}

Since (a ^ b) might be any integer value, we can strictly restrict the return value to either 0 or 1 like this:
int isUnequal(int a, int b)
{
    return !!(a ^ b);    // Returns zero if the numbers are equal, else returns one
}

Another simple solution could be using the minus operator:
int isUnequal(int a, int b)
{
    return !!(a - b);    // Returns zero if the numbers are equal, else returns one
}
Read More
Anirudh

Find the number of bits to be flipped to convert number A to number B

     No comments
Problem statement: You are given two numbers A and B. Write a program to count the number of bits needed to be flipped to convert A to B.

Example: Let A = 5 and B = 3, then they can be represented in binary as:
     A = 1 0 1
     B = 0 1 1
As can be seen, total 2 bits are needed to be flipped to convert A to B in this case.

Solution: This problem can be restated as to find the number of dissimilar corresponding bits in A and B. And the bitwise XOR operator (^) can help us in finding that. The XOR of two bits is 1 only when the bits are not same. So, our solution involves two simple steps:

1. Find the bitwise XOR of A and B.
2. Count the number of set bits in the result.

int countFlippedBits(int a, int b)
{
    unsigned int count = 0;

    /* Bitwise XOR of a and b */
    unsigned int x = a ^ b;

    /* Finding the no. of set bits in the XOR result */
    while (x)
    {
        count += (x & 1);
        x >>= 1;
    }

    return count;
}
Read More

Tuesday, 16 August 2016

Anirudh

Passing NULL to printf() in C

     No comments
Consider the following code snippet:
char *p = NULL;
printf ("%s", p);
What should be the output of the above code?

The printf() function with "%s" format specifier expects a '\0'-terminated array of characters (or string literal) whereas it receives a null pointer. Passing NULL to printf() is undefined behavior in C.

According to Section 7.1.4 (of C99 or C11): Use of library functions,
"If an argument to a function has an invalid value (such as a value outside the domain of the function, or a pointer outside the address space of the program, or a null pointer, or a pointer to non-modifiable storage when the corresponding parameter is not const-qualified) or a type (after promotion) not expected by a function with variable number of arguments, the behavior is undefined."

Some compilers may produce "(null)" written on the screen while others may give segmentation fault. GCC prints (null).

What is NULL?
NULL is a macro defined by several headers (including stdio.h, stddef.h, stdlib.h, string.h, time.h etc.) as a null pointer constant, typically 0 or ((void *)0). It is a value which is "guaranteed to compare unequal to a pointer to any object or function", as per C standard. That is, a null pointer points definitively nowhere - it is never the address of any object or function. The address-of operator '&' will never yield a null pointer, nor will a successful call to malloc() (malloc does return a null pointer when it fails).

Here is a program to demonstrate the effect of passing null pointer to printf() with different format specifiers.
/* Effects of passing null pointer to printf() */

#include <stdio.h>
int main()
{
    printf ("%s \n", NULL);  // Undefined behavior, prints (null) in GCC
    printf ("%d \n", NULL);  // The value of NULL macro (typically 0)
    printf ("%c \n", NULL);  // The ASCII character corresponding to the value of NULL macro
                             // (generally value is 0, so null character '\0', i.e. blank result).
    return 0;
}

Output in GCC:
(null)
0

Read More

Monday, 15 August 2016

Anirudh

The many different ways of swapping two numbers

     1 comment
One of the most seen snippets of code is the one that swaps the values of two variables. This little job is crucial to many algorithms, and there are multiple ways of doing it. Generally, for swapping two variables we use a temporary third variable, but various other ways do not even require the help of any third variable.
I find it very interesting that there are so many ways of doing this seemingly simple job and so, I thought to share all the ways I know of swapping two numbers...

1. The simple method using a third variable
#include <stdio.h>
int main()
{
    int a = 10, b = 5, temp;

    // Code to swap a and b:
    temp = a;
    a = b;
    b = temp;

    printf("After swapping: a = %d, b = %d", a, b);
    return 0;
}

Now let's look at some methods which do not require any additional variables.

2. Using arithmetic operators + and -
a = a + b;
b = a - b;
a = a - b;
The above way works well, but it may cause arithmetic overflow when adding large numbers.

3. Using arithmetic operators * and /
a = a * b;
b = a / b;
a = a / b;
This way will not work if one of the numbers is zero, as the product becomes zero. It may also cause arithmetic overflow when multiplying large numbers.

4. Using bitwise XOR operator ^
a = a ^ b;
b = a ^ b;
a = a ^ b;
This method is perhaps a bit more efficient, because it uses bitwise operator only. It can also be written in a more compact manner like this:
a ^= b;
b ^= a;
a ^= b;

Note: When using pointers to the variables, the above methods 2, 3 and 4 will fail if both the pointers point to the same variable. Example: If a function to swap two variables is accepting the addresses of the two variables, then a call like swap(&a, &a); should make no effect on the value of variable a, but in the above methods (except method 1) the variable will store incorrect value. So, we need to firstly check if both the pointers are exactly the same. A good example of using the above swap methods with pointers can be like:
void swap(int *x, int *y)
{
    if(x != y)    // Checking that x and y are not pointing to the same location
    {
        *x ^= *y;
        *y ^= *x;
        *x ^= *y;
    }
}

5. Using bitwise XOR operator ^ in one line
a ^= b ^= a ^= b;
This is similar to method 4 but three statements have been compounded into one. Order of evaluation is from right to left.

6. Using arithmetic operators + and - in one line
a = (a + b) - (b = a);
The problem of arithmetic overflow can occur in this method.

7. Using arithmetic operators * and / in one line
a = (a * b) / (b = a);
The problem of arithmetic overflow can occur in this method. Also, it will show undefined behavior if the first number a = 0 (because that will lead to division by zero).

8. Using arithmetic operators + and - in a slightly different way
a = b - a;
b = b - a;
a = b + a;
Note that the corresponding method with * and / operators does not work.

Note: The methods 5, 6, 7 and 8 also work well when using pointers to the variables. But methods 5 and 8 will give wrong result if the pointers point to the same location.

9. Using a file as buffer
FILE *fp;

fprintf(fp = fopen("temp.txt", "w"), "%d", a);
fclose(fp);
a = b;
fscanf(fp = fopen("temp.txt", "r"), "%d", &b);
fclose(fp);
Of course, using such a method incurs a lot more overhead than the usual methods. Just included for theoretical purposes.

10. Using a command-line-related variable as buffer
int main(int argc, char **argv)
{
    int a = 10, b = 5;

    argc = a;
    a = b;
    b = argc;

    printf("After swapping: a = %d, b = %d", a, b);
    return 0;
}

11. Using a macro
#define SWAP(x, y, Type) Type temp = x; x = y; y = temp;

int main()
{
    int a = 10, b = 5;

    SWAP(a, b, int);

    printf("After swapping: a = %d, b = %d", a, b);
    return 0;
}
Its advantage is that it is generic up to some extent. The same SWAP macro will work for types like int, float and char. By using this GCC-specific extension, we can improve it further like:
#define SWAP(x, y) typeof(x) temp = x; x = y; y = temp;
The problem with method 11 will arise when there is already a variable named temp in the program!
Read More
Anirudh

Puzzle: 100 statements

     1 comment
There are 100 statements.
1st one says: At least one statement is wrong.
2nd one says: At least two statements are wrong.
3rd one says: At least three statements are wrong.
4th one says: At least four statements are wrong.
...and so on till
100th one says: At least hundred statements are wrong.

Determine how many statements are actually wrong and how many are actually right?

Answer: Show answer
Let's start looking at the statements one by one. The 100th statement is definitely wrong because it says at least all 100 are wrong. But if that was correct, then the 100th statement itself cannot be right!
=> 100th statement is wrong
=> 1st statement is correct
(so far 1 wrong and 1 correct)

Similarly, the 99th statement says that at least 99 statements are wrong, i.e. maximum 1 among 100 may be correct, which we have already concluded that the 1st one is correct. But in that case, the 99th statement itself cannot be correct, because if we say that 99th is correct then we will get total 2 correct statements (1st and 99th), which is conflicting with the 99th statement itself.
=> 99th statement is wrong
=> 2nd statement is correct
(so far 2 wrong and 2 correct)

Calculating in a similar fashion, we will finally get the last 50 statements to be wrong and the first 50 statements to be right.

Read More

Sunday, 14 August 2016

Anirudh

Puzzle: Heaven or hell

     No comments
You are standing before two closed doors. One of the doors leads to heaven and the other one leads to hell. There are two guards, one by each door. You know that one of them always tells the truth and the other one always lies, but you don't know who is the honest one and who is the liar.

You can ask only one question to only one of them in order to find the way to heaven. What should be your question so that you can identify the door to heaven?

Answer: Show answer
This is one of the classic puzzles asked in interviews. The question you should ask is "If I ask the other guard about which side leads to heaven, what would he answer?". It should be fairly easy to see that irrespective of whom you ask this question, you will always get an answer which leads to hell. So you can chose the other path to continue your journey to heaven.

Here is the explanation: Let us assume that the left door leads to heaven. If you ask the guard who speaks truth about which path leads to heaven, he would say "left", as he always speaks the truth. So, if the liar is asked what "the other guard - the truth teller" would answer, he would lie and definitely say "right", which is the door to hell.

Similarly, if you ask the liar about which path leads to heaven, he would say "right". Now, when the truth teller is asked about what "the other guard - the liar one" would answer, he would fairly say "right", again the path to hell. So in any case, you would end up knowing the path to hell as an answer. So you can chose the other path as the way to heaven.

Read More
Anirudh

Implement a program that sorts given data according to the switch provided by the user

     No comments
Command line arguments, as discussed here, can be used to make a program run differently on different executions. The user is able to pass additional parameters while running a program, so that it can behave in different ways based on the user's request. We are going to implement one such program here.

Problem statement: Implement a program which sorts the data given in command line arguments according to the switch provided by the user, as explained below:
No switch : Sort lexicographically
-i : Sort lexicographically ignoring the case
-n : Sort numerically
-r : Sort numerically in reverse

Sample execution 1:
./a.out geek factorial aaa BCD 202 21
Sample output 1:
No switch detected. Sorting lexicographically:
202
21
BCD
aaa
factorial
geek

Sample execution 2:
./a.out -i BCD aaa
Sample output 2:
Switch -i detected. Sorting lexicographically ignoring the case:
aaa
BCD

Sample execution 3:
./a.out -n 101 30 60
Sample output 3:
Switch -n detected. Sorting numerically:
30
60
101

Sample execution 4:
./a.out -r 101 30 60
Sample output 4:
Switch -r detected. Sorting numerically in reverse:
101
60
30

Solution (using command line arguments as switches and a single sort function): We can test if the first argument provided is recognized as a switch, and then we can do the operations accordingly. The following C program works on this concept. It uses one sort function to sort data in any manner based on different comparison functions (the appropriate comparison function is passed to it via function pointer, after recognizing the switch).

#include <stdio.h>
#include <string.h>
#include <ctype.h>


/* The central sorting function which can take different comparison functions as argument via function pointer */
void sort(int argc, char *argv[], int (*compare)(char*, char*))
{
    int i, j;
    char *temp;

    for(i = 1; i < argc - 1; i++)
        for(j = 1; j < argc - 1; j++)
            if((*compare)(argv[j], argv[j+1]) > 0)  // Make comparison according to the passed comparison function
            {
                temp = argv[j];        // Swapping of pointers to strings, argv[j] and argv[j+1]
                argv[j] = argv[j+1];
                argv[j+1] = temp;
            }
}


/* Function to compare 2 strings (having numbers) numerically */
int compNum(char *s1, char *s2)
{
    int n1, n2;
    sscanf(s1, "%d", &n1);
    sscanf(s2, "%d", &n2);

    if(n1 > n2)
        return 1;
    else
        return 0;
}


/* Function to compare 2 strings (having numbers) numerically (according to reverse/descending order) */
int compNumReverse(char *s1, char *s2)
{
    int n1, n2;
    sscanf(s1, "%d", &n1);
    sscanf(s2, "%d", &n2);

    if(n1 < n2)
        return 1;
    else
        return 0;
}


/* Function to compare 2 strings lexicographically */
int compStr(char *s1, char *s2)
{
    if(strcmp(s1, s2) > 0)
        return 1;
    else
        return 0;
}


/* Function to compare 2 strings lexicographically (ignoring the case) */
int compStrIgnoreCase(char *s1, char *s2)
{

    /*
       We can use strcmpi(s1, s2) function to compare 2 strings ignoring their case. But strcmpi() is not a standard C function and may not work on every platform.
       Similarly, strlwr() and strupr() functions that can convert a passed string to lower and upper case respectively can be used here, but they are also non-standard.
       So, we should prefer using tolower() (or toupper()) functions which are standard functions defined in the header file "ctype.h" to convert a passed character variable to lowercase (or uppercase).
       We can convert strings to lowercase (or uppercase) character-by-character, as done below, and then compare them using strcmp(s1, s2) function.
    */

    int i;
    char s11[strlen(s1)+1], s22[strlen(s2)+1];  // Make copy of strings and convert them to lowercase
    for(i = 0; s1[i]; i++)
        s11[i] = tolower(s1[i]);
    for(i = 0; s2[i]; i++)
        s22[i] = tolower(s2[i]);

    if(strcmp(s11, s22) > 0)  // Compare the duplicated and lowercased strings
        return 1;
    else
        return 0;
}


/* Function for left shifting the array of strings by one, to remove the first string having the switch, and reduce argc by 1 */
void leftShift(int *argcPtr, char *argv[])
{
    int i;
    for(i = 1; i < (*argcPtr) - 1; i++)
        argv[i] = argv[i+1];  // Just make each argv[i] poiner point to the next string

    (*argcPtr)--;  // Reduce (*argcPtr) by one
}


/* Main function */
int main(int argc, char *argv[])
{
    int i;

    /* Check if no arguments are provided, then return */
    if(argc == 1)
    {
        printf("\nNo input command line arguments provided.\n");
        return 0;
    }

    if(strcmp(argv[1], "-n") == 0)         // Switch "-n" was given
    {
        /* Left shift the array of strings by one to remove the string having the switch, and reduce argc by 1 */
        leftShift(&argc, argv);

        printf("\nSwitch -n detected. Sorting numerically:\n");
        /* Call sort() function with appropriate comparison function passed as argument */
        sort(argc, argv, compNum);
    }
    else if(strcmp(argv[1], "-r") == 0)    // Switch "-r" was given
    {
        leftShift(&argc, argv);

        printf("\nSwitch -r detected. Sorting numerically in reverse:\n");
        sort(argc, argv, compNumReverse);
    }
    else if(strcmp(argv[1], "-i") == 0)    // Switch "-i" was given
    {
        leftShift(&argc, argv);

        printf("\nSwitch -i detected. Sorting lexicographically ignoring the case:\n");
        sort(argc, argv, compStrIgnoreCase);
    }
    else                                   // No switch identified
    {
        /* No need to left shift the array of strings as there is no switch */

        printf("\nNo switch detected. Sorting lexicographically:\n");
        sort(argc, argv, compStr);
    }

    /* Print the result */
    for(i = 1; i < argc; i++)
            printf("%s\n", argv[i]);

    return 0;
}

The above program runs like this:
./a.out geek factorial
No switch detected. Sorting lexicographically:
factorial
geek

./a.out -n 67 45 23 32
Switch -n detected. Sorting numerically:
23
32
45
67

./a.out -r 67 45 23 32
Switch -r detected. Sorting numerically in reverse:
67
45
32
23
 
./a.out
No input command line arguments provided.
Read More
© Copyright 2016 Geek Factorial Powered by Blogger