IBM Ponder This challenge - May 2019
May’s Ponder This challenge by IBM was considered quite difficult, it was only solved after five days1 and only sixteen people had solved it after a month. And indeed finding an efficient algorithm to build an optimal solution seems quite difficult and I haven’t been able to do it yet2. However to solve the challenge we don’t need our algorithm to be efficient or optimal as I will show you.
I’ve found the description of the problem a bit hard to understand, here is a version that I hope is simpler: We have eight people and a boat, each of which can be on either banks of a river (That’s 512 possible configurations). We can move from one configuration to another if it involves moving the boat across the river and one or two people with it. With these rules the minimum number of trips to move everyone from one side to the other is 13. Our goal is to find forbidden sets of people such that the minimum number of trips to move everyone without ever having a forbidden set on one bank becomes at least 73. There are 256 possible sets of people however if a set is forbidden, its complement is forbidden too as it would correspond to the set of people on the other bank. Hence we only need to decide which of the 128 sets containing the eighth person to forbid.
The first step in solving the challenge is to be able to compute the minimum number of trips given a set of forbidden sets. This can be done with a simple BFS on the graph of configurations:
#include <queue>
#include <vector>
#define PEOPLE 8
#define N (1 << PEOPLE)
#define MASK (N - 1)
using namespace std;
// A configuration is represented as a pair
// (set_of_people_on_the_0th_bank, number_of_trips_of_the_boat)
// and a set of people is represented as a number between 0 and 257.
// Use some bit tricks to find all sets of people one trip away from
// the current one.
vector<int> next(int n) {
vector<int> next_sets;
for(int i = n; i != 0; i &= i - 1) {
next_sets.push_back(n ^ (i & -i));
for(int j = i & (i - 1); j != 0; j &= j - 1) {
next_sets.push_back(n ^ (i & -i) ^ (j & -j));
}
}
return next_sets;
}
int minimum_number_of_trips(const vector<bool>& forbidden) {
vector<vector<bool>> allowed =
vector<vector<bool>>(N, vector<bool>(2, true));
for(int f = 0; f < forbidden.size(); ++f) {
if(forbidden[f]) {
int g = f | (N >> 1);
// Every forbidden set of people corresponds to four
// configurations:
allowed[g][0] = false;
allowed[g][1] = false;
allowed[(~g & MASK)][0] = false;
allowed[(~g & MASK)][1] = false;
}
}
queue<pair<int, int>> q;
q.emplace(MASK, 0);
allowed[MASK][0] = false;
while(!q.empty()) {
pair<int, int> current = q.front();
q.pop();
int people_set = current.first;
int number_of_trips = current.second;
if(people_set == 0) {
return number_of_trips;
}
if((number_of_trips & 1) == 1) {
people_set = ~people_set & MASK;
}
for(int s : next(people_set)) {
if((number_of_trips & 1) == 1) {
s = ~s & MASK;
}
if(allowed[s][number_of_trips & 1]) {
allowed[s][number_of_trips & 1] = false;
q.emplace(s, number_of_trips + 1);
}
}
}
return 0;
}Armed with this we can try to forbid random sets and see what numbers we get:
#include <cstdlib>
#include <ctime>
#include <iostream>
int main() {
srand(time(0));
int best_score = PEOPLE * 2 - 3;
vector<bool> forbidden = vector<bool>(N, false);
while(true) {
for(int i = 0; i < N; ++i) {
forbidden[i] = rand() % 2 == 0;
}
int score = minimum_number_of_trips(forbidden);
if(score > best_score) {
cout << score << endl;
best_score = score;
}
}
}After waiting for more than a minute, the best score I get is 15, not very promising. Let’s try again using a different random distribution that emphasizes more extreme solutions (with lots of forbidden sets or very few):
...
while(true) {
int threshold = rand();
for(int i = 0; i < N; ++i) {
forbidden[i] = rand() < threshold;
}
...This time, after a minute I reach a score of 31 which is much better but still far from our 73 target.
Instead of starting from scratch and generating a new random set of forbidden sets every time we should maybe try to improve our current set of forbidden sets. Let’s start by allowing every set and then forbidding sets randomly. If adding a new forbidden set makes it impossible to move everyone across the river then we revert back to the best known solution. And if we get stuck and don’t make progress, we forget everything and restart from scratch:
#include <cstdlib>
#include <ctime>
#include <iostream>
#define MAX_STEPS 10000
int main() {
srand(time(0));
int best_score = PEOPLE * 2 - 3;
int global_best_score = best_score; // For printing only.
vector<bool> forbidden = vector<bool>(N, false);
vector<bool> best_forbidden = forbidden;
int steps_without_progress = 0;
while(true) {
int i;
// We make sure to not forbid an already forbidden set to not
// compute its score twice.
while(i = rand() % N, forbidden[i]);
forbidden[i] = true;
int score = minimum_number_of_trips(forbidden);
++steps_without_progress;
if(score > best_score) {
if(score > global_best_score) {
cout << score << endl;
global_best_score = score;
}
best_score = score;
best_forbidden = forbidden;
steps_without_progress = 0;
} else if(score == 0) {
forbidden = best_forbidden;
}
if(steps_without_progress > MAX_STEPS) {
best_score = PEOPLE * 2 - 3;
forbidden = vector<bool>(N, false);
best_forbidden = forbidden;
steps_without_progress = 0;
}
}
}Now I get a score of 37 after a minute. Better but still not enough.
The problem is that when adding random forbidden sets, sometimes we add useful sets that increase the score of the solution and sometimes we add bad ones that prevent us from finding a better solution later. To solve this problem we can try to find minimum sets of forbidden sets, sets where every element is useful. For this we can go over every element of the set, see if removing it reduces the score and keep only the elements that would decrease the score if removed. Now every time we find a new best solution we minimize it before trying to improve it:
#include <algorithm>
#include <numeric>
...
if(score > best_score) {
if(score > global_best_score) {
cout << score << endl;
global_best_score = score;
}
best_score = score;
vector<int> random_order = vector<int>(N);
iota(random_order.begin(), random_order.end(), 0);
random_shuffle(random_order.begin(), random_order.end());
for(int i : random_order) {
if(forbidden[i]) {
forbidden[i] = false;
score = minimum_number_of_trips(forbidden);
if(score < best_score) {
forbidden[i] = true;
}
}
}
best_forbidden = forbidden;
steps_without_progress = 0;
} ...This change yields a huge improvement and we now get scores above 73 in a few minutes.
Here is the final code:
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <numeric>
#include <queue>
#include <vector>
#define MAX_STEPS 10000
#define PEOPLE 8
#define N (1 << PEOPLE)
#define MASK (N - 1)
using namespace std;
// A configuration is represented as a pair
// (set_of_people_on_the_0th_bank, number_of_trips_of_the_boat)
// and a set of people is represented as a number between 0 and 257.
// Use some bit tricks to find all sets of people one trip away from
// the current one.
vector<int> next(int n) {
vector<int> next_sets;
for(int i = n; i != 0; i &= i - 1) {
next_sets.push_back(n ^ (i & -i));
for(int j = i & (i - 1); j != 0; j &= j - 1) {
next_sets.push_back(n ^ (i & -i) ^ (j & -j));
}
}
return next_sets;
}
int minimum_number_of_trips(const vector<bool>& forbidden) {
vector<vector<bool>> allowed =
vector<vector<bool>>(N, vector<bool>(2, true));
for(int f = 0; f < forbidden.size(); ++f) {
if(forbidden[f]) {
int g = f | (N >> 1);
// Every forbidden set of people corresponds to four
// configurations:
allowed[g][0] = false;
allowed[g][1] = false;
allowed[(~g & MASK)][0] = false;
allowed[(~g & MASK)][1] = false;
}
}
queue<pair<int, int>> q;
q.emplace(MASK, 0);
allowed[MASK][0] = false;
while(!q.empty()) {
pair<int, int> current = q.front();
q.pop();
int people_set = current.first;
int number_of_trips = current.second;
if(people_set == 0) {
return number_of_trips;
}
if((number_of_trips & 1) == 1) {
people_set = ~people_set & MASK;
}
for(int s : next(people_set)) {
if((number_of_trips & 1) == 1) {
s = ~s & MASK;
}
if(allowed[s][number_of_trips & 1]) {
allowed[s][number_of_trips & 1] = false;
q.emplace(s, number_of_trips + 1);
}
}
}
return 0;
}
int main() {
srand(time(0));
int best_score = PEOPLE * 2 - 3;
int global_best_score = best_score; // For printing only.
vector<bool> forbidden = vector<bool>(N, false);
vector<bool> best_forbidden = forbidden;
int steps_without_progress = 0;
while(true) {
int i;
// We make sure to not forbid an already forbidden set to not
// compute its score twice.
while(i = rand() % N, forbidden[i]);
forbidden[i] = true;
int score = minimum_number_of_trips(forbidden);
++steps_without_progress;
if(score > best_score) {
if(score > global_best_score) {
cout << score << endl;
global_best_score = score;
}
best_score = score;
vector<int> random_order = vector<int>(N);
iota(random_order.begin(), random_order.end(), 0);
random_shuffle(random_order.begin(), random_order.end());
for(int i : random_order) {
if(forbidden[i]) {
forbidden[i] = false;
score = minimum_number_of_trips(forbidden);
if(score < best_score) {
forbidden[i] = true;
}
}
}
best_forbidden = forbidden;
steps_without_progress = 0;
} else if(score == 0) {
forbidden = best_forbidden;
}
if(steps_without_progress > MAX_STEPS) {
best_score = PEOPLE * 2 - 3;
forbidden = vector<bool>(N, false);
best_forbidden = forbidden;
steps_without_progress = 0;
}
}
}