Adventi naptár

Feladat: írjunk függvényt, amelyik egy paraméterként kapott sztringből eltávolítja a szóközöket. A sztring módosítását a függvény helyben végezze, vagyis nem kell új tömböt foglalni, se az eredményt egy, a forrástól eltérő tömbben tárolni. Írjuk meg a függvényt úgy, hogy a C nyelvű kódja karakterek számában a lehető legrövidebb legyen!

Alább látható a jelenleg ismert legrövidebb megoldás, amely 43 karakteres. Hogy hogyan jutottunk el ide, az szép sorban a függvényeken látszik. Az operátoros bűvészkedés ötletekért köszönet jár Kovács Dávidnak is.

a()

Az első (a) megoldás tömbként kezeli a sztringeket. Ez a triviális megoldás – for ciklussal végigmegyünk a sztring karakterein, és ha nem szóközt találunk, akkor azt másoljuk. A szóközök kihagyásával a forrás és cél indexek elcsúsznak, ezért két változóra van szükség (i a forrás és j a cél). Mivel i>=j minden pillanatban, ezért segédtömbre nincs szükség; mit[j]-vel csak olyan helyre írunk, amit a mit[i]-vel már vizsgáltunk és feldolgoztunk. A sztringben előrefelé haladunk, és pont a másik irányba tömörödik. (Az int visszatérési érték a későbbiek miatt van, amúgy void lenne a logikus.)

int a(char *mit) {
    int j=0;
    for (int i=0; mit[i]!=0; ++i) {
        if (mit[i]!=' ') {
            mit[j]=mit[i];
            j++;
        }
    }
    mit[j]=0;

    return 0;
}

b()

Kezdjük el rövidíteni a kódot. Az intuíció azt súgja, hogy érdemes pointerekre áttérni; a *mit rövidebb, mint a mit[i]. A paraméterként kapott „mit” pointert úgyis megváltoztathatjuk, hiszen az egy lokális változó – legyen ez a forrás pointer, és egy új változó a cél pointer. Ha nem szóközt találunk, azt a *cel++=*mit-tel másoljuk át; ez a precedencia szabályai és a postfix increment operátor működése miatt azt jelenti, hogy { *cel=*mit; cel++; } – vagyis pont jó.

int b(char *mit) {
    char *cel=mit;
    while (*mit!=0) {
        if (*mit!=' ')
            *cel++=*mit;
        mit++;
    }
    *cel=0;

    return 0;
}

c()

Az elöltesztelő ciklus addig megy, amíg 0-t nem talál, és akkor kilép. Ezért a lezáró nullát külön kell odatennünk. Ha kicseréljük egy hátultesztelőre, akkor automatikusan a lezáró 0 is át fog másolódni. (Hiszen az nem szóköz!) Itt a „mit” pointer növelését is elrejtettem a ciklus feltételében.

int c(char *mit) {
    char *cel=mit;
    do {
        if (*mit!=' ')
            *cel++=*mit;
    } while (*mit++);

    return 0;
}

d()

Mit lehetne még rövidíteni? Először is, minden változónevet cseréljünk ki egy betűsre. Az aposztrófok közötti szóközt pedig cseréljük ki 32-re, hiszen az ugyanazt jelenti, de rövidebb egy karakterrel. Ha void lenne a függvény, akkor a return 0 is elhagyható lenne, de azzal továbbra is tervek vannak, úgyhogy egyelőre marad.

Az if (*m-32) kis magyarázatot igényel. Az előbbi *mit!=' ' feltételből lett, ami *mit!=32-t jelent. Ha a *mit-ből kivonunk 32-t, akkor 0-t fogunk kapni, ha *mit eredetileg szóköz volt, és a feltétel nem teljesül; ha eredetileg nem szóköz, akkor pedig nem 0 lesz az eredmény, amely a C szerint igazra értékelődik ki. Ezért jelenti ugyanazt a *mit!=' ' és a *mit-32.

int d(char *m) {
    char *c=m;
    do {
        if (*m-32)
            *c++=*m;
    } while (*m++);

    return 0;
}

