J'en ai un dur pour toi!

Ma copine a récemment rencontré une nouvelle émission sur MTV (USA). C'est un spectacle terrible, et tout le monde est trash, mais le "jeu" est assez intéressant. De Wikipédia:

Es-tu l'élu? suit 20 personnes qui vivent ensemble à Hawaï pour trouver leur partenaire idéal. Si les 10 hommes et 10 femmes sont en mesure de choisir correctement les dix matches parfaits en dix semaines, ils gagneront 1 million de dollars à répartir entre eux.

Maintenant pour la partie du jeu (également de Wikipedia):

Chaque épisode, le casting s'associera à ceux qui, selon eux, sont le match parfait pour participer à un défi. Les gagnants du défi auront un rendez-vous et auront la chance de tester leur match dans la cabine de vérité. Les acteurs choisiront l'un des couples gagnants pour se rendre au stand de vérité afin de déterminer s'ils correspondent parfaitement ou non. C'est le seul moyen de confirmer les correspondances. Chaque épisode se termine par une cérémonie d'appariement où les couples seront informés du nombre de correspondances parfaites qu'ils ont, mais pas des correspondances correctes.

TL; DR: Il s'agit d'un dérivé de Mastermind (M (10,10) pour être spécifique). Les règles du jeu sont les suivantes:

1. Vous commencez avec 2 séries de 10, appelons-les Ensemble A: {A, B, C, D, E, F, G, H, I, J} et Ensemble 2: {1,2,3,4,5, 6,7,8,9,10}

2. L'ordinateur crée une solution (non visible pour vous) sous la forme de {A1, B2, C3, D4, E5, F6, G7, H8, I9, J10}, où les membres de l'ensemble A sont mappés 1 à 1 pour définir 2. Un autre exemple de solution pourrait être {A2, B5, C10, D8, E1, F7, G6, H4, I9, J3}.

3. Avant votre premier tour, vous pouvez demander si une seule paire particulière de votre choix est correcte. Votre question serait sous la forme de {A1} (par exemple {C8}), et vous recevez soit 1 (signifiant correct) soit 0 (signifiant que votre supposition est incorrecte).

4. Votre premier tour réel. Vous faites votre première supposition sous la forme de {A1, B2, C3, D4, E5, F6, G7, H8, I9, J10}, ou toute permutation de votre choix. Votre estimation ne peut contenir de multiples d'aucun élément, c'est-à-dire qu'une estimation de {A1, A2, A3, A4, A5, B6, B7, B8, B9, B10} n'est PAS une estimation valide. Après chaque tour, l'ordinateur vous indique le nombre de correspondances correctes, mais PAS les correspondances correctes.

5. Répétez les étapes 3 et 4 jusqu'à ce que chaque match soit correct (c.-à-d. Une réponse de 10), ou jusqu'à ce que vos 10 mouvements soient en hausse (selon la première éventualité). Si vous le résolvez avant ou à votre 10e tour, vous gagnez 1 million de dollars. Sinon, vous perdez, et certaines personnes (ou lettres et chiffres) rentrent seules chez elles pour passer l'éternité avec leurs 10 chats.

Ce n'est PAS un concours de code le plus court. La personne qui peut résoudre un appariement aléatoire dans le moins moyen nombre d'essais sera le gagnant. Un jeu intelligent et une vitesse de calcul seront également pris en compte. Je suppose que le nombre moyen de tours sera presque certainement supérieur à 10, donc les chances de gagner le prix de 1 million de dollars (vraisemblablement payé par MTV, pas moi) sont minces. À quel point est-il impossible pour le casting de remporter le grand prix?

Remarque: Le mettre au format {A1, B2, ...} n'est pas nécessairement requis. J'ai simplement utilisé ce formulaire dans la question pour clarifier ce qu'est le puzzle. Si vous ne le mettez pas dans ce formulaire, veuillez simplement expliquer comment l'appeler.

Bonne chance!

Python 2 (exécutez plus rapidement si vous utilisez Pypy)

On croit presque toujours deviner le bon appariement en 10 tours ou moins

