Pocit

Dnes mam asi takýto pocit:

Dumbledore: Predstav si svoj najkrásnejší pocit.

Ja: Už mám,pán Dumbledore....

Vypustil na mňa dementora a ja som vyčaroval najúžasnejšieho patronusa (samozrejme v tvare zúrivého C++ :) )

Dumbledore: To musela byť ale veľmi šťastná myšlienka, ani Harry Potter nedokázal také niečo. Čo to bolo?

Ja: Spomenul som si ako som 23.11.2011 opravil ten nepochopiteľný bug...

Koho by kurnik napadlo, že pridanie BYTE premennej do štruktúry spôsobí, že pamäť využívaná na prenos údajov kernel <-> user space pomocou LPC zrazu nebude zarovnaná na 4 BYTE. No a to potom odpálkuje celú LPC komunikáciu a keďže sa to dialo pri komunikácii s "file system minifilter driver" tak to freezlo všetky CreateFile (tam sme húúúknutý) volania a systém zmrzol skôr ako sa doň dalo prihlásiť....

V čom je chyba?

V jednom C++ kóde som spravil chybu a relatívne ma to prekvapilo. Aj keď po tom čo som si uvedomil, že to je chyba tak to bolo hneď zrejmé. Zjednodušene som túto chybu zaniesol do nasledujúceho kódu - nájdete chybu/chyby? Viete povedať čo sa stane bez toho aby ste spustili tento kód? A ako by ste ho opravili?

#include <string.h>

 class A

{

public:

       A()

       {

              Initialize();

       }

       ~A()

       {

              Deinitialize();

       }

       virtual void Initialize()

       {

       }

       virtual void Deinitialize()

       {

       }

};

 

class B : public A

{

public:

       char *m_pMemory;

       B()

       {

              m_pMemory = NULL;

       }

 
       virtual void Initialize()

       {

              m_pMemory = new char[ 200];

              strcpy( m_pMemory, "Pekne nam to funguje\n");

       }

 
       virtual void Deinitialize()

       {

              if ( m_pMemory)

                     delete []m_pMemory;

       }

 
       char *GetMemory()

       {

              return m_pMemory;

       }

};

 

int _tmain(int argc,  _TCHAR* argv[])

{
       B b;

       printf( b.GetMemory());

 
       return 0;

}

scanf a %i

Na zaujímavý problém sme narazili v robote a zistili sme, že čítať pozorne "help" je niekedy užitočné :)

Ten náš problém bol s funkciou scanf a parametrom %i pre číselný vstup. Koľko z Vás dokáže povedať bez nazretia do helpu, že ktorý z týchto príkladov nebude fungovať?

int i;
sscanf( "987600", "%i", &i);
sscanf( "087600", "%i", &i);
sscanf( "007600", "%i", &i);

.Net string alebo StringBuilder?

Včera mi kamarát dal "hádanku" ako z :

           var list = new string[] { "Jozef", "Roman", "Palo" };

najjednoduchšie spravím :

           "Jozef, Roman, Palo"

Mňa samozrejme hneď napadol foreach prístup. No ale viem že on sleduje .Net a číta si o ňom viac ako ja. Takže som vedel, že foreach nie je to čo má byť ako výsledok. Výsledok bol toto :

           list.Aggregate((a, b) = a + ", " + b);

Čo je zaujímavý a rýchly spôsob ako rozumne niečo vypísať. Mňa ale hneď nejak začalo trápiť aké rýchle to je. Skúsil som štyri rôzne prístupy a tu sú výsledky

	list.Aggregate((a, b) = a + ", " + b);	3101,8578ms
	string r = ""; f = false; foreach (string s in list) {       if (f)             r += ", ";       else             f = true;       r += s; }	5952,7529ms
	string r = ""; f = false; foreach (string sc in list) {       if (f)             r2 += ", " + sc;       else       {             r2 += sc;             f = true;       } }	2974,5727ms
	StringBuilder sb = new StringBuilder(); bool f = false; foreach (string sc in list) {       if (f)             sb.Append(", ");       else             f = true;       sb.Append(sc); }	2,3295ms

Pokus som robil na liste s 20000 prvkami. Pričom každý prvok bol náhodný text dlhý od 5 do 14 znakov.

Neviem prečo, ale ja som mal domnienku, že v .Nete je za stringom vlastne StringBuilder. Ako vidno tak to nie je pravda a string je v tomto konkrétnom prípade až 1277 krát rýchlejší.
Čo ma tiež prekvapilo bol rozdiel medzi foreach stringovou metódou a Aggregate a ten je minimálny.Čakal som väčší rozdiel.

Na záver môžem povedať, že do debugovacích výpisov kľudne použijem Aggregate lebo je prehľadná a "spratná". Ale ak pôjde o skladanie väčšieho počtu reťazcov tak určite siahnem bo StringBuilder.

Q.E.D. : Ako navigovať robota I - ako na to

Predchádzajúcom príspevku som len ukázal výsledok, ale nie postup ako som sa k nemu dopracoval. Tak teraz to naprávam :)

V prvom rade si človek musí uvedomiť jednu vec, že riešením úlohu je vlastne transformácia množiny. Prvky množiny sú miesta kde sa v danom kroku môže nachádzať robot a transformácia je určená modrou alebo červenou cestou. Takže na začiatku množina obsahuje prvky {A,B,C,D,E} a snažíme sa postupnými úpravami dostať množinu {A}. Ak zoberieme graf z "Ako navigovať robota I" tak potom z prvého kroku {A,B,C,D,E} po transformácii M (modrá) dostaneme {A,B,C,D} a keď znova použijeme transformáciu M tak dostaneme {A,B,D}. Teraz vytvoríme nový graf pričom vrcholy sú všetky možné podmnožiny množiny {A,B,C,D,E}, ktoré sú pospájane jednosmernými hranami definovanými M a Č transformáciami. Úloha sa nám teraz vlastne zredukovala na nájdenie najkratšej cesty z vrchola {A,B,C,D,E} do vrchola {A}.

Toto všetko je výhodné v prípade ak riešime úlohu na počítači. Výrazne nám to redukuje počet krokov ak by sme použili "brute force" a hľadali všetky možné cesty. Vytvorenie grafu je lineárna záležitosť a potom už existuje viac stratégií ako nájsť najkratšiu cestu. Ja som použil prehľadávanie do šírky čo znamená, že prvý vrchol má nastavenú vzdialenosť 0 a ostatné -1 a potom v každom kroku i kontrolujem kam sa dostanem z vrcholov so vzdialenosťou i - 1 pričom uvažujem iba o cieľových vrcholoch ktoré ešte nemajú priradenú vzdialenosť. V každom kroku môžu nastať 3 možnosti:

1. Ak nenájdem žiaden nový vrchol tak neexistuje cesta
2. Dostali sme sa do cieľového vrcholu a v tom prípade minimálna vzdialenosť je i
3. Ak neplatí 1. ani 2. tak pokračujeme krokom i + 1

Z daného postupu vyplýva, že počet krokov pre ľubovoľný počet vrcholov pôvodného grafu nemôže byť minimálna cesta ak existuje dlhšia ako je počet všetkých podmnožín a to je 2ⁿ. A to platí pre ľubovoľný počet transformácii (teda nie len pre 2 ako je použité v našom prípade).

Ak chceme nájsť maximálnu minimálnu cestu zo všetkých možných grafov - stačí generovať všetky možné grafy a vypočítať daným algoritmom najkratšiu dĺžku. Na priemernom počítači to trvalo menej ako 30s.

A ďalšia zaujímavá vec vyplýva z použitého algoritmu na nájdenie najkratšej dĺžky - pokiaľ si nepamätáme ako sme sa dostali do ktorého vrchola, čo je pre nájdenie minimálnej dĺžky zbytočné, tak na konci nie je známa postupnosť transformácií pre danú minimálnu cestu...

Q.E.D. : Ako navigovať robota I

