oaltman · April 25, 2014 14:08
diff --git a/gistfile1.txt b/gistfile1.txt
 Úkolem je realizovat sadu funkcí, které budou optimalizovat využití energie v kvarkových motorech.

 Autoři seriálu StarTrek vymysleli mnoho zajímavých způsobů, jak pohánět kosmické lodi. Příkladem jsou motory využívající dilithiové krystaly, anihilace, kvantové singularity nebo červené hmoty. V předmětu OSY autorům pomůžeme a navrhneme koncept motorů využívajících fúze kvarků. Kromě tohoto revolučního nápadu navíc dodáme i software, který umožní rychlé, efektivní a ekologické řízení takových motorů.

 Základních kvarků je 6 (viz Quark). Názvy kvarků (horní, dolní, podivný, půvabný, pravdivý a krásný) se nám pro strojové zpracování moc nehodí, názvy proto nahradíme čísly 0 až 5. Předpokládáme, že dvojice kvarků je schopna (za určitých podmínek) reagovat. Ze dvojice kvarků vznikne jeden jiný (nebo i stejný) kvark a uvolní se energie. Subatomární částice se chovají podivně, není tedy překvapivé, že fúze jedné dvojice kvarků může poskytovat různé výstupy s různou energií. Například fúze kvarků 0 + 1 může poskytnout výsledný kvark 0 s energií x, nebo např. kvark 4 s energií y. K fúzi dochází pouze v generátorech, konfigurace generátoru je přesně popsána symetrickou maticí 6 x 6 x 6 čísel (3D pole). První a druhý index udává vstupující kvarky, třetí index udává vznikající kvark. Pokud tedy probíhá fúze x + y na z, bude množství uvolněné energie udáno obsahem pole [x][y][z]. Pokud na dané pozici je kladné číslo (energie se uvolní), může v tomto generátoru taková reakce proběhnout, pokud je na pozici hodnota 0, znamená to, že reakce proběhnout nemůže (alespoň ne v tomto generátoru). Generátorů může být k dispozici více, každý generátor bude popsán svojí maticí 6 x 6 x 6 hodnot.

 Palivo do motorů je tvořeno kvarky, které jsou pro snadné skladování uložené v kruhových strukturách - palivových kruzích. Palivový kruh vložen do jednoho vybraného generátoru a v něm je přeměněn na energii. Generátor pracuje tak, že vybírá dvojici sousedních kvarků, provede požadovanou fúzi (výsledek dle volby, ale omezen podle své matice) a výsledný kvark umístí na uvolněné místo. Pak vybere další dvojici sousedních kvarků, provede další fúzi a celý proces se opakuje. Zpracování palivového kruhu skončí v okamžiku, kdy zbude poslední jeden kvark (ten je jako odpad vypuštěn).

 Na projektu kvarkového motoru se bohužel podílely strukturální fondy Evropské Unie. Závazná směrnice EUROQUARK V udává, že:

 palivový kruh musí být celý zpracovaný v jednom generátoru (v průběhu jej nelze přenášet mezi generátory),
 palivový kruh musí být spotřebovaný celý, tedy výstupem musí být právě jeden kvark,
 výsledný kvark musí být likvidován ekologicky s ohledem na udržitelný rozvoj, např. je zcela kategoricky zakázáno vypouštět v Bruselu podivné a pravdivé kvarky. Proto je požadavkem, aby bylo možné řídit, který výsledný kvark vznikne.
 Vaším úkolem je realizovat software, který dokáže kvarkové motory řídit. Předpokládejte, že dostanete popis dostupných generátorů (pro každý jeho popisnou matici) a dále předpokládejte, že dostáváte popis zpracovávaných palivových kruhů. Pro každý kruh dostanete jeho velikost (počet kvarků), seznam kvarků v něm umístěných a požadovaný výsledný kvark. Váš program musí rozhodnout, který generátor dokáže palivový kruh zpracovat a jakou energii lze z kruhu získat. Pokud je možností více, musí vybrat ten generátor, který poskytne největší energii. Výstupem je identifikace použitého generátoru, uvolněná energie a strom popisující postupné fúze kvarků v kruhu. Výpočet chceme samozřejmě co nejrychlejší, protože se jedná o úlohu výpočetně náročnou, hodí se využít výpočetní výkon co nejvíce CPU jader. K tomu využijete vlákna.

 Požadované rozhraní:

 #define QUARKS_NR     6
 
 struct TGenerator
 {
   unsigned int m_Energy[QUARKS_NR][QUARKS_NR][QUARKS_NR];
 }; 

 struct CReactNode
 {
                   CReactNode       ( uint8_t           product, 
                                      unsigned int      energy,
                                      CReactNode      * l = NULL,
                                      CReactNode      * r = NULL );
                  ~CReactNode       ( void );
   int             PrintTree        ( std::ostream    & os,
                                      int               pos,
                                      int               len,
                                      const std::string & nodePrefix = "",
                                      const std::string & subNodePrefix = "" );
   CReactNode    * m_L;
   CReactNode    * m_R;
   unsigned int    m_Energy;
   uint8_t         m_Product;
 };

 struct TRequest
 {
   uint8_t       * m_Fuel;
   int             m_FuelNr;
   uint8_t         m_FinalProduct;
 };

 struct TSetup 
 {   
   CReactNode    * m_Root;
   unsigned int    m_Energy;
   int             m_Generator;
   int             m_StartPos;
 };

 void               optimizeEnergySeq( const TGenerator* generators,
                                      int               generatorsNr,
                                      const TRequest  * request,
                                      TSetup          * setup );

 void               optimizeEnergy   ( int               threads,
                                      const TGenerator* generators,
                                      int               generatorsNr,
                                      const TRequest *(* dispatcher)( void ),
                                      void           (* engines ) ( const TRequest *, TSetup * ) );

 TGenerator
 struktura popisuje konfiguraci generátoru. Jedná se o zabalené 3D pole, prvé 2 indexy udávají slučované kvarky, třetí index udává výsledný kvark. Obsahem pole je buď 0 (takovou fúzi nelze provést) nebo kladné číslo (uvolněná energie).
 CReactNode
 třída popisující strom fúzí. Listy představují kvarky z palivového kruhu, vnitřní uzly pak produkty fúzí. Členská proměnná m_Energy udává celkovou energii uvolněnou při fúzi podstromu, proměnná m_Product kvark získaný fúzí podstromu. Tato třída je implementovaná v testovacím prostředí a v dodaném archivu, Váš program ji bude pouze používat.
 TRequest
 Struktura popisující požadavek na fúzi palivového kruhu. Obsahuje složku m_Fuel (pole kvarků obsažených v palivovém kruhu), m_FuelNr (počet kvarků) a m_FinalProduct (požadovaný kvark, který má vzniknout po syntéze celého kruhu). Strukturu budete dostávat z testovacího prostředí a budete ji v nezměněné podobě (stejná adresa, stejný obsah) vracet.
 TSetup
 je struktura popisující fúzi palivového kruhu. Má složky:
 m_Root - strom fúzí, viz níže. Pokud lze fúzi s danými požadavky provést, bude m_Root nastaven na kořen stromu popisujícího postupné fúze sousedů. Pokud fúzi nelze realizovat, bude nastaven na NULL,
 m_Energy - celková uvolněná energie při fúzi, 0 pokud nelze fúzi realizovat,
 m_Generator - index generátoru, který má být použit,
 m_StartPos - index kvarku z pole m_Fuel, který odpovídá nejlevějšímu listu ve stromu m_Root. Význam je lépe vidět na příkladu.
 optimizeEnergySeq
 Vámi implementovaná funkce, která sekvenčně vypočte optimální fúzi zadaného palivového kruhu. Funkce dostane parametry:
 generators/generatorsNr - popisy jednotlivých dostupných generátorů,
 request - popis palivového kruhu, pro který má být proveden výpočet,
 setup - výstupní parametr, do kterého funkce umístí výsledky výpočtu.
 Funkce je určena pro odladění algoritmu výpočtu. Dokud tato funkce nebude fungovat, testovací prostředí nebude Váš program dále testovat v testech s více vlákny.
 optimizeEnergy
 Vámi implementovaná funkce, která vypočte optimální fúze zadaných palivových kruhů s využitím vláken. Funkce dostane parametry:
 threads - udává počet vláken, která mají být použita pro paralelní výpočet optimálních řešení,
 generators/generatorsNr - popisy jednotlivých dostupných generátorů,
 dispatcher ukazatel na funkci, která bude dodávat problémy k řešení. Vaše implementace bude opakovaně volat tuto funkci, každé zavolání funkce dodá popis dalšího palivového kruhu ke zpracování. Pokud volání této funkce vrátí hodnotu NULL, znamená to, že palivo došlo a není co dále zpracovávat. Vaše funkce optimizeEnergy v takovém případě dokončí rozdělanou práci a vrátí se.
 engines ukazatel na funkci, kterou budete volat po zpracování každého jednoho palivového kruhu. Funkce má dva parametry - popis požadavku jak byl předán funkcí dispatcher a Vámi vyplněnou strukturu s nalezeným optimálním zpracováním.
 Ukázka výpočtu:
 Matice generátoru:
          0                  1                  2                  3                  4                  5
 0 [ x  x  x  x  x 66][ x  x 93  x  x  x][ x  x  x  x  x  x][48  x  6 81 46  x][53  x 44 37  x 73][ x  x  x 99  x  x]
 1 [ x  x 93  x  x  x][ x  x 98  x  x  x][ x  x 95  x  x  x][24  x  x 29 65  x][ x  x 22  7  x 22][80  x  x  x 89  x]
 2 [ x  x  x  x  x  x][ x  x 95  x  x  x][ x  x  x  x  x 14][ x  x  x  x 95  x][ x  x  x 56  x  x][ x  x 77  x  x  x]
 3 [48  x  6 81 46  x][24  x  x 29 65  x][ x  x  x  x 95  x][ x  x  x  x  x  x][ x  x  x  x  x 72][ x  x 50  x  x  x]
 4 [53  x 44 37  x 73][ x  x 22  7  x 22][ x  x  x 56  x  x][ x  x  x  x  x 72][ x 94  x  x  x 76][63 93  x  x 57  x]
 5 [ x  x  x 99  x  x][80  x  x  x 89  x][ x  x 77  x  x  x][ x  x 50  x  x  x][63 93  x  x 57  x][35 43  x  x  x  x]
 3D matice generátoru je zobrazená jako 2D, třetí index (uvolněná energie pro ten který výsledný kvark) se uplatní na hodnoty v hranaté závorce. Např. pro fúzi 5 + 4 se použije poslední řádek a předposlední sloupec, tedy možnosti jsou [63 93 x x 57 x]. Reakcí tedy lze získat kvarky 0, 1 nebo 4, uvolněná energie bude 63, 93, resp. 57. Všimněte si, že matice je symetrická podle diagonály, tedy fúze x + y a y + x dávají stejné možnosti.

 Požadovaný finální produkt: 2
 Palivový kruh: 3  4  2  1  5

 Nalezený výsledek: energie 349, pozice 2, strom:
 <2, 349>
 +-<2 @ 2>
 +-<1, 254>
    +-<4, 89>
    |  +-<1 @ 3>
    |  +-<5 @ 4>
    +-<5, 72>
       +-<3 @ 0>
       +-<4 @ 1>
 Výpis stromu ukazuje listy v zápisu typu <3 @ 0>. Tento zápis říká. že v tomto místě je použit kvark 3 z palivového kruhu na původní pozici 0. Všimněte si, že pozice tvoří cyklickou sekvenci (čteme-li listy zleva doprava). Zápis vnitřních uzlů typu < 1, 254 > udává, že výsledným produktem fúze je kvark 1 a uvolněná energie je 254 (součet energie ze synů plus energie uvolněné poslední fúzí).
	Úkolem je realizovat sadu funkcí, které budou optimalizovat využití energie v kvarkových motorech.

	Autoři seriálu StarTrek vymysleli mnoho zajímavých způsobů, jak pohánět kosmické lodi. Příkladem jsou motory využívající dilithiové krystaly, anihilace, kvantové singularity nebo červené hmoty. V předmětu OSY autorům pomůžeme a navrhneme koncept motorů využívajících fúze kvarků. Kromě tohoto revolučního nápadu navíc dodáme i software, který umožní rychlé, efektivní a ekologické řízení takových motorů.

	Základních kvarků je 6 (viz Quark). Názvy kvarků (horní, dolní, podivný, půvabný, pravdivý a krásný) se nám pro strojové zpracování moc nehodí, názvy proto nahradíme čísly 0 až 5. Předpokládáme, že dvojice kvarků je schopna (za určitých podmínek) reagovat. Ze dvojice kvarků vznikne jeden jiný (nebo i stejný) kvark a uvolní se energie. Subatomární částice se chovají podivně, není tedy překvapivé, že fúze jedné dvojice kvarků může poskytovat různé výstupy s různou energií. Například fúze kvarků 0 + 1 může poskytnout výsledný kvark 0 s energií x, nebo např. kvark 4 s energií y. K fúzi dochází pouze v generátorech, konfigurace generátoru je přesně popsána symetrickou maticí 6 x 6 x 6 čísel (3D pole). První a druhý index udává vstupující kvarky, třetí index udává vznikající kvark. Pokud tedy probíhá fúze x + y na z, bude množství uvolněné energie udáno obsahem pole [x][y][z]. Pokud na dané pozici je kladné číslo (energie se uvolní), může v tomto generátoru taková reakce proběhnout, pokud je na pozici hodnota 0, znamená to, že reakce proběhnout nemůže (alespoň ne v tomto generátoru). Generátorů může být k dispozici více, každý generátor bude popsán svojí maticí 6 x 6 x 6 hodnot.

	Palivo do motorů je tvořeno kvarky, které jsou pro snadné skladování uložené v kruhových strukturách - palivových kruzích. Palivový kruh vložen do jednoho vybraného generátoru a v něm je přeměněn na energii. Generátor pracuje tak, že vybírá dvojici sousedních kvarků, provede požadovanou fúzi (výsledek dle volby, ale omezen podle své matice) a výsledný kvark umístí na uvolněné místo. Pak vybere další dvojici sousedních kvarků, provede další fúzi a celý proces se opakuje. Zpracování palivového kruhu skončí v okamžiku, kdy zbude poslední jeden kvark (ten je jako odpad vypuštěn).

	Na projektu kvarkového motoru se bohužel podílely strukturální fondy Evropské Unie. Závazná směrnice EUROQUARK V udává, že:

	palivový kruh musí být celý zpracovaný v jednom generátoru (v průběhu jej nelze přenášet mezi generátory),
	palivový kruh musí být spotřebovaný celý, tedy výstupem musí být právě jeden kvark,
	výsledný kvark musí být likvidován ekologicky s ohledem na udržitelný rozvoj, např. je zcela kategoricky zakázáno vypouštět v Bruselu podivné a pravdivé kvarky. Proto je požadavkem, aby bylo možné řídit, který výsledný kvark vznikne.
	Vaším úkolem je realizovat software, který dokáže kvarkové motory řídit. Předpokládejte, že dostanete popis dostupných generátorů (pro každý jeho popisnou matici) a dále předpokládejte, že dostáváte popis zpracovávaných palivových kruhů. Pro každý kruh dostanete jeho velikost (počet kvarků), seznam kvarků v něm umístěných a požadovaný výsledný kvark. Váš program musí rozhodnout, který generátor dokáže palivový kruh zpracovat a jakou energii lze z kruhu získat. Pokud je možností více, musí vybrat ten generátor, který poskytne největší energii. Výstupem je identifikace použitého generátoru, uvolněná energie a strom popisující postupné fúze kvarků v kruhu. Výpočet chceme samozřejmě co nejrychlejší, protože se jedná o úlohu výpočetně náročnou, hodí se využít výpočetní výkon co nejvíce CPU jader. K tomu využijete vlákna.

	Požadované rozhraní:

	#define QUARKS_NR 6

	struct TGenerator
	{
	unsigned int m_Energy[QUARKS_NR][QUARKS_NR][QUARKS_NR];
	};

	struct CReactNode
	{
	CReactNode ( uint8_t product,
	unsigned int energy,
	CReactNode * l = NULL,
	CReactNode * r = NULL );
	~CReactNode ( void );
	int PrintTree ( std::ostream & os,
	int pos,
	int len,
	const std::string & nodePrefix = "",
	const std::string & subNodePrefix = "" );
	CReactNode * m_L;
	CReactNode * m_R;
	unsigned int m_Energy;
	uint8_t m_Product;
	};

	struct TRequest
	{
	uint8_t * m_Fuel;
	int m_FuelNr;
	uint8_t m_FinalProduct;
	};

	struct TSetup
	{
	CReactNode * m_Root;
	unsigned int m_Energy;
	int m_Generator;
	int m_StartPos;
	};

	void optimizeEnergySeq( const TGenerator* generators,
	int generatorsNr,
	const TRequest * request,
	TSetup * setup );

	void optimizeEnergy ( int threads,
	const TGenerator* generators,
	int generatorsNr,
	const TRequest ( dispatcher)( void ),
	void (* engines ) ( const TRequest , TSetup ) );

	TGenerator
	struktura popisuje konfiguraci generátoru. Jedná se o zabalené 3D pole, prvé 2 indexy udávají slučované kvarky, třetí index udává výsledný kvark. Obsahem pole je buď 0 (takovou fúzi nelze provést) nebo kladné číslo (uvolněná energie).
	CReactNode
	třída popisující strom fúzí. Listy představují kvarky z palivového kruhu, vnitřní uzly pak produkty fúzí. Členská proměnná m_Energy udává celkovou energii uvolněnou při fúzi podstromu, proměnná m_Product kvark získaný fúzí podstromu. Tato třída je implementovaná v testovacím prostředí a v dodaném archivu, Váš program ji bude pouze používat.
	TRequest
	Struktura popisující požadavek na fúzi palivového kruhu. Obsahuje složku m_Fuel (pole kvarků obsažených v palivovém kruhu), m_FuelNr (počet kvarků) a m_FinalProduct (požadovaný kvark, který má vzniknout po syntéze celého kruhu). Strukturu budete dostávat z testovacího prostředí a budete ji v nezměněné podobě (stejná adresa, stejný obsah) vracet.
	TSetup
	je struktura popisující fúzi palivového kruhu. Má složky:
	m_Root - strom fúzí, viz níže. Pokud lze fúzi s danými požadavky provést, bude m_Root nastaven na kořen stromu popisujícího postupné fúze sousedů. Pokud fúzi nelze realizovat, bude nastaven na NULL,
	m_Energy - celková uvolněná energie při fúzi, 0 pokud nelze fúzi realizovat,
	m_Generator - index generátoru, který má být použit,
	m_StartPos - index kvarku z pole m_Fuel, který odpovídá nejlevějšímu listu ve stromu m_Root. Význam je lépe vidět na příkladu.
	optimizeEnergySeq
	Vámi implementovaná funkce, která sekvenčně vypočte optimální fúzi zadaného palivového kruhu. Funkce dostane parametry:
	generators/generatorsNr - popisy jednotlivých dostupných generátorů,
	request - popis palivového kruhu, pro který má být proveden výpočet,
	setup - výstupní parametr, do kterého funkce umístí výsledky výpočtu.
	Funkce je určena pro odladění algoritmu výpočtu. Dokud tato funkce nebude fungovat, testovací prostředí nebude Váš program dále testovat v testech s více vlákny.
	optimizeEnergy
	Vámi implementovaná funkce, která vypočte optimální fúze zadaných palivových kruhů s využitím vláken. Funkce dostane parametry:
	threads - udává počet vláken, která mají být použita pro paralelní výpočet optimálních řešení,
	generators/generatorsNr - popisy jednotlivých dostupných generátorů,
	dispatcher ukazatel na funkci, která bude dodávat problémy k řešení. Vaše implementace bude opakovaně volat tuto funkci, každé zavolání funkce dodá popis dalšího palivového kruhu ke zpracování. Pokud volání této funkce vrátí hodnotu NULL, znamená to, že palivo došlo a není co dále zpracovávat. Vaše funkce optimizeEnergy v takovém případě dokončí rozdělanou práci a vrátí se.
	engines ukazatel na funkci, kterou budete volat po zpracování každého jednoho palivového kruhu. Funkce má dva parametry - popis požadavku jak byl předán funkcí dispatcher a Vámi vyplněnou strukturu s nalezeným optimálním zpracováním.
	Ukázka výpočtu:
	Matice generátoru:
	0 1 2 3 4 5
	0 [ x x x x x 66][ x x 93 x x x][ x x x x x x][48 x 6 81 46 x][53 x 44 37 x 73][ x x x 99 x x]
	1 [ x x 93 x x x][ x x 98 x x x][ x x 95 x x x][24 x x 29 65 x][ x x 22 7 x 22][80 x x x 89 x]
	2 [ x x x x x x][ x x 95 x x x][ x x x x x 14][ x x x x 95 x][ x x x 56 x x][ x x 77 x x x]
	3 [48 x 6 81 46 x][24 x x 29 65 x][ x x x x 95 x][ x x x x x x][ x x x x x 72][ x x 50 x x x]
	4 [53 x 44 37 x 73][ x x 22 7 x 22][ x x x 56 x x][ x x x x x 72][ x 94 x x x 76][63 93 x x 57 x]
	5 [ x x x 99 x x][80 x x x 89 x][ x x 77 x x x][ x x 50 x x x][63 93 x x 57 x][35 43 x x x x]
	3D matice generátoru je zobrazená jako 2D, třetí index (uvolněná energie pro ten který výsledný kvark) se uplatní na hodnoty v hranaté závorce. Např. pro fúzi 5 + 4 se použije poslední řádek a předposlední sloupec, tedy možnosti jsou [63 93 x x 57 x]. Reakcí tedy lze získat kvarky 0, 1 nebo 4, uvolněná energie bude 63, 93, resp. 57. Všimněte si, že matice je symetrická podle diagonály, tedy fúze x + y a y + x dávají stejné možnosti.

	Požadovaný finální produkt: 2
	Palivový kruh: 3 4 2 1 5

	Nalezený výsledek: energie 349, pozice 2, strom:
	<2, 349>
	+-<2 @ 2>
	+-<1, 254>
	+-<4, 89>
	\| +-<1 @ 3>
	\| +-<5 @ 4>
	+-<5, 72>
	+-<3 @ 0>
	+-<4 @ 1>
	Výpis stromu ukazuje listy v zápisu typu <3 @ 0>. Tento zápis říká. že v tomto místě je použit kvark 3 z palivového kruhu na původní pozici 0. Všimněte si, že pozice tvoří cyklickou sekvenci (čteme-li listy zleva doprava). Zápis vnitřních uzlů typu < 1, 254 > udává, že výsledným produktem fúze je kvark 1 a uvolněná energie je 254 (součet energie ze synů plus energie uvolněné poslední fúzí).