Un test a 100/100 Italian Scopa

Aiuto
1

Buongiorno, sto provando a risolvere il problema Italian Scopa, mi trovo a due test case dal 100% ma non riesco a capire il baco nella logica del mio programma.

Ho usato comb_mat in modo esplicito solo per velocizzare il programma a run-time.

Il codice:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

struct Card {
    int rank;
    char suit;

    Card(int rank, char suit) {
        this->rank = rank;
        this->suit = suit;
    }

    bool operator==(const Card &other) const {
        return suit == other.suit && rank == other.rank;
    }

    string to_string() const {
        return ::to_string(rank) + string(1, suit);
    }
};

int main() {
    const int HAND = 3;
    const int TABLE = 4;

    vector<Card> hand;
    vector<Card> table;

    for (int i = 0; i < HAND; i++) {
        int rank;
        char suit;
        scanf("%d%c", &rank, &suit);
        hand.emplace_back(rank, suit);
    }

    for (int i = 0; i < TABLE; i++) {
        int rank;
        char suit;
        scanf("%d%c", &rank, &suit);
        table.emplace_back(rank, suit);
    }

    bool comb_mat[16][TABLE] = {
            {false, false, false, false},
            {false, false, false, true},
            {false, false, true,  false},
            {false, false, true,  true},
            {false, true,  false, false},
            {false, true,  false, true},
            {false, true,  true,  false},
            {false, true,  true,  true},

            {true,  false, false, false},
            {true,  false, false, true},
            {true,  false, true,  false},
            {true,  false, true,  true},
            {true,  true,  false, false},
            {true,  true,  false, true},
            {true,  true,  true,  false},
            {true,  true,  true,  true}
    };

    vector<Card> best;
    Card settebello = Card(7, 'G');

    int found_7s_out = 0;
    bool settebello_out = false;
    bool scopa_out = false;

    for (int i = 0; i < HAND; i++) {
        for (int j = 0; j < 16; j++) {
            vector<Card> curr;

            int found_7s_in = 0;
            bool settebello_in = false;
            bool scopa_in = false;

            if (hand[i] == settebello) {
                settebello_in = true;
            }

            if (j == 16 - 1) {
                scopa_in = true;
            }

            int rank_sum = 0;

            for (int k = 0; k < TABLE; k++) {
                Card card = table[k];
                if (comb_mat[j][k]) {
                    curr.push_back(card);
                    rank_sum += card.rank;
                    if (card == settebello) {
                        settebello_in = true;
                    }
                    if (card.rank == 7) {
                        found_7s_in++;
                    }
                }
            }

            if (rank_sum == hand[i].rank) {
                if (!(settebello_out && !settebello_in)) {
                    settebello_out = settebello_in;
                    if (!(scopa_out && !scopa_in)) {
                        scopa_out = scopa_in;
                        if (found_7s_in > found_7s_out || (found_7s_in == found_7s_out && curr.size() > best.size())) {
                            found_7s_out = found_7s_in;
                            curr.push_back(hand[i]);
                            best = curr;
                        }
                    }
                }
            }
        }
    }

    for (const Card &card: best) {
        cout << card.to_string() << ' ';
    }

    return 0;
}

Sicuramente il problema sta nel come trovo la miglior mossa (best).

Se qualcuno l’ha fatto, chiedo un aiutino :pray:

2

In effetti il problema dovrebbe riguardare la scelta della best move come puoi verificare con questo input:

6S 8B 9C
2G 1S 5C 3B

il tuo codice restituisce 1S 5C 6S, mentre la soluzione corretta è 2G 1S 3B 6S.

Una soluzione è quella di aggiungere un contatore di carte in modo da prendere la somma che si può ottenere con il max numero di carte a terra.
Un altro modo per facilitare la ricerca della soluzione è quello di suddividere il problema nei 4 sottoproblemi come suggerito dal testo: settebello, scopa, altro 7 e mossa migliore.
In questo modo devi solo risolvere e completare l’ultimo sottoproblema.

3

Hai ragione.
Fixato il problema, ho seguito il tuo consiglioe ho suddiviso i sottopreoblemi riscrivendo l’intera logica del programma…per trovarmi a passare ancora meno test ahhahahah LOL :melting_face:

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cmath>

using namespace std;

struct Card {
    int rank;
    char suit;

    Card(int rank, char suit) {
        this->rank = rank;
        this->suit = suit;
    }

    Card() {
    }

    Card(Card const &card) {
        rank = card.rank;
        suit = card.suit;
    }

    bool operator==(const Card &other) const {
        return suit == other.suit && rank == other.rank;
    }
};

ostream &operator<<(ostream &strm, const Card &card) {
    return strm << to_string(card.rank) + string(1, card.suit);
}

bool contains_seven(const vector<Card> &cards) {
    for (const Card &card: cards) {
        if (card.rank == 7) {
            return true;
        }
    }
    return false;
}