Q.E.D. je môj obľúbený blog a rád tam riešim úlohy - aj keď väčšinou ma predbehnú tak ma to neodradí sa pohrať s danou úlohou. Nedávno tam pribudla úloha "Ako navigovať robota I" a tam som konečne mohol využiť moje programátorské schopnosti :) a došiel na najlepšie riešenie prvý :) Potom v diskusii padol návrh či by sa nedal nájsť graf ktorý by potreboval dlhší postup. Tak som sa na to podujal, ale keďže komentár môže mať maximálne 4096 znakov tak ten výsledok píšem tu :) Ak je môj program správny, tak maximum pre graf kde nie sú slučky je počet krokov 17 - všetky možné riešenia sú :

červená:{A->B, B->C, C->A, D->E, E->D) modrá:{A->D, B->A, C->D, D->E, E->B)
červená:{A->B, B->C, C->A, D->E, E->D) modrá:{A->D, B->D, C->B, D->E, E->C)
červená:{A->B, B->C, C->A, D->E, E->D) modrá:{A->E, B->A, C->E, D->B, E->D)
červená:{A->B, B->C, C->A, D->E, E->D) modrá:{A->E, B->E, C->B, D->C, E->D)
červená:{A->B, B->C, C->D, D->A, E->B) modrá:{A->B, B->C, C->D, D->E, E->A)
červená:{A->B, B->C, C->D, D->A, E->B) modrá:{A->D, B->C, C->B, D->E, E->A)
červená:{A->B, B->C, C->D, D->E, E->A) modrá:{A->B, B->C, C->D, D->A, E->B)
červená:{A->B, B->C, C->D, D->E, E->A) modrá:{A->B, B->C, C->D, D->E, E->B)
červená:{A->B, B->C, C->D, D->E, E->A) modrá:{A->C, B->C, C->D, D->E, E->B)
červená:{A->B, B->C, C->D, D->E, E->B) modrá:{A->B, B->C, C->D, D->E, E->A)
červená:{A->B, B->C, C->D, D->E, E->B) modrá:{A->E, B->C, C->B, D->A, E->D)
červená:{A->B, B->C, C->D, D->E, E->B) modrá:{A->E, B->C, C->D, D->A, E->B)
červená:{A->B, B->C, C->E, D->A, E->D) modrá:{A->B, B->C, C->E, D->B, E->A)
červená:{A->B, B->C, C->E, D->A, E->D) modrá:{A->B, B->C, C->E, D->B, E->D)
červená:{A->B, B->C, C->E, D->A, E->D) modrá:{A->C, B->C, C->E, D->B, E->D)
červená:{A->B, B->C, C->E, D->B, E->A) modrá:{A->B, B->C, C->E, D->A, E->D)
červená:{A->B, B->C, C->E, D->B, E->A) modrá:{A->E, B->C, C->B, D->A, E->D)
červená:{A->B, B->C, C->E, D->B, E->D) modrá:{A->B, B->C, C->E, D->A, E->D)
červená:{A->B, B->C, C->E, D->B, E->D) modrá:{A->D, B->C, C->B, D->E, E->A)
červená:{A->B, B->C, C->E, D->B, E->D) modrá:{A->D, B->C, C->E, D->B, E->A)
červená:{A->B, B->D, C->A, D->C, E->B) modrá:{A->B, B->D, C->E, D->C, E->A)
červená:{A->B, B->D, C->A, D->C, E->B) modrá:{A->C, B->D, C->E, D->B, E->A)
červená:{A->B, B->D, C->A, D->E, E->C) modrá:{A->B, B->D, C->B, D->E, E->A)
červená:{A->B, B->D, C->A, D->E, E->C) modrá:{A->B, B->D, C->B, D->E, E->C)
červená:{A->B, B->D, C->A, D->E, E->C) modrá:{A->D, B->D, C->B, D->E, E->C)
červená:{A->B, B->D, C->B, D->E, E->A) modrá:{A->B, B->D, C->A, D->E, E->C)
červená:{A->B, B->D, C->B, D->E, E->A) modrá:{A->E, B->D, C->A, D->B, E->C)
červená:{A->B, B->D, C->B, D->E, E->C) modrá:{A->B, B->D, C->A, D->E, E->C)
červená:{A->B, B->D, C->B, D->E, E->C) modrá:{A->C, B->D, C->B, D->E, E->A)
červená:{A->B, B->D, C->B, D->E, E->C) modrá:{A->C, B->D, C->E, D->B, E->A)
červená:{A->B, B->D, C->E, D->A, E->C) modrá:{A->C, B->A, C->E, D->C, E->B)
červená:{A->B, B->D, C->E, D->A, E->C) modrá:{A->C, B->C, C->E, D->B, E->D)
červená:{A->B, B->D, C->E, D->A, E->C) modrá:{A->E, B->A, C->B, D->E, E->C)
červená:{A->B, B->D, C->E, D->A, E->C) modrá:{A->E, B->E, C->D, D->B, E->C)
červená:{A->B, B->D, C->E, D->C, E->A) modrá:{A->B, B->D, C->A, D->C, E->B)
červená:{A->B, B->D, C->E, D->C, E->A) modrá:{A->B, B->D, C->E, D->C, E->B)
červená:{A->B, B->D, C->E, D->C, E->A) modrá:{A->D, B->D, C->E, D->C, E->B)
červená:{A->B, B->D, C->E, D->C, E->B) modrá:{A->B, B->D, C->E, D->C, E->A)
červená:{A->B, B->D, C->E, D->C, E->B) modrá:{A->E, B->D, C->A, D->B, E->C)
červená:{A->B, B->D, C->E, D->C, E->B) modrá:{A->E, B->D, C->A, D->C, E->B)
červená:{A->B, B->E, C->A, D->B, E->C) modrá:{A->B, B->E, C->D, D->A, E->C)
červená:{A->B, B->E, C->A, D->B, E->C) modrá:{A->C, B->E, C->D, D->A, E->B)
červená:{A->B, B->E, C->A, D->C, E->D) modrá:{A->B, B->E, C->B, D->A, E->D)
červená:{A->B, B->E, C->A, D->C, E->D) modrá:{A->B, B->E, C->B, D->C, E->D)
červená:{A->B, B->E, C->A, D->C, E->D) modrá:{A->E, B->E, C->B, D->C, E->D)
červená:{A->B, B->E, C->B, D->A, E->D) modrá:{A->B, B->E, C->A, D->C, E->D)
červená:{A->B, B->E, C->B, D->A, E->D) modrá:{A->D, B->E, C->A, D->C, E->B)
červená:{A->B, B->E, C->B, D->C, E->D) modrá:{A->B, B->E, C->A, D->C, E->D)
červená:{A->B, B->E, C->B, D->C, E->D) modrá:{A->C, B->E, C->B, D->A, E->D)
červená:{A->B, B->E, C->B, D->C, E->D) modrá:{A->C, B->E, C->D, D->A, E->B)
červená:{A->B, B->E, C->D, D->A, E->C) modrá:{A->B, B->E, C->A, D->B, E->C)
červená:{A->B, B->E, C->D, D->A, E->C) modrá:{A->B, B->E, C->D, D->B, E->C)
červená:{A->B, B->E, C->D, D->A, E->C) modrá:{A->E, B->E, C->D, D->B, E->C)
červená:{A->B, B->E, C->D, D->B, E->C) modrá:{A->B, B->E, C->D, D->A, E->C)
červená:{A->B, B->E, C->D, D->B, E->C) modrá:{A->D, B->E, C->A, D->B, E->C)
červená:{A->B, B->E, C->D, D->B, E->C) modrá:{A->D, B->E, C->A, D->C, E->B)
červená:{A->B, B->E, C->D, D->C, E->A) modrá:{A->C, B->A, C->D, D->B, E->C)
červená:{A->B, B->E, C->D, D->C, E->A) modrá:{A->C, B->C, C->D, D->E, E->B)
červená:{A->B, B->E, C->D, D->C, E->A) modrá:{A->D, B->A, C->B, D->C, E->D)
červená:{A->B, B->E, C->D, D->C, E->A) modrá:{A->D, B->D, C->E, D->C, E->B)
červená:{A->C, B->A, C->B, D->E, E->D) modrá:{A->D, B->C, C->D, D->E, E->B)
červená:{A->C, B->A, C->B, D->E, E->D) modrá:{A->D, B->D, C->A, D->E, E->C)
červená:{A->C, B->A, C->B, D->E, E->D) modrá:{A->E, B->C, C->E, D->B, E->D)
červená:{A->C, B->A, C->B, D->E, E->D) modrá:{A->E, B->E, C->A, D->C, E->D)
červená:{A->C, B->A, C->D, D->B, E->C) modrá:{A->B, B->E, C->D, D->C, E->A)
červená:{A->C, B->A, C->D, D->B, E->C) modrá:{A->C, B->E, C->D, D->B, E->A)
červená:{A->C, B->A, C->D, D->E, E->B) modrá:{A->C, B->C, C->D, D->E, E->A)
červená:{A->C, B->A, C->D, D->E, E->B) modrá:{A->C, B->C, C->D, D->E, E->B)
červená:{A->C, B->A, C->D, D->E, E->B) modrá:{A->D, B->C, C->D, D->E, E->B)
červená:{A->C, B->A, C->E, D->B, E->D) modrá:{A->C, B->C, C->E, D->A, E->D)
červená:{A->C, B->A, C->E, D->B, E->D) modrá:{A->C, B->C, C->E, D->B, E->D)
červená:{A->C, B->A, C->E, D->B, E->D) modrá:{A->E, B->C, C->E, D->B, E->D)
červená:{A->C, B->A, C->E, D->C, E->B) modrá:{A->B, B->D, C->E, D->A, E->C)
červená:{A->C, B->A, C->E, D->C, E->B) modrá:{A->C, B->D, C->E, D->A, E->B)
červená:{A->C, B->C, C->D, D->E, E->A) modrá:{A->C, B->A, C->D, D->E, E->B)
červená:{A->C, B->C, C->D, D->E, E->A) modrá:{A->E, B->A, C->D, D->C, E->B)
červená:{A->C, B->C, C->D, D->E, E->B) modrá:{A->B, B->C, C->D, D->E, E->A)
červená:{A->C, B->C, C->D, D->E, E->B) modrá:{A->B, B->E, C->D, D->C, E->A)
červená:{A->C, B->C, C->D, D->E, E->B) modrá:{A->C, B->A, C->D, D->E, E->B)
červená:{A->C, B->C, C->E, D->A, E->D) modrá:{A->C, B->A, C->E, D->B, E->D)
červená:{A->C, B->C, C->E, D->A, E->D) modrá:{A->D, B->A, C->E, D->B, E->C)
červená:{A->C, B->C, C->E, D->B, E->D) modrá:{A->B, B->C, C->E, D->A, E->D)
červená:{A->C, B->C, C->E, D->B, E->D) modrá:{A->B, B->D, C->E, D->A, E->C)
červená:{A->C, B->C, C->E, D->B, E->D) modrá:{A->C, B->A, C->E, D->B, E->D)
červená:{A->C, B->D, C->B, D->A, E->C) modrá:{A->C, B->D, C->B, D->E, E->A)
červená:{A->C, B->D, C->B, D->A, E->C) modrá:{A->D, B->C, C->B, D->E, E->A)
červená:{A->C, B->D, C->B, D->E, E->A) modrá:{A->B, B->D, C->B, D->E, E->C)
červená:{A->C, B->D, C->B, D->E, E->A) modrá:{A->C, B->D, C->B, D->A, E->C)
červená:{A->C, B->D, C->B, D->E, E->A) modrá:{A->C, B->D, C->B, D->E, E->C)
červená:{A->C, B->D, C->B, D->E, E->C) modrá:{A->C, B->D, C->B, D->E, E->A)
červená:{A->C, B->D, C->B, D->E, E->C) modrá:{A->E, B->C, C->B, D->A, E->D)
červená:{A->C, B->D, C->B, D->E, E->C) modrá:{A->E, B->D, C->B, D->A, E->C)
červená:{A->C, B->D, C->E, D->A, E->B) modrá:{A->C, B->A, C->E, D->C, E->B)
červená:{A->C, B->D, C->E, D->A, E->B) modrá:{A->C, B->D, C->E, D->C, E->B)
červená:{A->C, B->D, C->E, D->A, E->B) modrá:{A->E, B->D, C->E, D->C, E->B)
červená:{A->C, B->D, C->E, D->B, E->A) modrá:{A->B, B->D, C->A, D->C, E->B)
červená:{A->C, B->D, C->E, D->B, E->A) modrá:{A->B, B->D, C->B, D->E, E->C)
červená:{A->C, B->D, C->E, D->B, E->A) modrá:{A->D, B->C, C->A, D->B, E->D)
červená:{A->C, B->D, C->E, D->B, E->A) modrá:{A->D, B->E, C->D, D->B, E->C)
červená:{A->C, B->D, C->E, D->C, E->B) modrá:{A->C, B->D, C->E, D->A, E->B)
červená:{A->C, B->D, C->E, D->C, E->B) modrá:{A->D, B->A, C->E, D->B, E->C)
červená:{A->C, B->D, C->E, D->C, E->B) modrá:{A->D, B->A, C->E, D->C, E->B)
červená:{A->C, B->E, C->B, D->A, E->D) modrá:{A->B, B->E, C->B, D->C, E->D)
červená:{A->C, B->E, C->B, D->A, E->D) modrá:{A->C, B->E, C->B, D->C, E->A)
červená:{A->C, B->E, C->B, D->A, E->D) modrá:{A->C, B->E, C->B, D->C, E->D)
červená:{A->C, B->E, C->B, D->C, E->A) modrá:{A->C, B->E, C->B, D->A, E->D)
červená:{A->C, B->E, C->B, D->C, E->A) modrá:{A->E, B->C, C->B, D->A, E->D)
červená:{A->C, B->E, C->B, D->C, E->D) modrá:{A->C, B->E, C->B, D->A, E->D)
červená:{A->C, B->E, C->B, D->C, E->D) modrá:{A->D, B->C, C->B, D->E, E->A)
červená:{A->C, B->E, C->B, D->C, E->D) modrá:{A->D, B->E, C->B, D->C, E->A)
červená:{A->C, B->E, C->D, D->A, E->B) modrá:{A->B, B->E, C->A, D->B, E->C)
červená:{A->C, B->E, C->D, D->A, E->B) modrá:{A->B, B->E, C->B, D->C, E->D)
červená:{A->C, B->E, C->D, D->A, E->B) modrá:{A->E, B->C, C->A, D->E, E->B)
červená:{A->C, B->E, C->D, D->A, E->B) modrá:{A->E, B->D, C->E, D->C, E->B)
červená:{A->C, B->E, C->D, D->B, E->A) modrá:{A->C, B->A, C->D, D->B, E->C)
červená:{A->C, B->E, C->D, D->B, E->A) modrá:{A->C, B->E, C->D, D->B, E->C)
červená:{A->C, B->E, C->D, D->B, E->A) modrá:{A->D, B->E, C->D, D->B, E->C)
červená:{A->C, B->E, C->D, D->B, E->C) modrá:{A->C, B->E, C->D, D->B, E->A)
červená:{A->C, B->E, C->D, D->B, E->C) modrá:{A->E, B->A, C->D, D->B, E->C)
červená:{A->C, B->E, C->D, D->B, E->C) modrá:{A->E, B->A, C->D, D->C, E->B)
červená:{A->D, B->A, C->B, D->C, E->D) modrá:{A->B, B->E, C->D, D->C, E->A)
červená:{A->D, B->A, C->B, D->C, E->D) modrá:{A->D, B->E, C->B, D->C, E->A)
červená:{A->D, B->A, C->B, D->E, E->C) modrá:{A->D, B->D, C->A, D->E, E->C)
červená:{A->D, B->A, C->B, D->E, E->C) modrá:{A->D, B->D, C->B, D->E, E->C)
červená:{A->D, B->A, C->B, D->E, E->C) modrá:{A->E, B->D, C->B, D->E, E->C)
červená:{A->D, B->A, C->D, D->E, E->B) modrá:{A->B, B->C, C->A, D->E, E->D)
červená:{A->D, B->A, C->D, D->E, E->B) modrá:{A->D, B->C, C->A, D->E, E->B)
červená:{A->D, B->A, C->E, D->B, E->C) modrá:{A->C, B->C, C->E, D->A, E->D)
červená:{A->D, B->A, C->E, D->B, E->C) modrá:{A->C, B->D, C->E, D->C, E->B)
červená:{A->D, B->A, C->E, D->B, E->C) modrá:{A->E, B->D, C->B, D->E, E->C)
červená:{A->D, B->A, C->E, D->B, E->C) modrá:{A->E, B->E, C->D, D->A, E->C)
červená:{A->D, B->A, C->E, D->C, E->B) modrá:{A->C, B->D, C->E, D->C, E->B)
červená:{A->D, B->A, C->E, D->C, E->B) modrá:{A->D, B->D, C->E, D->C, E->A)
červená:{A->D, B->A, C->E, D->C, E->B) modrá:{A->D, B->D, C->E, D->C, E->B)
červená:{A->D, B->C, C->A, D->B, E->D) modrá:{A->C, B->D, C->E, D->B, E->A)
červená:{A->D, B->C, C->A, D->B, E->D) modrá:{A->D, B->C, C->E, D->B, E->A)
červená:{A->D, B->C, C->A, D->E, E->B) modrá:{A->D, B->A, C->D, D->E, E->B)
červená:{A->D, B->C, C->A, D->E, E->B) modrá:{A->D, B->C, C->D, D->E, E->B)
červená:{A->D, B->C, C->A, D->E, E->B) modrá:{A->E, B->C, C->D, D->E, E->B)
červená:{A->D, B->C, C->B, D->E, E->A) modrá:{A->B, B->C, C->D, D->A, E->B)
červená:{A->D, B->C, C->B, D->E, E->A) modrá:{A->B, B->C, C->E, D->B, E->D)
červená:{A->D, B->C, C->B, D->E, E->A) modrá:{A->C, B->D, C->B, D->A, E->C)
červená:{A->D, B->C, C->B, D->E, E->A) modrá:{A->C, B->E, C->B, D->C, E->D)
červená:{A->D, B->C, C->D, D->E, E->B) modrá:{A->C, B->A, C->B, D->E, E->D)
červená:{A->D, B->C, C->D, D->E, E->B) modrá:{A->C, B->A, C->D, D->E, E->B)
červená:{A->D, B->C, C->D, D->E, E->B) modrá:{A->D, B->C, C->A, D->E, E->B)
červená:{A->D, B->C, C->E, D->B, E->A) modrá:{A->B, B->C, C->E, D->B, E->D)
červená:{A->D, B->C, C->E, D->B, E->A) modrá:{A->D, B->C, C->A, D->B, E->D)
červená:{A->D, B->C, C->E, D->B, E->A) modrá:{A->D, B->C, C->E, D->B, E->D)
červená:{A->D, B->C, C->E, D->B, E->D) modrá:{A->D, B->C, C->E, D->B, E->A)
červená:{A->D, B->C, C->E, D->B, E->D) modrá:{A->E, B->C, C->A, D->B, E->D)
červená:{A->D, B->C, C->E, D->B, E->D) modrá:{A->E, B->D, C->A, D->B, E->C)
červená:{A->D, B->D, C->A, D->E, E->C) modrá:{A->C, B->A, C->B, D->E, E->D)
červená:{A->D, B->D, C->A, D->E, E->C) modrá:{A->D, B->A, C->B, D->E, E->C)
červená:{A->D, B->D, C->B, D->E, E->C) modrá:{A->B, B->C, C->A, D->E, E->D)
červená:{A->D, B->D, C->B, D->E, E->C) modrá:{A->B, B->D, C->A, D->E, E->C)
červená:{A->D, B->D, C->B, D->E, E->C) modrá:{A->D, B->A, C->B, D->E, E->C)
červená:{A->D, B->D, C->E, D->C, E->A) modrá:{A->D, B->A, C->E, D->C, E->B)
červená:{A->D, B->D, C->E, D->C, E->A) modrá:{A->E, B->A, C->D, D->C, E->B)
červená:{A->D, B->D, C->E, D->C, E->B) modrá:{A->B, B->D, C->E, D->C, E->A)
červená:{A->D, B->D, C->E, D->C, E->B) modrá:{A->B, B->E, C->D, D->C, E->A)
červená:{A->D, B->D, C->E, D->C, E->B) modrá:{A->D, B->A, C->E, D->C, E->B)
červená:{A->D, B->E, C->A, D->B, E->C) modrá:{A->B, B->E, C->D, D->B, E->C)
červená:{A->D, B->E, C->A, D->B, E->C) modrá:{A->D, B->E, C->D, D->B, E->A)
červená:{A->D, B->E, C->A, D->B, E->C) modrá:{A->D, B->E, C->D, D->B, E->C)
červená:{A->D, B->E, C->A, D->C, E->B) modrá:{A->B, B->E, C->B, D->A, E->D)
červená:{A->D, B->E, C->A, D->C, E->B) modrá:{A->B, B->E, C->D, D->B, E->C)
červená:{A->D, B->E, C->A, D->C, E->B) modrá:{A->E, B->C, C->D, D->E, E->B)
červená:{A->D, B->E, C->A, D->C, E->B) modrá:{A->E, B->D, C->E, D->A, E->B)
červená:{A->D, B->E, C->B, D->C, E->A) modrá:{A->C, B->E, C->B, D->C, E->D)
červená:{A->D, B->E, C->B, D->C, E->A) modrá:{A->D, B->A, C->B, D->C, E->D)
červená:{A->D, B->E, C->B, D->C, E->A) modrá:{A->D, B->E, C->B, D->C, E->D)
červená:{A->D, B->E, C->B, D->C, E->D) modrá:{A->D, B->E, C->B, D->C, E->A)
červená:{A->D, B->E, C->B, D->C, E->D) modrá:{A->E, B->A, C->B, D->C, E->D)
červená:{A->D, B->E, C->B, D->C, E->D) modrá:{A->E, B->A, C->D, D->C, E->B)
červená:{A->D, B->E, C->D, D->B, E->A) modrá:{A->D, B->E, C->A, D->B, E->C)
červená:{A->D, B->E, C->D, D->B, E->A) modrá:{A->E, B->D, C->A, D->B, E->C)
červená:{A->D, B->E, C->D, D->B, E->C) modrá:{A->C, B->D, C->E, D->B, E->A)
červená:{A->D, B->E, C->D, D->B, E->C) modrá:{A->C, B->E, C->D, D->B, E->A)
červená:{A->D, B->E, C->D, D->B, E->C) modrá:{A->D, B->E, C->A, D->B, E->C)
červená:{A->E, B->A, C->B, D->C, E->D) modrá:{A->D, B->E, C->B, D->C, E->D)
červená:{A->E, B->A, C->B, D->C, E->D) modrá:{A->E, B->E, C->A, D->C, E->D)
červená:{A->E, B->A, C->B, D->C, E->D) modrá:{A->E, B->E, C->B, D->C, E->D)
červená:{A->E, B->A, C->B, D->E, E->C) modrá:{A->B, B->D, C->E, D->A, E->C)
červená:{A->E, B->A, C->B, D->E, E->C) modrá:{A->E, B->D, C->B, D->A, E->C)
červená:{A->E, B->A, C->D, D->B, E->C) modrá:{A->C, B->E, C->D, D->B, E->C)
červená:{A->E, B->A, C->D, D->B, E->C) modrá:{A->E, B->E, C->D, D->A, E->C)
červená:{A->E, B->A, C->D, D->B, E->C) modrá:{A->E, B->E, C->D, D->B, E->C)
červená:{A->E, B->A, C->D, D->C, E->B) modrá:{A->C, B->C, C->D, D->E, E->A)
červená:{A->E, B->A, C->D, D->C, E->B) modrá:{A->C, B->E, C->D, D->B, E->C)
červená:{A->E, B->A, C->D, D->C, E->B) modrá:{A->D, B->D, C->E, D->C, E->A)
červená:{A->E, B->A, C->D, D->C, E->B) modrá:{A->D, B->E, C->B, D->C, E->D)
červená:{A->E, B->A, C->E, D->B, E->D) modrá:{A->B, B->C, C->A, D->E, E->D)
červená:{A->E, B->A, C->E, D->B, E->D) modrá:{A->E, B->C, C->A, D->B, E->D)
červená:{A->E, B->C, C->A, D->B, E->D) modrá:{A->D, B->C, C->E, D->B, E->D)
červená:{A->E, B->C, C->A, D->B, E->D) modrá:{A->E, B->A, C->E, D->B, E->D)
červená:{A->E, B->C, C->A, D->B, E->D) modrá:{A->E, B->C, C->E, D->B, E->D)
červená:{A->E, B->C, C->A, D->E, E->B) modrá:{A->C, B->E, C->D, D->A, E->B)
červená:{A->E, B->C, C->A, D->E, E->B) modrá:{A->E, B->C, C->D, D->A, E->B)
červená:{A->E, B->C, C->B, D->A, E->D) modrá:{A->B, B->C, C->D, D->E, E->B)
červená:{A->E, B->C, C->B, D->A, E->D) modrá:{A->B, B->C, C->E, D->B, E->A)
červená:{A->E, B->C, C->B, D->A, E->D) modrá:{A->C, B->D, C->B, D->E, E->C)
červená:{A->E, B->C, C->B, D->A, E->D) modrá:{A->C, B->E, C->B, D->C, E->A)
červená:{A->E, B->C, C->D, D->A, E->B) modrá:{A->B, B->C, C->D, D->E, E->B)
červená:{A->E, B->C, C->D, D->A, E->B) modrá:{A->E, B->C, C->A, D->E, E->B)
červená:{A->E, B->C, C->D, D->A, E->B) modrá:{A->E, B->C, C->D, D->E, E->B)
červená:{A->E, B->C, C->D, D->E, E->B) modrá:{A->D, B->C, C->A, D->E, E->B)
červená:{A->E, B->C, C->D, D->E, E->B) modrá:{A->D, B->E, C->A, D->C, E->B)
červená:{A->E, B->C, C->D, D->E, E->B) modrá:{A->E, B->C, C->D, D->A, E->B)
červená:{A->E, B->C, C->E, D->B, E->D) modrá:{A->C, B->A, C->B, D->E, E->D)
červená:{A->E, B->C, C->E, D->B, E->D) modrá:{A->C, B->A, C->E, D->B, E->D)
červená:{A->E, B->C, C->E, D->B, E->D) modrá:{A->E, B->C, C->A, D->B, E->D)
červená:{A->E, B->D, C->A, D->B, E->C) modrá:{A->B, B->D, C->B, D->E, E->A)
červená:{A->E, B->D, C->A, D->B, E->C) modrá:{A->B, B->D, C->E, D->C, E->B)
červená:{A->E, B->D, C->A, D->B, E->C) modrá:{A->D, B->C, C->E, D->B, E->D)
červená:{A->E, B->D, C->A, D->B, E->C) modrá:{A->D, B->E, C->D, D->B, E->A)
červená:{A->E, B->D, C->A, D->C, E->B) modrá:{A->B, B->D, C->E, D->C, E->B)
červená:{A->E, B->D, C->A, D->C, E->B) modrá:{A->E, B->D, C->E, D->A, E->B)
červená:{A->E, B->D, C->A, D->C, E->B) modrá:{A->E, B->D, C->E, D->C, E->B)
červená:{A->E, B->D, C->B, D->A, E->C) modrá:{A->C, B->D, C->B, D->E, E->C)
červená:{A->E, B->D, C->B, D->A, E->C) modrá:{A->E, B->A, C->B, D->E, E->C)
červená:{A->E, B->D, C->B, D->A, E->C) modrá:{A->E, B->D, C->B, D->E, E->C)
červená:{A->E, B->D, C->B, D->E, E->C) modrá:{A->D, B->A, C->B, D->E, E->C)
červená:{A->E, B->D, C->B, D->E, E->C) modrá:{A->D, B->A, C->E, D->B, E->C)
červená:{A->E, B->D, C->B, D->E, E->C) modrá:{A->E, B->D, C->B, D->A, E->C)
červená:{A->E, B->D, C->E, D->A, E->B) modrá:{A->D, B->E, C->A, D->C, E->B)
červená:{A->E, B->D, C->E, D->A, E->B) modrá:{A->E, B->D, C->A, D->C, E->B)
červená:{A->E, B->D, C->E, D->C, E->B) modrá:{A->C, B->D, C->E, D->A, E->B)
červená:{A->E, B->D, C->E, D->C, E->B) modrá:{A->C, B->E, C->D, D->A, E->B)
červená:{A->E, B->D, C->E, D->C, E->B) modrá:{A->E, B->D, C->A, D->C, E->B)
červená:{A->E, B->E, C->A, D->C, E->D) modrá:{A->C, B->A, C->B, D->E, E->D)
červená:{A->E, B->E, C->A, D->C, E->D) modrá:{A->E, B->A, C->B, D->C, E->D)
červená:{A->E, B->E, C->B, D->C, E->D) modrá:{A->B, B->C, C->A, D->E, E->D)
červená:{A->E, B->E, C->B, D->C, E->D) modrá:{A->B, B->E, C->A, D->C, E->D)
červená:{A->E, B->E, C->B, D->C, E->D) modrá:{A->E, B->A, C->B, D->C, E->D)
červená:{A->E, B->E, C->D, D->A, E->C) modrá:{A->D, B->A, C->E, D->B, E->C)
červená:{A->E, B->E, C->D, D->A, E->C) modrá:{A->E, B->A, C->D, D->B, E->C)
červená:{A->E, B->E, C->D, D->B, E->C) modrá:{A->B, B->D, C->E, D->A, E->C)
červená:{A->E, B->E, C->D, D->B, E->C) modrá:{A->B, B->E, C->D, D->A, E->C)
červená:{A->E, B->E, C->D, D->B, E->C) modrá:{A->E, B->A, C->D, D->B, E->C) 

