Mam dla ciebie trudny!

Moja dziewczyna niedawno spotkała się z nowym programem na MTV (USA). To okropny program i wszyscy na nim są tandetni, ale „gra” jest dość interesująca. Z Wikipedii:

Czy jesteś tym jedynym? śledzi 20 osób mieszkających razem na Hawajach, aby znaleźć idealne dopasowanie. Jeśli 10 mężczyzn i 10 kobiet będzie w stanie poprawnie wybrać wszystkie dziesięć idealnych dopasowań w ciągu dziesięciu tygodni, zyskają 1 milion dolarów na podzielenie się między nimi.

Teraz część gry (również z Wikipedii):

W każdym odcinku obsada połączy się z tym, kto uważa, że ​​ich idealnym dopasowaniem jest rywalizacja w wyzwaniu. Zwycięzcy wyzwania wybiorą się na randkę i będą mieli okazję sprawdzić swój mecz na stoisku prawdy. Członkowie obsady wybiorą jedną ze zwycięskich par, aby udać się do stoiska z prawdą, aby ustalić, czy pasują idealnie, czy nie. To jedyny sposób na potwierdzenie dopasowania.Każdy odcinek kończy się ceremonią dopasowania, podczas której pary zostaną poinformowane, ile mają idealnych meczów, ale nie które mecze są prawidłowe.

TL; DR: Jest to pochodna Mastermind (konkretnie M (10,10)). Zasady gry są następujące:

1. Zaczynasz od 2 zestawów po 10, nazwijmy je Zestaw A: {A, B, C, D, E, F, G, H, I, J} i Zestaw 2: {1,2,3,4,5, 6,7,8,9,10}

2. Komputer tworzy rozwiązanie (niewidoczne dla Ciebie) w postaci {A1, B2, C3, D4, E5, F6, G7, H8, I9, J10}, w którym elementy w zestawie A są mapowane 1 na 1 ustawić 2. Kolejnym przykładem rozwiązania może być {A2, B5, C10, D8, E1, F7, G6, H4, I9, J3}.

3. Przed pierwszą turą możesz zapytać, czy wybrana konkretna para jest poprawna. Twoje pytanie będzie miało postać {A1} (np. {C8}), a otrzymasz 1 (co oznacza poprawność) lub 0 (co oznacza, że ​​twoje przypuszczenie jest nieprawidłowe).

4. Twoja pierwsza prawdziwa tura. Pierwszy zgadujesz w postaci {A1, B2, C3, D4, E5, F6, G7, H8, I9, J10} lub dowolnej kombinacji. Twoja domysł nie może zawierać wielokrotności dowolnego elementu, tj. Domysł {A1, A2, A3, A4, A5, B6, B7, B8, B9, B10} NIE jest prawidłowym domysłem. Po każdej turze komputer podaje liczbę poprawnych dopasowań, ale NIE, które dopasowania są poprawne.

5. Powtarzaj kroki 3 i 4, aż uzyskasz poprawność każdego meczu (tj. Odpowiedź 10) lub dopóki twoje 10 ruchów nie wzrośnie (w zależności od tego, co nastąpi wcześniej). Jeśli rozwiążesz go przed lub w 10. turze, wygrywasz milion dolarów. W przeciwnym razie tracisz, a niektórzy ludzie (lub litery i cyfry) idą do domu samotnie, aby spędzić wieczność ze swoimi 10 kotami.

To NIE jest najkrótszy konkurs kodu. Osoba, która może rozwiązać losowo dopasowanie w najmniejszej średniej liczby prób będzie zwycięzcą. Prawdopodobnie uwzględni się także sprytna gra i szybkość obliczeń. Zakładam, że średnia liczba tur prawie na pewno będzie większa niż 10, więc szanse wygrania nagrody w wysokości 1 miliona dolarów (prawdopodobnie wypłaconej przez MTV, a nie mnie) są niewielkie. Tylko jak niemożliwe jest dla obsady, aby wygrać główną nagrodę?

Uwaga: Umieszczenie go w formacie {A1, B2, ...} nie jest koniecznie wymagane. Po prostu użyłem tej formy w pytaniu, aby całkowicie wyjaśnić, na czym polega łamigłówka. Jeśli nie umieścisz go w tym formularzu, wyjaśnij, jak to nazwać.

