Google and eggs

One of the famous "google puzzle" - questions asked while applying for a job in Google.

There's a 100 stories building, and you have 2 eggs. You need to find out which is the highest story you can throw the egg from, and it will stay intact with the minimal throws possible. If you threw and egg and it did not break, you may throw it again. We assume that egg always breaks when throws from 100th story.

First solution

Simply throw an egg starting from 1th story and go up until egg breaks. In the worst case you need 99 throws.

Second solution

Start from 50th floor than go up (if egg does not break) or down (if breaks). In the worst case you need 50 throws (1+49).

General solution

Take number N  (N > 0 and N < 100) than start throwing the first egg by 100/N, 2 * (100/N), 3* (100/N) until 100 is reached or egg breaks (assume that it is k*(100/N) story). Than take the second egg (or first if still in one piece) and start throwing from (k-1)(100/N).

The number of trials in the worst case is (100/N) -1 + N-2.

The question : what is the minimum of this function ?

Solution, very simple using basic analysis

(derivative) 


The F is minimal when F'(N) is equal 0, so it is minimal for N=10.

Answer

The worst case takes place if the "breaking" store is 100.
So you throw egg starting from 10,20... to 90 (9 trials). Then start 91...98 (8 trials) - it is not necessary to throw egg when 98th store does not break.
The minimum number of throws is 17.

Addition remark.

The worst case takes place when the breaking store is 89.  In this case the number of throws is 16 (8+8). In the case of 99 floor we still have 2 eggs. So we can throw from 93 and 96th floor and go on accordingly using less than 16 throws

So the final answer is: 16 throws.

Byliśmy na koncercie

VII KONCERT ORGANOWY

Byliśmy na koncercie muzyki organowej dnia 25 października 2009. Po wejściu do kościoła uderza wystrój wnętrza - a ścisle rzecz biorąc, brak takiego wystroju. Gdyby nie krzyż stojący w miejscu, gdzie na ogół jest spodziewany ołtarz, można by odnieść wrażenie, że to synagoga. Ale to co przykuwa uwagę osoby z zewnątrz, jest normalnym widokiem dla wiernych Kościoła Ewangelicko-Reformowanego, inaczej zwanego kalwinizmem. Gdy rozglądałem się po kościele przychodziły mi na myśl lekcje historii z XVI wieku, reforma zapoczątkowana przez Lutra, Kalwina i Zwinglego, konflikty i dysputy z Kościołem Katolickim dotyczące odpustów, kultu świętych, obrazów i rzeżb o treści religinej czy kultu maryjnego. Dysputa aktualna po dziś dzień, ale na szczęście prowadzona w nie tak gwałtowej formie.

Wykonawca muzyki,  Michał Markuszewski, powiedział we wstępnym słowie, że intencją koncertu jest pokazanie organów, niemal automatycznie wiązanych z Bachem i epoką baroku. jako instrumentu służącego do wyrażania bardzo różnorodnej muzyki. Na poczatek usłyszeliśmy więc dwa utwory wchodzące w skład tzw. Gdańskiej Tabulatory Organowej, utwór Bextehudego, mistrza i wielkiego poprzednika Bacha i monumentalną. wypełniającą cały kościół "Fantasia super Komm, Heiliger Geist, BWV651" najsłynniejszego lipskiego organisty.

Potem koncert wypełniły utwory niemieckich kompozytorów romantycznych, muzyka romantyczna rzadko kojarzy się z organami. Lącznikiem był sam Mendelssohn-Bartoldy, który wydobył muzykę Bacha z otchłani zapomnienia i ponownie wprowadził do światowego obiegu muzycznego. Mendelssohna niestety spotkał także trochę podobny los co Bacha. Nieustającymi przebojami są utwory symfoniczne czy koncerty jak. np uwertura do Snu Nocy Letniej, symfonie lub słynny koncert skrzypcowy, ale pozostałą muzykę tego kompozytora rzadko się wykonuje i troche pokryta jest kurzem. Tutaj zostały przypomnianie dwa preludia i fugi - w pierwszej chwili uderzająco podobne do muzyki Bacha, ale jak uważnie posłuchać, to jest oczywiste, że to muzyka całkowicie odmienna.

Dalej mieliśmy muzykę mniej znanych w Polsce kompozytorów, jeden z nich, August Fryer, swoje życie związał z Polską i Warszawą. Były to zarówno utwory potężne i dynamiczne jak "Toccata ze Suity Gotyckiej" Boellmana, subtelna i wyciszona muzyka religijna Augusta Freyera, a także "Romanze" Josepha Rheinbergra.