Maximum pre slučkové je počet krokov 20:

červená:{A->B, B->B, C->C, D->D, E->E) modrá:{A->B, B->C, C->D, D->E, E->A)
červená:{A->B, B->B, C->C, D->D, E->E) modrá:{A->B, B->C, C->E, D->A, E->D)
červená:{A->B, B->B, C->C, D->D, E->E) modrá:{A->B, B->D, C->A, D->E, E->C)
červená:{A->B, B->B, C->C, D->D, E->E) modrá:{A->B, B->D, C->E, D->C, E->A)
červená:{A->B, B->B, C->C, D->D, E->E) modrá:{A->B, B->E, C->A, D->C, E->D)
červená:{A->B, B->B, C->C, D->D, E->E) modrá:{A->B, B->E, C->D, D->A, E->C)
červená:{A->B, B->C, C->D, D->E, E->A) modrá:{A->B, B->B, C->C, D->D, E->E)
červená:{A->B, B->C, C->E, D->A, E->D) modrá:{A->B, B->B, C->C, D->D, E->E)
červená:{A->B, B->D, C->A, D->E, E->C) modrá:{A->B, B->B, C->C, D->D, E->E)
červená:{A->B, B->D, C->E, D->C, E->A) modrá:{A->B, B->B, C->C, D->D, E->E)
červená:{A->B, B->E, C->A, D->C, E->D) modrá:{A->B, B->B, C->C, D->D, E->E)
červená:{A->B, B->E, C->D, D->A, E->C) modrá:{A->B, B->B, C->C, D->D, E->E)
červená:{A->C, B->A, C->D, D->E, E->B) modrá:{A->C, B->B, C->C, D->D, E->E)
červená:{A->C, B->A, C->E, D->B, E->D) modrá:{A->C, B->B, C->C, D->D, E->E)
červená:{A->C, B->B, C->C, D->D, E->E) modrá:{A->C, B->A, C->D, D->E, E->B)
červená:{A->C, B->B, C->C, D->D, E->E) modrá:{A->C, B->A, C->E, D->B, E->D)
červená:{A->C, B->B, C->C, D->D, E->E) modrá:{A->C, B->D, C->B, D->E, E->A)
červená:{A->C, B->B, C->C, D->D, E->E) modrá:{A->C, B->D, C->E, D->A, E->B)
červená:{A->C, B->B, C->C, D->D, E->E) modrá:{A->C, B->E, C->B, D->A, E->D)
červená:{A->C, B->B, C->C, D->D, E->E) modrá:{A->C, B->E, C->D, D->B, E->A)
červená:{A->C, B->D, C->B, D->E, E->A) modrá:{A->C, B->B, C->C, D->D, E->E)
červená:{A->C, B->D, C->E, D->A, E->B) modrá:{A->C, B->B, C->C, D->D, E->E)
červená:{A->C, B->E, C->B, D->A, E->D) modrá:{A->C, B->B, C->C, D->D, E->E)
červená:{A->C, B->E, C->D, D->B, E->A) modrá:{A->C, B->B, C->C, D->D, E->E)
červená:{A->D, B->A, C->B, D->E, E->C) modrá:{A->D, B->B, C->C, D->D, E->E)
červená:{A->D, B->A, C->E, D->C, E->B) modrá:{A->D, B->B, C->C, D->D, E->E)
červená:{A->D, B->B, C->C, D->D, E->E) modrá:{A->D, B->A, C->B, D->E, E->C)
červená:{A->D, B->B, C->C, D->D, E->E) modrá:{A->D, B->A, C->E, D->C, E->B)
červená:{A->D, B->B, C->C, D->D, E->E) modrá:{A->D, B->C, C->A, D->E, E->B)
červená:{A->D, B->B, C->C, D->D, E->E) modrá:{A->D, B->C, C->E, D->B, E->A)
červená:{A->D, B->B, C->C, D->D, E->E) modrá:{A->D, B->E, C->A, D->B, E->C)
červená:{A->D, B->B, C->C, D->D, E->E) modrá:{A->D, B->E, C->B, D->C, E->A)
červená:{A->D, B->C, C->A, D->E, E->B) modrá:{A->D, B->B, C->C, D->D, E->E)
červená:{A->D, B->C, C->E, D->B, E->A) modrá:{A->D, B->B, C->C, D->D, E->E)
červená:{A->D, B->E, C->A, D->B, E->C) modrá:{A->D, B->B, C->C, D->D, E->E)
červená:{A->D, B->E, C->B, D->C, E->A) modrá:{A->D, B->B, C->C, D->D, E->E)
červená:{A->E, B->A, C->B, D->C, E->D) modrá:{A->E, B->B, C->C, D->D, E->E)
červená:{A->E, B->A, C->D, D->B, E->C) modrá:{A->E, B->B, C->C, D->D, E->E)
červená:{A->E, B->B, C->C, D->D, E->E) modrá:{A->E, B->A, C->B, D->C, E->D)
červená:{A->E, B->B, C->C, D->D, E->E) modrá:{A->E, B->A, C->D, D->B, E->C)
červená:{A->E, B->B, C->C, D->D, E->E) modrá:{A->E, B->C, C->A, D->B, E->D)
červená:{A->E, B->B, C->C, D->D, E->E) modrá:{A->E, B->C, C->D, D->A, E->B)
červená:{A->E, B->B, C->C, D->D, E->E) modrá:{A->E, B->D, C->A, D->C, E->B)
červená:{A->E, B->B, C->C, D->D, E->E) modrá:{A->E, B->D, C->B, D->A, E->C)
červená:{A->E, B->C, C->A, D->B, E->D) modrá:{A->E, B->B, C->C, D->D, E->E)
červená:{A->E, B->C, C->D, D->A, E->B) modrá:{A->E, B->B, C->C, D->D, E->E)
červená:{A->E, B->D, C->A, D->C, E->B) modrá:{A->E, B->B, C->C, D->D, E->E)
červená:{A->E, B->D, C->B, D->A, E->C) modrá:{A->E, B->B, C->C, D->D, E->E)

