¡Tengo uno duro para ti!

Mi novia recientemente se encontró con un nuevo programa en MTV (EE. UU.). Es un espectáculo terrible, y todos en él son basura, pero el "juego" es bastante interesante. De Wikipedia:

¿Eres el elegido? Sigue a 20 personas que viven juntas en Hawai para encontrar su pareja perfecta. Si los 10 hombres y las 10 mujeres son capaces de elegir correctamente las diez parejas perfectas en diez semanas, ganarán $ 1 millón para dividirse entre ellos.

Ahora para la parte del juego (también de Wikipedia):

En cada episodio, el elenco se emparejará con quienes creen que su pareja perfecta es competir en un desafío. Los ganadores del desafío irán a una cita y tendrán la oportunidad de probar su partido en la cabina de la verdad. Los miembros del elenco elegirán una de las parejas ganadoras para ir al stand de la verdad y determinar si son una pareja perfecta o no. Esta es la única forma de confirmar coincidencias. Cada episodio termina con una ceremonia de emparejamiento en la que se les dirá a las parejas cuántas coincidencias perfectas tienen, pero no qué coincidencias son correctas.

TL; DR: Este es un derivado de Mastermind (M (10,10) para ser específico). Las reglas del juego son las siguientes:

1. Comienza con 2 conjuntos de 10, llamémoslos Conjunto A: {A, B, C, D, E, F, G, H, I, J} y Conjunto 2: {1,2,3,4,5, 6,7,8,9,10}

2. La computadora crea una solución (no visible para usted) en forma de {A1, B2, C3, D4, E5, F6, G7, H8, I9, J10}, donde los miembros del conjunto A se asignan de 1 a 1 para establecer 2. Otro ejemplo de una solución podría ser {A2, B5, C10, D8, E1, F7, G6, H4, I9, J3}.

3. Antes de tu primer turno, puedes preguntar si un par particular de tu elección es correcto. Su pregunta sería en forma de {A1} (por ejemplo, {C8}), y recibirá un 1 (que significa correcto) o 0 (que significa que su suposición es incorrecta).

4. Tu primer turno real. Usted hace su primera suposición en forma de {A1, B2, C3, D4, E5, F6, G7, H8, I9, J10}, o cualquier permutación de su elección. Su suposición no puede contener múltiplos de ningún elemento, es decir, una suposición de {A1, A2, A3, A4, A5, B6, B7, B8, B9, B10} NO es una suposición válida. Después de cada turno, la computadora le indica el número de coincidencias correctas, pero NO qué coincidencias son correctas.

5. Repita los pasos 3 y 4 hasta que obtenga todas las coincidencias correctas (es decir, una respuesta de 10), o hasta que sus 10 movimientos estén arriba (lo que ocurra antes). Si lo resuelve antes o en su décimo turno, gana $ 1 millón. De lo contrario, pierdes, y algunas personas (o letras y números) se van solos a casa para pasar la eternidad con sus 10 gatos.

Este NO es un concurso de código más corto. La persona que pueda resolver una coincidencia aleatoria en el menor número promedio de conjeturas será la ganadora. Es probable que el juego inteligente y la velocidad de cálculo también tengan en cuenta. Supongo que el número promedio de turnos seguramente será mayor que 10, por lo que las probabilidades de que ganes el premio de $ 1 millón (presumiblemente pagado por MTV, no yo) son escasas. Sólo la forma imposible es que para el reparto de ganar el gran premio?

Nota: Ponerlo en el formato {A1, B2, ...} no es necesariamente necesario. Simplemente utilicé ese formulario en la pregunta para dejar absolutamente claro cuál es el rompecabezas. Si no lo pone en este formulario, simplemente explique cómo llamarlo.

¡Buena suerte!

Python 2 (corre más rápido si corres usando Pypy)

Se cree que casi siempre adivina el emparejamiento correcto en 10 rondas o menos

Mi algoritmo se toma de mi respuesta para mastermind como mi hobby (ver en Ideone ). La idea es encontrar la suposición que minimice el número de posibilidades que quedan en el peor de los casos. Mi algoritmo a continuación solo lo fuerza por fuerza bruta, pero para ahorrar tiempo, solo selecciona conjeturas aleatorias si el número de posibilidades restantes es mayor que RANDOM_THRESHOLD. Puede jugar con este parámetro para acelerar las cosas o para ver un mejor rendimiento.

El algoritmo es bastante lento, en promedio 10 segundos para una ejecución si se ejecuta utilizando Pypy (si se utiliza el intérprete CPython normal, son alrededor de 30 segundos), por lo que no puedo probarlo en todas las permutaciones. Pero el rendimiento es bastante bueno, después de alrededor de 30 pruebas, no he visto ninguna instancia en la que no pueda encontrar el emparejamiento correcto en 10 rondas o menos.

De todos modos, si esto se usa en un espectáculo de la vida real, tiene mucho tiempo antes de la próxima ronda (¿una semana?), Por lo que este algoritmo se puede usar en la vida real = D

Así que creo que es seguro asumir que, en promedio, esto encontrará los emparejamientos correctos en 10 conjeturas o menos.

Inténtalo tú mismo. Podría mejorar la velocidad en los próximos días (EDITAR: parece difícil mejorar aún más, así que dejaré el código tal como está. Intenté hacer una selección aleatoria, pero incluso size=7en 3 de los 5040 casos falla , así que decidí mantener el método más inteligente). Puedes ejecutarlo como:

pypy are_you_the_one.py 10

O, si solo quiere ver cómo funciona, ingrese un número menor (para que se ejecute más rápido)

