117 lines
2.5 KiB
C
117 lines
2.5 KiB
C
#define _GNU_SOURCE
|
|
#include <stdio.h>
|
|
#include <string.h>
|
|
#include <pthread.h>
|
|
#include <sched.h>
|
|
|
|
#define MAX_CPUS 8 // increase this if you got more CPUs/cores
|
|
|
|
typedef struct { char v[16]; } deck;
|
|
|
|
int n, best[16];
|
|
|
|
// Update a shared variable by spinlock. Since this program really only
|
|
// enters locks dozens of times, a pthread_mutex_lock() would work
|
|
// equally fine, but RC already has plenty of examples for that.
|
|
#define SWAP_OR_RETRY(var, old, new) \
|
|
if (!__sync_bool_compare_and_swap(&(var), old, new)) { \
|
|
volatile int spin = 64; \
|
|
while (spin--); \
|
|
continue; }
|
|
|
|
void tryswaps(deck *a, int f, int s, int d) {
|
|
#define A a->v
|
|
#define B b->v
|
|
|
|
while (best[n] < d) {
|
|
int t = best[n];
|
|
SWAP_OR_RETRY(best[n], t, d);
|
|
}
|
|
|
|
#define TEST(x) \
|
|
case x: if ((A[15-x] == 15-x || (A[15-x] == -1 && !(f & 1<<(15-x)))) \
|
|
&& (A[15-x] == -1 || d + best[15-x] >= best[n])) \
|
|
break; \
|
|
if (d + best[15-x] <= best[n]) return; \
|
|
s = 14 - x
|
|
|
|
switch (15 - s) {
|
|
TEST(0); TEST(1); TEST(2); TEST(3); TEST(4);
|
|
TEST(5); TEST(6); TEST(7); TEST(8); TEST(9);
|
|
TEST(10); TEST(11); TEST(12); TEST(13); TEST(14);
|
|
return;
|
|
}
|
|
#undef TEST
|
|
|
|
deck *b = a + 1;
|
|
*b = *a;
|
|
d++;
|
|
|
|
#define FLIP(x) \
|
|
if (A[x] == x || ((A[x] == -1) && !(f & (1<<x)))) { \
|
|
B[0] = x; \
|
|
for (int j = x; j--; ) B[x-j] = A[j]; \
|
|
tryswaps(b, f|(1<<x), s, d); } \
|
|
if (s == x) return;
|
|
|
|
FLIP(1); FLIP(2); FLIP(3); FLIP(4); FLIP(5);
|
|
FLIP(6); FLIP(7); FLIP(8); FLIP(9); FLIP(10);
|
|
FLIP(11); FLIP(12); FLIP(13); FLIP(14); FLIP(15);
|
|
#undef FLIP
|
|
}
|
|
|
|
int num_cpus(void) {
|
|
cpu_set_t ct;
|
|
sched_getaffinity(0, sizeof(ct), &ct);
|
|
|
|
int cnt = 0;
|
|
for (int i = 0; i < MAX_CPUS; i++)
|
|
if (CPU_ISSET(i, &ct))
|
|
cnt++;
|
|
|
|
return cnt;
|
|
}
|
|
|
|
struct work { int id; deck x[256]; } jobs[MAX_CPUS];
|
|
int first_swap;
|
|
|
|
void *thread_start(void *arg) {
|
|
struct work *job = arg;
|
|
while (1) {
|
|
int at = first_swap;
|
|
if (at >= n) return 0;
|
|
|
|
SWAP_OR_RETRY(first_swap, at, at + 1);
|
|
|
|
memset(job->x, -1, sizeof(deck));
|
|
job->x[0].v[at] = 0;
|
|
job->x[0].v[0] = at;
|
|
tryswaps(job->x, 1 | (1 << at), n - 1, 1);
|
|
}
|
|
}
|
|
|
|
int main(void) {
|
|
int n_cpus = num_cpus();
|
|
|
|
for (int i = 0; i < MAX_CPUS; i++)
|
|
jobs[i].id = i;
|
|
|
|
pthread_t tid[MAX_CPUS];
|
|
|
|
for (n = 2; n <= 14; n++) {
|
|
int top = n_cpus;
|
|
if (top > n) top = n;
|
|
|
|
first_swap = 1;
|
|
for (int i = 0; i < top; i++)
|
|
pthread_create(tid + i, 0, thread_start, jobs + i);
|
|
|
|
for (int i = 0; i < top; i++)
|
|
pthread_join(tid[i], 0);
|
|
|
|
printf("%2d: %2d\n", n, best[n]);
|
|
}
|
|
|
|
return 0;
|
|
}
|