用q来解骑士周游问题

〇〇

//到目前为止的实现,因为搞不定表字段的字符串拼接(用,就理解为另一个字段了)，先用整数
WITH c AS (
SELECT LEVEL id,POWER(2,LEVEL-1) b,CEIL(LEVEL/5) r,MOD(LEVEL-1,5) c FROM DUAL CONNECT BY LEVEL<=25
)
,m AS (
   SELECT c1.id id1,c2.id id2,c1.b b1,c2.b b2
    FROM c c1,c c2
   WHERE (ABS(c1.r-c2.r),ABS(c1.c-c2.c)) IN ((1,2),(2,1))
)   
,t(path,b,id) AS (
SELECT CAST(id AS VARCHAR2(100)),b,id FROM c WHERE id=1
UNION ALL
SELECT t.path||','||m.id2,t.b+m.b2,m.id2 FROM t,m WHERE t.id=m.id1 AND BITAND(t.b,m.b2)=0
)
SELECT path FROM t WHERE t.b=POWER(2,25)-1;
//------------------------------------------------------------------
//构造25个格子
n:til 25
L:flip (n;ceiling((n+1) % 5);1+(n mod 5))
c:([id:1+L[;0]];b:`long$(2 xexp L[;0]);r:L[;1];c:L[;2]) //table c

lc:L cross L
t0:([]c1:1+lc[;0];ro1:lc[;1];co1:lc[;2];c2:1+lc[;3];ro2:lc[;4];co2:lc[;5])
tm:select from t0 where (((abs(ro1-ro2))=2)and((abs(co1-co2))=1) ) or ( ((abs(ro1-ro2))=1)and((abs(co1-co2))=2))



m:([id1:tm.c1;id2:tm.c2];b1:`long$(2 xexp (tm.c1-1));b2:`long$(2 xexp (tm.c2-1))) //table m
//t:select path:string id,b,id from c where id=1 //table t
t:select path:id,b,id from c where id=1 //table t

t1:select (path*100)+id2,b+b2,id:id2 from t cross m where id=id1

〇〇

数据溢出
q)do[10;t:select (path*100)+id2,b+b2,id:id2 from t cross m where id=id1;]
wsfull

〇〇

〇〇 发表于 2016-5-31 21:03
//到目前为止的实现,因为搞不定表字段的字符串拼接(用,就理解为另一个字段了)，先用整数
WITH c AS (
SE ...

用表而不是列表cross的办法生成m表
q)tm2:select from (select id1:id,b1:b,r1:r,c1:c from c) cross c where (((abs(r-r1))=2)and((abs(c-c1))=1) ) or ( ((abs(r-
r1))=1)and((abs(c-c1))=2))
q)count tm2
96
q)tm
c1 ro1 co1 c2 ro2 co2
---------------------
1  1   1   8  2   3
1  1   1   12 3   2
2  1   2   9  2   4
2  1   2   11 3   1
2  1   2   13 3   3
3  1   3   6  2   1
3  1   3   10 2   5
3  1   3   12 3   2
3  1   3   14 3   4
4  1   4   7  2   2
4  1   4   13 3   3
4  1   4   15 3   5
5  1   5   8  2   3
5  1   5   14 3   4
6  2   1   3  1   3
6  2   1   13 3   3
6  2   1   17 4   2
7  2   2   4  1   4
7  2   2   14 3   4
7  2   2   16 4   1
..
q)tm2
id| id1 b1 r1 c1 b     r c
--| ----------------------
8 | 1   1  1  1  128   2 3
12| 1   1  1  1  2048  3 2
9 | 2   2  1  2  256   2 4
11| 2   2  1  2  1024  3 1
13| 2   2  1  2  4096  3 3
6 | 3   4  1  3  32    2 1
10| 3   4  1  3  512   2 5
12| 3   4  1  3  2048  3 2
14| 3   4  1  3  8192  3 4
7 | 4   8  1  4  64    2 2
13| 4   8  1  4  4096  3 3
15| 4   8  1  4  16384 3 5
8 | 5   16 1  5  128   2 3
14| 5   16 1  5  8192  3 4
3 | 6   32 2  1  4     1 3
13| 6   32 2  1  4096  3 3
17| 6   32 2  1  65536 4 2
4 | 7   64 2  2  8     1 4
14| 7   64 2  2  8192  3 4
16| 7   64 2  2  32768 4 1
..
q)

〇〇

加了取模判断
q)t:select path:id,b,id from c where id=1 //table t
q)t
path b id
---------
1    1 1
q)t1:select (path*100)+id2,b+b2,id:id2 from t cross m where (id=id1) and (("j"$(b % (2 xexp (id2-1)))mod 2 )<>1)
q)t1
path b    id
------------
108  129  8
112  2049 12
q)meta t1
c   | t f a
----| -----
path| j
b   | j
id  | j
q)t1:select (path*100)+id2,b+b2,id:id2 from t1 cross m where (id=id1) and (("j"$(b % (2 xexp (id2-1)))mod 2 )<>1)
q)t1
path  b       id
----------------
10805 145     5
10811 1153    11
10815 16513   15
10817 65665   17
10819 262273  19
11203 2053    3
11209 2305    9
11219 264193  19
11221 1050625 21
11223 4196353 23

〇〇

数据没有溢出，用来表示路径的东西溢出了
10
q)do[10;t1:select (path*100)+id2,b+b2,id:id2 from t1 cross m where (id=id1) and (("j"$(b % (2 xexp (id2-1)))mod 2 )<>1);
]
q)count t1
3082
q)t1[1]
path| -4003104376271675979
b   | 5298901
id  | 21

〇〇

〇〇 发表于 2016-6-1 11:07
加了取模判断
q)t:select path:id,b,id from c where id=1 //table t
q)t

这一步还是与sql结果对着的
WITH c AS (
SELECT LEVEL id,POWER(2,LEVEL-1) b,CEIL(LEVEL/5) r,MOD(LEVEL-1,5) c FROM DUAL CONNECT BY LEVEL<=25
)
,m AS (
    SELECT c1.id id1,c2.id id2,c1.b b1,c2.b b2
     FROM c c1,c c2
    WHERE (ABS(c1.r-c2.r),ABS(c1.c-c2.c)) IN ((1,2),(2,1))
)   
,t(path,b,id) AS (
SELECT CAST(id AS VARCHAR2(100)),b,id FROM c WHERE id=1),
t1 (path,b,id)as(
SELECT t.path||','||m.id2,t.b+m.b2,m.id2 FROM t,m WHERE t.id=m.id1 AND BITAND(t.b,m.b2)=0
),
t2 (path,b,id)as
(
SELECT t.path||','||m.id2,t.b+m.b2,m.id2 FROM t1 t,m WHERE t.id=m.id1 AND BITAND(t.b,m.b2)=0
)
select * from t2;


PATH                                              B         ID
---------------------------------------- ---------- ----------
1,8,19                                       262273         19
1,8,17                                        65665         17
1,8,15                                        16513         15
1,8,11                                         1153         11
1,8,5                                           145          5
1,12,23                                     4196353         23
1,12,21                                     1050625         21
1,12,19                                      264193         19
1,12,9                                         2305          9
1,12,3                                         2053          3

〇〇

这一步就出事了
1,8,5,14                                       8337         14
1,8,11,22                                   2098305         22
1,8,11,18                                    132225         18
1,8,11,2 ------------                                      1155          2
1,8,15,24                                   8405121         24
1,8,15,18                                    147585         18
1,8,15,4                                      16521          4
1,8,17,24                                   8454273         24
1,8,17,14                                     73857         14
1,8,17,6                                      65697          6
1,8,19,22                                   2359425         22
1,8,19,12                                    264321         12
1,8,19,10                                    262785         10
1,12,3,14                                     10245         14
1,12,3,10                                      2565         10
1,12,3,6                                       2085          6
1,12,9,20                                    526593         20
1,12,9,18                                    133377         18
1,12,9,2 -------------                                      2307          2
1,12,19,22                                  2361345         22
1,12,19,10                                   264705         10
1,12,19,8                                    264321          8
1,12,21,18                                  1181697         18
1,12,23,20                                  4720641         20
1,12,23,16                                  4229121         16
1,12,23,14                                  4204545         14

path    b       id
------------------
1080514 8337    14
1081118 132225  18
1081122 2098305 22
1081504 16521   4
1081518 147585  18
1081524 8405121 24
1081706 65697   6
1081714 73857   14
1081724 8454273 24
1081910 262785  10
1081912 264321  12
1081922 2359425 22
1120306 2085    6
1120310 2565    10
1120314 10245   14
1120918 133377  18
1120920 526593  20
1121908 264321  8
1121910 264705  10
1121922 2361345 22
1122118 1181697 18
1122314 4204545 14
1122316 4229121 16
1122320 4720641 20

这个应该可以放2的
10811 1153    11
但是好像四舍五入了
q)"j"$(1153 % 2)
577
q)577 mod 2
1

〇〇

〇〇 发表于 2016-6-1 14:00
这一步就出事了
1,8,5,14                                       8337         14
1,8,11,22            ...

向下取整，好了
q)t1:select (path*100)+id2,b+b2,id:id2 from t1 cross m where (id=id1) and (("j"$floor(b % (2 xexp (id2-1)))mod 2 )<>1)
q)count t1
26
q)t1
path    b       id
------------------
1080514 8337    14
1081102 1155    2
1081118 132225  18
1081122 2098305 22
1081504 16521   4
1081518 147585  18
1081524 8405121 24
1081706 65697   6
1081714 73857   14
1081724 8454273 24
1081910 262785  10
1081912 264321  12
1081922 2359425 22
1120306 2085    6
1120310 2565    10
1120314 10245   14
1120902 2307    2
1120918 133377  18
1120920 526593  20
1121908 264321  8

〇〇

〇〇 发表于 2016-6-1 14:06
向下取整，好了
q)t1:select (path*100)+id2,b+b2,id:id2 from t1 cross m where (id=id1) and (("j"$fl ...

还是溢出了
q)t
path b id
---------
1    1 1
q)t1:t
q)t1
path b id
---------
1    1 1
q)do [24;t1:select (path*100)+id2,b+b2,id:id2 from t1 cross m where (id=id1) and (("j"$floor(b % (2 xexp (id2-1)))mod 2
)<>1);]
wsfull

〇〇

〇〇 发表于 2016-6-1 14:09
还是溢出了
q)t
path b id

第14步还可以，然后就不行了
q)t1:t
q)\t do[13;count t1:select (path*100)+id2,b+b2,id:id2 from t1 cross m where (id=id1) and (("j"$floor(b % (2 xexp (id2-1)
))mod 2)<>1);]
3094
q)count t1
133394
q)\t do[1;count t1:select (path*100)+id2,b+b2,id:id2 from t1 cross m where (id=id1) and (("j"$floor(b % (2 xexp (id2-1))
)mod 2)<>1);]
3006
q)count t1
186956

t1 186956 * m 96 =1800w行