У меня есть жесткий для вас!

Недавно моя девушка познакомилась с новым шоу на MTV (США). Это ужасное зрелище, и все на нем грязные, но «игра» довольно интересная. Из Википедии:

Ты ли Тот самый? следует за 20 людьми, которые живут вместе на Гавайях, чтобы найти свою идеальную пару. Если 10 мужчин и 10 женщин смогут правильно выбрать все десять идеальных матчей за десять недель, они получат 1 миллион долларов, чтобы разделить их.

Теперь для игровой части (также из Википедии):

В каждом эпизоде ​​актеры будут сочетаться с теми, кто, по их мнению, идеально подходит для участия в соревнованиях. Победители конкурса отправятся на свидание, и у них будет возможность проверить свой матч в стенде правды. Участники съемочной группы выберут одну из победивших пар, чтобы отправиться в киоск правды, чтобы определить, идеально они подходят или нет. Это единственный способ подтвердить совпадения. Каждый эпизод заканчивается церемонией сопоставления, где парам сообщают, сколько у них совершенных совпадений, но не какие совпадения являются правильными.

TL; DR: это производная Mastermind (M (10,10), чтобы быть конкретным). Правила игры следующие:

1. Вы начинаете с 2 наборов по 10, назовем их Набором A: {A, B, C, D, E, F, G, H, I, J} и Набором 2: {1,2,3,4,5, 6,7,8,9,10}

2. Компьютер создает решение (не видимое для вас) в форме {A1, B2, C3, D4, E5, F6, G7, H8, I9, J10}, где члены в наборе A отображаются 1-в-1 установить 2. Другим примером решения может быть {A2, B5, C10, D8, E1, F7, G6, H4, I9, J3}.

3. Перед первым ходом вы должны спросить, верна ли одна конкретная пара по вашему выбору. Ваш вопрос будет в форме {A1} (например, {C8}), и вы получите либо 1 (что означает правильное), либо 0 (что означает, что ваше предположение неверно).

4. Ваш первый настоящий ход. Вы делаете свое первое предположение в виде {A1, B2, C3, D4, E5, F6, G7, H8, I9, J10} или любой перестановки по вашему выбору. Ваше предположение не может содержать кратные значения какого-либо элемента, т. Е. Предположение {A1, A2, A3, A4, A5, B6, B7, B8, B9, B10} НЕ является действительным предположением. После каждого хода компьютер сообщает вам количество правильных совпадений, но НЕ, какие совпадения являются правильными.

5. Повторяйте шаги 3 и 4 до тех пор, пока вы не получите правильное соответствие (т. Е. Ответ 10) или пока ваши 10 ходов не увеличатся (в зависимости от того, что произойдет раньше). Если вы решите это до или в свой 10-й ход, вы выиграете 1 миллион долларов. В противном случае вы проигрываете, и некоторые люди (или буквы и цифры) уходят домой одни, чтобы провести вечность со своими 10 кошками.

Это НЕ конкурс на самый короткий код. Человек, который может решить случайное сопоставление в наименьшем среднем количестве догадок, будет победителем. Умная игра и скорость вычислений также, вероятно, будут влиять. Я предполагаю, что среднее число ходов почти наверняка будет больше 10, так что шансы на то, что вы выиграете приз в 1 миллион долларов (предположительно, выплачивается MTV, а не мной), невелики. Так же , как невозможно это для броска , чтобы выиграть главный приз?

Примечание. Помещение в формат {A1, B2, ...} не обязательно. Я просто использовал эту форму в вопросе, чтобы понять, что это за головоломка. Если вы не указали это в этой форме, просто объясните, как это назвать.

Удачи!

Python 2 (работает быстрее, если используется Pypy)

Считается, что почти всегда угадывают правильное соединение в 10 раундов или ниже

Мой алгоритм взят из моего ответа для вдохновителя как мое хобби (см. В Ideone ). Идея состоит в том, чтобы найти предположение, которое минимизирует количество оставшихся возможностей в худшем случае. Мой алгоритм ниже просто перебор, но чтобы сэкономить время, он просто выбирает случайное предположение, если количество оставшихся возможностей больше, чем RANDOM_THRESHOLD. Вы можете поиграть с этим параметром, чтобы ускорить процесс или увидеть лучшую производительность.

Алгоритм довольно медленный, в среднем 10 с за один прогон, если он выполняется с использованием Pypy (если используется обычный интерпретатор CPython, это около 30 с), поэтому я не могу проверить его на всех перестановках. Но производительность довольно хорошая, после 30 тестов я не видел ни одного случая, когда бы он не мог найти правильное соединение в 10 раундах или ниже.

Во всяком случае, если это используется в реальной жизни шоу, у него есть много времени до следующего раунда (одна неделя?), Поэтому этот алгоритм может быть использован в реальной жизни = D

Поэтому я думаю, можно с уверенностью предположить, что в среднем это найдет правильные пары в 10 догадках или ниже.

Попробуй сам. Я мог бы улучшить скорость в следующие несколько дней (РЕДАКТИРОВАТЬ: дальнейшее улучшение кажется трудным, поэтому я просто оставлю код как есть. Я пробовал делать только случайный выбор, но даже при size=7трех неудачных попытках из 5040 , поэтому я решил сохранить более умный метод). Вы можете запустить его как:

