Összetett feladatok az STL-hez

Ne töröld ki a meglévő kódot! Elsőre felépíteni azt a tárolót, amiben gyakoriság szerint vannak csoportosítva a szavak, nagyon nehéz lenne. A feladat igazából az, hogy a meglévő tárolót feldolgozva építs fel egy másikat.

Ügyelni kell arra, hogy egy gyakorisághoz több szó is tartozhat. Például a fenti bemenetnél az almának és a körtének is 1 a gyakorisága. Csinálhatunk olyan leképezést, aminél a gyakoriság a kulcs, de akkor egy kulcshoz több értéket is kell tárolni.

A megoldás pl. egy map<int, vector<string>> lehet; ez egy kulcshoz több értéket is tud tárolni.

Az alábbi mintamegoldás a hecc kedvéért nem tartalmaz ciklust.

#include <iostream>
#include <map>
#include <string>
#include <iterator>
#include <algorithm>
#include <vector>

int main() {
    std::map<std::string, int> m;
    for_each(std::istream_iterator<std::string>(std::cin),
             std::istream_iterator<std::string>(),
             [&] (std::string s) {
                 ++m[s];
             });
             
    std::cout << "Szavak szerint:" << std::endl;
    for_each(m.begin(), m.end(), [] (auto p) {
        std::cout << p.first << " " << p.second << std::endl;
    });

    std::cout << "Gyakoriság szerint:" << std::endl;
    std::map<int, std::vector<std::string>> mm;
    for_each(m.begin(), m.end(), [&] (auto p) {
        mm[p.second].push_back(p.first);
    });
    for_each(mm.begin(), mm.end(), [] (auto p) {
        std::cout << p.first << " ";
        std::copy(p.second.begin(), p.second.end(), std::ostream_iterator<std::string>(std::cout, " "));
        std::cout << std::endl;
    });
}

Az std::tuple hasonló az std::pair osztályhoz: egy ad-hoc adatcsomag, de nem két elemből, hanem bármennyiből.

A pair érdekessége, hogy definiálja a relációs operátorokat, ==, != és a többiek. Ezek az operátorok előbb a first, aztán a second adattagot hasonlítják össze. A tuple ugyanezt csinálja: megvizsgálja az első adatot, ha abból nem dől el, akkor a másodikat, és így tovább. A dátumoknál pont ez kell nekünk: az év kisebb-e vagy nem; ha az évek egyformák, akkor a hónap kisebb-e vagy nem, és végül a nap.

Minden háznál azt kell megjegyezni, hogy voltunk-e már ott, vagy nem. Azaz hogy láttuk-e már azt a pozíciót, vagy nem. Ha többször voltunk ott, az nem számít már. Ez egy matematikai fogalomhoz vezet.

A pozíció egy egész számpárral adható meg.

A megoldás egy halmaz, amelynek a számossága a kérdés. A pozíciót egy egész számpár (std::pair<int, int>) tárolhatja. Ez azért előnyös, mert annak van < operátora, amit amúgy a halmaz igényel.

#include <iostream>
#include <utility>
#include <set>
#include <sstream>

int main() {
    std::istringstream is("^>v<");
    
    using position = std::pair<int, int>;
    std::set<position> visited;
    position pos = {0, 0};
    visited.insert(pos);
    char c;
    while (is >> c) {
        switch (c) {
            case '<': pos.first--; break;
            case '>': pos.first++; break;
            case '^': pos.second++; break;
            case 'v': pos.second--; break;
        }
        visited.insert(pos);
    }
    std::cout << visited.size();
}

A pozíciókat leképezzük egy egész számra: hány ajándék került oda.

Van, nem kell megírni: std::max_element. De hogy kell paraméterezni?

A tároló map<position, int> lehet. Ha egy ilyenen iterálunk, látjuk azt is, hogy miket tartalmaz: pair<position, int>-eket, ahol p.first a kulcs és p.second az érték. A maximumkeresésnél az értéket figyeljük, ezért a max_element függvénynek adott lambda a second adattagokat hasonlítja össze.