Mon algorithme est tiré de ma réponse pour le cerveau comme mon hobby (voir dans Ideone ). L'idée est de trouver la supposition qui minimise le nombre de possibilités restantes dans le pire des cas. Mon algorithme ci-dessous le force simplement brutalement, mais pour gagner du temps, il suffit de choisir au hasard si le nombre de possibilités restantes est supérieur à RANDOM_THRESHOLD. Vous pouvez jouer avec ce paramètre pour accélérer les choses ou pour voir de meilleures performances.

L'algorithme est assez lent, en moyenne 10 secondes pour une exécution s'il est exécuté à l'aide de Pypy (si vous utilisez un interpréteur CPython normal, c'est environ 30 secondes), je ne peux donc pas le tester sur toutes les permutations. Mais les performances sont assez bonnes, après environ 30 tests, je n'ai vu aucun cas où il ne pouvait pas trouver le bon appariement en 10 tours ou moins.

Quoi qu'il en soit, si cela est utilisé dans une émission réelle, il a beaucoup de temps avant le prochain tour (une semaine?), Donc cet algorithme peut être utilisé dans la vraie vie = D

Je pense donc qu'il est prudent de supposer qu'en moyenne, cela trouvera les bons appariements en 10 suppositions ou moins.

Essayez-le vous-même. Je pourrais améliorer la vitesse dans les prochains jours (EDIT: il semble difficile de continuer à s'améliorer, je vais donc laisser le code tel size=7quel . J'ai essayé de faire un choix aléatoire, mais même à , il échoue dans 3 des 5040 cas , j'ai donc décidé de garder la méthode la plus intelligente). Vous pouvez l'exécuter comme:

pypy are_you_the_one.py 10

Ou, si vous voulez simplement voir comment cela fonctionne, entrez un nombre plus petit (pour qu'il s'exécute plus rapidement)

Pour exécuter un test complet (avertissement: cela prendra très longtemps pour size> 7), mettez un nombre négatif.

Test complet pour size=7(terminé en 2m 32s):

...
(6, 5, 4, 1, 3, 2, 0): 5 suppositions
(6, 5, 4, 2, 0, 1, 3): 5 suppositions
(6, 5, 4, 2, 0, 3, 1): 4 suppositions
(6, 5, 4, 2, 1, 0, 3): 5 suppositions
(6, 5, 4, 2, 1, 3, 0): 6 suppositions
(6, 5, 4, 2, 3, 0, 1): 6 suppositions
(6, 5, 4, 2, 3, 1, 0): 6 suppositions
(6, 5, 4, 3, 0, 1, 2): 6 suppositions
(6, 5, 4, 3, 0, 2, 1): 3 suppositions
(6, 5, 4, 3, 1, 0, 2): 7 suppositions
(6, 5, 4, 3, 1, 2, 0): 7 suppositions
(6, 5, 4, 3, 2, 0, 1): 4 suppositions
(6, 5, 4, 3, 2, 1, 0): 7 suppositions
Nombre moyen: 5,05
Nombre max: 7
Nombre minimal: 1
Succès num: 5040

Si RANDOM_THRESHOLDet CLEVER_THRESHOLDsont tous deux définis sur une valeur très élevée (comme 50000), cela forcera l'algorithme à trouver la supposition optimale qui minimise le nombre de possibilités dans le pire des cas. C'est très lent, mais très puissant. Par exemple, l'exécuter sur size=6affirme qu'il peut trouver les bons appariements en 5 tours maximum.

Bien que la moyenne soit plus élevée par rapport à l'utilisation de l'approximation (qui est de 4,11 tours en moyenne), elle réussit toujours, d'autant plus qu'il reste un tour à revendre. Cela renforce encore notre hypothèse selon laquelle size=10, il devrait presque toujours trouver les bons appariements en 10 tours ou moins.

Le résultat (complété en 3m 9s):

(5, 4, 2, 1, 0, 3): 5 suppositions
(5, 4, 2, 1, 3, 0): 5 suppositions
(5, 4, 2, 3, 0, 1): 4 suppositions
(5, 4, 2, 3, 1, 0): 4 suppositions
(5, 4, 3, 0, 1, 2): 5 suppositions
(5, 4, 3, 0, 2, 1): 5 suppositions
(5, 4, 3, 1, 0, 2): 5 suppositions
(5, 4, 3, 1, 2, 0): 5 suppositions
(5, 4, 3, 2, 0, 1): 5 suppositions
(5, 4, 3, 2, 1, 0): 5 suppositions
Nombre moyen: 4,41
Nombre max: 5
Nombre minimal: 1
Succès numérique: 720

Le code.

from itertools import permutations, combinations
import random, sys
from collections import Counter

INTERACTIVE = False
ORIG_PERMS = []
RANDOM_THRESHOLD = 100
CLEVER_THRESHOLD = 0

class Unbuffered():
    def __init__(self, stream):
        self.stream = stream

    def write(self, data):
        self.stream.write(data)
        self.stream.flush()

    def __getattr__(self, attr):
        self.stream.getattr(attr)
sys.stdout = Unbuffered(sys.stdout)

def init(size):
    global ORIG_PERMS
    ORIG_PERMS = list(permutations(range(size)))

def evaluate(solution, guess):
    if len(guess) == len(solution):
        cor = 0
        for sol, gss in zip(solution, guess):
            if sol == gss:
                cor += 1
        return cor
    else:
        return 1 if solution[guess[0]] == guess[1] else 0

def remove_perms(perms, evaluation, guess):
    return [perm for perm in perms if evaluate(perm, guess)==evaluation]

def guess_one(possible_perms, guessed_all, count):
    if count == 1:
        return (0,0)
    pairs = Counter()
    for perm in possible_perms:
        for pair in enumerate(perm):
            pairs[pair] += 1
    perm_cnt = len(possible_perms)
    return sorted(pairs.items(), key=lambda x: (abs(perm_cnt-x[1]) if x[1]<perm_cnt else perm_cnt,x[0]) )[0][0]

def guess_all(possible_perms, guessed_all, count):
    size = len(possible_perms[0])
    if count == 1:
        fact = 1
        for i in range(2, size):
            fact *= i
        if len(possible_perms) == fact:
            return tuple(range(size))
        else:
            return tuple([1,0]+range(2,size))
    if len(possible_perms) == 1:
        return possible_perms[0]
    if count < size and len(possible_perms) > RANDOM_THRESHOLD:
        return possible_perms[random.randint(0, len(possible_perms)-1)]
    elif count == size or len(possible_perms) > CLEVER_THRESHOLD:
        (_, next_guess) = min((max(((len(remove_perms(possible_perms, evaluation, next_guess)), next_guess) for evaluation in range(len(next_guess))), key=lambda x: x[0])
                               for next_guess in possible_perms if next_guess not in guessed_all), key=lambda x: x[0])
        return next_guess
    else:
        (_, next_guess) = min((max(((len(remove_perms(possible_perms, evaluation, next_guess)), next_guess) for evaluation in range(len(next_guess))), key=lambda x: x[0])
                               for next_guess in ORIG_PERMS if next_guess not in guessed_all), key=lambda x: x[0])
        return next_guess

def main(size=4):
    if size < 0:
        size = -size
        init(size)
        counts = []
        for solution in ORIG_PERMS:
            count = run_one(solution, False)
            counts.append(count)
            print '%s: %d guesses' % (solution, count)
        sum_count = float(sum(counts))
        print 'Average count: %.2f' % (sum_count/len(counts))
        print 'Max count    : %d' % max(counts)
        print 'Min count    : %d' % min(counts)
        print 'Num success  : %d' % sum(1 for count in counts if count <= size)
    else:
        init(size)
        solution = ORIG_PERMS[random.randint(0,len(ORIG_PERMS)-1)]
        run_one(solution, True)

def run_one(solution, should_print):
    if should_print:
        print solution
    size = len(solution)
    cur_guess = None
    possible_perms = list(ORIG_PERMS)
    count = 0
    guessed_one = []
    guessed_all = []
    while True:
        count += 1
        # Round A, guess one pair
        if should_print:
            print 'Round %dA' % count
        if should_print:
            print 'Num of possibilities: %d' % len(possible_perms)
        cur_guess = guess_one(possible_perms, guessed_all, count)
        if should_print:
            print 'Guess: %s' % str(cur_guess)
        if INTERACTIVE:
            evaluation = int(raw_input('Number of correct pairs: '))
        else:
            evaluation = evaluate(solution, cur_guess)
            if should_print:
                print 'Evaluation: %s' % str(evaluation)
        possible_perms = remove_perms(possible_perms, evaluation, cur_guess)

        # Round B, guess all pairs
        if should_print:
            print 'Round %dB' % count
            print 'Num of possibilities: %d' % len(possible_perms)
        cur_guess = guess_all(possible_perms, guessed_all, count)
        if should_print:
            print 'Guess: %s' % str(cur_guess)
        guessed_all.append(cur_guess)
        if INTERACTIVE:
            evaluation = int(raw_input('Number of correct pairs: '))
        else:
            evaluation = evaluate(solution, cur_guess)
            if should_print: print 'Evaluation: %s' % str(evaluation)
        if evaluation == size:
            if should_print:
                print 'Found %s in %d guesses' % (str(cur_guess), count)
            else:
                return count
            break
        possible_perms = remove_perms(possible_perms, evaluation, cur_guess)

if __name__=='__main__':
    size = 4
    if len(sys.argv) >= 2:
        size = int(sys.argv[1])
        if len(sys.argv) >= 3:
            INTERACTIVE = bool(int(sys.argv[2]))
    main(size)

CJam -19 tourne- La stratégie d'un idiot

Ce n'est pas une réponse sérieuse mais une démonstration. C'est une solution idiote où il ne prend pas en compte le nombre d'informations de paires correctes fournies à partir de la deuxième partie du tour. Avec des appariements complètement aléatoires, cela prend en moyenne 27 semaines. Cette réponse est insuffisant comme je l'ai dit, mais indique que les chances pour un groupe intellegent (beaucoup plus intellegent que ce programme) n'est probablement pas aussi mince que vous pourriez vous y attendre. Les algorithmes les plus intelligents que j'ai écrits, cependant, prennent beaucoup plus de temps pour que je puisse réellement obtenir des réponses d'eux.

Mise à jour: Le code ci-dessous a été mis à jour pour indiquer qu'il doit supprimer ceux qui ne fonctionnent pas si les seuls corrects sont ceux que nous savions déjà corrects. Il a également été édité pour afficher mon générateur aléatoire de «réponses correctes». Le résultat moyen n'est maintenant que de 19. C'est toujours une solution stupide mais elle est meilleure que la précédente légèrement.

A,{__,mr=_@@-}A*;]sedS*:Z;