Je tam veľa "podobných" - nemal som zatiaľ čas zistiť, že koľko typov tam reálne je... Snáď keď budem mať čas tak spravím program ktorý to vizualizuje :)

Pomocníci

Tento mesiac som menil zamestnanie a to znamená aj nový počítač s čistým systémom. Postupne si znova inštalujem malých pomocníkov na to aby sa mi pracovalo lepšie. Každý má asi svoju sadu - tak ak máte nápady na niečo lepšie alebo zaujímavé, tak existuje niečo ako komentár k článku :) Toto sú pomocníci čo som si doinštaloval:

• XnView - dakedy som používal Acdsee ale po "objavení" XnView už nič iné nepoužívam na prezeranie fotiek a obrázkov
• Notepad++ - veľmi príjemná náhrada Notepadu pričom toho dokáže oveľa oveľa viac
• Feedreader - RSS čítačka, pravdu povediac má svoje chyby ale zvykol som si na ňu
• Skype - primárny komunikačný nástroj :)
• Icq - keby ste všetci boli konečne na skype tak by som icq nemusel inštalovať :)
• Paint.Net - ak poznáte niekto lepšiu free alternatívu tak sem s ňou, Pain.net je núdzová alternatíva (raz som chcel do nej niečo doprogramovať - je to open source - ten kód čo som videl ma veľmi zhrozil)

