Ich habe es schwer für dich!

Meine Freundin ist kürzlich auf MTV (USA) auf eine neue Show gestoßen. Es ist eine schreckliche Show und jeder auf ihr ist trashig, aber das "Spiel" ist ziemlich interessant. Aus Wikipedia:

Bist du der eine? folgt 20 Leuten, die zusammen in Hawaii leben, um ihre perfekte Übereinstimmung zu finden. Wenn die 10 Männer und 10 Frauen in der Lage sind, alle zehn perfekten Übereinstimmungen in zehn Wochen richtig auszuwählen, erhalten sie eine Million US-Dollar, um sie unter ihnen aufzuteilen.

Nun zum Spielteil (auch aus Wikipedia):

Jede Episode, mit der die Besetzung zusammenarbeitet, ist der perfekte Partner, um sich einer Herausforderung zu stellen. Die Gewinner der Challenge treffen sich zu einem Date und haben die Möglichkeit, ihr Match in der Wahrheitslounge zu testen. Die Darsteller wählen eines der siegreichen Paare aus, um am Wahrheitsstand zu ermitteln, ob es sich um ein perfektes Paar handelt oder nicht. Dies ist die einzige Möglichkeit, Übereinstimmungen zu bestätigen. Jede Episode endet mit einer Matching-Zeremonie, bei der den Paaren mitgeteilt wird, wie viele perfekte Übereinstimmungen sie haben, aber nicht, welche Übereinstimmungen korrekt sind.

TL; DR: Dies ist ein Mastermind-Derivat (M (10,10) um genau zu sein). Die Spielregeln lauten wie folgt:

1. Sie beginnen mit 2 Zehnersätzen. Nennen wir sie Satz A: {A, B, C, D, E, F, G, H, I, J} und Satz 2: {1,2,3,4,5, 6,7,8,9,10}

2. Der Computer erstellt eine (für Sie nicht sichtbare) Lösung in Form von {A1, B2, C3, D4, E5, F6, G7, H8, I9, J10}, wobei die Mitglieder in Gruppe A 1-zu-1 zugeordnet werden Ein weiteres Beispiel für eine Lösung könnte {A2, B5, C10, D8, E1, F7, G6, H4, I9, J3} sein.

3. Vor deiner ersten Runde wirst du gefragt, ob ein einzelnes, bestimmtes Paar deiner Wahl richtig ist. Ihre Frage hat die Form {A1} (z. B. {C8}) und Sie erhalten entweder eine 1 (richtig) oder eine 0 (falsch).

4. Deine erste richtige Runde. Sie machen Ihre erste Vermutung in Form von {A1, B2, C3, D4, E5, F6, G7, H8, I9, J10} oder einer beliebigen Permutation Ihrer Wahl. Ihre Vermutung darf kein Vielfaches eines Elements enthalten, dh eine Vermutung von {A1, A2, A3, A4, A5, B6, B7, B8, B9, B10} ist KEINE gültige Vermutung. Nach jeder Runde teilt der Computer Ihnen die Anzahl der korrekten Übereinstimmungen mit, NICHT jedoch, welche Übereinstimmungen korrekt sind.

5. Wiederholen Sie die Schritte 3 und 4, bis alle Übereinstimmungen korrekt sind (dh eine Antwort von 10) oder bis Ihre 10 Züge verstrichen sind (je nachdem, welcher Zeitpunkt früher liegt). Wenn Sie es vor oder in Ihrem 10. Zug lösen, gewinnen Sie 1 Million Dollar. Andernfalls verlieren Sie und einige Leute (oder Buchstaben und Zahlen) gehen alleine nach Hause, um die Ewigkeit mit ihren 10 Katzen zu verbringen.

Dies ist KEIN kürzester Code-Wettbewerb. Die Person, die eine zufällige Übereinstimmung mit der geringsten durchschnittlichen Anzahl von Vermutungen lösen kann, wird der Gewinner sein. Cleveres Spiel und Rechengeschwindigkeit werden wahrscheinlich ebenfalls eine Rolle spielen. Ich gehe davon aus, dass die durchschnittliche Anzahl der Runden mit ziemlicher Sicherheit größer als 10 sein wird, sodass die Gewinnchancen für Sie (vermutlich von MTV, nicht von mir) gering sind. Genau wie unmöglich ist es für die Besetzung des großen Preis zu gewinnen?

Hinweis: Das Einfügen in das Format {A1, B2, ...} ist nicht unbedingt erforderlich. Ich habe diese Form in der Frage einfach verwendet, um zu verdeutlichen, was das Rätsel ist. Wenn Sie es nicht in dieses Formular einfügen, erklären Sie einfach, wie Sie es aufrufen.

Viel Glück!

Python 2 (schneller laufen, wenn Pypy verwendet wird)