pypy are_you_the_one.py 10

Или, если вы просто хотите посмотреть, как это работает, введите меньшее число (чтобы оно работало быстрее)

Чтобы запустить полный тест (предупреждение: это займет очень много времени size> 7), поставьте отрицательное число.

Полный тест для size=7(завершено за 2 м 32 с):

...
(6, 5, 4, 1, 3, 2, 0): 5 догадок
(6, 5, 4, 2, 0, 1, 3): 5 догадок
(6, 5, 4, 2, 0, 3, 1): 4 догадки
(6, 5, 4, 2, 1, 0, 3): 5 догадок
(6, 5, 4, 2, 1, 3, 0): 6 догадок
(6, 5, 4, 2, 3, 0, 1): 6 догадок
(6, 5, 4, 2, 3, 1, 0): 6 догадок
(6, 5, 4, 3, 0, 1, 2): 6 догадок
(6, 5, 4, 3, 0, 2, 1): 3 догадки
(6, 5, 4, 3, 1, 0, 2): 7 догадок
(6, 5, 4, 3, 1, 2, 0): 7 догадок
(6, 5, 4, 3, 2, 0, 1): 4 догадки
(6, 5, 4, 3, 2, 1, 0): 7 догадок
Средний счет: 5,05
Максимальное количество: 7
Минимальное количество: 1
Num success: 5040

Если RANDOM_THRESHOLDи CLEVER_THRESHOLDдля обоих задано очень высокое значение (например, 50000), это заставит алгоритм найти оптимальное предположение, которое минимизирует количество возможностей в худшем случае. Это очень медленно, но очень мощно. Например, его запуск size=6подтверждает, что он может найти правильные пары максимум за 5 раундов.

Хотя среднее значение выше по сравнению с использованием аппроксимации (которая в среднем составляет 4,11 раунда), но оно всегда получается успешным, даже больше, когда остается один запасной раунд. Это еще больше укрепляет нашу гипотезу о том, что, когда size=10, он почти всегда должен найти правильные пары в 10 раундов или меньше.

Результат (выполнено за 3м 9с):

(5, 4, 2, 1, 0, 3): 5 догадок
(5, 4, 2, 1, 3, 0): 5 догадок
(5, 4, 2, 3, 0, 1): 4 догадки
(5, 4, 2, 3, 1, 0): 4 догадки
(5, 4, 3, 0, 1, 2): 5 догадок
(5, 4, 3, 0, 2, 1): 5 догадок
(5, 4, 3, 1, 0, 2): 5 догадок
(5, 4, 3, 1, 2, 0): 5 догадок
(5, 4, 3, 2, 0, 1): 5 догадок
(5, 4, 3, 2, 1, 0): 5 догадок
Средний счет: 4.41
Максимальное количество: 5
Минимальное количество: 1
Num success: 720

Код.

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 ходов - стратегия идиота

Это не серьезный ответ, а демонстрация. Это решение идиота, когда он не учитывает количество правильных парных данных, предоставленных во второй части хода. При полностью случайных парах это занимает в среднем 27 недель. Этот ответ, как я уже сказал, недостаточен, но указывает на то, что шансы для разумной группы (гораздо более умной, чем эта программа), вероятно, не так малы, как вы могли бы ожидать. Более интеллектуальные алгоритмы, которые я написал, однако требуют больше времени для запуска, чтобы я мог «фактически получить ответы от них».

Обновление: приведенный ниже код был обновлен, чтобы использовать состояние, при котором он должен удалить те, которые не работают, если единственными правильными являются те, которые, как мы уже знали, были правильными. Он также был отредактирован, чтобы показать мой генератор случайных «правильных ответов». Средний результат теперь только 19. Это все еще глупое решение, но оно лучше, чем предыдущий незначительно.

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

Быстрая многопоточная версия C ++

Я знаю, что прошло много времени с тех пор, как этот поток был активным, но у меня есть замечательное дополнение: вот реализация C ++ минимаксного алгоритма для Are You The One? , который использует многопоточность, чтобы ускорить оценку каждого возможного предположения.

Эта версия намного быстрее, чем версия Python (более чем в 100 раз быстрее, если в исходной версии Python установлено максимальное значение RANDOM_THRESHOLDи CLEVER_THRESHOLD). Он не использует случайное предположение, а скорее оценивает все перестановки и представляет в качестве своего предположения перестановку, которая исключает наибольшее количество возможных решений (учитывая реакцию в худшем случае).

Для небольших игр вызов "ayto -n" запустит игру на всех n! возможные скрытые совпадения, и даст вам краткое резюме результатов в конце.

Поскольку все еще трудно оценить все 10! возможные скрытые совпадения, например, если вы называете «ayto 10», симулятор делает свои первые три предположения с фиксированными значениями, затем запускает минимакс, чтобы выбрать свое предположение, и предполагает, что ему была дана оценка наихудшего случая. Это ведет нас по «пути наихудшего случая» к скрытому вектору, который, предположительно, находится в классе векторов, который использует алгоритму максимальное количество догадок для идентификации. Эта гипотеза не была проверена.

До n = 9 не было моделирования, для решения которого потребовалось бы больше n ходов.

Чтобы проверить это самостоятельно, пример компиляции будет следующим:

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

Вот небольшой пример с выводом:

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

Код

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