Toto sú zas pomocníci čo už boli predinštalovaný:

• FireFox - možno je to len môj subjektívny dojem, ale v najnovšej 3.5 verzii sa mi FireFox zdá pomalší a resource žravejší. IE sa síce zlepšuje, ale stále to nie je ono, Chromý nechcem byť a bol som lenivý ísť do Opery :)
• WinRar - keby nebol pred inštalovaný tak siahnem asi po niečom inom - ale svoj účel spĺňa bez problémov tak nie je dôvod meniť
• Total Commander - no, ešte som ho nespustil :) ale v určitých momentoch je nenahraditeľný :)

Ak máte nápad na niečo zaujímavé a najlepšie free, tak prosím napíšte. Dopredu Vám ďakujem :)

Ctrl + click -> Go To Definition

Zas niečo z programovania - takže "normálni" nečítajte ďalej :) Eclipse som nikdy neprišiel na chuť. Mala pár veci zvládnutých možná lepšie ako VSko, ale aj to niektoré iba do vtedy pokiaľ som nenašiel alebo nedozvedel sa od môjho online helpu (volá sa Jozef :) ) ako na to. To je prípad napríklad Alt+Shift+Enter čo Vám roztiahne editačné okno na celý screen. Čo som si ale zvykol počas tých pár rokov s Eclipsou bol Ctr+click, čo ma vždy priviedlo k definícii symbolu. Vo VSku buď right-click a výber z menu alebo F12 ak už ste na danom symbole. Ak sa človek prehrabáva v kóde tak right-click je zdĺhavý a F12 pre ruku ďaleko. Možno som sa mal spýtať online helpu, ale pre tento raz som využil druhý spôsob a napísal som ujovi Googlovy. Po niekoľkých pokusoch a preformulovávaní správy som našiel pomoc. Nejedná sa ani o macro ani o žiaden add-on. Ide o návod ako použiť pre daný účel AutoHotkey aplikáciu. Návod:

