Aku punya yang sulit untukmu!

Pacar saya baru-baru ini menemukan acara baru di MTV (AS). Ini adalah pertunjukan yang mengerikan, dan semua orang di dalamnya adalah sampah, tetapi "permainan" itu cukup menarik. Dari Wikipedia:

Apakah Anda Orangnya?mengikuti 20 orang yang tinggal bersama di Hawaii untuk menemukan pasangan yang cocok. Jika 10 pria dan 10 wanita dapat memilih dengan benar semua sepuluh pertandingan yang sempurna dalam sepuluh minggu, mereka akan mendapatkan $ 1 juta untuk dibagi di antara mereka.

Sekarang untuk bagian permainan (juga dari Wikipedia):

Setiap episode para pemain akan berpasangan dengan siapa yang mereka yakini sebagai pasangan sempurna mereka untuk bersaing dalam sebuah tantangan. Pemenang tantangan akan berkencan, dan memiliki kesempatan untuk menguji pertandingan mereka di stan kebenaran. Anggota pemeran akan memilih salah satu pasangan yang menang untuk pergi ke stan kebenaran untuk menentukan apakah mereka pasangan yang cocok atau tidak. Ini adalah satu-satunya cara untuk mengkonfirmasi kecocokan.Setiap episode berakhir dengan upacara pencocokan di mana pasangan akan diberitahu berapa banyak pasangan yang cocok yang mereka miliki, tetapi tidak yang cocok.

TL; DR: Ini adalah turunan Mastermind (M (10,10) untuk lebih spesifik). Aturan mainnya adalah sebagai berikut:

1. Anda mulai dengan 2 set 10, sebut mereka Set A: {A, B, C, D, E, F, G, H, I, J} dan Set 2: {1,2,3,4,5, 6,7,8,9,10}

2. Komputer menciptakan solusi (tidak terlihat oleh Anda) dalam bentuk {A1, B2, C3, D4, E5, F6, G7, H8, I9, J10}, di mana anggota di set A dipetakan 1-ke-1 untuk mengatur 2. Contoh lain dari solusi bisa {A2, B5, C10, D8, E1, F7, G6, H4, I9, J3}.

3. Sebelum giliran pertama Anda, Anda harus bertanya apakah satu pasangan tertentu pilihan Anda sudah benar. Pertanyaan Anda akan dalam bentuk {A1} (mis. {C8}), dan Anda menerima 1 (artinya benar) atau 0 (artinya tebakan Anda salah).

4. Giliran aktual pertama Anda. Anda membuat tebakan pertama Anda dalam bentuk {A1, B2, C3, D4, E5, F6, G7, H8, I9, J10}, atau permutasi pilihan Anda. Tebakan Anda tidak dapat berisi kelipatan dari setiap item yaitu tebakan {A1, A2, A3, A4, A5, B6, B7, B8, B9, B10} BUKAN tebakan yang valid. Setelah setiap belokan, komputer memberi tahu Anda jumlah kecocokan yang benar, tetapi BUKAN kecocokan mana yang benar.

5. Ulangi langkah 3 dan 4 sampai Anda mendapatkan setiap pertandingan yang benar (yaitu respons 10), atau sampai 10 gerakan Anda naik (mana yang lebih cepat). Jika Anda menyelesaikannya sebelum atau pada giliran 10 Anda, Anda memenangkan $ 1 juta. Kalau tidak, Anda kalah, dan beberapa orang (atau huruf dan angka) pulang sendirian untuk menghabiskan keabadian dengan 10 kucing mereka.

Ini BUKAN kontes kode terpendek. Orang yang dapat menyelesaikan pencocokan acak dalam jumlah tebakan rata-rata paling rendah akan menjadi pemenang. Bermain game yang cerdas dan kecepatan kalkulasi juga kemungkinan akan menjadi faktor. Saya mengasumsikan jumlah rata-rata belokan hampir pasti lebih besar dari 10, sehingga kemungkinan Anda memenangkan hadiah $ 1 juta (mungkin dibayar oleh MTV, bukan saya) tipis. Hanya bagaimana mungkin itu untuk pemain untuk memenangkan hadiah utama?

Catatan: Menempatkannya dalam format {A1, B2, ...} tidak harus dilakukan. Saya hanya menggunakan formulir itu dalam pertanyaan untuk membuatnya jelas apa teka-teki itu. Jika Anda tidak memasukkannya dalam formulir ini, cukup jelaskan bagaimana cara menyebutnya.