Powodzenia!

Python 2 (uruchom szybciej, jeśli uruchamiasz za pomocą Pypy)

Uważa się, że prawie zawsze odgadnie się prawidłowe parowanie w 10 rundach lub niżej

Mój algorytm wzięty jest z mojej odpowiedzi dla mistrza jako hobby (patrz Ideone ). Chodzi o to, aby znaleźć przypuszczenie, które zminimalizuje liczbę możliwości pozostawionych w najgorszym przypadku. Mój algorytm poniżej brutalnie go zmusza, ale aby zaoszczędzić czas, po prostu losowo zgaduję, czy liczba pozostałych możliwości jest większa niż RANDOM_THRESHOLD. Możesz pobawić się tym parametrem, aby przyspieszyć lub zobaczyć lepszą wydajność.

Algorytm działa dość wolno, średnio 10 sekund na jeden cykl, jeśli jest uruchamiany przy użyciu Pypy (jeśli używa się normalnego interpretera CPython, to około 30 sekund), więc nie mogę go przetestować na całej permutacji. Ale wydajność jest całkiem dobra, po około 30 testach nie widziałem żadnego przypadku, w którym nie można znaleźć prawidłowej pary w 10 rundach lub niżej.

W każdym razie, jeśli używa się tego w prawdziwym życiu, ma dużo czasu przed następną rundą (tydzień?), Więc ten algorytm można wykorzystać w prawdziwym życiu = D

Myślę więc, że można bezpiecznie założyć, że średnio znajdzie to prawidłowe pary w 10 domysłach lub mniej.

Spróbuj sam. Mogę poprawić prędkość w ciągu najbliższych kilku dni (EDYCJA: wydaje się, że dalsza poprawa wydaje się trudna, więc po prostu zostawiam kod bez size=7zmian . Próbowałem tylko wybierać losowo, ale nawet przy nie udaje się to w 3 z 5040 przypadków , więc postanowiłem zachować lepszą metodę). Możesz uruchomić go jako:

pypy are_you_the_one.py 10

Lub, jeśli chcesz tylko zobaczyć, jak to działa, wprowadź mniejszą liczbę (aby działała szybciej)

Aby uruchomić pełny test (ostrzeżenie: zajmie to dużo czasu dla size> 7), wpisz liczbę ujemną.

Pełny test size=7(ukończony w 2m 32s):

...
(6, 5, 4, 1, 3, 2, 0): 5 domysłów
(6, 5, 4, 2, 0, 1, 3): 5 domysłów
(6, 5, 4, 2, 0, 3, 1): 4 domysły
(6, 5, 4, 2, 1, 0, 3): 5 domysłów
(6, 5, 4, 2, 1, 3, 0): 6 domysłów
(6, 5, 4, 2, 3, 0, 1): 6 domysłów
(6, 5, 4, 2, 3, 1, 0): 6 domysłów
(6, 5, 4, 3, 0, 1, 2): 6 domysłów
(6, 5, 4, 3, 0, 2, 1): 3 domysły
(6, 5, 4, 3, 1, 0, 2): 7 domysłów
(6, 5, 4, 3, 1, 2, 0): 7 domysłów
(6, 5, 4, 3, 2, 0, 1): 4 domysły
(6, 5, 4, 3, 2, 1, 0): 7 domysłów
Średnia liczba: 5,05
Maksymalna liczba: 7
Min. Liczba: 1
Num sukces: 5040

Jeśli RANDOM_THRESHOLDi CLEVER_THRESHOLDto zarówno zestaw do bardzo dużej wartości (np 50000), to będzie zmusić algorytm, aby znaleźć optymalne przypuszczenie, że minimalizuje liczbę możliwości w najgorszym wypadku. To jest bardzo wolne, ale bardzo potężne. Na przykład uruchomienie go na size=6upewnia się, że może znaleźć prawidłowe pary w maksymalnie 5 rundach.