Es wird davon ausgegangen, dass fast immer die richtige Paarung in 10 Runden oder weniger erraten wird

Mein Algorithmus wird von meiner Antwort für Mastermind als mein Hobby genommen (siehe in Ideone ). Die Idee ist, die Vermutung zu finden, die die Anzahl der im schlimmsten Fall verbleibenden Möglichkeiten minimiert. Mein unten stehender Algorithmus erzwingt es einfach, aber um Zeit zu sparen, wählt er einfach eine Zufallsrate, wenn die Anzahl der verbleibenden Möglichkeiten größer als ist RANDOM_THRESHOLD. Mit diesem Parameter können Sie herumspielen, um Dinge zu beschleunigen oder eine bessere Leistung zu erzielen.

Der Algorithmus ist ziemlich langsam, im Durchschnitt 10s für einen Lauf, wenn er mit Pypy ausgeführt wird (wenn ein normaler CPython-Interpreter verwendet wird, sind es ungefähr 30s), daher kann ich ihn nicht auf allen Permutationen testen. Aber die Leistung ist ziemlich gut, nach ungefähr 30 Tests habe ich noch keinen Fall gesehen, bei dem es in 10 Runden oder weniger nicht gelingt, die richtige Paarung zu finden.

Wie auch immer, wenn dies in der realen Show verwendet wird, hat es genügend Zeit vor der nächsten Runde (eine Woche?), So dass dieser Algorithmus im realen Leben verwendet werden kann = D

Ich bin also der Meinung, dass man davon ausgehen kann, dass dies im Durchschnitt die richtigen Paarungen in 10 oder weniger Vermutungen ergibt.

