May 2019

[SmartMersenne]

Originally Posted by Dieter

What is your best until now? I have 212 „solutions“ with 51. I guess that they are equivalent — one yields another by renaming the people. But for further searching I‘ll consider them all.

I have some solutions with 63.

[Dieter]

Does anyone still try to solve the may challenge?
I have many solutions with 71 since yesterday, but now I get stuck.

[Xyzzy]

http://www.research.ibm.com/haifa/po...s/May2019.html

[uau]

Here's the search code I used. It does an exhaustive search on possible ways to cross. That is, it starts from a series of moves to move people beginning from the starting position (A and B cross, B comes back, B and C cross, ...) and calculates all the configurations that must be allowed for these moves to be valid (this is the thing asked for as an answer). A breadth-first search on the allowed configurations checks whether they already create a path that allows everyone to cross. If not, the list of moves is made longer. If yes, the length of minimal path is checked, and then search continues to different moves.

There are a just a couple of checks beyond a completely stupid exhaustive search; it's likely that this could still be sped up a lot. First, to avoid searching each of the 8! permutations of reordering the people separately, lowest-numbered people must move first (only AB or A moving are allowed from start position). If two people move across together as their first move, there's still a check on the first move where they move separately. Second, moves that cannot be a shortest path anywhere are rejected - if the configurations that must be allowed for the moves to be valid at all allow reaching the position after 10 moves in 8 steps then the moves are rejected.

The program supports threading. Run as follows:
./a.out 8 4 12
8 is the problem size. 4 is thread count (set as appropriate). 12 is tree depth at which search is split into per-thread tasks. Larger depth means smaller chunks; leaving it at 12 should be OK. A last optional argument can be given to (re)start the search from another position (using the same position values the program uses in its "done" per-thread work output).

The points at which you should expect various length solutions to be found, given as number of output lines using split depth 12 like above:
63: ~500
67: 2.4k
69: 3.8k
71: 8k
73: 56k
75: 58k
77: 59k
79: 59k
81: 200k