Para ejecutar una prueba completa (advertencia: tomará mucho tiempo size> 7), ingrese un número negativo.

Prueba completa para size=7(completado en 2m 32s):

...
(6, 5, 4, 1, 3, 2, 0): 5 conjeturas
(6, 5, 4, 2, 0, 1, 3): 5 conjeturas
(6, 5, 4, 2, 0, 3, 1): 4 conjeturas
(6, 5, 4, 2, 1, 0, 3): 5 conjeturas
(6, 5, 4, 2, 1, 3, 0): 6 conjeturas
(6, 5, 4, 2, 3, 0, 1): 6 conjeturas
(6, 5, 4, 2, 3, 1, 0): 6 conjeturas
(6, 5, 4, 3, 0, 1, 2): 6 conjeturas
(6, 5, 4, 3, 0, 2, 1): 3 conjeturas
(6, 5, 4, 3, 1, 0, 2): 7 conjeturas
(6, 5, 4, 3, 1, 2, 0): 7 conjeturas
(6, 5, 4, 3, 2, 0, 1): 4 conjeturas
(6, 5, 4, 3, 2, 1, 0): 7 conjeturas
Conteo promedio: 5.05
Cuenta máxima: 7
Cuenta mínima: 1
Num éxito: 5040

Si RANDOM_THRESHOLDy CLEVER_THRESHOLDse establecen en un valor muy alto (como 50000), que va a forzar el algoritmo para encontrar la estimación óptima que minimiza el número de posibilidades en el peor de los casos. Esto es muy lento, pero muy poderoso. Por ejemplo, ejecutarlo size=6afirma que puede encontrar los emparejamientos correctos en un máximo de 5 rondas.

Aunque el promedio es más alto en comparación con el uso de la aproximación (que es 4.11 rondas en promedio), pero siempre tiene éxito, aún más con una ronda de sobra. Esto fortalece aún más nuestra hipótesis de que cuando size=10, casi siempre debería encontrar los emparejamientos correctos en 10 rondas o menos.

El resultado (completado en 3m 9s):

(5, 4, 2, 1, 0, 3): 5 conjeturas
(5, 4, 2, 1, 3, 0): 5 conjeturas
(5, 4, 2, 3, 0, 1): 4 conjeturas
(5, 4, 2, 3, 1, 0): 4 conjeturas
(5, 4, 3, 0, 1, 2): 5 conjeturas
(5, 4, 3, 0, 2, 1): 5 conjeturas
(5, 4, 3, 1, 0, 2): 5 conjeturas
(5, 4, 3, 1, 2, 0): 5 conjeturas
(5, 4, 3, 2, 0, 1): 5 conjeturas
(5, 4, 3, 2, 1, 0): 5 conjeturas
Conteo promedio: 4.41
Cuenta máxima: 5
Cuenta mínima: 1
Num éxito: 720

El código.

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 vueltas- La estrategia de un idiota

Esta no es una respuesta seria sino una demostración. Esta es la solución de un idiota en la que no tiene en cuenta la cantidad de información de emparejamiento correcta proporcionada en la segunda parte del turno. Con emparejamientos completamente aleatorios, esto toma un promedio de 27 semanas. Esta respuesta es insuficiente como he dicho, pero indica que las probabilidades de un grupo inteligente (mucho más inteligente que este programa) probablemente no sean tan escasas como cabría esperar. Los algoritmos más inteligentes que he escrito, sin embargo, toman mucho más tiempo en ejecutarse para que realmente pueda obtener respuestas de ellos.

Actualización: El siguiente código se actualizó para usar el estado de que debería eliminar los que no funcionan si los únicos correctos son los que ya sabíamos que eran correctos. También fue editado para mostrar mi generador aleatorio de "respuesta correcta". El resultado promedio ahora es solo 19. Sigue siendo una solución tonta, pero es mejor que la anterior marginalmente.

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";

Versión C ++ multiproceso rápida

Sé que ha pasado un tiempo desde que este hilo estuvo activo, pero tengo una excelente adición para compartir: Aquí hay una implementación en C ++ del algoritmo minimax para Are You The One? , que utiliza subprocesos múltiples para acelerar la evaluación de cada posible suposición.

Esta versión es mucho más rápida que la versión de Python (más de 100 veces más rápida cuando la versión original de Python está configurada al máximo RANDOM_THRESHOLDy CLEVER_THRESHOLD). No utiliza ninguna conjetura al azar, sino que evalúa todas las permutaciones y envía como suposición la permutación que elimina la mayor cantidad de soluciones posibles (dada la respuesta en el peor de los casos).

Para juegos más pequeños, llamar "ayto -n" ejecutará el juego en todos los n! posibles coincidencias ocultas, y le dará un breve resumen de los resultados al final.

¡Ya que todavía es intratable evaluar los 10! posibles coincidencias ocultas, si llama "ayto 10", por ejemplo, el simulador realiza sus primeras tres conjeturas fijas, luego ejecuta minimax para elegir su suposición y asume que se le dio la peor evaluación. Esto nos lleva por el "camino del peor de los casos" a un vector oculto que presumiblemente está en la clase de vectores que le toma al algoritmo un número máximo de conjeturas para identificar. Esta conjetura no ha sido probada.

Hasta n = 9 , no ha habido una simulación que haya tomado más de n turnos para resolver.

Para probar esto usted mismo, una compilación de ejemplo sería la siguiente:

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

Aquí hay un pequeño ejemplo con salida:

$ ./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.

Código

/* 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 << ")";
    }
}