1. Stiahni
2. Pridaj makro

   SetTitleMatchMode RegEx
   #IfWinActive, .* - Microsoft Visual Studio
   
   ^LButton::Send {click}{f12}
   

A je to. Už len nájsť add-on čo by fungoval presne ako alt-šipky vľavo alebo vpravo v Eclipse :)

Pre tvorcov webu

Na začiatku ďakujem JI za tú linku, teda on snáď bude vedieť koho myslím tým JI. Pre ostatných to je ten chlap kvôli ktorému sedím tam kde sedím. Myslim tým novú prácu :) A teraz k linke - Scott Hanselman a Phil Haack v nej po anglicky rozprávajú o niekoľkých aspektoch bezpečnosti webov z hľadiska programátora a ukazujú ako sa niektoré chyby dajú zneužiť. Všetko sa to udialo na Norweigian Developer's Conference 2009. Tu je linka : http://media01.smartcom.no/Microsite/go.aspx?eventid=4468&urlback=null&bitrate=1701831

Prvý počítačový bug bola moľa

Vedeli ste, že prvý počítačový bug bola vlastne moľa? Už to, že slovo bug ktoré je hojne používané medzi programátormi na celom svete, pričom nezáleží na krajine, je pravdepodobne naozaj odvodené od reálneho chrobáka je zaujímavé. A to so zaujímavosťami nekončíme. Prvý bug sa objavil 9 septembra 1945 na prístroji s menom Mark II Computer na Harvardskej Univerzite a je z neho dokonca fotografia Tento bug bola vlastne moľa čo sa dostala do relé a počítač nefungoval správne :) Čo bolo aj riadne zdokumentované. A zaujímavé je aj to, že to bola žena čo "bug" použila - námorná dôstojníčka Grace Murray Hopper. Teda nehovorím to kôli tomu, že by utrpelo moje mužské ego ale terajší pomer programátorov a programátoriek je značný v neprospech žien. Ja osobne by som bral viac žien v našom obore :) Inak 9 september má pre mňa aj osobný význam - teraz nehovorím o roku 1945 ale o roku 2000. Je to dátum mojej svadby :) ale to už bug nebol :)