Total number of lines to complete exhaustive search and prove 81 optimal would be 3.8M (I haven't actually run one).

#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <stdio.h>
#include <pthread.h>
#include <string.h>

int foo(long long x) {
    return __builtin_ctzll(x);
}

struct i256 {
    unsigned long long i[4];
};

static void xorbit(struct i256 *n, int i) {
    int l = i >> 6;
    int b = i & 63;
    n->i[l] ^= 1ULL << b;
}

static void setbit(struct i256 *n, int i) {
    int l = i >> 6;
    int b = i & 63;
    n->i[l] |= 1ULL << b;
}

static bool getbit(struct i256 *n, int i) {
    int l = i >> 6;
    int b = i & 63;
    return n->i[l] & (1ULL << b);
}

static void or(struct i256 *a, struct i256 *b) {
    a->i[0] |= b->i[0];
    a->i[1] |= b->i[1];
    a->i[2] |= b->i[2];
    a->i[3] |= b->i[3];
}

static void and(struct i256 *a, struct i256 *b) {
    a->i[0] &= b->i[0];
    a->i[1] &= b->i[1];
    a->i[2] &= b->i[2];
    a->i[3] &= b->i[3];
}

static void andnot(struct i256 *a, struct i256 *b) {
    a->i[0] &= ~b->i[0];
    a->i[1] &= ~b->i[1];
    a->i[2] &= ~b->i[2];
    a->i[3] &= ~b->i[3];
}

static void xor3(struct i256 *d, struct i256 *a, struct i256 *b) {
    d->i[0] = a->i[0] ^ b->i[0];
    d->i[1] = a->i[1] ^ b->i[1];
    d->i[2] = a->i[2] ^ b->i[2];
    d->i[3] = a->i[3] ^ b->i[3];
}

static int ctz(struct i256 *n) {
    if (n->i[0])
        return __builtin_ctzll(n->i[0]);
    if (n->i[1])
        return __builtin_ctzll(n->i[1]) + 64;
    if (n->i[2])
        return __builtin_ctzll(n->i[2]) + 128;
    if (n->i[3])
        return __builtin_ctzll(n->i[3]) + 192;
    return -1;
}

#define MAX_THREADS 128
static pthread_t threads[MAX_THREADS];
static pthread_mutex_t global_lock = PTHREAD_MUTEX_INITIALIZER;
static unsigned global_counter;
static int global_best;
static int num_people;
static int cutoff;
char *startpos;

static void *calc(void *arg) {
    int thread_id = (pthread_t *)arg - threads;
    int sz = num_people;
    int best = 0;
    unsigned local_counter = 0;
    int local_best;
    assert(sz > 0 && sz <= 8);
    int nstates = 1 << sz;
    int mask = nstates - 1;
    struct i256 moves[256] = {0};
    for (int i = 0; i < nstates; i++) {
        for (int j = 0; j < sz; j++) {
            if (!(i & (1 << j)))
                continue;
            setbit(moves + i, mask ^ i ^ (1 << j));
            for (int k = j + 1; k < sz; k++) {
                if (!(i & (1 << k)))
                    continue;
                setbit(moves + i, mask ^ i ^ (1 << j) ^ (1 << k));
            }
        }
    }
    struct {
        int pos;
        struct i256 forceon;
        struct i256 left;
    } stack [256] = {0};
    stack[0].pos = mask;
    setbit(&stack[0].forceon, 0);
    setbit(&stack[0].forceon, mask);
    stack[0].left = moves[mask];
    int depth = 0;
    bool dostart = startpos;
    while (1) {
        int pos = ctz(&stack[depth].left);
        if (pos == -1) {
            if (depth == 0)
                break;
            if (depth == cutoff) {
                char buf[512];
                for (int i = 0; i <= cutoff; i++)
                    sprintf(buf + 2*i, "%02x", stack[i].pos);
                printf("thread %3d: done %.*s local_best %d/%d\n", thread_id,
                       2*cutoff+2, buf, local_best, best);
                fflush(stdout);
            }
            depth--;
            continue;
        }
        xorbit(&stack[depth].left, pos);
        stack[depth+1].forceon = stack[depth].forceon;
        depth++;
        if (dostart) {
            if (2 * depth < strlen(startpos)) {
                char buf[3] = {0};
                memcpy(buf, startpos + 2*depth, 2);
                int n = strtol(buf, NULL, 16);
                if (pos < n)
                    goto reject;
            } else
                dostart = false;
        }
        stack[depth].pos = pos;
        setbit(&stack[depth].forceon, pos);
        setbit(&stack[depth].forceon, pos ^ mask);
        stack[depth].left = moves[pos];
        unsigned zz = mask;
        unsigned check = 0;
        unsigned pair = 0;
        for (int se = 0; se < depth + 1; se++) {
            unsigned prev = check;
            unsigned side2 = stack[se].pos ^ zz;
            check |= side2;
            if (check & (check + 1))
                goto reject;
            pair |= (check >> 1) & ~prev;
            unsigned diff = side2 ^ (side2 >> 1);
            if (pair & diff & side2)
                goto reject;
            pair &= ~diff;
            zz ^= mask;
        }
        struct i256 seen0 = {0}, seen1 = {0}, seen2 = {0};
        setbit(&seen0, mask);
        int sdepth = 0;
        while (1) {
            struct i256 sweep;
            xor3(&sweep, &seen0, &seen2);
            and(&sweep, &stack[depth].forceon);
            if (sdepth <= depth && !getbit(&sweep, stack[sdepth].pos)) {
                goto reject;
            }
            if (sdepth == depth - 1)
                andnot(&stack[depth].left, &seen0);
            if ((sdepth & 1) && getbit(&sweep, mask)) {
                if (sdepth > best) {
                    pthread_mutex_lock(&global_lock);
                    if (sdepth > global_best) {
                        global_best = sdepth;
                        printf("found %d\n", sdepth);
                        printf("%016llx%016llx\n", stack[depth].forceon.i[1],
                               stack[depth].forceon.i[0]);
                        fflush(stdout);
                    }
                    best = global_best;
                    pthread_mutex_unlock(&global_lock);
                }
                if (sdepth > local_best)
                    local_best = sdepth;
                goto reject;
            }
            if (ctz(&sweep) == -1)
                break;
            struct i256 news = seen1;
            while (1) {
                int p = ctz(&sweep);
                if (p == -1)
                    break;
                xorbit(&sweep, p);
                or(&news, &moves[p]);
            }
            seen2 = seen1;
            seen1 = seen0;
            seen0 = news;
            sdepth++;
        }
        if (depth == cutoff) {
            pthread_mutex_lock(&global_lock);
            bool reject = true;
            if (local_counter == global_counter) {
                reject = false;
                global_counter++;
            }
            best = global_best;
            pthread_mutex_unlock(&global_lock);
            local_counter++;
            local_best = 0;
            if (reject)
                goto reject;
        }
        continue;
    reject:
        depth--;
    }
    return NULL;
}

int main(int argc, char *argv[]) {
    assert(argc >= 2);
    num_people = atoi(argv[1]);
    int n_threads = 1;
    if (argc >= 3) {
        assert(argc >= 4);
        n_threads = atoi(argv[2]);
        cutoff = atoi(argv[3]);
    }
    assert(n_threads >= 1 && n_threads <= MAX_THREADS);
    if (argc >= 5) {
        startpos = argv[4];
        assert((strlen(startpos) & 1) == 0);
    }
    for (int i = 0; i < n_threads; i++)
        pthread_create(&threads[i], NULL, calc, &threads[i]);
    for (int i = 0; i < n_threads; i++)
        pthread_join(threads[i], NULL);
}