e()

A fent említett terv pedig az, hogy az int szót elhagyjuk, mivel a C szabvány történelmi okokból megengedi, hogy a függvénynek ne adjuk meg a visszatérési típusát. Ilyenkor az intre defaultol. A return 0-t is nagyvonalúan elhagytam – innentől jönnek a warningok a fordítótól, de működni ettől még működik. A szóközöket is elhagytam. Jelen állapotban a függvény 53 karakterből áll.

e(char*m){char*c=m;do{if(*m-32)*c++=*m;}while(*m++);}

f()

Jó a hátultesztelő ciklus, de van benne egy fölösleges do szó, és ott vannak a blokkot jelző {} karakterek. Térjünk vissza elöltesztelőre, 4 karaktert próbálva spórolni ezzel. A karaktert a ciklus fejlécében mindig átmásolom, és ha rájövök (if), hogy egy szóközt másoltam, akkor a már megnövelt pointert csökkentem eggyel, hogy legközelebb felülírjam. A c-1-re azért van szükség, mert a másoláskor c már megnövekedett (c++). Mire az if-hez jut a végrehajtás, a c++ hatása már biztos megtörténik, mert a while után szekvenciapont van. Egyelőre ez nőtt egy karakterrel, de idővel...

f(char*m){char*c=m;while(*c++=*m++)if(*(c-1)==32)c--;}

g()

Ha a *(c-1) helyett *--c-t írunk, akkor megspóroljuk a zárójelet a nekünk kedvező precedenciaszabályok miatt. Ilyenkor viszont ész nélkül mindig csökkentjük a feltételben a pointert, vagyis nem szóköz esetén kell majd csökkenteni, hanem minden más esetben visszanövelni. Itt is a feltétel után szekvenciapont van, vagyis biztos csökken a c az összehasonlítás előtt (amúgy is prefixes), a c++ pedig a lecsökkentettet növeli vissza. 52 karakter.

g(char*m){char*c=m;while(*c++=*m++)if(*--c!=32)c++;}

h()

Nem nagy különbség; a !=32-t újra visszaírom -32-re, ami kevésbé olvasható, de rövidebb. 51 karakter.

h(char*m){char*c=m;while(*c++=*m++)if(*--c-32)c++;}

i()

Az if is minimum két fölösleges karaktert behoz, a zárójeleket a feltétel körül. Ha kicserélem egy && operátorra, akkor ezeket meg tudom spórolni. Az && operátor rövidzár * tulajdonsága miatt a jobb oldali kifejezés nem értékelődik ki, ha a bal oldali hamis, vagyis pont az if működését kapom meg. Így a c növelésének eldöntése egyetlen egy kifejezéssé rövidült, *--c-32&&c++. Szerencsére az && operátor alacsony precedenciájú, zárójelekre nincs szükség.

Érdekes itt amúgy a gcc „value computed not used” hibaüzenete. A *--c-32&&c++ kifejezés miatt szól, arra utalva, hogy az és kapcsolat értékét (0 vagy 1) nem használjuk semmire. Nekünk viszont most ez nem célunk. Úgy látszik, ez a fordító szerint is idióta használata a && operátornak. Ugyanígy, a ciklus fejlécében lévő feltételre is figyelmeztetést küld, mivel általában ott kulturált kódban nem szerepelne olyan kifejezés, aminek mellékhatása van. 49 karakter.

i(char*m){char*c=m;while(*c++=*m++)*--c-32&&c++;}

j()

Túl sok a ++ és --, ezért átrendezzük őket. A ciklus fejlécében, a másolásnál a cél pointert még nem növeljük meg, hanem majd csak akkor, ha nem spacet másoltunk. Ezzel egy increment és egy decrement operátort is megspórolunk – visszakaptuk az első változat if-jét, csak menet közben a sok increment/decrement logikusabbnak tűnt.

j(char*m){char*c=m;while(*c=*m++)*c-32&&c++;}

k()

