扩展最新的“好的”OEIS序列:网格上的垫脚石拼图
今天，OEIS 发电子邮件的Neil要求确认当前的术语，并用关键字“尼斯”计算最新的OEIS序列A337663的一些更大的术语。
下面是这个序列的工作原理:在无限正方形网格上用n S标记1单元，然后
将数字2,3,4,\dots,m按顺序排列，但必须遵守这样的规则，即放置k时，其水平、垂直和对角线邻居的和必须等于k。然后，A337663(n)是可以在1-cells的所有初始位置上实现的最大m。
下面是A337663(2) = 16的一个例子：
+----+----+----+----+----+----+
| 9 | 5 | 10 | 11 | | |
+----+----+----+----+----+----+
| | 4 | 1 | | | |
+----+----+----+----+----+----+
| 12 | 8 | 3 | 2 | | 16 |
+----+----+----+----+----+----+
| | | | 6 | 1 | 15 |
+----+----+----+----+----+----+
| | | 13 | 7 | 14 | |
+----+----+----+----+----+----+注意，2-cell有两个1-cells作为邻居(和1 + 1 = 2)；3-cell有一个1-cell和一个2-cell作为邻居(和1 + 2 = 3)；等等。
挑战
.
和这之前的挑战一样，这个代码挑战的目标是在这个序列中计算尽可能多的项，这个序列从1, 16, 28, 38开始，n-th项是A337663(n)。
运行您的代码，只要您愿意。这一挑战的赢家将是发布序列中最多的术语的用户，以及他们生成该序列的代码。如果两个用户发布相同数量的术语，那么谁发布他们的上一学期最早的胜利。
回答 2
Code Golf用户
发布于 2020-10-08 14:07:43
C + OpenMP，N=5
新版本，妥善处理112-1113案件。
a(5) = 49
0 46 26 0 0 0 0 0 0 0 0 35 0
0 20 0 6 28 48 0 0 0 0 34 1 36
39 19 1 2 3 17 0 30 0 0 33 0 37
0 0 18 7 1 4 9 0 21 32 0 0 0
0 40 0 8 38 5 43 10 11 0 44 0 0
0 0 22 0 13 0 15 0 1 12 0 0 0
47 23 0 14 27 0 31 16 29 0 0 0 0
0 24 1 0 41 0 0 0 45 0 0 0 0
49 25 0 42 0 0 0 0 0 0 0 0 0是如何工作的
该程序只适用于N=5，对于较高的数字，您需要进行一些调整。首先，让我们看看N=4的一种更简单的方法是什么样子的。在某种安排中，我们至少需要112个人在一起。因为只剩下两个1s，所以其他的数字不能只由新的1s来决定。
因此，从112的六个可能的起始位置开始：
1 1 1 2 1 1 _ 1 1 _ 1 _ _ 1 _ _
2 _ _ 2 _ 2 1 _ 2 1 _ 2 _
_ _ 1我们可以查看两个位置之外的每一个空间，并检查它们的和(注意:如果有了适当的案例处理，您应该可以检查直接的邻居，尽管我选择了安全的路线)。
0 0 0 0 0 0
0 1 2 2 1 011 -> 0 3。。1 0 2 0 3。4 1 0 0 2 2 2 0 0 0
对于每个点:检查和是否是下一个所需的数字(在本例中是3)，或者我们是否仍然可以放置一些1s:之和加上一些新添加的1s是下一个所需的数字。在后一种情况下，我们需要确保新的1不干扰现有的数字>1。
3 1
1 1 1
2不会有效，因为2-安置是非法的，但是
1 1
2 3 1
1会很好的。请注意，我只增加了非1数字周围两个点的包围框。因此，对于右下角，下一个要尝试的点如下：
1 _ _ _
_ 3 1 _
_ 1 _ _
_ _ _ _
xx点不会被检查，因为它的编号只会是相邻的新1-而对于N=4，这是不可能的，正如前面提到的。
对于N>4，这会变得更加复杂:不能保证每个数字都会连接到前112号。另一个集群可能独立启动: 1113。但在此之后，每个数字不能仅由新1构成，因此将连接到1113或112。请注意，在N=5情况下，我们不需要处理其他任何事情(但是需要使用N>5)：拥有两个具有1和11114的集群将被处理，因为2和3也必须放置在11114中；因此，每11114都将由112或1113进行检查。
因此，我们需要得到一个包围盒，以了解有多接近112和1113可以放置。为此，我们运行两个板子，不能触摸，得分他们的距离，他们设法摆脱了起始位置。这是他们管理的最好的：
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 15 0 0 0 0
0 0 11 10 5 0 0 0 0
0 0 0 1 4 12 0 0 0
0 0 0 0 2 1 13 0 0
0 0 0 0 0 0 14 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
…
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 17 9 0 3 1 0
0 0 0 8 1 6 1 0
0 0 0 16 7 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0他们不能留下5个瓷砖。因此，如果我们将初始的3放置在一个20x20 (+一个填充为4的填充区域)中，这个字段以2为中心，我们要么得到两个独立于它们所在位置的独立得分的断开连接的集群，要么得到两个最终将结合在一起的集群。所以任何事情都可以
1 1 _ _ _ _ _ _ _ _ _ _ _ 1 1
_ 2 a b c d e _ e d c b a 3 1将在两者之间使用11个空格进行检查；足够使它们无法满足。
所有这些，然后递归地尝试所有的可能性，在一个深度优先-搜索。总是只修改一个板，我们只需要内存的a(N)递归步骤。
OMP只用于并行检查初始板。这远远不是一个平衡的工作量；最后的职位需要的时间大约是其他职位的两倍。然而，这是最容易实现的。:-)
程序
用clang -O3 -o main main.c -fopenmp编译，用time OMP_NUM_THREADS=4 ./main运行。
#include <stdint.h>
#include <stddef.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef uint8_t mem_t;
typedef uint16_t sum_t;
#define S 64
const int startx = S/2, starty = S/2;
// for N > 5, adjust the unrolled loops in step
#define MAX_CELL 5
#define MAX_BOARDS 2
#define MAX(x,y) (x>y?x:y)
#define MIN(x,y) (x<y?x:y)
const int ys[8] = {0,1,1,1,0,-1,-1,-1};
const int xs[8] = {1,1,0,-1,-1,-1,0,1};
inline
void add_sum(sum_t v, int y, int x, sum_t sum[S][S]) {
for(int d=0;d<8;d++)
sum[y+ys[d]][x+xs[d]] += v;
}
inline
void add_placed(sum_t v, int y, int x, mem_t placed[S][S]) {
for(int d=0;d<8;d++)
placed[y+ys[d]][x+xs[d]] += v;
}
typedef struct board {
int y0, y1, x0, x1;
mem_t b[S][S], placed[S][S];
sum_t sum[S][S];
} board_t;
void st_print(int c, int max, board_t *b) {
printf("%d cells, %d max\n", c, max);
for(int y=b->y0;y<=b->y1;y++){
for(int x=b->x0;x<=b->x1;x++) printf("%*d", 3, b->b[y][x]);
puts("\n");
}
}
void step(int c, mem_t max, board_t *bs, int bl, mem_t *best_max, board_t best_b[MAX_BOARDS], int optimize_spread) {
// check board size
for(int i=0;i<bl;i++) {
if (bs[i].y0 < 2 || bs[i].y1 >= S - 2 || bs[i].x0 < 2 || bs[i].x1 >= S - 2) {
st_print(c, max, &bs[i]);
printf("board too small %d %d %d %d", bs[i].y0, bs[i].y1, bs[i].x0, bs[i].x1);
exit(1);
}
}
// new best
if (c == MAX_CELL) {
int score = 0;
if (optimize_spread) {
for (int i=0;i<bl;i++)
score += MAX(starty - bs[i].y0,
MAX(bs[i].y1 - starty,
MAX(startx - bs[i].x0,
bs[i].x1 - startx)));
} else {
score = max;
}
if (*best_max < score) {
for (int i=0;i<bl;i++)
memcpy(&best_b[i], &bs[i], sizeof(board_t));
*best_max = score;
}
}
// place with 0 new 1-cells
if(!optimize_spread || max != 2)
for(int i=0;i<bl;i++) {
board_t *b=bs+i;
for(int y=b->y0;y<=b->y1;y++)
for(int x=b->x0;x<=b->x1;x++)
if(b->sum[y][x] == max + 1 && !b->b[y][x]) {
b->b[y][x] = max + 1;
add_sum(max+1,y,x,b->sum);
add_placed(1,y,x,b->placed);
int y0o = b->y0, y1o = b->y1, x0o = b->x0, x1o = b->x1;
b->y0 = MIN(b->y0, y-2);
b->y1 = MAX(b->y1, y+2);
b->x0 = MIN(b->x0, x-2);
b->x1 = MAX(b->x1, x+2);
step(c, max + 1, bs, bl, best_max, best_b, optimize_spread);
b->y0 = y0o, b->y1 = y1o, b->x0 = x0o, b->x1 = x1o;
add_placed(-1,y,x,b->placed);
add_sum(-(max+1),y,x,b->sum);
b->b[y][x] = 0;
}
}
// sorry for the repetition, couldn't get clang to optimize it otherwise
// place with 1 new 1-cells
if(!optimize_spread || max != 2)
if(c + 1 <= MAX_CELL)
for(int i=0;i<bl;i++) {
board_t *b=bs+i;
for(int y=b->y0;y<=b->y1;y++)
for(int x=b->x0;x<=b->x1;x++)
if(b->sum[y][x] == (max + 1) - 1 && !b->b[y][x]) {
for(int d1=0;d1<8;d1++) {
if (b->placed[y+ys[d1]][x+xs[d1]]) continue;
b->b[y+ys[d1]][x+xs[d1]] = 1;
b->b[y][x] = max + 1;
add_sum(max+1,y,x,b->sum);
add_sum(1,y+ys[d1],x+xs[d1],b->sum);
add_placed(1,y,x,b->placed);
int y0o = b->y0, y1o = b->y1, x0o = b->x0, x1o = b->x1;
b->y0 = MIN(b->y0, y-2);
b->y1 = MAX(b->y1, y+2);
b->x0 = MIN(b->x0, x-2);
b->x1 = MAX(b->x1, x+2);
step(c + 1, max + 1, bs, bl, best_max, best_b, optimize_spread);
b->y0 = y0o, b->y1 = y1o, b->x0 = x0o, b->x1 = x1o;
add_placed(-1,y,x,b->placed);
add_sum(-(max+1),y,x,b->sum);
add_sum(-1,y+ys[d1],x+xs[d1],b->sum);
b->b[y+ys[d1]][x+xs[d1]] = 0;
b->b[y][x] = 0;
}
}
}
// place with 2 new 1-cells
if(!optimize_spread || max != 2)
if(c + 2 <= MAX_CELL)
for(int i=0;i<bl;i++) {
board_t *b=bs+i;
for(int y=b->y0;y<=b->y1;y++)
for(int x=b->x0;x<=b->x1;x++)
if(b->sum[y][x] == (max + 1) - 2 && !b->b[y][x]) {
for(int d1=0;d1<8-1;d1++) {
if (b->placed[y+ys[d1]][x+xs[d1]]) continue;
for(int d2=d1+1;d2<8;d2++) {
if (b->placed[y+ys[d2]][x+xs[d2]]) continue;
b->b[y+ys[d1]][x+xs[d1]] = 1;
b->b[y+ys[d2]][x+xs[d2]] = 1;
b->b[y][x] = max + 1;
add_sum(max+1,y,x,b->sum);
add_sum(1,y+ys[d1],x+xs[d1],b->sum);
add_sum(1,y+ys[d2],x+xs[d2],b->sum);
add_placed(1,y,x,b->placed);
int y0o = b->y0, y1o = b->y1, x0o = b->x0, x1o = b->x1;
b->y0 = MIN(b->y0, y-2);
b->y1 = MAX(b->y1, y+2);
b->x0 = MIN(b->x0, x-2);
b->x1 = MAX(b->x1, x+2);
step(c + 2, max + 1, bs, bl, best_max, best_b, optimize_spread);
b->y0 = y0o, b->y1 = y1o, b->x0 = x0o, b->x1 = x1o;
add_placed(-1,y,x,b->placed);
add_sum(-(max+1),y,x,b->sum);
add_sum(-1,y+ys[d1],x+xs[d1],b->sum);
add_sum(-1,y+ys[d2],x+xs[d2],b->sum);
b->b[y+ys[d1]][x+xs[d1]] = 0;
b->b[y+ys[d2]][x+xs[d2]] = 0;
b->b[y][x] = 0;
}
}
}
}
// place with 3 new 1-cells
if(c + 3 <= MAX_CELL)
for(int i=(optimize_spread && max == 2);i<bl;i++) {
board_t *b=bs+i;
for(int y=b->y0;y<=b->y1;y++)
for(int x=b->x0;x<=b->x1;x++)
if(b->sum[y][x] == (max + 1) - 3 && !b->b[y][x]) {
for(int d1=0;d1<8-2;d1++) {
if (b->placed[y+ys[d1]][x+xs[d1]]) continue;
for(int d2=d1+1;d2<8-1;d2++) {
if (b->placed[y+ys[d2]][x+xs[d2]]) continue;
for(int d3=d2+1;d3<8;d3++) {
if (b->placed[y+ys[d3]][x+xs[d3]]) continue;
b->b[y+ys[d1]][x+xs[d1]] = 1;
b->b[y+ys[d2]][x+xs[d2]] = 1;
b->b[y+ys[d3]][x+xs[d3]] = 1;
b->b[y][x] = max + 1;
add_sum(max+1,y,x,b->sum);
add_sum(1,y+ys[d1],x+xs[d1],b->sum);
add_sum(1,y+ys[d2],x+xs[d2],b->sum);
add_sum(1,y+ys[d3],x+xs[d3],b->sum);
add_placed(1,y,x,b->placed);
int y0o = b->y0, y1o = b->y1, x0o = b->x0, x1o = b->x1;
b->y0 = MIN(b->y0, y-2);
b->y1 = MAX(b->y1, y+2);
b->x0 = MIN(b->x0, x-2);
b->x1 = MAX(b->x1, x+2);
step(c + 3, max + 1, bs, bl, best_max, best_b, optimize_spread);
b->y0 = y0o, b->y1 = y1o, b->x0 = x0o, b->x1 = x1o;
add_placed(-1,y,x,b->placed);
add_sum(-(max+1),y,x,b->sum);
add_sum(-1,y+ys[d1],x+xs[d1],b->sum);
add_sum(-1,y+ys[d2],x+xs[d2],b->sum);
add_sum(-1,y+ys[d3],x+xs[d3],b->sum);
b->b[y+ys[d1]][x+xs[d1]] = 0;
b->b[y+ys[d2]][x+xs[d2]] = 0;
b->b[y+ys[d3]][x+xs[d3]] = 0;
b->b[y][x] = 0;
}
}
}
}
}
}
void set_starting_board(board_t* b, int i) {
int x0 = startx, y0 = starty;
b->b[y0][x0] = 2;
if (i == 0) b->b[y0-1][x0-1] = 1,
b->b[y0+1][x0+1] = 1;
if (i == 1) b->b[y0-1][x0-1] = 1,
b->b[y0][x0+1] = 1;
if (i == 2) b->b[y0][x0-1] = 1,
b->b[y0][x0+1] = 1;
if (i == 3) b->b[y0-1][x0] = 1,
b->b[y0][x0+1] = 1;
if (i == 4) b->b[y0-1][x0-1] = 1,
b->b[y0-1][x0+1] = 1;
if (i == 5) b->b[y0-1][x0] = 1,
b->b[y0-1][x0+1] = 1;
for(int y=1;y+1<S;y++)
for(int x=1;x+1<S;x++)
for(int yd=-1;yd<=1;yd++)
for(int xd=-1;xd<=1;xd++)
if(yd!=0||xd!=0)
b->sum[y][x] += b->b[y+yd][x+xd];
for(int y=1;y+1<S;y++)
for(int x=1;x+1<S;x++)
for(int yd=-1;yd<=1;yd++)
for(int xd=-1;xd<=1;xd++)
b->placed[y][x] += b->b[y+yd][x+xd] > 1;
}
int get_bounding_box() {
int x0 = startx, y0 = starty;
board_t best_b[6][3] = {0};
mem_t best_max[6] = {0};
#pragma omp parallel for
for(int i=0;i<6;i++) {
board_t bs[] = {(board_t){y0 - 3, y0 + 3, x0 - 3, x0 + 3, {0}, {0}, {0}},
(board_t){y0, y0, x0, x0, {0}, {0}, {0}}};
set_starting_board(&bs[0], i);
step(2, 2, bs, 2, &best_max[i], best_b[i], 1);
}
int best_i=0, mm = 0;
for(int i=0;i<6;i++)
if (best_max[i] > mm)
mm = best_max[i],
best_i = i;
printf("most spread of distant 112 and 1113: %d\n", best_max[best_i]);
st_print(MAX_CELL, best_max[best_i], &best_b[best_i][0]);
st_print(MAX_CELL, best_max[best_i], &best_b[best_i][1]);
return best_max[best_i] + 4;
}
int main(int argc, char **argv) {
int bb = get_bounding_box();
int x0 = startx, y0 = starty;
board_t best_b[6][3] = {0};
mem_t best_max[6] = {0};
#pragma omp parallel for
for(int i=0;i<6;i++) {
board_t bs[] = {(board_t){y0 - bb, y0 + bb, x0 - bb, x0 + bb, {0}, {0}, {0}},};
set_starting_board(&bs[0], i);
step(2, 2, bs, 1, &best_max[i], best_b[i], 0);
}
int best_i=0, mm = 0;
for(int i=0;i<6;i++)
if (best_max[i] > mm)
mm = best_max[i],
best_i = i;
st_print(MAX_CELL, best_max[best_i], &best_b[best_i][0]);
return 0;
};Code Golf用户
发布于 2020-10-10 11:14:09
C (Perl) n=6
我在这里的第一个^第二关是可用的论github；我认为原则上这应该可以计算到a(8)，但这需要一段时间，即使现在它已经在C中被重新编码了。
在我的机器上，a(4)需要42 s，a(5)需要14 On，分别遍历63,200,517和18,371,175,865个板位置；用C重写大约比最初的Perl原型快250倍。
a(5) =49的解：
. . 39 . . . 47 . 49
46 20 19 . 40 . 23 24 25
26 . 1 18 . 22 . 1 .
. 6 2 7 8 . 14 . 42
. 28 3 1 38 13 27 41 .
. 48 17 4 5 . . . .
. . . 9 43 15 31 . .
. . 30 . 10 . 16 . .
. . . 21 11 1 29 45 .
. . . 32 . 12 . . .
. 34 33 . 44 . . . .
35 1 . . . . . . .
. 36 37 . . . . . .(哦，这是xash解决方案的对称性，我某种程度上认为它是不同的。)
确认一个(6)= 60需要大约10个CPU-周(手动切分)，并遍历4.57e12位置。找到解决办法：
. 56 42 . 60 . . . . . . . . .
. . 14 28 32 . . . . . . . . .
. 29 10 4 . 35 . . . . . . . .
. 44 5 1 3 46 . . . . . . . .
. . . 31 2 6 . 37 . . . . . .
55 . . 11 9 1 7 30 . . . . . .
54 1 12 45 . 25 8 15 . . . . . .
27 26 13 . . 33 . 40 16 34 51 . . .
53 . 39 52 . . . . 1 17 . . . .
. . . . . . . 57 18 . 36 . . .
. . . . . . . . 38 19 . . . .
. . . . . . . . 58 1 20 41 . .
. . . . . . . . 59 . 21 . . 47
. . . . . . . . . . 43 22 23 24
. . . . . . . . . . . . 1 48
. . . . . . . . . . . 50 49 .通过外推，找到a(7)所需的时间是a(6)的200到250倍。我不打算尝试这个。
方法是: a)根据需要延迟插入1s；b)分别存储未连接的组，根据需要合并它们。
超出(8)的范围将需要允许我们同时合并3个或更多组的可能性。除非我把速度降到一天以下，否则我不会费心去解决这个问题。
核心工作由板->试函数(C：试一试_板)完成，它尝试每一种可能的方法将下一个数字放置在当前板中，然后递归。
集团->聚结 (C：聚结_组)函数是编写的最后一个也是最棘手的部分:给定两个组，每个组内的位置将构成插入新值的公共点，以及必须放置在其周围的额外1s数，此算法：
- 确定第一组的方向，并试验第二组的8种可能的方向；
- 首先检查公共地点的近邻，寻找允许这两个群体共存的方向，并留出足够多的1s空间；
- 然后试图将一组覆盖在另一组，检查是否有进一步的冲突；
- 最后，在所述公共位置周围生成n个可用小区的k个组合，其中可以放置所请求的k个附加的1s。
最难的是找到bug，因为需要检查的数据点太少了。我增加了更多的测试，但是我没有信心我已经找到了所有的but。
雨果
2020年年-10-10:增加精确的时间和位置计数
2020年年-10-13:C方面的进展，a(5)
2020年年-11-05: a(6) = 60
https://codegolf.stackexchange.com/questions/212160
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号