ZS/:i:G;                               "Set the input (goal) to G";
{UU@{G2$==@+\)}%~;}:C;                 "This is the tool to count how many of an array agree with G";
{:Y;1$1$<{Y-}%Yaa+@@)>{Y-}%+}:S;       "for stack A X Y, sets the Xth value in the array to Y";
{:Y;1$1$<2$2$=Y-a+@@)>+}:R;            "for stack A X Y, removes Y from the Xth value in the array";

1:D;                                   "Set turn counter to one. if zero exits loop";

A,]A*                                  "array of arrays that has all possible values for an ordering";

{                                      "start of loop";

_V=(\;_GV=={V\SV):V;}{V\R}?            "Guesses a number for the first unknown. If right sets the pair; else erases it";

_[{(_,_{mr=}{;;11}?:Y\{Y-}%}A*;]_C     "guesses random possible arrangement and determines how many are right, error=11";
\_{+}*45-:Y{Y;{_11={;BY-}{}?}%}{}?\    "error correct by including the missing number";

_V={;V:X>{X\RX):X;}%~LV}{}?            "if all new are wrong, makes sure they aren't guessed again";
_A={Dp0:D;;p;}{D):D;;;}?               "If all are right, prints it an tells loop to exit.  Else increments counter";

D}g                                    "repeat from start of loop";