A while is elég hosszú kulcsszó, lecseréljük for-ra. Ez azért előnyös, mert a fornál külön hely van, ahol elhelyezhetünk egy utasítást, amelyik a ciklus előtt csak egyszer fut le, és külön hely van a feltételnek (ahova a másolást rejtjük). Az első helyre a változódeklarációt berakva még egy pontosvesszőt spórolhatunk. Ezt a C++-nak kinéző dolgot a C99 megengedi. Ha már mindent ide rakunk, akkor a szóközök ellenőrzését is berakjuk a for ciklus fejlécének a harmadik boxába. Ettől rövidebb nem lesz, viszont úgy néz ki, mintha üres ciklus lenne – az összes művelet a fejlécbe van rejtve. 44 karakter.

k(char*m){for(char*c=m;*c=*m++;*c-32&&c++);}

l()

Még egy karaktert lehet tömöríteni a fenti programrészleten. A for(;;) ciklus harmadik ficakjában lévő kifejezést, a 32-set ugyanis másképp is meg lehet fogalmazni. Ennek célja az, hogy a c pointer értékét növelje akkor eggyel, ha nem szóköz volt a másolt karakter. Ezt meg lehet fogalmazni így is: c+=*c!=32. Ha a másolt karakter (*c) szóköz, akkor 32 a karakterkódja, vagyis a kifejezés hamisra, nullára értékelődik ki. Ha nem szóköz, akkor viszont igazra, vagyis egyre. Ezt a nullát vagy egyet adjuk hozzá a pointerhez, ezáltal léptetve azt a következő karakterre, vagy meghagyva az aktuálison (Marosi Gergely ötlete nyomán). 43 karakter.

l(char*m){for(char*c=m;*c=*m++;c+=*c!=32);}

Ez tűnik a legrövidebb változatnak. A dolog érdekessége, hogy egyébként maga a kód sem tartalmaz szóközöket – ha már az a feladata, hogy kiszedje azokat egy sztringből. :) A szóköz az úgyis felesleges karakter lenne, ami a függvény hosszát növeli. Amiatt tudjuk az összeset megspórolni, hogy a pointereket jelző *-ok elválasztják a char szót a változó nevétől. A másolást és a space vizsgálatát nem tűnik úgy, hogy szét lehet szedni egy kifejezésbe, mert a másolás eredményét külön ki kell értékelni (hogy nulla-e, mert az a sztring vége).

A lenti main() itt arra jó, hogy kipróbálja az összes függvényt. Azért int az első, a() függvények visszatérési típusa is, hogy mind kompatibilisek legyenek. Remélem, tetszik mindenkinek a függvénypointerekből álló tömb deklarációja. :) Ennek értelmezése: ha megindexeljük a fuggvenyek tömböt [], akkor kapunk valamit, ami egy pointer (*). Ez a pointer egy függvényre mutat (), amelyet ha meghívunk egy char * paraméterrel, akkor egy int-et ad vissza.

#include <stdio.h>
#include <string.h>

int main()
{
    char eredeti[]=" Ez egy   proba  szoveg. ", szoveg[30];
    int (*fuggvenyek[])(char *)={a, b, c, d, e, f, g, h, i, j, k, l, NULL};
    
    printf ("Eredeti: [%s]\n", eredeti);
    
    for (int i=0; fuggvenyek[i]!=NULL; ++i) {
        strcpy(szoveg, eredeti);
        fuggvenyek[i](szoveg);
        printf("%c. [%s]\n", 'a'+i, szoveg);
    }

    return 0;
}

A program teljes forráskódja: advent6-spacetelenito.c.

Rekurzió – Nagy Gergely megoldása

A ciklus rekurzióra cserélhető. Ilyenkor a for szó helyett egy egybetűs függvénynév szerepelhet. A következő rekurzív megoldással az a baj, hogy két paramétert vár. Emiatt sajnos nem teljesíti a specifikációt. Úgy lehet egyébként indítani, hogy kétszer kell megadni ugyanazt a sztringet paraméternek. A két paraméter tölti be a két lokális változó szerepét is.

m(char*e,char*c){*e&&m((*e=*c)-32?e+1:e,c+1);}

Rekurzió II. – Andrika Dávid megoldása