Utwory wykonane na bis konsekwentnie domykały cały koncert, były to zagrane i stworzone na gorąco improwizacje wykonawcy. Jednym bisem była powolna i spokojna melodia troche przypominająca sentymentalne tematy z holywoodzkich filmów. Drugim bisem była improwizacja oparta na motywie popularnej pieśni kościelnej "Wszystkie nasze dzienne sprawy". Zwłaszcza ten drugi bis jest dobrym podsumowaniem całego koncertu. Pobożna pieśń śpiewana współcześnie przez wiernych na zakończenie wieczornego nabożeństwa, ale autorem jest Franciszek Karpiński. Sam Karpiński jest zaliczany do oświeceniowego nurtu naszej kultury, ale jako autor sentymentamych slelanek jest także zwiastunem romantyzmu. Pieśń jest obecna w tradycji pobożności katolickiej, ale tutaj grana na organach w surowym wnętrzu protestanckiego kościoła. Bardzo dużo różnorodnej treści ujętej w kilkuminutowym, wytworzonym sztuką wykonawczą, organowym utworze.

To samo mozna powiedziec o calym koncercie. Tak naprawdę jedynym czynnikiem łączącym jest tylko sam instrument, poprzez który artyści na przestrzeni wieków i epok wyrażali najróżniejsze intencje i emocje, stosując bardzo róznorodną estetykę.

Cały koncert bardzo nam się podobał, ogromnie załowaliśmy, ze umknęło nam sześć poprzednich koncertów z tego cyklu.

Singleton without private constructor and static getInstance metod

Create SingletonFactory class. This class is the owner of the one Singleton instance. Add also a static switch "already created" and use this switch in constructor (public) to break the second and next Singleton initialization.

Code snippet below:

singleton.h 

#include <iostream

class Singleton {
public:
  Singleton() {
     if (exists_already) {
        std::cout << "You mustn't do that !" << std::endl;
        // failure action !!!
     }
     else {
       std::cout << "Singleton first init" << std::endl;
       exists_already = true;
     }
  }

  void singleAction() {
     std::cout << "Run single action" << std::endl;
  }

private:
  static bool exists_already;
};

SingleFactory.h

#include <singleton.h>

class SingleFactory {

  public:
    static Singleton *getInstance() {
      return &single;
    }

  private:
    static Singleton single;
};

SingleFactory.cpp
(pay attention that it keeps movables belonging to Singleton class)

#include <singlefactory.h>

Singleton SingleFactory::single;
bool Singleton::exists_already = false;

and finally the usage example
main.cpp

include <iostream>
#include <cstdlib>
#include <singlefactory.h>

using namespace std;

int main(int argc, char *argv[])
{
  Singleton *n = SingleFactory::getInstance();
  cout << "Hello, world!" << endl;
  n->singleAction();
  Singleton *nextS = new Singleton();
  Singleton singleS;


  return EXIT_SUCCESS;
}

Math exercise and proof

(Michał Krych - Analiza Matematyczna część 1)

Assume that we have N positive numbers and the sum of this numbers is not greater than N.



Prove that multiplication of this numbers is not greater than 1.


Proof                                                                                                        
Assume that all number are equal - obvious.
Assume that not all numbers are equal.

Induction proof.
The statement is satisfied for N=1 - obvious.

Inductive step.
Assume that statement holds true for all 1...N-1
Now consider a set of N positive numbers, call their sum as S(n) and assume that S(n) is less or equal N. Call the product if this numbers as P(n).
Because the numbers are not equal at least one should be greater than 1 and at least one should be less than 1.
Call them a1 = 1 + x and a2 = 1 - y.
Consider set of N-2 number (all numbers except a1 and a2) and call its product as P(n-2) and sum as S(n-2)
Than add to this set the number 1 + x - y. This number is positive and call the sum of this numbers (including 1 + x - y) as S(n-1).

Call the product as P(n-1). Using the induction hypothesis P(n-1) is less or equal 1.

Now let's calculate P(n). Keep in mind that x*y is greater than 0.

Q.E.D

When to use void* pointer

What is void* pointer in C++ ?
By standard it is a pointer to an object of unknown type ( of course, if not null).
"Unknown" means unknown for one type of users and known to the other type of users, particularly to the owner of this "unknown" type.
An example of usage of void* pointer is a proxy pointer to something which internal structure should be hidden, secret or invisible.

http://code.google.com/p/javahotel/wiki/UseVoidPointer#Top_secret_usage_of_void_pointer

"secretpointer" can point to anything but this way we get off C++ object oriented paradigm.

Another way is to split class declaration into two parts: public and private/hidden. Nothing new, one can say, all the time we can have public and private declarations in a class definition. But the disadvantage of the standard approach is that not only public but also private method and attributes should be exposed in a class declaration. Also every change in a private section involves recompiling the users of this classes. Below is an example of class splited into public and hidden part.

http://code.google.com/p/javahotel/wiki/UseVoidPointer#Partially_secret_class_definition

Migration to Google App Engine and unit testing.

