Created
December 4, 2020 20:57
-
-
Save possibly-wrong/a501f1f6e39f55f94e9cedc97072a85c to your computer and use it in GitHub Desktop.
Searching for chocolates
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// https://possiblywrong.wordpress.com/2015/02/08/searching-for-chocolates/ | |
#include "math_Rational.h" // https://github.com/possibly-wrong/precision | |
#include <vector> | |
#include <map> | |
#include <iterator> | |
#include <algorithm> | |
#include <numeric> | |
#include <iostream> | |
#include <ctime> | |
using namespace math; | |
int n = 0; | |
typedef std::vector<int> State; | |
typedef std::vector<State> States; | |
typedef std::map<States, Rational> Cache; | |
Cache cache; | |
// There are really two arguments embedded in states[], so that we don't have | |
// to write our own comparator for the memoization cache. | |
// | |
// states[0] is an (int) boolean vector with states[0][k] indicating whether we | |
// have already tried the chocolate in position k. | |
// | |
// states[1..] is a list of remaining possible derangements of the chocolates. | |
Rational search(const States& states, bool root = true) | |
{ | |
// Retrieve memoized value if we've been here before. | |
auto& result = cache[states]; | |
if (result != 0) | |
{ | |
return result; | |
} | |
// Consider trying each remaining chocolate, picking the one that minimizes | |
// the expected number of additional guesses. | |
result = n; | |
for (int guess = n - 1; guess >= 0; --guess) | |
{ | |
if (states[0][guess] == 0) | |
{ | |
// Compute expected number of additional guesses, averaging over | |
// remaining possible derangements. | |
Rational value = 0; | |
bool skip = true; | |
for (auto&& state : states) | |
{ | |
// Don't forget that states[0] isn't really a state. | |
if (skip) | |
{ | |
skip = false; | |
continue; | |
} | |
int revealed = state[guess]; | |
if (revealed != 0) | |
{ | |
// Our guess was wrong, so recursively evaluate optimal | |
// strategy, keeping only derangements consistent with what | |
// we've seen so far. | |
States next; | |
next.reserve(states.size()); | |
next.push_back(states[0]); | |
next[0][guess] = 1; | |
std::copy_if(states.begin() + 1, states.end(), | |
std::back_inserter(next), | |
[=](const State& s) { return s[guess] == revealed; }); | |
value += search(next, false); | |
} | |
} | |
value = value / static_cast<std::int32_t>(states.size() - 1) + 1; | |
if (value < result) | |
{ | |
result = value; | |
} | |
} | |
// This is just an optimization, observing that all possible *first* | |
// guesses yield the same result by symmetry. | |
if (root) | |
{ | |
break; | |
} | |
} | |
return result; | |
} | |
int main() | |
{ | |
for (n = 2; n <= 9; ++n) | |
{ | |
cache.clear(); | |
std::clock_t tic = std::clock(); | |
States states; | |
// Initially we haven't tried any chocolates. | |
State state(n, 0); | |
states.push_back(state); | |
// Generate all n! permutations, keeping derangements only. | |
std::iota(state.begin(), state.end(), 0); | |
do { | |
bool is_derangement = true; | |
for (int k = 0; k < n; ++k) | |
{ | |
if (state[k] == k) | |
{ | |
is_derangement = false; | |
break; | |
} | |
} | |
if (is_derangement) | |
{ | |
states.push_back(state); | |
} | |
} while (std::next_permutation(state.begin(), state.end())); | |
Rational value = search(states); | |
double elapsed = | |
static_cast<double>(std::clock() - tic) / CLOCKS_PER_SEC; | |
std::cout << n << "\t" << elapsed << "\t" << value << std::endl; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment