How to prevent this program from printing anything?

Place something instead of blanks to prevent below program from printing anything.

#include <stdio.h>

int main() {
    if (     ) {
        printf("foo");
    }
    else {
        printf("bar");
    }

    return 0;
}

Read More

German tank problem

Sometimes science is applied in really amazing ways, one of examples is German tank problem. During World War II, the Allies observed that the Nazis created a new model of tank. Total number of manufactured units was unknown, but the Allies, know serial numbers of some tanks. In this case, the first produced tank has serial number starts = 1, the second has serial number = 2, etc. How the Allies could estimate total amount of manufactured tanks?

Answer may be estimated by using simple equitation. Let's assume that N = estimated total amount of enemy tanks, k = amount of observed tanks, m = maximum observed serial number. Then:

N = m - 1 + m/k

Example

We observed enemy tanks with serial numbers: 20, 23, 45, 47, 48. In this case, m=48, k=4, answer can be computed on calculator or for example in R language (I really like to use it as a powerful "calculator"):

> 48 - 1 + 48/4
[1] 59

Other use cases

The same as used for German tank problem was used to estimate amount of sold Apple's products. The customers were asked to upload their serial numbers.

Read More

How does recursive packing of a file changes its size?

How the size of a packed file will change if you will pack it again? How will it change if you do that again and again? Will it be the same, bigger of smaller? I checked this with popular kinds of files and below I will show the results. I used Bash script and R language to check this. Charts shows how the file size changes in each iteration, first bar is the size of original, unpacked file.

Read More

How to sort numbers from STDIN

You get 10 numbers on STDIN, each followed by newline character, after that you have to display those numbers sorted from the smaller to the bigger. You cannot use sorting algorithms.

Read More

The riddle of the stolen wood

Sometimes piles of wood are marked by paint to protect them against thiefs. Continuous line is painted on the trees that are on the top of the pile, if one will steal some of them, then painted line on remaining stack will be discontinuous. To illustrate this tactic I made below picture:

If a thief would like to hide his crime, then what should he do? Present an algorithm to take n% of original trees and leave continuous red line on the remain pile.

Read More

3 x if

Below snippets in C check if foo() and bar() returns nonzero value and execute something() if needed. Are they equivalent? Why?

    // first version
    if (foo() && bar()) {
        something();
    }

    // second version
    if (bar() && foo()) {
        something();
    }

    // third version
    if (foo()) {  
        if (bar()) {
            something();
        }
    }

Read More

[Riddle] simulation of behaviors in population

There are things that aren’t interesting because they are complicated, but because they have simple solutions. Today I will present one of those riddles that comes from the book "THE SELFISH GENE" by Richard Dawkins. You can find there more of such stuff and all is presented from biological point of view, far away from informatics.

Consider this problem: in population, in given situation, species may behave in two ways: as a fighter or as a coward. Fighter always wins fight with coward. This behavior is set by a single gene, if a specimen behave in a way that give him an advantage, then he is in a better position and will have more descendants. For us it means that his gene have better chance to spread in population.

Assume that species don’t remember behavior of other species and that they can’t predict it. Score function that says, how profitable the behavior is will be needed – we will use arbitrary numbers, like in the book: let's attribute +50 points to win, 0 to fail, -10 to waisting time, -100 for serious damage.

• Coward meets Coward, the winner gets +50 points, both of them get -10 points for waisting time (they could do something valuable instead). Those -10 points are here because cowards waist time on trying to make their opponents scary, if they can't do that they run away,
• Coward meets Fighter, the winner gets 50 points, the loser gets 0 points, as we said, fighter always wins with coward,
• Fighter meets Fighter, the winner gets 50 points, the loser gets -100 points for a serious damage.

At the beginning there are only cowards - nothing interesting for us. When fighter (obviously a mutant) appears in population, then he is in a privileged position, his genes spreads quickly. Situation changes when fighters become dominant part in the population, then it’s much better to be a coward. At first it looks like amount of fighters and cowards will changes periodically, in fact it will go into a stable ratio (there is a lot of math here, but it’s not important here). The goal is to display at each generation the percentage of cowards and fighters in population (this should summarize to 100% ofc). There is a given number of generations to show and initial generation (again in a form of percentages of cowards and fighters).

We will use following notations:
sf – score of all fighters in generation
sc – score of all cowards in generation
pf – percentage of fighters in generation
pc – percentage of cowards in generation

Score function may be described as:

sf = (-25 * pc) + (50 * pf)
sc = (15 * pc) + (0 * pf)

As we will see later, it would be better if values of s_f and s_c would be non negative. We will be also interested rather in ratios that in concrete values, so we may add constant value to both equations:

sf = 25 + (-25 * pc) + (50 * pf)
sc = 25 + (15 * pc) + (0 * pf)

Now percentage of cowards and fighters in next generation may be counted simply:

pf = sf / (sf + sc)
pc = sc / (sf + sc)

Implementations in C and in Haskell.

#include <stdio.h>
#include <stdlib.h>

int main() {
    double pg = 0.9, pj = 0.1;

    const unsigned iters = 20;
    unsigned i;

    for (i=0; i<iters; i++) {
        printf("pg: %1.2f pg: %1.2f\n", pg, pj);

        double zg = 25 + (15 * pg) + (0 * pj);
        double zj = 25 + (-25 * pg) + (50 * pj);

        pg = zg / (zg+zj);
        pj = zj / (zg+zj);
    }

    return EXIT_SUCCESS;
}

main = generate (0.9, 0.1) 20

generate _ 0 = putStr ""
generate (pc, pf) iterations = do
                putStrLn ("pc: " ++ (show pc) ++ ", pf: " ++ (show pf))
                generate (new_pc, new_pf) (iterations-1) where
                                new_pc = sc / (sc + sf)
                                new_pf = sf / (sc + sf)
                                sc = 25 + (15 * pc) + (0 * pf)
                                sf = 25 + (-25 * pc) + (50 * pf)

Read More