Excel - csoportok színezése

Ebben a leírásban egy igazából az oldal profiljába nem vágó, de gondolkodtató feladatot írok le, amellyel a napokban találkoztam, majd adok rá egy megoldást is.

Az oldalnak nem nagyon vág a profiljába ez a leírás, talán annyiban, hogy a programozáshoz némileg köze van, mégis ajánlom elolvasni. Javaslom, hogy először a feladatkiírást értelmezve próbáld meg megoldani magad a feladatot (a megadott szabályoknak megfelelően), majd ha sikerült, vagy feladtad, nézd meg az általam írt megoldást a részletes leírással. Ha Te máshogy oldanád meg, azt kérlek írd meg egy hozzászólásba, egy darabig nekem gondolkoznom kellett rajta.

A feladat a következő: adott egy tetszőleges méretű Excel tábla, amely egyik oszlopa alapján rendezve van. Ezen oszlopban előfordulnak megegyező elemek. Például:

CMS	tutorial.hu videó – új cikk felvétele
CMS	Wordpress és Facebook összekötése
CMS	WordPress manuális frissítése 3.0-ra
CMS	Letölthető a Wordpress 3.0
Grafika	76 ingyenesen letölthető vektor grafika
Grafika	Photoshop fotó retusálás – előtte és utána – 2
Grafika	Photoshop fotó retusálás – előtte és utána – 1
Grafika	Újabb ingyenes ikon gyűjtemény
Kódolás	Hosszú linkek és szövegek megtörése
Kódolás	Megosztás-sáv készítése jQuery-vel, összesített képekkel
Kódolás	CSS 3 gradiens a Firefox 3.6-ban
Kódolás	Hogyan használj bármilyen betűtípust a weben? (Cufón)

A feladat: színezzük ki ezt a táblát két színnel úgy, hogy azok a sorok, amelyeknél megegyezik az első oszlop tartalma azonos színt kapjanak.

CMS	tutorial.hu videó – új cikk felvétele
CMS	Wordpress és Facebook összekötése
CMS	WordPress manuális frissítése 3.0-ra
CMS	Letölthető a Wordpress 3.0
Grafika	76 ingyenesen letölthető vektor grafika
Grafika	Photoshop fotó retusálás – előtte és utána – 2
Grafika	Photoshop fotó retusálás – előtte és utána – 1
Grafika	Újabb ingyenes ikon gyűjtemény
Kódolás	Hosszú linkek és szövegek megtörése
Kódolás	Megosztás-sáv készítése jQuery-vel, összesített képekkel
Kódolás	CSS 3 gradiens a Firefox 3.6-ban
Kódolás	Hogyan használj bármilyen betűtípust a weben? (Cufón)

További kikötések:

• Az Excelen belül kell maradni. Semmilyen külső eszköz nem használható
• Csak Feltételes formázás és Excel-képlet használható

A következőkben az én megoldásom szerepel, de gondolkodtató feladványról lévén szó, ajánlom, hogy először próbáld magadtól megoldani!

Alapesetben ez egy egyszerű probléma, a megoldása triviális. Tároljuk egy változóban az utolsóként használt színt, majd soronként haladva a táblázatban ellenőrizzük, hogy az aktuális sor első oszlopa megegyezik-e az előzővel, ha nem, akkor színt cserélünk. Minden sort fessünk be olyanra, amilyen szín épp a változóban van. PHP-szerű pszeudó-kódban:

<?php
$color = 0;
$last = array('');	/* Így inicializálunk, plusz egy feltételt megúszunk a ciklusban */
$lines = file($bemeneti_file); /* Beolvassuk a filet */
foreach($lines as &$line) {
	if($line[0] != $last[0]) {	/* Új érték az első oszlopban */
		$color = ($color == 0) ? 1 : 0;	/* Színcsere */
	}
	colorize($line, $color);	/* Képzeletbeli színező függvény */
}
?>

Csakhogy az Excel-ben nem nagyon lehet változókat és ciklust használni, és ez így túl egyszerű lenne, nincs benne kihívás. Más megoldás után kell néznünk!

Közelítsük meg más irányból a dolgot: ki tudjuk-e vajon számolni, hogy hány egyedi név fordult elő a táblában az aktuális sor fölött? Nem akarok senkit rémisztgetni az ezt a számolást végrehajtó köztes próbálkozásaimmal; a végleges megoldásomban a kulcsszó: rekurzió. Hogyan tudjuk ezt egyszerűen kiszámolni? Tegyük fel, hogy tudjuk, hogy az előző sor előtt hány egyedi érték volt. Ezután az aktuális sorra vonatkozó értéket megkaphatjuk, ha megvizsgáljuk, hogy az előző sorban levő értékkel megegyezik-e a jelenlegi sorban levő érték; ha igen, akkor ugyanannyi egyedi érték volt az aktuális sor felett, mint az előző felett, ha nem, akkor nem. Így a ciklust visszavezethetjük a rekurzió műveletre!

Egy új oszlopban (legyen a C) az első sorba vegyük fel a 0 értéket (mert ugye rekurziónál mindig kell, hogy legyen érték, aminél már nincs újabb hívás!). Utána a következő sorba szúrjuk be a =C1+HA(A1=A2;0;1) képletet, és húzzuk végig a teljes táblázaton. A rekurzív hívást láttán sokan azonnal letesznek egy-egy algoritmus használatáról, mert az úgyis lassú lesz (tévedés, algoritmustól függ, hogy mennyiszer számol feleslegesen), de ha megnézzük ebben az esetben ez O(n)-es (vagyis annyi hívás van, ahány sor), tehát nem lassabb, mint a fenti ciklust használó kódunk.

Ekkor a C oszlopban megkaptuk, hogy hány egyedi elem volt az adott sor fölött. Innen már triviális a megoldás, a változó használatát egyszerűen kikerüljük két feltételes formázási szabály használatával. Ha ugyanis egy sorban ez az érték páros, akkor az egyik színnel festjük, ha nem, akkor a másikkal (=MARADÉK(INDIREKT('C'&SOR();2)=0 és nem egyenlő párja).

Mi a leírás tanulsága? Azon kívül, hogy minden, egy pár perc alatt összedobható scripttel megoldható probléma kiterjeszthető fél órás gondolkodást igénylő problémává? Megfelelő módon ábrázolt adatokkal (legyen az a leírásban levő hozzáadott számérték, egy self-balancing bináris fa, akármi) sok probléma megoldható elegáns (itt: rövid, hatékony) algoritmussal.