10. hét: λ

Függvény építése RPN kifejezésből

Az RPN jelölésben (Reverse Polish Notation) az operátorokat az operandusokat után írjuk: "2 3 +" jelentése 2+3, és "2 3 + x *" jelentése (2+3)*x. Egy ilyen kifejezés egy veremmel könnyen kiértékelhetjük. Pl. konstans feldolgozásához bedobjuk a verembe a számot, műveletnél pedig a verem tetején lévő két számot kell kivenni, elvégezni a műveletet, és az eredményt visszatenni a verembe. A műveletsor végére egyetlen egy szám kell legyen a veremben, ami az eredmény.

Ha függvényt kell előállítani ("2 3 + x *" → (2+3)*x), akkor ugyanígy lehet gondolkodni, csak a veremben függvényeknek kell lenniük. Ebben a feladatban ezt kell megoldanod. Kell egy olyan függvényt írnod, amelyik megkapja a sztringet, és visszatér egy egyváltozós matematikai függvénnyel. Ez utóbbi bárhányszor meghívható, különböző x értékekkel:

auto f = create_func_from_rpn("21.7 34.2 x * +");     // f = 21.7+34.2*x

std::cout << f(3) << std::endl;                 // 21.7+34.2*3 értéke
std::cout << f(4) << std::endl;                 // 21.7+34.2*4 értéke
std::cout << f(5) << std::endl;                 // 21.7+34.2*5 értéke

Oldd meg ezt úgy, hogy 1) a sztringet csak egyszer dolgozod fel, a create_func_from_rpn() függvényhíváskor, 2) nem definiálsz saját osztályt, tisztán csak beépített eszközöket használsz! Írj std::move-ot, ahova csak lehet!

#include <iostream>
#include <functional>
#include <stack>
#include <string>
#include <sstream>
 
std::function<double(double)> create_fun_from_rpn(std::string const & rpn) {
    std::istringstream is(rpn);
    
    std::stack<std::function<double(double)>> s;
    std::string word;
    while (is >> word) {
        if (word == "x") {
            s.push([](double x) { return x; });
        }
        else if (word == "+") {
            auto rhs = std::move(s.top()); s.pop();
            auto lhs = std::move(s.top()); s.pop();
            s.push([lhs = std::move(lhs), rhs = std::move(rhs)](double x) {
                return lhs(x) + rhs(x);
            });
        }
        else if (word == "*") {
            auto rhs = std::move(s.top()); s.pop();
            auto lhs = std::move(s.top()); s.pop();
            s.push([lhs = std::move(lhs), rhs = std::move(rhs)](double x) {
                return lhs(x) + rhs(x);
            });
        }
        else {
            double d = std::stod(word);
            s.push([d](double x) { return d; });
        }
    }
    
    return std::move(s.top());
}
 
int main() {
    std::cout << "Ird be a fuggvenyt RPN alakban!" << std::endl;
    std::string line;
    std::getline(std::cin, line);
    auto f = create_fun_from_rpn(line);
    
    std::cout << f(3) << std::endl;
    std::cout << f(4) << std::endl;
    std::cout << f(5) << std::endl;
}

Hanoi tornyai

Klasszikus példa a rekurzióra az ún. Hanoi tornyai játék. Ebben a korongokat át kell tenni az első rúdról a harmadikra, de úgy, hogy 1) egyszerre csak egy korongat mozgathatunk, 2) kicsi korongra nagyot nem tehetünk. A középső oszlop ideiglenes tárolónak használható.

Négy korong esetén ez a lépéssorozat adja a megoldást: A→B, A→C, B→C, A→B, C→A, C→B, A→B, A→C, B→C, B→A, C→A, B→C, A→B, A→C, B→C. A látszólag bonyolult probléma rekurzív megoldása pár soros: n-1 korong mozgatása, alsó korong mozgatása, megint n-1 korong mozgatása.

#include <iostream>

void hanoi(int n, char honnan, char seged, char hova) {
    if (n == 0)
        return;
    hanoi(n-1, honnan, hova, seged);
    std::cout << "Rakd a korongot " << honnan << " oszloprol " << hova << " oszlopra\n";
    hanoi(n-1, seged, honnan, hova);
}

int main(void) {
    hanoi(4, 'A', 'B', 'C');
}

Írd át úgy a programot, hogy a hanoi() függvénynek ötödik paraméterként lehessen átadni, mit tegyen a kiírás helyett! Az std::cout... kezdetű sor helyett legyen egy függvényhívás, ahol a paraméterként átvett, void(char, char) alakú függvény megkapja a honnan és hova oszlopok jeleit!

• Írd meg először úgy, hogy a hanoi() függvény sablon legyen. Az átvett függvény, az ötödik paraméter miatt kell ennek sablonnak lennie.
• Hívd meg úgy a függvényt, hogy lambda kifejezésben az eredeti kiírást adod meg neki!
• Módosítsd a lambda kifejezést úgy, hogy be legyenek számozva a lépések!
• Írd meg úgy is, hogy sablonfüggvény helyett std::function paraméterű legyen a hanoi() függvény! Működik úgy is, ha a lambda kifejezésben C++14-es count = 0 capture-specifier-t használsz? Mit kell tenni ahhoz, hogy működjön?