A je tu znova Sudoku

Včera v noci som išiel spať asi o 2:30. Nepozeral som telku a ani nehral niečo užitočné ako je napríklad CounterStrike :), ale robil som program na hľadanie najťažšieho sudoku. Chcel som to nechať hľadať cez noc. Cca o 1:00 som to nechal aj bežať, prezliekol som sa do pyžama a v tedy ma napadla nejaká optimalizácia. Tak som sa vrátil a dorobil ju. O 2:30 som pokračoval v ceste do postele. Ráno som našiel spadnutý program - došla pamäť - memory leak :) Takže výsledok nebol :( Opravil som memory leak a zistil, že mám v ňom chybu a preto aj keby sa niečo našlo, tak aj tak by to nebolo správne :) V priebehu dňa som spravil potrebné úpravy, spustil počítanie a išiel na hokejbal. Keď som sa vrátil tak počítanie ešte prebiehalo - v podstate by to počítalo ešte asi pár dní - ale aspoň tam bolo vidno najlepší medzivýsledok. Tu je : Kto bude prvý kto ho vyrieši? Napíšte riešenie do komentáru. A prosím nepoužívajte solvery :)

Sudoku

Sudoku je moja obľúbená zábava. Naučil som sa ho lúštiť počas chôdze, v rozbehnutom autobuse, no proste všade kde sa dá. Väčšinou si vytlačím sudoku z http://www.pdfpad.com/sudoku/. Včera som urobil to isté a začal som riešiť toto sudoku (č. c5688 - dá sa znova vytlačiť na tej stránke): Kto ho vyrieši je frajer :). Keďže nie som úplne normálny v takýchto veciach (poznám celú radu ľudí čo Vám to s radosťou odprisahajú :) ), a keď sa niečo spája s matematikou tak sa pre mňa začína zábava ( predpokladám, že pred chvíľkou spomínaný zoznam sa akurát rozrástol o niekoľko ďalších ľudí :) ). Prvé čo človeka napadne je počet všetkých sudoku plôch. Druhé čo ma pri sudoku trápi :) je nájsť čo najobtiažnejšie sudoku. Prvý problém - počet sudoku plôch mi ležal v hlave už dlhšie. Pôvodne som ho chcel vyriešiť sám, ale nejak som sa zamotával a výsledok nikde. Tak som si zavolal toho pána s tým čudným menom. Akože sa len volal? Hmm, ahá už to mám - Mr. Google :) Po krátkom hľadaní som našiel veľmi zaujímavý článok "Mathematics of Sudoku I" od Bertram Felgenhauer a Frazer Jarvis. Pokiaľ Vám matematika nevonia a predsa len chcete kliknúť na danú linku, odporúčam najprv zavolať vymetača diabla. V prípade, že ste už klikli na odkaz, odložte všetky ostré predmety a hláste sa na najbližšej psychiatrii :) Ale teraz vážne, v tom článku je postup veľmi podobný tomu v mojej hlave, dokonca aj brute force časť kde treba niečo naprogramovať je tam. Rozdiel je, že v tom článku sa dotiahli veci ďalej ako som ich dotiahol ja. Článok nie je písaný nejakou hroznou matematickou rečou tak pre toho koho to naozaj zaujíma to bude poučné čítanie. Ja už len dodám, že výsledok je

6 670 903 752 021 072 936 960

Pekne veľké číslo :) A teraz poďme na najťažšie sudoku. Tu si chcem ale vystačiť bez toho pána s tým zvláštnym menom. Prvé čo je treba je si definovať čo chceme dosiahnuť - najťažšie sudoku je predsa len príliš vágny pojem.

1. sudoku musí byť jednoznačné - inak povedané je len jedno riešenie
2. definovať funkciu "ťažkosti" - každému sudoku treba vedieť priradiť jednoznačne číslo - váhu, najväčšie číslo bude najťažšie sudoku

Prvá časť sa overí riešením sudoku. Samozrejme, že to ale nebudem riešiť ja ale nejaký ten počítač. Druhá časť je už skôr empirická a každý môže rôznym situáciám priradiť iné váhy. Ale najprv si preberme situácie (zóna sa myslí ako 9tica - buď celý stĺpec, celý riadok alebo sudoku štvorec 3x3) :

1. Existuje políčko pre ktoré jednoznačne existuje číslo N - je to jediná možná pozícia pre N v zóne pretože ostatné pozície sú buď už vyplnené alebo ich kryje pozícia ďalšieho N
2. Existuje políčko pre ktoré jednoznačne existuje číslo N - existujú prípady keď neplatí prvý prípad ale Nko je ako jediné možné v zóne - všetky ostatné čísla kryjú danú pozíciu
3. Neexistuje žiadne jednoznačné číslo - je treba si zvoliť v nejakom políčku jedno číslo z možných čísel pre dané políčko a skúsiť vyriešiť sudoku. Ak neexistuje riešenie tak treba zvoliť ďalšie číslo a opakovať postup pokiaľ sa nenájde riešenie

To sú základne situácie. Keďže pri riešení sudoku nastanie viac takýchto situácií tak si treba zvoliť spôsob agregácie a podla toho aj zvoliť ohodnotenie situácie. Najjednoduchšie čo môžeme použiť je aditívna alebo multiplikatívna agregácia. Ja sa prikláňam k multiplikativnej agregácii kde sa hodnoty násobia. Váha prvej možnosti bude 1,01. Ak by sme dali iba 1 tak potom by sudoku s viac číslami na začiatku malo rovnaké číslo obtiažnosti. Takto to to bude síce malá hodnota ale pomôže to usporiadať obtiažnosti. V druhom prípade dáme 1,2. Vo väčšine prípadov nie je obtiažne doplniť dané číslo. Posledný prípad je ale trošku komplikovaný. Nechcem priradiť nejaké konkrétne číslo ale nejakú inú hodnotu ktorá reflektuje obtiažnosť riešenia sudoku pre všetky možné čísla v danom políčku. Použijeme aditívnu agregáciu obtiažnosti pre všetky riešenia sudoku s možnými číslami pre dané políčko. Keďže z prvého problému vieme, že všetkých možných plôch sudoku je obrovské množstvo a nie je reálne pri terajšej výpočtovej kapacite vyskúšať všetky možnosti, preto sa uspokojíme s náhodným sudoku. Samozrejme, že to znamená, že asi nenájdem najobtiažnejšie sudoku, ale predpokladám, že to čo nájdem bude tiež stáť za to.

sudoku = náhodná plocha sudoku
náhodne odoberieme polovicu čísel
počítaj(sudoku)

funkcia počítaj(sudoku)
{
        riešime sudoku a zároveň pri riešení zistíme obtiažnosť
        ak ( sa nedá jednoznačne vyriešiť)
                     tak ukonči funkciu
        ak ( vypočítaná obtiažnosť je väčšia ako najväčšia obtiažnosť doteraz) tak
                     aktuálne sudoku je pre teraz najobtiažnejšie sudoku
        cyklus (pre všetky zostávajúce čísla)
        {
                 odoberieme dané číslo zo sudoku
                 počítaj( sudoku)
                 vrátime dané číslo na svoje miesto
         }
}

Výpočtová zložitosť bude poriadna. Predpokladám, že ma čaká veľa optimalizovania :) Dúfam že v blízkej budúcnosti sa tu objaví hrozne ťažké sudoku :)

PR0GR4M470R5K4 UL0H4