Version C ++ multithread rapide

Je sais que cela fait un moment que ce fil n'est pas actif, mais j'ai un ajout intéressant à partager: voici une implémentation C ++ de l'algorithme minimax pour Are You The One?, qui utilise le multithreading pour accélérer l'évaluation de chaque supposition possible.

Cette version est beaucoup plus rapide que la version Python (plus de 100 fois plus rapide lorsque la version originale de Python est définie au maximum RANDOM_THRESHOLDetCLEVER_THRESHOLD ). Il n'utilise pas de supposition aléatoire, mais évalue plutôt toutes les permutations et soumet comme supposition la permutation qui élimine le plus grand nombre de solutions possibles (compte tenu de la réponse la plus défavorable).

Pour les petits jeux, appeler "ayto -n" exécutera le jeu sur tous les n! correspondances cachées possibles et vous donnera un bref résumé des résultats à la fin.

Puisqu'il est toujours difficile d'évaluer les 10! correspondances cachées possibles, si vous appelez "ayto 10", par exemple, le simulateur fait ses trois premières suppositions fixes, puis exécute minimax pour choisir sa supposition et suppose qu'il a reçu l'évaluation du pire des cas. Cela nous amène sur le "pire des cas" vers un vecteur caché qui est vraisemblablement dans la classe des vecteurs qui prend l'algorithme un nombre maximum de suppositions à identifier. Cette conjecture n'a pas été testée.

