Algorithm on dice game (two players)

Question

Algorithm on dice game (two players)

Navigation

#1 by (1 votes)

0

The problem I want to solve is not to get a solution to the problem, but to make it more efficient , in particular, go from O (N²) to O (N) or O (N) log (N)) if possible.

Context: problem raised at the university about a dice game .

Basically the game consists of the following: each player rolls a die and the one that gets the highest score wins.

The "grace" of the game is that the dice are not normal , they have between 1 and 100000 numbered faces each with numbers between 1 and 10000, such data entered via keyboard.

The question to be answered is, if you give me the option to choose the die first, which dice do I choose to have the highest probability of winning?

My proposal (and solution, I think effective) not efficient:

int main() {
    int caras;

    int tope_wins = caras * caras * 0.5;
    int wins = 0;

    vi faces1(caras, 1), faces2(caras, 1);

    for (int i = 0; i < caras; i++) {
        cin >> faces1[i];
    }
    for (int i = 0; i < caras; i++) {
        cin >> faces2[i];
    }

    sort(faces2.begin(), faces2.end());
    sort(faces1.begin(), faces1.end(), greater<int>());

    for (int i = 0; i < caras; i++) {
        if (faces1[i] > faces2[0]) {
            for (int j = 0; j < caras; j++) {
                if (faces1[i] <= faces2[j]) {
                    continue;
                }
                if (faces1[i] > faces2[j]) {
                    wins++;
                }
            }
        }
    }

    if (wins == tope_wins || wins == 0)
        cout << "NO GANA NADIE\n";
    else if (wins > tope_wins)
        cout << "GANA EL PRIMERO\n";
    else if (wins < tope_wins)
        cout << "GANA EL SEGUNDO\n";


    return 0;
}

You can see how I check only the number of times the first die entered on the screen would win, saving us some iterations for having ordered the values of the faces before.

According to the professor, there must be a solution to this problem more efficient than this one.

Execution example:

D1: 4 4 4 8 11 11

D2: 1 1 9 9 9 9

WIN THE FIRST

In summary: you are given to choose two uncommon dice (many faces with values in each of them without following any sequence). How to choose the one with the highest probability of winning after many throws (the one that obtains the highest value when shooting, after throwing many times), but we only want to know which one we have left to start playing.

c++ eficiencia

asked by Juane Garcia Martinez 19.12.2018 в 18:17

source

1 answer

how to order numbers from highest to lowest with lambda expression Know when addChildEventListener has finished

score 1 · Answer 1

I have finally managed to do it, without having to make expensive * expensive iterations to check each of the possible combinations of dice, checking who wins in each roll:

#include <bits/stdc++.h>
#include <iostream>
#include <vector>

using namespace std;

typedef vector<int> vi;

const int CASO_ESPECIAL = 0;

int main() {
    int faces;

    cin >> faces;
    int ptr1 = 0, ptr2 = 0;
    int wins1 = 0, wins2 = 0;
    int ptr1aux = 0, ptr2aux = 0;

    vi faces1(faces, 1), faces2(faces, 1);

    for (int i = 0; i < faces; i++) {
        cin >> faces1[i];
    }
    for (int i = 0; i < faces; i++) {
        cin >> faces2[i];
    }

    sort(faces1.begin(), faces1.end());
    sort(faces2.begin(), faces2.end());

    while (ptr1 < faces || ptr2 < faces) {
        if (ptr2 == faces || (ptr1 < faces && faces1[ptr1] < faces2[ptr2])) {
            ptr1++;
            wins1 += ptr2;
            ptr1aux = ptr1;
        } else if (ptr1 == faces ||
                (ptr2 < faces && faces1[ptr1] > faces2[ptr2])) {
            ptr2++;
            wins2 += ptr1;
            ptr2aux = ptr2;
        } else {
            int repeated = (ptr1 < faces) ? faces1[ptr1] : faces2[ptr2];
            while (ptr1 < faces && faces1[ptr1] == repeated) {
                ptr1++;
                wins1 += ptr2aux;
            }
            while (ptr2 < faces && faces2[ptr2] == repeated) {
                ptr2++;
                wins2 += ptr1aux;
            }

            ptr1aux = ptr1;
            ptr2aux = ptr2;
        }
    }

    if (wins1 > wins2)
        cout << "WINS 1\n";
    else if (wins1 < wins2)
        cout << "WINS 2\n";
    else
        cout << "NOBODY WINS\n";

    return 0;
}