Monday, October 22, 2012

Sixth IEEE Xtreme Programming Contest: Bunnies in the Forest

At the annual IEEE Xtreme Programming Contest teams of three programmers are given a set approximately 20 problems, for which they have to write a program that solves the task. Choice of programming language is mostly free; the contest system supports Java, C, C++, C#, PHP, Python, Ruby. The contest goes on for exactly 24 hours, therefore the "Xtreme" in its name. In the 2012 issue, there had been 1900 teams worldwide. To be successful, it is necessary to work concentrated under pressure for hours and have excellent programming skills. In fact it is rather software engineering skills, since a sloppy or ad-hoc programming style does not lead to successful solutions. Watching a good team one can observe the classic stages of software engineering like specification of operational and performance qualification, design specification, implementation, black box/white box testing, and validation in a fast-forward manner within a few hours.


One important aspect of software engineering is also the proper specification of the intended project by the customer. A mistake in the initial specification is crucial, so it is important to state a task in a clear unambiguous manner. In practice, unfortunately, a software engineering team often has to guess what the customer really wants. This was the case for problem AA at IEEE Xtreme 2012:

In a forest, there were 'x' bunnies, 50% male, and 50% female, all adults. Bunnies doubles every 15 days, 10% of the baby rabbits dies at birth. They mature after 30 days, 30% leave the forest, and rest becomes rabbits. In every 30 days , 25% dies off due to flu. If every bunny dies off, the bunny world ends. Calculate the final number of bunnies alive after 1 year for any number of initial bunnies, x.

The problem is very interesting since it defines a simulation of an ecologic system. See for comparison the description of the Lotka Volterra system featuring rabbits and foxes. However, the problem specification is unclear in many aspects. What is the essential difference between an "adult bunny", a bunny, a "baby bunny" and a rabbit? It is not mentioned how to handle rounding, if the leaving of the forest happens once for a group that just matured or if an adult rabbit is tempted to leave the forest every time.

The problem had been complemented by these two test cases:
Test Case 1
444 (input)
0 (output)
Test Case 2
30000 (input)
56854 (output)
So a group of 444 dies out after one year, while a group of 30000 almost doubles. Given that the described effects are all linearly superimposable (except for possible rounding errors), it seems odd how the two groups yield so different results. 30000 is around 68 times as much as 444, so the results just also differ by that factor. The following python program implements one possible interpretation of this problem:
b0=0            #newborn bunnies  
b15=0           #15 day old bunnies 
b30=input()     #30 day old, read from stdin
for i in range(25): #one year
    print "t:",(i*15)," bunnies:",(b0+b15+b30)
    oldb0=b0
    b0=int(b30*0.9) # babies, 10% die
    b30=int(b30+b15*0.7) # maturing, 30% leave forest
    b15=int(oldb0)
    b0=int(b0*0.75)      # 25% die off by the flue
    b15=int(b15*0.75)    # 25% die off by the flue
    b30=int(b30*0.75)    # 25% die off by the flue

Running the program gives us 772 bunnies after one year with a starting population of 444 and 54816 for a starting population of 30000, both in contradiction to the test cases. Obviously the specification is unclear or wrong. Among all 1900 participating teams, not a single one was able to find the correct solution. Poor bunnies :-)

On rabbits and foxes, see also section 2 of