int main() {

    const int HAND = 3;
    vector<Card> hand;

    for (int i = 0; i < HAND; i++) {
        int rank;
        char suit;
        scanf("%d%c", &rank, &suit);
        hand.emplace_back(rank, suit);
    }

    const int TABLE = 4;
    vector<Card> table;

    for (int i = 0; i < TABLE; i++) {
        int rank;
        char suit;
        scanf("%d%c", &rank, &suit);
        table.emplace_back(rank, suit);
    }

    map<int, vector<Card>> map_settebello;
    map<int, vector<Card>> map_scopa;
    map<int, vector<Card>> map_seven_or_num;

    for (int i = 1; i < pow(TABLE, 2); i++) {

        int rank_sum = 0;
        vector<Card> comb;

        bool found_settebello = false;
        bool found_seven = false;

        for (int j = 0; j < TABLE; j++) {
            if (i & (1 << j)) {
                Card card = table[j];
                if (card.rank == 7) {
                    if (card.suit == 'G') {
                        found_settebello = true;
                    }
                    found_seven = true;
                }
                rank_sum += card.rank;
                comb.push_back(card);
            }
        }

        if (rank_sum > 10) {
            continue;
        }

        if (found_settebello) {
            auto it_settebello = map_settebello.find(rank_sum);
            if (it_settebello != map_settebello.end()) {
                if (comb.size() > it_settebello->second.size()) {
                    it_settebello->second = comb;
                }
            } else {
                map_settebello[rank_sum] = comb;
            }
        }

        if (comb.size() == TABLE) {
            map_scopa[rank_sum] = comb;
        }

        auto it_seven_or_num = map_seven_or_num.find(rank_sum);
        if (it_seven_or_num != map_seven_or_num.end()) {
            if (found_seven == contains_seven(it_seven_or_num->second)) {
                if (comb.size() > it_seven_or_num->second.size()) {
                    it_seven_or_num->second = comb;
                }
            } else {
                if (found_seven && !contains_seven(it_seven_or_num->second)) {
                    it_seven_or_num->second = comb;
                }
            }
        } else {
            map_seven_or_num[rank_sum] = comb;
        }
    }

    vector<Card> best_pick;
    Card best_card;

    for (int i = 0; i < HAND; i++) {
        Card curr_card = hand[i];

        auto it_settebello = map_settebello.find(curr_card.rank);
        if (it_settebello != map_settebello.end()) {
            best_pick = it_settebello->second;
            best_card = curr_card;
            break;
        }

        auto it_scopa = map_scopa.find(curr_card.rank);
        if (it_scopa != map_scopa.end()) {
            best_pick = it_scopa->second;
            best_card = curr_card;
            break;
        }

        auto it_seven_or_num = map_seven_or_num.find(curr_card.rank);
        if (it_seven_or_num != map_seven_or_num.end()) {
            if (curr_card == Card(7, 'G')) {
                best_pick = it_seven_or_num->second;
                best_card = curr_card;
                break;
            }
            int my_sevens = (int) (contains_seven(it_seven_or_num->second)) + (int) (curr_card.rank == 7);
            int best_pick_sevens = (int) (contains_seven(best_pick)) + (int) (best_card.rank == 7);
            if ((my_sevens > best_pick_sevens) ||
                (my_sevens == best_pick_sevens && it_seven_or_num->second.size() > best_pick.size())) {
                best_pick = it_seven_or_num->second;
                best_card = curr_card;
            }
        }
    }

    best_pick.push_back(best_card);
    for (const Card &card: best_pick) {
        cout << card << ' ';
    }

    return 0;
}

Rispetto a prima mi pare più corretta, ma anche troppo lunga.

Mi sto perdendo qualche struttura dati che protrebbe aiutarmi o ridurre il codice ?

4

Non occorre nessuna struttura particolare per risolvere il task oltre quelle che stai utilizzando.
A ridurre la lunghezza del codice lo puoi sempre fare in un secondo momento quando hai risolto il task.
Non ho verificato completamente il codice per individuare dove si trova l’eventuale bug che non ti permette di chiudere correttamente il task.
Provo a riassumere il lavoro fatto per arrivare a 100/100 suddividendo il task in 4 sottoproblemi nello stesso ordine come richiesto:

  1. settebello
    prendere il settebello in mano o a terra solo con un altro 7

  2. scopa
    cercare se in mano c’é una carta che prende tutte quelle a terra

  3. sette+
    verificare quanti più sette si possono prendere con una mossa (1 o 2), nel caso in cui un 7 è in mano (1) oppure un 7 è a terra (1) oppure un 7 è in mano e uno a terra (2).
    Per questo sottoproblema non viene richiesto di massimizzare il numero di carte da prendere.

  4. best move
    cercare la mossa per massimizzare il numero di carte da prendere a terra.

P.S.
In questo modo ti dovrebbe essere anche più agevole generare testcase con cui verificare la tua soluzione.