Jusqu'à n = 9 , aucune simulation n'a pris plus de n tours à résoudre.

Pour tester cela vous-même, un exemple de compilation serait le suivant:

g++ -std=c++11 -lpthread -o ayto ayto.cpp

Voici un petit exemple avec sortie:

$ ./ayto -4
Found (0, 1, 2, 3) in 2 guesses.
Found (0, 1, 3, 2) in 3 guesses.
Found (0, 2, 1, 3) in 2 guesses.
Found (0, 2, 3, 1) in 3 guesses.
Found (0, 3, 1, 2) in 2 guesses.
Found (0, 3, 2, 1) in 2 guesses.
Found (1, 0, 2, 3) in 1 guesses.
Found (1, 0, 3, 2) in 3 guesses.
Found (1, 2, 0, 3) in 3 guesses.
Found (1, 2, 3, 0) in 3 guesses.
Found (1, 3, 0, 2) in 3 guesses.
Found (1, 3, 2, 0) in 3 guesses.
Found (2, 0, 1, 3) in 3 guesses.
Found (2, 0, 3, 1) in 3 guesses.
Found (2, 1, 0, 3) in 3 guesses.
Found (2, 1, 3, 0) in 3 guesses.
Found (2, 3, 0, 1) in 3 guesses.
Found (2, 3, 1, 0) in 3 guesses.
Found (3, 0, 1, 2) in 3 guesses.
Found (3, 0, 2, 1) in 3 guesses.
Found (3, 1, 0, 2) in 3 guesses.
Found (3, 1, 2, 0) in 3 guesses.
Found (3, 2, 0, 1) in 3 guesses.
Found (3, 2, 1, 0) in 3 guesses.
***** SUMMARY *****
Avg. Turns: 2.75
Worst Hidden Vector: (0, 1, 3, 2) in 3 turns.

Code

/* Multithreaded Mini-max Solver for MTV's Are You The One? */

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <algorithm>
#include <numeric>
#include <string>
#include <vector>
#include <map>
#include <thread>
#include <cmath>

#define TEN_FACT (3628800)
#define NUM_CHUNKS (8)

using std::cout;
using std::cin;
using std::endl;
using std::vector;
using std::string;
using std::map;
using std::pair;
using std::find;
using std::abs;
using std::atoi;
using std::next_permutation;
using std::max_element;
using std::accumulate;
using std::reverse;
using std::thread;

struct args {
    vector<string> *perms;
    vector<string> *chunk;
    pair<string, int> *cd;
    int thread_id;
};

void simulate_game(const string &hidden, map<string, int> &turns_taken,
                   bool running_all);
bool picmp(const pair<string, int> &p1, const pair<string, int> &p2);
double map_avg(const map<string, int> &mp);
int nrand(int n);
int evaluate(const string &sol, const string &query);
vector<string> remove_perms(vector<string> &perms, int eval, string &query);
pair<string, int> guess_tb(vector<string> &perms, vector<string> &guessed_tb, int turn);
pair<string, int> guess_pm(vector<string> &perms, vector<string> &guessed, int turn);
void make_chunks(vector<string> &orig, vector<vector<string> > &chunks, int n);
string min_candidate(pair<string, int> *candidates, int n);
void get_score(struct args *args);
int wc_response(string &guess, vector<string> &perms);
bool prcmp(pair<int, int> x, pair<int, int> y);
void sequence_print(string s);
struct args **create_args(vector<string> &perms, pair<string, int> *cd, vector<string> &chunk, int thread_id);