5 comments:

  1. Hello prof. Wilfried Elmenreich :
    I wrote a code in c# that tries to solve the Forest bunnies case, when I read your blog i discovered that my code is 80% similar to your code so it will be so nice if if you give me your opinion ,because this will help me a lot to know how much i understood the requirement and how good i implemented it : my code is written by c# as follows :


    int CalcBunnies(int InitialBunnies)
    {
    int _intMatureBunnies = 0;
    int _intOldAdultBunnies = InitialBunnies;//because they are adult this means that 15 day left
    int _intNewAdult = 0;
    int _intNewAdultTemp = 0;
    int _intTotal = 0;
    for (int i = 1; i <= 24; i++)//24 of 15days
    {

    if (i % 2 == 0)//after 30 day
    {
    _intMatureBunnies += (int)(_intOldAdultBunnies * .7);//Old Become Mature
    _intNewAdultTemp = _intNewAdult;
    //calculate New Adult ,i added OldBunnies to the previous newAdults because Oldbunnies and NewAdults
    //are still being adults so we will assume that 10% of their childs will day
    _intNewAdult = (int)((_intOldAdultBunnies + _intNewAdult) * 0.9);
    //_intNewAdult = (int)(_intNewAdult * 0.9);//calculate New Adults
    _intOldAdultBunnies = _intNewAdultTemp;//New Become Old


    //====25 % of bunnies die=================
    _intNewAdult = (int)(_intNewAdult * .75);
    _intOldAdultBunnies = (int)(_intOldAdultBunnies * .75);
    _intMatureBunnies = (int)(_intMatureBunnies * .75);


    _intTotal = _intNewAdult + _intOldAdultBunnies + _intMatureBunnies;

    }
    else//after 15 day
    {

    //because old adults and new adults are still adults we will assume that both of them will be duplicated
    _intNewAdult = (int)((_intOldAdultBunnies + _intNewAdult) * 0.9);

    }

    }

    return _intTotal;

    }


    Thanks alot

    ReplyDelete
  2. Dear Mahmoud, your approach is similar, but I think your concept of "adult" is wrong. I would connect the concept of "adult" with "mature". In your simulation you have the newborn already doubling within 15 days, which leads to very high numbers of your rabbit population even for small starting values (444 bunnies become 154936 after one year). I doubt also your approach with "if (i % 2 == 0)" - once new rabbits are born every 15 days you will also have maturing events every 15 days instead of 30.

    ReplyDelete
  3. Dear Prof.Wilfried Elmenreich let me thank you for your reply and your effort .i totaly agree with your point of view ,i misunderstood the adult meaning .but i think i could use "if (i % 2 == 0)" to calculate the bunnies dies due to flu because the case did not mention that they die every 15 day so my code will be as follows :
    int CalcBunnies(int InitialBunnies)
    {
    int _intMatureBunnies30 = InitialBunnies;
    int _intOldAdultBunnies15 = 0;
    int _intNewAdult0 = 0;
    int _intNewAdultTemp = 0;
    int _intTotal = 0;
    for (int i = 1; i <= 24; i++)//24 of 15days
    {

    _intNewAdultTemp = _intNewAdult0;

    _intNewAdult0 = (int)((_intMatureBunnies30) * 0.9);

    _intMatureBunnies30 += (int)(_intOldAdultBunnies15 * .7);//Old Become Mature

    _intOldAdultBunnies15 = _intNewAdultTemp;

    if (i % 2 == 0)//after 30 day
    {
    //====25 % of bunnies die=================
    _intNewAdult0 = (int)(_intNewAdult0 * .75);
    _intOldAdultBunnies15 = (int)(_intOldAdultBunnies15 * .75);
    _intMatureBunnies30 = (int)(_intMatureBunnies30 * .75);
    }
    _intTotal = _intNewAdult0 + _intOldAdultBunnies15 + _intMatureBunnies30;

    }

    return _intTotal;

    }

    ReplyDelete
    Replies
    1. "In every 30 days , 25% dies off due to flu." makes sense to do it your way. If I change my program by adding a condition for the flu to appear only every second iteration it creates almost the same values as your program. The remaining differences are because of rounding errors which are different for different programming languages.
      e.g. in Python, int(1680*0.7) evaluates to 1176
      in C/C++, there is a rounding error which makes (int)(1680*0.7) evaluate to 1175

      Delete
    2. Dear Mr. Elmenreich,
      I tested your statement as follow :
      Console.WriteLine("Rounding error test: 1680*0.7=1176=[{0}?]", (int)(1680 * 0.7));
      and it did output the right value :
      > Rounding error test: 1680*0.7=1176=[1176?]

      I understand it could be a rounding problem, but not with the given case of 1680*0.7.


      Delete