Semoga berhasil!

Python 2 (berjalan lebih cepat jika dijalankan menggunakan Pypy)

Diyakini hampir selalu menebak pasangan yang benar dalam 10 putaran atau lebih rendah

Algoritme saya diambil dari jawaban saya untuk dalang sebagai hobi saya (lihat di Ideone ). Idenya adalah untuk menemukan tebakan yang meminimalkan jumlah kemungkinan yang tersisa dalam kasus terburuk. Algoritme saya di bawah ini hanya memaksa, tetapi untuk menghemat waktu, pilih saja tebakan acak jika jumlah kemungkinan yang tersisa lebih besar dari RANDOM_THRESHOLD. Anda dapat bermain-main dengan parameter ini untuk mempercepat atau untuk melihat kinerja yang lebih baik.

Algoritma ini sangat lambat, rata-rata 10s untuk satu kali dijalankan jika dijalankan menggunakan Pypy (jika menggunakan juru bahasa CPython normal sekitar 30-an) jadi saya tidak dapat mengujinya pada seluruh permutasi. Tetapi kinerjanya cukup baik, setelah sekitar 30 tes saya belum melihat contoh di mana ia tidak dapat menemukan pasangan yang benar dalam 10 putaran atau lebih rendah.

Lagi pula, jika ini digunakan dalam pertunjukan kehidupan nyata, ia memiliki banyak waktu sebelum babak berikutnya (satu minggu?) Sehingga algoritma ini dapat digunakan dalam kehidupan nyata = D

Jadi saya pikir aman untuk mengasumsikan bahwa rata-rata ini akan menemukan pasangan yang benar dalam 10 tebakan atau lebih rendah.

Cobalah sendiri. Saya mungkin meningkatkan kecepatan dalam beberapa hari ke depan (EDIT: tampaknya sulit untuk lebih meningkatkan, jadi saya hanya akan meninggalkan kode apa adanya. Saya hanya mencoba melakukan pengambilan acak, tetapi bahkan pada size=7, gagal dalam 3 dari 5040 kasus , jadi saya memutuskan untuk tetap menggunakan metode yang lebih pintar). Anda dapat menjalankannya sebagai:

pypy are_you_the_one.py 10

Atau, jika Anda hanya ingin melihat cara kerjanya, masukkan angka yang lebih kecil (agar dapat berjalan lebih cepat)

Untuk menjalankan tes penuh (peringatan: akan sangat lama size > 7), tulis angka negatif.

Tes penuh untuk size=7 (diselesaikan dalam 2m 32s):

...
(6, 5, 4, 1, 3, 2, 0): 5 tebakan
(6, 5, 4, 2, 0, 1, 3): 5 tebakan
(6, 5, 4, 2, 0, 3, 1): 4 tebakan
(6, 5, 4, 2, 1, 0, 3): 5 tebakan
(6, 5, 4, 2, 1, 3, 0): 6 tebakan
(6, 5, 4, 2, 3, 0, 1): 6 tebakan
(6, 5, 4, 2, 3, 1, 0): 6 tebakan
(6, 5, 4, 3, 0, 1, 2): 6 tebakan
(6, 5, 4, 3, 0, 2, 1): 3 tebakan
(6, 5, 4, 3, 1, 0, 2): 7 tebakan
(6, 5, 4, 3, 1, 2, 0): 7 tebakan
(6, 5, 4, 3, 2, 0, 1): 4 tebakan
(6, 5, 4, 3, 2, 1, 0): 7 tebakan
Jumlah rata-rata: 5,05
Jumlah maksimal: 7
Jumlah minimum: 1
Jumlah sukses: 5040

Jika RANDOM_THRESHOLDdan CLEVER_THRESHOLDkeduanya diatur ke nilai yang sangat tinggi (seperti 50.000), itu akan memaksa algoritma untuk menemukan tebakan optimal yang meminimalkan jumlah kemungkinan dalam kasus terburuk. Ini sangat lambat, tetapi sangat kuat. Misalnya, menjalankannya dengan size=6menyatakan bahwa ia dapat menemukan pasangan yang benar dalam maksimum 5 putaran.

