Saturday, June 11, 2011

C : thank you for the memories

C is in general a quite free language, in a sense that it usually compiles! However, when it comes to running, even the most experienced programmers get errors or values that they wouldn't expect.
The most common error is a segmentation fault. This happens when your program tries to write or read a memory location out of its bounds, so the operating system does not allow it.
In addition, sometimes, you get some unexpected values, because you accidentally read a wrong memory location that belongs to your program, so the operating system does not block it. Furthermore,somebody can write accidentally a piece of code that might cause the program to freeze:
Imagine you want to create an array of length 10 and initialise it with 0 values.
What would happen if you write this (by mistake of course)

int main()
    int a[10];
    int i = 0;
    for (;i<=10; i++)
            a[i] = 0;

Why your program freezes? What would happen if you read the array without putting initial values in it if you print it out?
Can you guess what would happen if you read a[10]?
Try it! It's really fun!
by VasLabs

Wednesday, June 8, 2011

Text File Encryptor

Here is the idea. Create a simple program that changes the bytes of a file using a passphrase in a such way that they can be revered to their initial state.
Of course this program is not suitable for commercial use because the encryption is very simple. But you get the idea.
The program is written in java and you can download the source code and the compiled program from there:

ByteReader source code
ByteReader byte code
ByteEncryptor source code
ByteEncryptor byte code
DataEncryptor source code
DataEncryptor byte code

The process is:
We have an object ByteReader that reads the contents of a text file using a BufferedReader which wraps a FileReader. It reads it line by line to avoid reading dumb null bytes (it happened when we used InputStreamReader, no idea why!
After that we convert each character of the line to an int! And then we store it in a variable such that b = object ByteReader and b.bytes[][] = thearray of ByteReader that keeps the bytes read.

Then we create another object, a ByteEncryptor which takes as one of its arguments the byte reader and according to another argument password and whether to subtract from the value of the bytes or add(i.e. 0 or 1) as another argument. It also takes the number of lines and the destination to store the encrypted data.

It encrypts each byte with the simplest calculation that exists!
for each byte
byte = byte + (passphrase.hashCode() % 91)
and decrypts
byte = byte - (passphrase.hashCode() % 91)

Some notes to have in mind!
1) Never use this program on important data! They might be corrupt! Use it only on test data that you don't mind to lose!
2) It fails to decrypt images, videos, pdf and similar formats. Do you suspect why?
3) Never use this program to encrypt data and feel safe! Can you think of a simple program that it can decrypt these data without knowing the password? If yes, let others know! (We know :) )

To run the program open a terminal the directory you saved the files and then run
java DataEncryptor yourFileYouWantToEncrypt destinationFile password 1/0

1 is for adding, ie encryption, 0 is for subtracting, ie decryption.
Do not run it the first time with the value 0, you may not be able to recover it, and also remember the notes above.
If you put less arguments you will get an ArrayIndexOutOfBoundsException, i.e. the program will crash.
You can make whatever changes you like on this program since it's just a simple silly one that aims to excite your imagination for building similar things, more sophisticated. So, it is not licensed and there is no copyright.


Tuesday, June 7, 2011

The MontyHallProblem

The Monty Hall problem is as follows(stated in wikipedia):
The Monty Hall problem is a probability puzzle based on the American television game show Let's Make a Deal that was originally hosted by Monty Hall. The problem, also called the Monty Hall paradox, is a veridical paradox because the result appears odd but is demonstrably true. The Monty Hall problem, in its usual interpretation, is mathematically equivalent to the earlier Three Prisoners problem, and both bear some similarity to the much older Bertrand's box paradox.

In a few words
Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?
 Furthermore the Monty Hall problem is briefly discussed in the movie "21 Blackjack".
The answer in the question switch or not is given but without a mathematical analysis.
The mathematical solution for this problem is based on Bayes' Theorem. This article, however, does not aim to explain Bayes' Theorem, but how we use it to create a program in java that will give us the best solution for N doors.
The steps is that you choose a door, and Monty Hall opens a door other that yours and the winning door. In each stage you choose to switch or stick to your choice. This process is until there's nothing left but two closed doors, yours and another one.

So let's say we have N doors. The prior probability of each door to have the car behind it is obviously 1/N

So, let's say D is the set of containing all closed doors, such that its initial value is
P(D) = 1
(That means that the car is behind of a closed door)
and card(D) = N
(that means that D has N elements)

         P(L) = 1/N
(this means that each door that is a closed door has probability be the right door of 1/N)

So now Monty Hall opens a door b other than your door you chose.
D = D-{b}
P(D) = 1

Now for every door that is closed the probability changes.
Let Oi be the event that Monty Hall opens a door i, and P(Oi | L) be the probability that
he opens door I by knowing that the right door is L.
so if L = "your door" ⇒ i is a door other than L

so P(Oi | L) = 1/(N-1)
Wonder why? think about it. He knows that you choosed the right door, so he has a range of N-1 doors to choose.
He wouldn't open the right door (that's the rules) and so if L = i ⇒ P(Oi | L) = 0
Now what happens if the door is not the door you chose?
if (L ≠ your door) and (L ≠ i) then
  P(L) = 1/(N-2)

If you still wonder why count how many doors left for Monty Hall to choose.

Now, we have to update our probabilities of belief for each door. We must forget the prior probabilities we begun because they have no meaning any more.

So we've found those probabilities of opening, how do we find the new probabilities for each door?

Using Bayes' theorem to find the probability that L is the right door under the event that Moonty Hall opened door i
P(L | Oi) = P(Oi | L)p(L) / (∑P(Oi | d)P(d))

So for each step you must do the same thing, and in the end you will have your probability.

You can ask for questions on facebook or below this article

If you find the solution in a language other than Java we would be glad to share it with us along with your name!

Solution is uploaded, you can find the source code here and the byte code there!