#include <iostream>
#include <utility>
#include <map>
#include <algorithm>
#include <fstream>

int main() {
    std::ifstream is("santa.txt");
    
    using position = std::pair<int, int>;
    std::map<position, int> presents;
    position pos = {0, 0};
    presents[pos] += 1;
    char c;
    while (is >> c) {
        switch (c) {
            case '<': pos.first--; break;
            case '>': pos.first++; break;
            case '^': pos.second++; break;
            case 'v': pos.second--; break;
        }
        // itt figyelni kellene arra, hogy a mozgás elmaradása esetén
        // a növelés elmaradjon (pl. szóköz van a bemeneti fájlban) 
        presents[pos] += 1;
    }
    // ellenőrzés: hova mennyi került?
    // for (auto const& pair : presents)
    //     std::cout << pair.first.first << ";" << pair.first.second
    //               << " -> " << pair.second << std::endl;

    auto it = std::max_element(presents.begin(), presents.end(),
        [] (std::pair<position, int> a, std::pair<position, int> b) {
            return a.second < b.second;
        });
    std::cout << "Legtöbb ajándék: " << it->second << " darab, "
              << "(" << it->first.first << ";" << it->first.second << ")" << std::endl;
}

Az adatszerkezet kizárja, hogy azonos oszlopban vagy azonos sorban több királynő helyezkedjen el. Ez azt jelenti, hogy már csak azt kell vizsgálnunk, hogy átlósan támadják-e egymást.

Átlósan akkor támadják egymást, ha a sorok és oszlopok szerinti távolságuk megegyezik: Δx = Δy. Figyelve persze arra, hogy a távolságok abszolút értékét vegyük: (2;2) és (2;-2) is támadásnak számít, az egyik ╱, a másik ╲ irányban.

Az nqueen_ok() függvényben minden királynő (i) pozícióját összevetjük minden további királynővel (j). A sort a tömbindexek adják meg, az oszlopot a tömbértékek. Mivel j>i, az egyik abszolút érték elmaradhat – igaz, gond sem lenne belőle.

#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>

void nqueen_print(std::vector<int> const &queens) {
    for (int i = 0; i < (int)queens.size(); ++i) {
        for (int j = 1; j <= (int)queens.size(); ++j)
            std::cout << (queens[i] == j ? 'X' : '.');
        std::cout << std::endl;
    }
    std::cout << std::endl;
}

bool nqueen_ok(std::vector<int> const &queens) {
    for (int i = 0; i < (int)queens.size()-1; ++i)
        for (int j = i+1; j < (int)queens.size(); ++j)
            if (j-i == std::abs(queens[j]-queens[i]))
                return false;
    return true;
}

int main() {
    std::vector<int> queens(8);
    std::iota(queens.begin(), queens.end(), 1);
    do {
        if (nqueen_ok(queens))
            nqueen_print(queens);
    } while (std::next_permutation(queens.begin(), queens.end()));
}

Alább egy másik lehetőség, amelyben std::all_of-ot és std::none_of-ot használunk. std::all_of, mindegyik királynőnek olyannak kell lennie, hogy std::none_of, semelyik másikat nem üti. Az i és j változók, továbbá az abszolút érték ugyanolyan szerepűek, mint a fenti kódban. A megoldás Dobos-Kovács Mihály ötletét kiegészítve készült.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>

int main() {
    std::vector<int> pos = {1, 2, 3, 4, 5, 6, 7, 8};
    std::vector<int> const idxs = {0, 1, 2, 3, 4, 5, 6, 7};
    std::vector<std::vector<int>> solutions;

    do {
        if (std::all_of(idxs.begin(), idxs.end() - 1, [&](int i) {
            return std::none_of(idxs.begin() + i+1, idxs.end(), [&](int j) {
                return j-i == std::abs(pos[i]-pos[j]);
            });
        })) solutions.push_back(pos);
    } while (std::next_permutation(pos.begin(), pos.end()));

    for (auto const & solution: solutions) {
        for (auto pos : solution)
            std::cout << pos;
        std::cout << std::endl;
    }
}