vector<string> ORIGPERMS;

int main(int argc, char **argv)
{
    int sz;
    map<string, int> turns_taken;
    const string digits = "0123456789";
    bool running_all = false;

    if (argc != 2) {
        cout << "usage: 'ayto npairs'" << endl;
        return 1;
    } else {
        if ((sz = atoi(argv[1])) < 0) {
            sz = -sz;
            running_all = true;
        }
        if (sz < 3 || sz > 10) {
            cout << "usage: 'ayto npairs' where 3 <= npairs <= 10" << endl;;
            return 1;
        }
    }

    // initialize ORIGPERMS and possible_perms
    string range = digits.substr(0, sz);
    do {
        ORIGPERMS.push_back(range);
    } while (next_permutation(range.begin(), range.end()));

    if (running_all) {
        for (vector<string>::const_iterator it = ORIGPERMS.begin();
             it != ORIGPERMS.end(); ++it) {
            simulate_game(*it, turns_taken, running_all);
        }
        cout << "***** SUMMARY *****\n";
        cout << "Avg. Turns: " << map_avg(turns_taken) << endl;
        pair<string, int> wc = *max_element(turns_taken.begin(),
                                            turns_taken.end(), picmp);
        cout << "Worst Hidden Vector: ";
        sequence_print(wc.first);
        cout << " in " << wc.second << " turns." << endl;
    } else {
        string hidden = ORIGPERMS[nrand(ORIGPERMS.size())];
        simulate_game(hidden, turns_taken, running_all);
    }

    return 0;
}

// simulate_game:  run a single round of AYTO on hidden vector
void simulate_game(const string &hidden, map<string, int> &turns_taken,
                   bool running_all)
{
    vector<string> possible_perms = ORIGPERMS;
    pair<string, int> tbguess;
    pair<string, int> pmguess;
    vector<string> guessed;
    vector<string> guessed_tb;
    int e;
    int sz = hidden.size();

    if (!running_all) {
        cout << "Running AYTO Simulator on Hidden Vector: ";
        sequence_print(hidden);
        cout << endl;
    }

    for (int turn = 1; ; ++turn) {
        // stage one: truth booth
        if (!running_all) {
            cout << "**** Round " << turn << "A ****" << endl;
            cout << "Num. Possibilities: " << possible_perms.size() << endl;
        }
        tbguess = guess_tb(possible_perms, guessed_tb, turn);
        if (!running_all) {
            cout << "Guess: ";
            sequence_print(tbguess.first);
            cout << endl;
            e = tbguess.second;
            cout << "Worst-Case Evaluation: " << e << endl;
        } else {
            e = evaluate(hidden, tbguess.first);
        }
        possible_perms = remove_perms(possible_perms, e, tbguess.first);

        // stage two: perfect matching
        if (!running_all) {
            cout << "Round " << turn << "B" << endl;
            cout << "Num. Possibilities: " << possible_perms.size() << endl;
        }
        pmguess = guess_pm(possible_perms, guessed, turn);

        if (!running_all) {
            cout << "Guess: ";
            sequence_print(pmguess.first);
            cout << endl;
            e = pmguess.second;
            cout << "Worst-Case Evaluation: " << e << endl;
        } else {
            e = evaluate(hidden, pmguess.first);
        }
        if (e == sz) {
            cout << "Found ";
            sequence_print(pmguess.first);
            cout << " in " << turn << " guesses." << endl;
            turns_taken[pmguess.first] = turn;
            break;
        }

        possible_perms = remove_perms(possible_perms, e, pmguess.first);
    }
}

// map_avg:  returns average int component of a map<string, int> type
double map_avg(const map<string, int> &mp)
{
    double sum = 0.0;

    for (map<string, int>::const_iterator it = mp.begin(); 
         it != mp.end(); ++it) {
        sum += it->second;
    }

    return sum / mp.size();
}