Meskipun rata-rata lebih tinggi dibandingkan dengan menggunakan perkiraan (yang rata-rata adalah 4,11 putaran), tetapi selalu berhasil, bahkan lebih dengan satu putaran tersisa untuk cadangan. Ini semakin memperkuat hipotesis kami bahwa ketika size=10, hampir selalu harus menemukan pasangan yang benar dalam 10 putaran atau kurang.

Hasilnya (selesai dalam 3m 9d):

(5, 4, 2, 1, 0, 3): 5 tebakan
(5, 4, 2, 1, 3, 0): 5 tebakan
(5, 4, 2, 3, 0, 1): 4 tebakan
(5, 4, 2, 3, 1, 0): 4 tebakan
(5, 4, 3, 0, 1, 2): 5 tebakan
(5, 4, 3, 0, 2, 1): 5 tebakan
(5, 4, 3, 1, 0, 2): 5 tebakan
(5, 4, 3, 1, 2, 0): 5 tebakan
(5, 4, 3, 2, 0, 1): 5 tebakan
(5, 4, 3, 2, 1, 0): 5 tebakan
Jumlah rata-rata: 4,41
Jumlah maksimal: 5
Jumlah minimum: 1
Jumlah yang berhasil: 720

Kode.

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 ternyata- Strategi An Idiot

Ini bukan jawaban yang serius tetapi sebuah demonstrasi. Ini adalah solusi orang bodoh di mana dia tidak memperhitungkan jumlah informasi pasangan yang benar yang diberikan dari bagian kedua belokan. Dengan pasangan yang sepenuhnya acak, ini membutuhkan rata-rata 27 minggu. Jawaban ini tidak cukup seperti yang saya katakan tetapi menunjukkan bahwa peluang untuk kelompok intellegent (jauh lebih cerdas dari program ini) kemungkinan tidak setipis yang Anda harapkan. Algoritma yang lebih cerdas yang saya tulis, namun membutuhkan banyak waktu untuk menjalankannya sehingga saya benar-benar bisa mendapatkan jawaban dari mereka.

Pembaruan: Kode di bawah ini diperbarui untuk menggunakan status yang seharusnya menghapus yang tidak berfungsi jika yang benar adalah yang sudah kita ketahui benar. Itu juga diedit untuk menunjukkan generator "jawaban yang benar" secara acak. Hasil rata-rata sekarang hanya 19. Ini masih merupakan solusi bodoh tetapi lebih baik dari sebelumnya secara marginal.

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

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

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

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

{                                      "start of loop";

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

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

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

D}g                                    "repeat from start of loop";

Versi C ++ Multi-Threaded Cepat

Saya tahu sudah lama sejak utas ini aktif, tetapi saya memiliki tambahan yang keren untuk dibagikan: Berikut ini adalah implementasi C ++ dari algoritma minimax untuk Are You The One? , yang menggunakan multi-threading untuk mempercepat evaluasi setiap tebakan yang mungkin.

Versi ini jauh lebih cepat daripada versi Python (lebih dari 100x lebih cepat ketika versi Python asli diatur ke maksimum RANDOM_THRESHOLDdan CLEVER_THRESHOLD). Itu tidak menggunakan tebakan acak, melainkan mengevaluasi semua permutasi dan mengirimkan sebagai tebakan permutasi yang menghilangkan jumlah terbesar dari solusi yang mungkin (diberikan respon kasus terburuk).

Untuk gim yang lebih kecil, memanggil "ayto -n" akan menjalankan gim di semua n! kemungkinan kecocokan tersembunyi, dan akan memberi Anda ringkasan singkat hasil di akhir.

Karena masih sulit untuk mengevaluasi semua 10! kemungkinan kecocokan tersembunyi, jika Anda memanggil "ayto 10", misalnya, simulator membuat tiga tebakan pertamanya, lalu jalankan minimax untuk memilih tebakannya dan mengasumsikan bahwa ia diberi evaluasi kasus terburuk. Ini membawa kita ke "jalur kasus terburuk" ke vektor tersembunyi yang mungkin ada di kelas vektor yang menggunakan algoritma jumlah maksimum dugaan untuk diidentifikasi. Dugaan ini belum diuji.

Hingga n = 9 , belum ada simulasi yang harus diselesaikan lebih dari n putaran.

Untuk mengujinya sendiri, contoh kompilasi adalah sebagai berikut:

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

Inilah contoh kecil dengan output:

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

Kode

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