Chociaż średnia jest wyższa w porównaniu do zastosowania przybliżenia (czyli średnio 4,11 rund), ale zawsze się udaje, tym bardziej, że jedna runda jest wolna. To dodatkowo wzmacnia naszą hipotezę, że kiedy size=10prawie zawsze powinno znaleźć prawidłowe pary w 10 rundach lub mniej.

Wynik (ukończony w 3m 9s):

(5, 4, 2, 1, 0, 3): 5 domysłów
(5, 4, 2, 1, 3, 0): 5 domysłów
(5, 4, 2, 3, 0, 1): 4 domysły
(5, 4, 2, 3, 1, 0): 4 domysły
(5, 4, 3, 0, 1, 2): 5 domysłów
(5, 4, 3, 0, 2, 1): 5 domysłów
(5, 4, 3, 1, 0, 2): 5 domysłów
(5, 4, 3, 1, 2, 0): 5 domysłów
(5, 4, 3, 2, 0, 1): 5 domysłów
(5, 4, 3, 2, 1, 0): 5 domysłów
Średnia liczba: 4,41
Maksymalna liczba: 5
Min. Liczba: 1
Num sukces: 720

Kod.

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 turn- Strategia An Idiot

To nie jest poważna odpowiedź, ale demonstracja. Jest to rozwiązanie idioty, w którym nie bierze pod uwagę liczby poprawnych informacji o parowaniu dostarczonych z drugiej części tury. W przypadku całkowicie losowych par zajmuje to średnio 27 tygodni. Ta odpowiedź jest niewystarczająca, jak powiedziałem, ale wskazuje, że szanse dla inteligentnej grupy (znacznie bardziej inteligentnej niż ten program) prawdopodobnie nie są tak małe, jak można się spodziewać. Bardziej inteligentne algorytmy, które napisałem, wymagają jednak dużo więcej czasu na uruchomienie, dzięki czemu mogę właściwie uzyskać od nich odpowiedzi.

Aktualizacja: Poniższy kod został zaktualizowany, aby używać stanu, który powinien usunąć te, które nie działają, jeśli jedynymi poprawnymi są te, o których wiemy, że są poprawne. Został również edytowany, aby pokazać mój losowy generator „poprawnej odpowiedzi”. Średni wynik to teraz tylko 19. To wciąż głupie rozwiązanie, ale jest nieznacznie lepsze od poprzedniego.

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

Szybka wielowątkowa wersja C ++

Wiem, że minęło trochę czasu, odkąd ten wątek był aktywny, ale mam fajny dodatek do podzielenia się: Oto implementacja algorytmu C ++ algorytmu minimax dla Are You The One? , który wykorzystuje wielowątkowość, aby przyspieszyć ocenę każdego możliwego domysły.

Ta wersja jest znacznie szybsza niż wersja Python (ponad 100 razy szybsza, gdy oryginalna wersja Python jest ustawiona na maksimum RANDOM_THRESHOLDi CLEVER_THRESHOLD). Nie używa żadnego losowego zgadywania, ale raczej ocenia wszystkie permutacje i podaje jako przypuszczenie permutację, która eliminuje największą liczbę możliwych rozwiązań (biorąc pod uwagę odpowiedź najgorszego przypadku).

W przypadku mniejszych gier wywołanie „ayto -n” spowoduje uruchomienie gry na wszystkich n! możliwe ukryte dopasowania, a na końcu znajdziesz krótkie podsumowanie wyników.

Ponieważ wciąż trudno jest ocenić wszystkie 10! możliwe ukryte dopasowania, jeśli na przykład nazwiesz „ayto 10”, symulator ustala pierwsze trzy domysły, a następnie uruchamia minimax, aby wybrać przypuszczenie i zakłada, że ​​otrzymał ocenę najgorszego przypadku. Prowadzi nas to „ścieżką najgorszego przypadku” do ukrytego wektora, który prawdopodobnie należy do klasy wektorów, w których algorytm określa maksymalną liczbę odgadnięć. Ta hipoteza nie została przetestowana.

Aż do n = 9 , nie było symulacji, której rozwiązanie wymagałoby więcej niż n zakrętów.

Aby to przetestować sam, przykładowa kompilacja wyglądałaby następująco:

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

Oto mały przykład z danymi wyjściowymi:

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

Kod

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