#include <iostream>

template <typename FUNC>
void hanoi(int n, char honnan, char seged, char hova, FUNC f) {
    if (n == 0)
        return;
    hanoi(n-1, honnan, hova, seged, f);
    f(honnan, hova);
    hanoi(n-1, seged, honnan, hova, f);
}

int main(void) {
    int count = 0;
    hanoi(4, 'A', 'B', 'C', [&count] (char honnan, char hova) {
        std::cout << ++count << ": rakd a korongot " << honnan << " oszloprol " << hova << " oszlopra\n";
    });
}

#include <iostream>
#include <functional>

/* a függvényt const & kell átvenni, hogy a rekurzióban ne másolódjon le
 * - mert akkor másolódna a számláló is! */
void hanoi(int n, char honnan, char seged, char hova,
           std::function<void(char, char)> const & f)
{
    if (n == 0)
        return;
    hanoi(n-1, honnan, hova, seged, f);
    f(honnan, hova);
    hanoi(n-1, seged, honnan, hova, f);
}

int main(void) {
    hanoi(4, 'A', 'B', 'C', [count = 0] (char honnan, char hova) mutable {
        std::cout << ++count << ": rakd a korongot " << honnan << " oszloprol " << hova << " oszlopra\n";
    });
}

Ezek a feladatok az előadás Solver osztályához kapcsolódnak.

Solver osztály – bármilyen típusra

Az előadás Solver osztálya letölthető a fenti a linkről. Ennek a változatnak van egy sablonparamétere: milyen típusú változókon dolgozik. Meg lehet úgy is oldani a feladatot, hogy erre ne legyen szükség: hogy a Solver különféle típusokon is tudjon dolgozni.

(Ehhez az összetartozó tároló-iterátor párosokból egy osztályt kell csinálni, megszünetetve a párhuzamos tömböket. Utána az osztályt kell sablonná tenni, és a különféle Variable<T>-knek pedig egy közös őst kell létrehozni (type erasure), hogy az újdonsült tárolójukban heterogén kollekcióként lehessen tárolni őket.)

Oldd meg így a feladatot! Ha mindent jól csinálsz, az alábbi programrész működni fog:

int main() {
    NewSolver t;

    /* Bugyuta példa: kilistázza azokat a (szám;szó) párokat,
     * amelyeknél hossz(szó) = szám */
    auto size = t.add_variable({1,2,3,4,5});
    auto word = t.add_variable({"alma", "korte", "barack"});
    t.add_constraint([=] {
        return size() == (int) strlen(word());
    });
    t.solve([=] {
        std::cout << "strlen(" << word() << ") = " << size() << std::endl;
    });
}

Egyediek

Elég sok olyan feladatot adtunk a laborban Solver-nek, ahol előírtuk azt, hogy az összes tesztelt változó értéke különféle kell legyen: ilyen a send+more=money (minden betű értéke különbözik), és ilyen az emeletes házas feladat is (mindenki más emeleten lakik).

Egészítsd ki a Solver osztályt megkötés mintákkal! Az egy ilyen minta lehet az, hogy bizonyos változók értéke nem lehet egyforma. Például:

Solver<int> s;
s.add_alldifferent_constraint({baker, cooper, fletcher, miller, smith});

Permutáció

Néhány feladatnál, amit láttunk, ennél is szigorúbb megkötés van: minden értéket hozzá kell rendelnünk egy változóhoz, és pontosan annyi változó van, ahány érték. Matematikailag: nem a feltételeknek megfelelő variációt, hanem a feltételeknek megfelelő permutációt keresünk. Másképp fogalmazva, nem a halmazok Descartes-szorzatával előálló halmazban keressük a megoldást, hanem egyetlen egy halmaz lesz, és annak permutációi között.

A nyolckiránynő-probléma pont ilyen: tudjuk, hogy minden sorban egy királynő van, és azt is tudjuk, hogy mindegyik oszlophoz pontosan egy királynőt kell rendelni. De tulajdonképp ilyen volt az emeletes házas feladat is.

Dolgozd át az osztályt úgy, hogy ne variációk, hanem permutációk keresésére legyen alkalmas, és azokat keresse hatékonyan! Vigyázz: ez egy teljes újragondolást jelent.

send + more = money

... ahol minden betű különböző, és persze s és m nem lehetnek 0 értékűek, mert akkor nem lennének 4, illetve 5 betűsek a számok. Rengeteg ilyen rejtvény van (kapcsolódó Wikipedia szócikk: https://en.wikipedia.org/wiki/Verbal_arithmetic). Némelyiknek egy megoldása van (crack + hack = error), másoknak több (four + five = nine).

Írj C++ programot a Solver segítségével (vagy a permutációs változatával, vagy anélkül), amelyik általánosságban képes ilyeneket megoldani!