惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

爱范儿
爱范儿
MyScale Blog
MyScale Blog
Recent Announcements
Recent Announcements
N
Netflix TechBlog - Medium
GbyAI
GbyAI
Vercel News
Vercel News
The GitHub Blog
The GitHub Blog
阮一峰的网络日志
阮一峰的网络日志
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
V
Visual Studio Blog
Martin Fowler
Martin Fowler
腾讯CDC
大猫的无限游戏
大猫的无限游戏
aimingoo的专栏
aimingoo的专栏
云风的 BLOG
云风的 BLOG
J
Java Code Geeks
WordPress大学
WordPress大学
P
Proofpoint News Feed
雷峰网
雷峰网
酷 壳 – CoolShell
酷 壳 – CoolShell
有赞技术团队
有赞技术团队
人人都是产品经理
人人都是产品经理
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
Y
Y Combinator Blog

物灵

A non-gamer’s view on games ◎物灵 I am a ruin aborigine ◎ 物灵 The spreadsheet-makers ◎物灵 وِسَ ڠ دَاِقࣨ؟ ◎物灵 领有和非领有的 C++ range ◎物灵 Do not get gentle into your CS major ◎物灵 ཡིའུ་ཀང་ལག་ ◎ 物灵 슈홋(守候) 2038넌(年) ◎物灵 Buku-name de Mini kon Sina-litera ◎物灵 ‘My Path’ after twenty years ◎物灵 My linguistic history ◎物灵 A slice of Bash programmable completion ◎物灵 Enhypen Alphabet ◎物灵 GNU 四十年 ◎物灵 ‘If need be, I will leave w/o looking back…’ ◎物灵 omekapo, Lánzhōu ⟲物灵 说说选登 ◎ 物灵 Back in old Ruyqiuan ◎物灵 linluwi lili li pona a! ⟲物灵 「挺」的中古三字 ◎物灵 最后一天 ◎物灵 基于 RFID 及智能终端的户外团队运动系统 ◎物灵 Which character for inbound passengers? ◎物灵 Kokanu in lika Hanci ◎物灵 دࣱخُاْ ۋاًخُوَاتࣨ ◎物灵 Childhood ◎物灵 个人视觉识别系统(辛丑) ◎物灵 ((报告 书) = (书 (报告 书)) ◎物灵 Speech before final examination ◎物灵 第 34 届山西科创记 ◎物灵
Number of shapes of Rubik’s snake ◎物灵
Unknown · 2022-09-20 · via 物灵

I wrote a program running on my roommate’s laptop for a day.

#include <stdio.h>
#include <omp.h>
#define N 24
#define PARALLEL_THRESHOLD 6
#define OUTPUT_THRESHOLD 12

struct Point {
    short x, y, z;
};

struct Block {
    struct Point s, d;
};

struct Point move(struct Point p, short d)
{
    switch (d) {
    case 1:  p.x++; break;  case 2:  p.y++; break;  case 3:  p.z++; break;
    case -1: p.x--; break;  case -2: p.y--; break;  case -3: p.z--; break;
    }
    return p;
}

struct Block extend(struct Block x)
{
    x.s = move(move(x.s, x.d.x), x.d.z);
    short dx = x.d.x;
    x.d.x = -x.d.y;
    x.d.y = -dx;
    x.d.z *= -1;
    return x;
}

struct Point backHelper2(struct Point p, short d)
{
    return d < 0 ? move(p, d) : p;
}

struct Point backHelper(struct Block x)
{
    return backHelper2(backHelper2(backHelper2(x.s, x.d.x), x.d.y), x.d.z);
}

short collapse(struct Block u, struct Block v)
{
    struct Point pu = backHelper(u), pv = backHelper(v);
    return (pu.x == pv.x && pu.y == pv.y && pu.z == pv.z)
           && !((u.d.x == -v.d.x && u.d.y == -v.d.y && u.d.z == v.d.z)
             || (u.d.x == -v.d.y && u.d.y == -v.d.x && u.d.z == -v.d.z));
}

struct Block rotate(struct Block x) 
{
    short dz = x.d.z;
    x.s = move(x.s, dz);
    x.d.z = x.d.y;
    x.d.y = -dz;
    return x;
}

static long long progress_done = 0;
long long count(struct Block blocks[], int p)
{
    long long result = 0;
    if (p == N)
        return 1;
    blocks[p] = extend(blocks[p - 1]);
    #pragma omp parallel for if(p <= PARALLEL_THRESHOLD) reduction(+: result)
    for (int i = 0; i < 4; ++i) {
        struct Block local[N];
        for (int k = 0; k < N; ++k)
            local[k] = blocks[k];
        for (int r = 0; r < i; ++r)
            local[p] = rotate(local[p]);
        for (int j = 0; j < p; ++j)
            if (collapse(local[p], local[j]))
                goto f1;
        result += count(local, p + 1);
        f1: ;
    }
    if (p <= OUTPUT_THRESHOLD) {
        if (p == OUTPUT_THRESHOLD)
            ++progress_done;
        printf("Progress: level %d, partial=%lld, completed=%f%%\n",
                p, result, 100.0 * progress_done / (1ll << (2 * OUTPUT_THRESHOLD)));
    }
    return result;
}

int main()
{
    struct Block blocks[N];
    blocks[0].s.x = blocks[0].s.y = blocks[0].s.z = 0;
    blocks[0].d.z = 1 + (blocks[0].d.y = 1 + (blocks[0].d.x = 1));
    printf("%lld\n", count(blocks, 1));
}

Interact via ActivityPub