Tento blogový príspevok je čisto o programovaní a matematike. Koho tieto oblasti nezaujímajú, odporúčam nečítať ;) Málokto z programátorskej komunity mohol prehliadnuť Esetácku domácu úlohu. Úlohu dali na web a ak ju pošleš dobre vyriešenú Esetu tak máš šancu u nich na zamestnanie. Nie že by som sa uchádzal u nich o zamestnanie, to zatiaľ nie. Dlho som odolával, ale po tom čo som videl ako sa s ňou trápi moje okolie, tak som neodolal a venoval som jej jeden večer. Ale musím priznať, že treba pripočítať takú hodinku až dve, ktoré som využil na rozmyslenie si ako na to. Zadanie Máte zoznam súborov, v ktorom je každý súbor identifikovaný menom a podpisom. Meno je ľubovoľný reťazec v úvodzovkách a podpis je postupnosť nezáporných 32-bitových čísiel v šestnástkovej sústave ako môžete vidieť na obr. 01. "test_name" 3a 45ffa2 236da0 34cc 21 "/usr/stdio.h" 456fa 34dd 28ab9 457e ".other.txt" 5623d ff3a21 783d 22456 Obr. 01: formát zoznamu súborov Vašou úlohou je nájsť počet jedinečných súborov v zozname. Súbor je považovaný za jedinečný, ak jeho podpis nie je riadnym prefixom podpisu akéhokoľvek iného súboru v zozname. Podpis s1 je považovaný za riadny prefix podpisu s2 vtedy (a len vtedy), keď s2 začína s s1 a podpisy majú rôzne dĺžky. V prípade, že viaceré súbory majú rovnaký podpis, započítajte ich všetky. Viac sa môžete dozvedieť na linke http://www.3537.sk/programator.html. Riešenie V prvom rade si musíme rozmyslieť ako budeme uchovávať údaje. Najjednoduchší spôsob by asi bol, načítať všetko do pamäte do poľa . V danom prípade by sme sa mohli hrať s tým poľom rôznym spôsobom. Napríklad utriediť ho a potom porovnávať iba susediace prvky a prefixové podpisy označovať. Nakoniec jednoducho spočítať neoznačené prvky. V tomto prípade by bolo sortovanie časovo najdlhšou operáciou. Využitie pamäte by bolo dosť obrovské, ale viac na záver v časti úvah. Spôsob, akým ja chcem ukladať údaje je les - teda viac stromov. Prvé číslo podpisu by bol koreň stromu. Nasledujúce číslo by bolo jeho dieťa a ďalšie číslo dieťa dieťaťa, a tak ďalej. Každý prvok stromu by mal smerník na prvého syna a zároveň smerník na ďalšieho syna otcovského uzla. Každý uzol okrem týchto dvoch smerníkov obsahuje aj DWORD hodnotu uzla a koľko krát bol už uzol započítaný. O poslednej premennej si povieme viac za chvíľku pri popise akým spôsobom budeme napĺňať strom. Naplňanie stromu bude prebiehať nasledujúcim spôsobom:

while (fileReader.ReadNext())
   memory.AddSignature(fileReader.CurrentItems(), fileReader.CurrentItemsCount());

Pričom fileReader je trieda, ktorá načítava údaje riadok po riadku a fileReader.CurrentItems() je smerník na pole DWORDov aktuálneho riadku fileReader.CurrentItemsCount() je počet DWORDov získaných z predchádzajúcej funkcie Fungovanie AddSignature vidno na obrázku

obr.2

Tento algoritmus zatiaľ len napĺňa les ale nedovolí nám vypočítať počet jedinečných súborov. V tomto momente by problém spôsobovali duplicitné podpisy. Ak by duplicitné podpisy neexistovali tak by stačilo spočítať počet listov stromu. Riešením by bolo v každom liste mať premennú ktorá by počítala početnosť. To by sa dalo počítať tak, že po ukončení algoritmu v danej funkcii zistiť, či posledne spracovávaný otec má nejaké dieťa a ak nie tak zvýšiť početnosť v danom otcovi. No a potom už nepočítať počet listov ale počítať s početnosťou listov, teda podpisov končiacich v danom liste. Tento postup by ale znamenal post-proces po vytvorení dát a ak by sa dalo tak by bolo dobré sa mu vyhnúť. Hlavne v prípade, že výsledok sa dá počítať priebežne bez veľkých nárokov na pamäť a procesor. A to sa jednoduchým spôsobom dá. Potrebujeme jednú premennú ktorá bude udržiavať aktuálnu hodnotu. Potom necháme počítanie početnosti listov, ale v momente ako zvyšujeme početnosť v liste tak zvýšime hodnotu aj v aktuálnej premennej. V tomto momente nám spôsobujú problém iba listy, ktoré prestanú byť listami pri pridaní nového podpisu. A to sa deje na jedinom mieste v algoritme a to je v oranžovom obdĺžniku na obr.2. Stačí nám pridať odpočítanie početnosti daného uzla (bývalého listu) od aktuálnej premennej. Ešte jednu vec treba popísať a to je zelený obdĺžnik - Inicializácia údajov. Potrebujeme inicializovať hodnoty otca a dieťaťa. Otec na začiatku neexistuje a teda je NULL. Problém je s dieťaťom. Les máme našťastie spravený tak ako keby to bol strom, len koreň je virtuálny, teda máme pospájané korene pomocou smerníkov Ďaľší. Okrem prvého podpisu keď je aj dieťa neexistujúce, stačí nastaviť dieťa ako prvý koreň. Algoritmus sa už postará o zvyšok prehľadaním všetkých koreňov. Druhý spôsob je vytvoriť si hashovaciu mapu. Kľúč by bola prvá hodnota podpisu. Hodnota by zas bol smerník na prislúchajúci koreň hodnoty kľúča. Rozdeľ v spracovaní je pri týchto dvoch postupoch markantný. Testy na Eseťáckom set_large.dat v prvom prípade trvali cca 150s a v druhom prípade iba 1.5s. Celá funkcia vyzerá potom takto

template<typename T>
void CMemory<T>::AddSignature(T * values, int count)
{
    if ( !count)
        return;

    MemoryItem<T> *child = NULL;
    MemoryItem<T> *parent = NULL;

    stdext::hash_map <T, MemoryItem<T> *>::iterator iter = m_TopItems.find(*values);

    if ( iter != m_TopItems.end())
        child = iter->second;

    bool topItem = true;

    for ( int i = 0; i < count; i++)
    {
        if ( !child)
        {
            MemoryItem<T> *newItem = Add( values[ i]);
            if ( topItem)
            {
                std::pair <T, MemoryItem<T> *> p( *values, newItem);
                m_TopItems.insert(p);
            }

            if (parent)
            {
                m_Counter -= parent->Count;
                parent->Count = 0;
                parent->Child = newItem;
            }

            parent = newItem;
            child = NULL;
        }
        else
        {
            T &curValue = values[ i];
            MemoryItem<T> *last = NULL;
            bool found = false;

            while (child)
            {
                last = child;

                if ( child->Value == curValue)
                {
                    parent = child;
                    child = parent->Child;
                    found = true;

                    break;
                }

                child = child->Next;
            }

            if ( !found)
            {
                MemoryItem<T> *newItem = Add( curValue);
                last->Next = newItem;
                parent = newItem;
                child = NULL;
            }
        }

        topItem = false;
    }

    if ( parent)
    {
        if ( !parent->Child)
        {
            parent->Count++;
            m_Counter++;
        }
    }
}

A zabudol som poznamenať, že dátová časť je spravená cez template funkcionalitu, takže miesto DWORDu sa dá použiť ľubovoľný typ ktorý podporuje porovnanie (==). Ďalším dôležitým faktorom rýchlosti je aj akým spôsobom sú ukladané dáta. Ja nealokujem jednotlive malé štruktúry ale mám list väčších polí, pričom ten list podla potreby rozširujem. A sme hotový. Stačí už len výpis:

std::wcout << L"Unique items : " << memory.GetCount() << std::endl << std::endl;

Záver No čo na záver? Výsledky pri Eseťáckych súboroch set_small.dat 851 set_large.dat 96312 Ešte budem musieť doplniť pár úvah o pamäťovej a procesorovej náročnosti. Do konca roka to snáď stihnem :) Zdrojový kód Môj kód som poslal do Esetu tak prosím nezneužite ho a nepošlite len jeho upravenú verziu. Eset.zip