A fentihez hasonlóan ez sem tartalmaz a char-on kívül más C kulcsszót. Egy kicsit rövidebb a fentinél. a+=*b!=32 – ha a b pointer által mutatott karakter nem szóköz (32), akkor a kifejezés jobb oldala igazra, azaz 1-re értékelődik ki. Vagyis akkor az a pointer ugrik a következő karakterre.

n(char*a,char*b){(*a=*b)&&n(a+=*b!=32,b+1);}

Rekurzió III. – Garami Bence megoldása

Ennek nincs két paramétere, mint az eddigieknek, viszont hosszabb. Kihasznája az implicit int visszatérési típust, sőt konkrétan egy karakterkóddal tér vissza. A kapott stringen kívül más segédváltozót nem használ. Ez úgy lehetséges, hogy szóközökkel fenntartja a távolságot (az előfordult szóközszámot) a következő karaktertől, így ezt a távolságot nem kell külön eltárolni, mindig elsétál odáig majd visszamásolja.

t(char*s){return*s-32||(*s=t(s+1),s[1]=32),*s&&t(s+1),*s;}

Kohári Zsolt megoldása – hátrafelé indexelés

A lenti függvény a következőképpen működik. s a spacetelenítendő sztring, d pedig egy integer. A ciklus feltételében egy összetett kifejezés van. A 32==*s++ kifejezésben *s a karakter; ha ez space, akkor igazra értékelődik ki a kifejezés (1), hanem, hamisra (0). Vagyis space esetén a d változó értéke eggyel csökken. (Közben az s pointer ugrik a következő karakterre.) Az s tömböt ezzel a d változóval indexeli; d értéke egészen addig 0, amíg az első space elő nem kerül, utána pedig spacenként egyre csökken az értéke. Vagyis az s pointer minden karakter megvizsgálása után nő, de a d változóval hátrafelé, negatív irányba indexelődik (ezt szabad!); mindig annyival, ahány space karaktert ki kellett hagyni. A megfelelő helyre pedig a következő karakter (*s) átmásolódik.

A megoldás sajnos nem működik minden fordítóval. Az s pointert három helyen is kiértékeli; és van benne egy mellékhatással járó kifejezés, s++. Ez a szabvány szerint nem definiált működés, mivel a hatása nem lehet tudni, hogy mikor jelenik meg. Azt sem lehet tudni (ezt sem köti meg a szabvány), hogy az értékadás bal vagy jobb oldala értékelődik ki először. Vagyis sajnos ez nem helyes megoldás, de jó kis ötleteket tartalmaz!

o(char*s){for(int d=0;s[d-=32==*s++]=*s;);}

Holló Norbert megoldása – ?: operátor

A lenti függvényben két változóval indexelődik az s karaktertömb. A ciklus fejlécében a kifejezés először veszi a tömb n-edik karakterét. Ha az nem space, akkor a ?: operátorban a ? utáni kifejezés fog kiértékelődni; ha space, akkor pedig a : utáni. A karakter megvizsgálása után n biztosan megnövekszik, mert a ?: operátorban a kérdőjel egyben szekvenciapont is. Ha nem space volt, akkor az s[v++] helyre másolódik a vizsgált karakter (a -1 miatt még azt a karaktert látni, amelyiket a feltétel is vizsgált). Ha space volt, akkor nem történik semmi; az 1 kifejezésnek nincs hatása. Az 1-es csak azért kell, mert valaminek muszáj a : után lennie (különben szintaktikailag hibás lenne a kifejezés), de azért is, mert igazra kell kiértékelődnie az egész kifejezésnek. Lévén, ez még mindig a ciklus feltétele! Vagyis ha az s[n] karakter space volt, akkor biztosan fut tovább a ciklus (1). Ha nem space volt, akkor a másolás, mint kifejezés eredményétől függ; ha a másolt karakter 0, akkor a ciklus leáll (ez a sztring vége), egyébként pedig fut tovább.

p(char*s){int n=0,v=0;while(s[n++]!=32?s[v++]=s[n-1]:1);}