Versuch es selber. Ich könnte die Geschwindigkeit in den nächsten Tagen verbessern (BEARBEITEN: Es scheint schwierig zu sein, sich weiter zu verbessern, also lasse ich den Code einfach so, wie er ist. Ich habe versucht, nur zufällige Auswahl zu machen, aber selbst bei size=7scheitert er in 3 der 5040 Fälle Also habe ich beschlossen, die clevere Methode beizubehalten. Sie können es ausführen als:

pypy are_you_the_one.py 10

Oder, wenn Sie nur sehen möchten, wie es funktioniert, geben Sie eine kleinere Zahl ein (damit es schneller läuft)

Geben Sie sizeeine negative Zahl ein, um einen vollständigen Test durchzuführen (Warnung: > 7 dauert sehr lange ).

Voller Test für size=7(abgeschlossen in 2m 32s):

...
(6, 5, 4, 1, 3, 2, 0): 5 Vermutungen
(6, 5, 4, 2, 0, 1, 3): 5 Vermutungen
(6, 5, 4, 2, 0, 3, 1): 4 Vermutungen
(6, 5, 4, 2, 1, 0, 3): 5 Vermutungen
(6, 5, 4, 2, 1, 3, 0): 6 Vermutungen
(6, 5, 4, 2, 3, 0, 1): 6 Vermutungen
(6, 5, 4, 2, 3, 1, 0): 6 Vermutungen
(6, 5, 4, 3, 0, 1, 2): 6 Vermutungen
(6, 5, 4, 3, 0, 2, 1): 3 Vermutungen
(6, 5, 4, 3, 1, 0, 2): 7 Vermutungen
(6, 5, 4, 3, 1, 2, 0): 7 Vermutungen
(6, 5, 4, 3, 2, 0, 1): 4 Vermutungen
(6, 5, 4, 3, 2, 1, 0): 7 Vermutungen
Durchschnittliche Anzahl: 5,05
Maximale Anzahl: 7
Mindestanzahl: 1
Num Erfolg: 5040

Wenn RANDOM_THRESHOLDund CLEVER_THRESHOLDauf einen sehr hohen Wert gesetzt sind (wie 50000), wird der Algorithmus gezwungen, die optimale Schätzung zu finden, die die Anzahl der Möglichkeiten im schlimmsten Fall minimiert. Das ist sehr langsam, aber sehr mächtig. Wenn Sie es beispielsweise mit ausführen, wird davon size=6ausgegangen, dass es in maximal 5 Runden die richtigen Paarungen finden kann.

Der Durchschnitt ist zwar höher als bei Verwendung der Näherung (die im Durchschnitt 4,11 Runden beträgt), aber es gelingt immer, noch mehr, wenn noch eine Runde übrig ist. Dies stärkt unsere Hypothese, dass size=10fast immer in 10 Runden oder weniger die richtigen Paarungen gefunden werden sollten.

Das Ergebnis (abgeschlossen in 3m 9s):

(5, 4, 2, 1, 0, 3): 5 Vermutungen
(5, 4, 2, 1, 3, 0): 5 Vermutungen
(5, 4, 2, 3, 0, 1): 4 Vermutungen
(5, 4, 2, 3, 1, 0): 4 Vermutungen
(5, 4, 3, 0, 1, 2): 5 Vermutungen
(5, 4, 3, 0, 2, 1): 5 Vermutungen
(5, 4, 3, 1, 0, 2): 5 Vermutungen
(5, 4, 3, 1, 2, 0): 5 Vermutungen
(5, 4, 3, 2, 0, 1): 5 Vermutungen
(5, 4, 3, 2, 1, 0): 5 Vermutungen
Durchschnittliche Anzahl: 4.41
Maximale Anzahl: 5
Mindestanzahl: 1
Anzahl der Erfolge: 720

Der Code.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

CJam -19-Turns-Strategie eines Idioten

Dies ist keine ernsthafte Antwort, sondern eine Demonstration. Dies ist die Lösung eines Idioten, bei der er die Anzahl der korrekten Paarungsinformationen aus dem zweiten Teil der Runde nicht berücksichtigt. Bei völlig zufälligen Paarungen dauert dies durchschnittlich 27 Wochen. Diese Antwort ist, wie ich bereits sagte, unzureichend, weist jedoch darauf hin, dass die Chancen für eine intellegente Gruppe (viel intellegenter als dieses Programm) wahrscheinlich nicht so gering sind, wie Sie es vielleicht erwarten. Die intelligenteren Algorithmen, die ich geschrieben habe, benötigen jedoch viel mehr Zeit zum Ausführen, damit ich tatsächlich Antworten von ihnen erhalten kann.

Update: Der folgende Code wurde aktualisiert, um den Status zu verwenden, dass diejenigen entfernt werden sollten, die nicht funktionieren, wenn nur diejenigen korrekt sind, von denen wir bereits wussten, dass sie korrekt sind. Es wurde auch überarbeitet, um meinen Zufallsgenerator "Richtige Antwort" anzuzeigen. Das durchschnittliche Ergebnis ist jetzt nur 19. Es ist immer noch eine dumme Lösung, aber es ist besser als die vorherige geringfügig.

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

Schnelle Multithread-C ++ - Version

Ich weiß, es ist schon eine Weile her, dass dieser Thread aktiv war, aber ich habe eine coole Ergänzung zu teilen: Hier ist eine C ++ - Implementierung des Minimax-Algorithmus für Are You The One? , die Multithreading verwendet, um die Auswertung jeder möglichen Vermutung zu beschleunigen.

Diese Version ist viel schneller als die Python-Version (über 100x schneller, wenn die ursprüngliche Python-Version auf Maximum RANDOM_THRESHOLDund festgelegt ist CLEVER_THRESHOLD). Es wird kein zufälliges Erraten verwendet, sondern alle Permutationen ausgewertet und als Erraten die Permutation übergeben, die die größtmögliche Anzahl möglicher Lösungen eliminiert (bei der Antwort im ungünstigsten Fall).

Bei kleineren Spielen wird das Spiel mit "ayto -n" auf allen n ausgeführt! mögliche versteckte Übereinstimmungen und geben Ihnen am Ende eine kurze Zusammenfassung der Ergebnisse.

Da ist es doch unlösbar alle 10 auszuwerten! Mögliche versteckte Übereinstimmungen: Wenn Sie zum Beispiel "ayto 10" aufrufen, führt der Simulator die ersten drei festen Vermutungen aus, führt dann minimax aus, um die Vermutung auszuwählen, und geht davon aus, dass er die schlechteste Bewertung erhalten hat. Dies führt uns auf einem "Worst-Case-Pfad" zu einem verborgenen Vektor, der sich vermutlich in der Klasse der Vektoren befindet, für die der Algorithmus eine maximale Anzahl von Raten zur Identifizierung benötigt. Diese Vermutung wurde nicht getestet.

Bis zu n = 9 gab es keine Simulation, für deren Lösung mehr als n Umdrehungen benötigt wurden.

Um dies selbst zu testen, wäre eine Beispielzusammenstellung wie folgt:

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

Hier ist ein kleines Beispiel mit Ausgabe:

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

Code

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

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

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

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

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

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


vector<string> ORIGPERMS;

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

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

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

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

    return 0;
}

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

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

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

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

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

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

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

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

    return sum / mp.size();
}

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

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

    return rand() % n;
}

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

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

    return hits;
}

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

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

    return new_perms;
}

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

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

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

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

    guessed_tb.push_back(next_guess.first);

    return next_guess;
}

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

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

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

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

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

    guessed.push_back(next_guess.first);

    return next_guess;
}

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

    return args;
}

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

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

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

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

    return minstring;
}

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

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

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

    cd[thread_id] = best_guess;

    return;
}

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

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

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

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

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