// picmp:  comparison function for pair<string, int> types, via int component
bool picmp(const pair<string, int> &p1, const pair<string, int> &p2)
{
    return p1.second < p2.second;
}

// nrand:  random integer in range [0, n)
int nrand(int n)
{
    srand(time(NULL));

    return rand() % n;
}

// evaluate:  number of black hits from permutation or truth booth query
int evaluate(const string &sol, const string &query)
{
    int hits = 0;

    if (sol.size() == query.size()) {
        // permutation query
        int s = sol.size();
        for (int i = 0; i < s; i++) {
            if (sol[i] == query[i])
                ++hits;
        }
    } else {
        // truth booth query
        if (sol[atoi(query.substr(0, 1).c_str())] == query[1])
            ++hits;
    }

    return hits;
}

// remove_perms:  remove solutions that are no longer possible after an eval
vector<string> remove_perms(vector<string> &perms, int eval, string &query)
{
    vector<string> new_perms;

    for (vector<string>::iterator i = perms.begin(); i != perms.end(); i++) {
        if (evaluate(*i, query) == eval) {
            new_perms.push_back(*i);
        }
    }

    return new_perms;
}

// guess_tb:  guesses best pair (pos, val) to go to the truth booth
pair<string, int> guess_tb(vector<string> &possible_perms,
                           vector<string> &guessed_tb, int turn)
{
    static const string digits = "0123456789";
    int n = possible_perms[0].size();
    pair<string, int> next_guess;

    if (turn == 1) {
        next_guess.first = "00";
        next_guess.second = 0;
    } else if (possible_perms.size() == 1) {
        next_guess.first = "0" + possible_perms[0].substr(0, 1);
        next_guess.second = 1;
    } else {
        map<string, double> pair_to_count;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                pair_to_count[digits.substr(i, 1) + digits.substr(j, 1)] = 0;
            }
        }

        // count up the occurrences of each pair in the possible perms
        for (vector<string>::iterator p = possible_perms.begin();
             p != possible_perms.end(); p++) {
            int len = possible_perms[0].size();
            for (int i = 0; i < len; i++) {
                pair_to_count[digits.substr(i, 1) + (*p).substr(i, 1)] += 1;
            }
        }

        double best_dist = 1;
        int perm_cnt = possible_perms.size();
        for (map<string, double>::iterator i = pair_to_count.begin();
             i != pair_to_count.end(); i++) {
            if (find(guessed_tb.begin(), guessed_tb.end(), i->first)
                == guessed_tb.end()) {
                // hasn't been guessed yet
                if (abs(i->second/perm_cnt - .5) < best_dist) {
                    next_guess.first = i->first;
                    best_dist = abs(i->second/perm_cnt - .5);
                    if (i->second / perm_cnt < 0.5) // occurs in < half perms
                        next_guess.second = 0;
                    else                            // occurs in >= half perms
                        next_guess.second = 1;
                }
            }
        }
    }

    guessed_tb.push_back(next_guess.first);

    return next_guess;
}

// guess_pm:  guess a full permutation using minimax
pair<string, int> guess_pm(vector<string> &possible_perms,
                           vector<string> &guessed, int turn)
{
    static const string digits = "0123456789";
    pair<string, int> next_guess;
    vector<vector<string> > chunks;
    int sz = possible_perms[0].size();

    // on first turn, we guess "0, 1, ..., n-1" if truth booth was correct
    // or "1, 0, ..., n-1" if truth booth was incorrect
    if (turn == 1) {
        int fact, i;
        for (i = 2, fact = 1; i <= sz; fact *= i++)
            ;
        if (possible_perms.size() == fact) {
            next_guess.first = digits.substr(0, sz);
            next_guess.second = 1;
        } else {
            next_guess.first = "10" + digits.substr(2, sz - 2);
            next_guess.second = 1;
        }
    } else if (possible_perms.size() == 1) {
        next_guess.first = possible_perms[0];
        next_guess.second = possible_perms[0].size();
    } else {
        // run multi-threaded minimax to get next guess
        pair<string, int> candidates[NUM_CHUNKS];
        vector<thread> jobs;
        make_chunks(ORIGPERMS, chunks, NUM_CHUNKS);
        struct args **args = create_args(possible_perms, candidates, chunks[0], 0);

        for (int j = 0; j < NUM_CHUNKS; j++) {
            args[j]->chunk = &(chunks[j]);
            args[j]->thread_id = j;
            jobs.push_back(thread(get_score, args[j]));
        }
        for (int j = 0; j < NUM_CHUNKS; j++) {
            jobs[j].join();
        }

        next_guess.first = min_candidate(candidates, NUM_CHUNKS);
        next_guess.second = wc_response(next_guess.first, possible_perms);

        for (int j = 0; j < NUM_CHUNKS; j++)
            free(args[j]);
        free(args);
    }

    guessed.push_back(next_guess.first);

    return next_guess;
}