Summary

This post describes how to migrate existing test cases (JUnit4) to Google App Engine keeping backward compatibility. It extends solution described under link http://code.google.com/intl/pl/appengine/docs/java/howto/unittesting.html. The method described here is about testing in the local environment, it cannot be applied to the production environment.

Introduction

Like the main application it is unlikely to achieve 100% source compatibility while migrating test cases to Google App Engine.  But it does not mean that rewriting the whole test suite is necessary, quite the opposite. With minimal effort it is possible to set up environment where existing test cases can be executed and, what also very important, starting from that point the common test suite can be developed further without bothering about migrating and portability problems.

It is very good programming technique to have server side code separated from the client side and being tested independently. After porting application to Google App Engine further development should cover both frameworks, so keeping common and concise suite of tests plays very important role.

Google App Engine JPA/JDO implementation requires setting up additional environment - how to accomplish it is descibed under link http://code.google.com/intl/pl/appengine/docs/java/howto/unittesting.html. The disadvantage of this solution is that it is specific for Google App Engine, so a naive approach will break backward compatiblity. Additional code should be injected for Google App Engine and not Google App Engine testing but applying an injection framework (like Guice) for very simple and only one task is like using a steam hammer to crack a nut.

Solution description

Details:

http://code.google.com/p/javahotel/wiki/GooglaAppEngineUnitTesting


Addtional remarks.

• In this example the amount of framework specific code is greater than framework independent code. But the amount of framework specific code is the same regardless of the application size. In real application the common code (data access service and test cases) is  huge and advantages of this approach is more visible.

• Testing Google App Engine that way does not have sandbox restriction enabled (http://code.google.com/appengine/docs/java/jrewhitelist.html). So even having all tests passed does not guarantee that everything will run smoothly.

Math exercise and proof

Exercise from "Michał Krych, Analiza Matematyczna część 1".

Assume that we have an infinite grid filled with natural numbers. Every number P and four number a,b,c,d in adjacent cells should satisfy the equation 4*P <= a + b + c + d.
Prove that all numbers in grid are equal.






Proof                                                                                                                       

Notice that grid filed with equal numbers holds statement.

Assume that there exists a grid which satisfy equation and have different numbers.

Inductive proof.

Assume that P = 1. It involves that a,b,c,d should be also equal 1 because it is the only way to satisfy equation. The same can be applied for a, b,c d and their adjacent cells and on. So having number 1 in one cell cause all grid being filled with 1. So we have to exclude number 1 from grid.

Assume that all numbers from 1 to N are excluded. Look at the cell with number N+1 and having at least one number different than N+1 in adjacent cell (assume number a). "Different" means greater then N+1 because all number less than N are excluded. But if a > N and b, c and d  >= N then a+b+c+d > N which breaks equation.

That means that all natural number are excluded from the grid and the only grid holding statement must have all number equal.

Byliśmy na koncercie

29 września 2009 rok.

http://www.dkpraga.pl/index.php?option=com_eventlist&view=details&id=90&Itemid=71

Bardzo nam się podobało. Okazało się, że znany koncert organowy Handla bardzo  ładnie brzmi, nawet jeśli orkiestrę stanowi kwartet smyczkowy.Bardzo brawurowo zabrzmiało wykonanie kwartetu smyczkowego Mendelssohna.

W przeciągu godziny koncertu zaprezentowano cały przekrój muzyczny, od wielkich klasyków: Handla, Mendelssohna-Bartholdyego oraz Józefa Haydna aż po muzykę współczesnego kompozytora.

Ale to co było zaletą było także wadą. Za dużo muzyki wtłoczonej w krótki czas powodowało, że niestety nic się specjalnie nie utrwaliło w pamięci. A wielka szkoda, na przykład z wielką przyjemnością byśmy posłuchali dłużej muzyki Jarosława Ciecierskiego (zarazem organisty), ale zanim się na dobre zaczęło juz się skończyło. Gdzieś się zagubiła niestety gra organisty, za wykonanie muzyki Louisa Vierna nie zebrał oklasków. Ponieważ jest to mało znany kompozytor, więc publiczność zapewne nie zorientowała się, kiedy miał miejsce koniec. Na pewno przydałoby się tutaj jakieś wprowadzenie.

To jednak są drobiazgi, była to bardzo miło spędzona godzina.

Innym problem było słabe rozreklamowanie samego koncertu, w kościele naliczyliśmy może 30-40 osób, część z nich to zapewne osoby z parafii zachęcona ogłoszeniami parafialnymi.

Jest to jednak dopiero druga edycja Praskiego Festiwalu Muzyki Kameralnej i Organowej, to wspaniałe, że na bardzo ubogim muzycznym firnamencie Warszawy pojawiła się nowa gwiazda, miejmy nadzieję, że na stałe.