struct args **create_args(vector<string> &perms, pair<string, int> *cd, vector<string> &chunk, int thread_id)
{
    struct args **args = (struct args **) malloc(sizeof(struct args*)*NUM_CHUNKS);
    assert(args);
    for (int i = 0; i < NUM_CHUNKS; i++) {
        args[i] = (struct args *) malloc(sizeof(struct args));
        assert(args[i]);
        args[i]->perms = &perms;
        args[i]->cd = cd;
    }

    return args;
}

// make_chunks:  return pointers to n (nearly) equally sized vectors
//                from the original vector
void make_chunks(vector<string> &orig, vector<vector<string> > &chunks, int n)
{
    int sz = orig.size();
    int chunk_sz = sz / n;
    int n_with_extra = sz % n;
    vector<string>::iterator b = orig.begin();
    vector<string>::iterator e;

    for (int i = 0; i < n; i++) {
        int m = chunk_sz;    // size of this chunk
        if (n_with_extra) {
            ++m;
            --n_with_extra;
        }
        e = b + m;
        vector<string> subvec(b, e);
        chunks.push_back(subvec);
        b = e;
    }
}

// min_candidate:  string with min int from array of pair<string, ints>
string min_candidate(pair<string, int> *candidates, int n)
{
    int i, minsofar;
    string minstring;

    minstring = candidates[0].first;
    minsofar = candidates[0].second;
    for (i = 1; i < n; ++i) {
        if (candidates[i].second < minsofar) {
            minsofar = candidates[i].second;
            minstring = candidates[i].first;
        }
    }

    return minstring;
}

// get_score:  find the maximum number of remaining solutions over all
//             possible responses to the query s
//             this version takes a chunk and finds the guess with lowest score
//             from that chunk
void get_score(struct args *args)
{
    // parse the args struct
    vector<string> &chunk = *(args->chunk);
    vector<string> &perms = *(args->perms);
    pair<string, int> *cd = args->cd;
    int thread_id = args->thread_id;

    typedef vector<string>::const_iterator vec_iter;
    int sz = perms[0].size();

    pair<string, int> best_guess;
    best_guess.second = perms.size();
    int wc_num_remaining;
    for (vec_iter s = chunk.begin(); s != chunk.end(); ++s) {
        vector<int> matches(sz + 1, 0);
        for (vec_iter p = perms.begin(); p != perms.end(); ++p) {
            ++matches[evaluate(*s, *p)];
        }
        wc_num_remaining = *max_element(matches.begin(), matches.end());
        if (wc_num_remaining < best_guess.second) {
            best_guess.first = *s;
            best_guess.second = wc_num_remaining;
        }
    }

    cd[thread_id] = best_guess;

    return;
}

// wc_response:  the response to guess that eliminates the least solutions
int wc_response(string &guess, vector<string> &perms)
{
    map<int, int> matches_eval;

    for (vector<string>::iterator it = perms.begin(); it!=perms.end(); ++it) {
        ++matches_eval[evaluate(guess, *it)];
    }

    return max_element(matches_eval.begin(), matches_eval.end(), prcmp)->first;
}

// prcmp:  comparison function for pair<int, int> types in map
bool prcmp(pair<int, int> x, pair<int, int> y)
{
    return x.second < y.second;
}

void sequence_print(const string s)
{
    for (string::const_iterator i = s.begin(); i != s.end(); i++) {
        if (i == s.begin())
            cout << "(";
        cout << *i;
        if (i != s.end() - 1)
            cout << ", ";
        else
            cout << ")";
    }
}