puzzleup 2021

solomon_007 · 发表于 2021-10-17 21:44

〇〇发表于 2021-10-17 06:02
点阵在x轴和y轴上的投影都多于3个点就行

不错的总结，换句话就是，不同的X,不同的Y坐标都大于等于 4，就是一个解！

〇〇 · 发表于 2021-10-17 22:22

写成oracle语法也比newkid差很多

〇〇 · 发表于 2021-10-18 08:37

本帖最后由〇〇于 2021-10-18 08:52 编辑

〇〇发表于 2021-10-17 16:19
把你们的方法结合了，很慢，用取模去掉了一些，24秒。sqlite数据库with t6(n) as (select 1 union all sele ...

pypy38 7.3.6 https://downloads.python.org/pypy/pypy3.8-v7.3.6-win64.zip
sqlite 3.36 https://sqlite.org/2021/sqlite-tools-win32-x86-3360000.zip

同样的代码，同样的机器，在pypy上居然比sqlite的可执行程序更快。
D:\pypy38\pypy3.8-v7.3.6-win64>pypy3
Python 3.8.12 (279d80ac2079, Oct 17 2021, 05:26:02)
[PyPy 7.3.6 with MSC v.1929 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.

import time

import sqlite3
con=sqlite3.connect(':memory:')
cur=con.cursor()

t=time.time()
for row in cur.execute('''
with t6(n) as (select 1 union all select n+1 from t where n<6)
,
b3(a,b,c,bit)as(select a.n,b.n,c.n,(1<<(a.n-1))+(1<<(b.n-1))+(1<<(c.n-1)) from t6 a,t6 b,t6 c where a.n<b.n and b.n<c.n)
,
b9(b)as(select c.bit*((1<<(r.a-1)*6)+(1<<(r.b-1)*6)+(1<<(r.c-1)*6)) from b3 c,b3 r)
,
t(n,c,x,y)
as(select 1,'1',1,1 union all select n+1,cast(n+1 as varchar),n/6+1,n%6+1 from t where n<6*6)
,
s(lv,n,nlist,blist)
as(select 1,t.n,t.c,1<<(t.n-1) from t where t.n<=6
union all
select lv+1,b.n,nlist||','||c,blist+(1<<(b.n-1))
from s,t b
where lv<10 and s.n<b.n
and(blist%19<14)
and(select max(sum(case when a.x=b.x then 1 end), sum(case when a.y=b.y then 1 end))from t a
where ((blist+(1<<(b.n-1))&(1<<(a.n-1)))>0))<=2
and b.n -lv/2*6 between 1 and 6*2
)
select * from s where lv=10 and (lv<3 or not exists(select 1 from b9 where (blist & b9.b) =0))
limit 100
'''):
print(row)

print(time.time()-t)
....
8.011458158493042

==================
D:\sqlite>sqlite3
SQLite version 3.34.0 2020-12-01 16:14:00
Enter ".help" for usage hints.
Connected to a transient in-memory database.
Use ".open FILENAME" to reopen on a persistent database.
sqlite> .timer on

Run Time: real 40.734 user 40.513460 sys 0.046800
D:\sqlite>sqlite336
SQLite version 3.36.0 2021-06-18 18:36:39
Enter ".help" for usage hints.
Connected to a transient in-memory database.
Use ".open FILENAME" to reopen on a persistent database.
sqlite> .timer on

Run Time: real 11.117 user 10.810869 sys 0.062400

〇〇 · 发表于 2021-10-18 08:50

用二进制位代替sum,快了一倍，还是pypy3略快

D:\pypy38\pypy3.8-v7.3.6-win64>pypy3
Python 3.8.12 (279d80ac2079, Oct 17 2021, 05:26:02)
[PyPy 7.3.6 with MSC v.1929 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
import time

import sqlite3
con=sqlite3.connect(':memory:')
cur=con.cursor()

t=time.time()
for row in cur.execute('''
with t6(n) as (select 1 union all select n+1 from t where n<6)
,
b3(a,b,c,bit)as(select a.n,b.n,c.n,(1<<(a.n-1))+(1<<(b.n-1))+(1<<(c.n-1)) from t6 a,t6 b,t6 c where a.n<b.n and b.n<c.n)
,
b9(b)as(select c.bit*((1<<(r.a-1)*6)+(1<<(r.b-1)*6)+(1<<(r.c-1)*6)) from b3 c,b3 r)
,
t(n,c,x,y)
as(select 1,'1',1,1 union all select n+1,cast(n+1 as varchar),n/6+1,n%6+1 from t where n<6*6)
,
s(lv,n,nlist,blist,px,py)
as(select 1,t.n,t.c,1<<(t.n-1),pow(10,t.x),pow(10,t.y) from t where t.n<=6
union all
select lv+1,b.n,nlist||','||c,blist+(1<<(b.n-1)),px+pow(10,b.x),py+pow(10,b.y)
from s,t b
where lv<10 and s.n<b.n
and(blist%19<14)
and (instr(px+pow(10,b.x),3)=0 and instr(py+pow(10,b.y),3)=0)
--and(select max(sum(case when a.x=b.x then 1 end), sum(case when a.y=b.y then 1 end))from t a
--  where ((blist+(1<<(b.n-1))&(1<<(a.n-1)))>0))<=2
and b.n  between lv/2*6+1 and lv/2*6+6*2
)
select * from s where lv=10 and (lv<3 or not exists(select 1 from b9 where  (blist & b9.b) =0))
limit 100
'''):
  print(row)

print(time.time()-t)

-----
3.277186870574951

D:\sqlite>sqlite336
SQLite version 3.36.0 2021-06-18 18:36:39
Enter ".help" for usage hints.
Connected to a transient in-memory database.
Use ".open FILENAME" to reopen on a persistent database.
sqlite> .timer on

Run Time: real 4.340 user 4.134027 sys 0.078001

〇〇 · 发表于 2021-10-18 09:04

本帖最后由〇〇于 2021-10-18 09:34 编辑

将最后一个改成postgres的语法

D:\pgsql140\bin>psql -d test
psql (14.0)
输入 "help" 来获取帮助信息.

test=# \timing on
启用计时功能.

with  RECURSIVE t6(n) as (select 1 union all select n+1 from t where n<6)
,
b3(a,b,c,bit)as(select a.n,b.n,c.n,(1<<(a.n-1))+(1<<(b.n-1))+(1<<(c.n-1))::bigint from t6 a,t6 b,t6 c where a.n<b.n and b.n<c.n)
,
b9(b)as(select c.bit*((1<<(r.a-1)*6)+(1<<(r.b-1)*6)+(1<<(r.c-1)*6)) from b3 c,b3 r)
,
t(n,c,x,y)
as(select 1,cast(1 as varchar),1,1 union all select n+1,cast(n+1 as varchar),n/6+1,n%6+1 from t where n<6*6)
,
s(lv,n,nlist,blist,px,py)
as(select 1,t.n,t.c,1<<(t.n-1),pow(10,t.x),pow(10,t.y) from t where t.n<=6
union all
select lv+1,b.n,nlist||','||c,blist+(1<<(b.n-1)),px+pow(10,b.x),py+pow(10,b.y)
from s,t b
where lv<10 and s.n<b.n
and(blist%19<14)
and (position('3' in (px+pow(10,b.x))::varchar)=0 and position('3' in (py+pow(10,b.y))::varchar)=0)
--and(select max(sum(case when a.x=b.x then 1 end), sum(case when a.y=b.y then 1 end))from t a
--  where ((blist+(1<<(b.n-1))&(1<<(a.n-1)))>0))<=2
and (b.n  between lv/2*6+1 and lv/2*6+6*2)
)
select * from s where lv=10 and (lv<3 or not exists(select 1 from b9 where  (blist & b9.b) =0))
limit 100;

时间：2108.833 ms (00:02.109)

但全部计数的结果是错的
with  RECURSIVE t6(n) as (select 1 union all select n+1 from t where n<6)
,
b3(a,b,c,bit)as(select a.n,b.n,c.n,(1<<(a.n-1))+(1<<(b.n-1))+(1<<(c.n-1))::bigint from t6 a,t6 b,t6 c where a.n<b.n and b.n<c.n)
,
b9(b)as(select c.bit*((1<<(r.a-1)*6)+(1<<(r.b-1)*6)+(1<<(r.c-1)*6)) from b3 c,b3 r)
,
t(n,c,x,y)
as(select 1,cast(1 as varchar),1,1 union all select n+1,cast(n+1 as varchar),n/6+1,n%6+1 from t where n<6*6)
,
s(lv,n,nlist,blist,px,py)
as(select 1,t.n,t.c,1<<(t.n-1),pow(10,t.x),pow(10,t.y) from t where t.n<=6
union all
select lv+1,b.n,nlist||','||c,blist+(1<<(b.n-1)),px+pow(10,b.x),py+pow(10,b.y)
from s,t b
where lv<10 and s.n<b.n
--and(blist%19<16)
and (position('3' in (px+pow(10,b.x))::varchar)=0 and position('3' in (py+pow(10,b.y))::varchar)=0)
--and(select max(sum(case when a.x=b.x then 1 end), sum(case when a.y=b.y then 1 end))from t a
--  where ((blist+(1<<(b.n-1))&(1<<(a.n-1)))>0))<=2
and (b.n  between lv/2*6+1 and lv/2*6+6*2)
)
select count(*) from s where lv=10 and (lv<3 or not exists(select 1 from b9 where  (blist & b9.b) =0))
;

count
--------
138384
(1 行记录)

时间：147927.202 ms (02:27.927)

把blist类型改成bigint，结果也一样

〇〇 · 发表于 2021-10-18 09:11

本帖最后由〇〇于 2021-10-18 09:16 编辑

newkid的代码在同一个机器的VMware虚机win11的oracle 21c
SQL*Plus: Release 21.0.0.0.0 - Production on 星期四 10月 14 16:44:56 2021
Version 21.3.0.0.0

Copyright (c) 1982, 2021, Oracle.  All rights reserved.

请输入用户名:  / as sysdba

连接到:
Oracle Database 21c Enterprise Edition Release 21.0.0.0.0 - Production
Version 21.3.0.0.0

SQL> show sga

Total System Global Area 2583687296 bytes
Fixed Size                9859200 bytes
Variable Size          637534208 bytes
Database Buffers       1929379840 bytes
Redo Buffers             6914048 bytes
SQL> set timi on
60  select all_rows from r6
61  where not exists (select 1 from bitmap where bitand(bitmap.bit,r6.b)=0) -------- 和400个掩码的按位与结果都不为零
62  and rownum<=100;
已选择 100 行。

已用时间:  00: 00: 00.59

60  select count(all_rows) from r6
61  where not exists (select 1 from bitmap where bitand(bitmap.bit,r6.b)=0) -------- 和400个掩码的按位与结果都不为零
62  ;

COUNT(ALL_ROWS)
---------------
      32400

已用时间:  00: 02: 17.13

〇〇 · 发表于 2021-10-18 10:12

本帖最后由〇〇于 2021-10-18 10:43 编辑

〇〇发表于 2021-10-18 09:04
将最后一个改成postgres的语法D:\pgsql140\bin>psql -d testpsql (14.0)输入 "help" 来获取帮助信息.test=# ...

sqlite的结果是对的，应该是postgresql数据溢出的问题
sqlite> create table chess6 as
...> with t6(n) as (select 1 union all select n+1 from t where n<6)
...> ,
...> b3(a,b,c,bit)as(select a.n,b.n,c.n,(1<<(a.n-1))+(1<<(b.n-1))+(1<<(c.n-1)) from t6 a,t6 b,t6 c where a.n<b.n and b.n<c.n)
...> ,
...> b9(b)as(select c.bit*((1<<(r.a-1)*6)+(1<<(r.b-1)*6)+(1<<(r.c-1)*6)) from b3 c,b3 r)
...> ,
...> t(n,c,x,y)
...> as(select 1,'1',1,1 union all select n+1,cast(n+1 as varchar),n/6+1,n%6+1 from t where n<6*6)
...> ,
...> s(lv,n,nlist,blist,px,py)
...> as(select 1,t.n,t.c,1<<(t.n-1),pow(10,t.x),pow(10,t.y) from t where t.n<=6
...> union all
...> select lv+1,b.n,nlist||','||c,blist+(1<<(b.n-1)),px+pow(10,b.x),py+pow(10,b.y)
...> from s,t b
...> where lv<10 and s.n<b.n
...> --and(blist%19<14)
...> and (instr(px+pow(10,b.x),3)=0 and instr(py+pow(10,b.y),3)=0)
...> --and(select max(sum(case when a.x=b.x then 1 end), sum(case when a.y=b.y then 1 end))from t a
...> --  where ((blist+(1<<(b.n-1))&(1<<(a.n-1)))>0))<=2
...> and b.n  between lv/2*6+1 and lv/2*6+6*2
...> )
...> select * from s where lv=10 and (lv<3 or not exists(select 1 from b9 where  (blist & b9.b) =0))
...> ;
Run Time: real 537.988 user 535.660634 sys 1.965613
sqlite> select count(*) from chess6;
32400
Run Time: real 0.000 user 0.000000 sys 0.000000
pypy3的sqlite快不少

import time

import sqlite3
con=sqlite3.connect(':memory:')
cur=con.cursor()

t=time.time()
for row in cur.execute('''
create table chess6 as
with t6(n) as (select 1 union all select n+1 from t where n<6)
,
b3(a,b,c,bit)as(select a.n,b.n,c.n,(1<<(a.n-1))+(1<<(b.n-1))+(1<<(c.n-1)) from t6 a,t6 b,t6 c where a.n<b.n and b.n<c.n)
,
b9(b)as(select c.bit*((1<<(r.a-1)*6)+(1<<(r.b-1)*6)+(1<<(r.c-1)*6)) from b3 c,b3 r)
,
t(n,c,x,y)
as(select 1,'1',1,1 union all select n+1,cast(n+1 as varchar),n/6+1,n%6+1 from t where n<6*6)
,
s(lv,n,nlist,blist,px,py)
as(select 1,t.n,t.c,1<<(t.n-1),pow(10,t.x),pow(10,t.y) from t where t.n<=6
union all
select lv+1,b.n,nlist||','||c,blist+(1<<(b.n-1)),px+pow(10,b.x),py+pow(10,b.y)
from s,t b
where lv<10 and s.n<b.n
--and(blist%19<14)
and (instr(px+pow(10,b.x),3)=0 and instr(py+pow(10,b.y),3)=0)
--and(select max(sum(case when a.x=b.x then 1 end), sum(case when a.y=b.y then 1 end))from t a
--  where ((blist+(1<<(b.n-1))&(1<<(a.n-1)))>0))<=2
and b.n  between lv/2*6+1 and lv/2*6+6*2
)
select * from s where lv=10 and (lv<3 or not exists(select 1 from b9 where  (blist & b9.b) =0))
'''):
  print(row)

print(time.time()-t)

395.96064710617065

>>>> for row in cur.execute('''
.... select count(*) from chess6
.... '''):
.... print(row)
....
(32400,)

在postgresql把1<<替换成1::bigint<<就对了

create table chess6a as
with  RECURSIVE t6(n) as (select 1 union all select n+1 from t where n<6)
,
b3(a,b,c,bit)as(select a.n,b.n,c.n,(1::bigint<<(a.n-1))+(1::bigint<<(b.n-1))+(1::bigint<<(c.n-1)) from t6 a,t6 b,t6 c where a.n<b.n and b.n<c.n)
,
b9(b)as(select c.bit*((1::bigint<<(r.a-1)*6)+(1::bigint<<(r.b-1)*6)+(1::bigint<<(r.c-1)*6)) from b3 c,b3 r)
,
t(n,c,x,y)
as(select 1,cast(1 as varchar),1,1 union all select n+1,cast(n+1 as varchar),n/6+1,n%6+1 from t where n<6*6)
,
s(lv,n,nlist,blist,px,py)
as(select 1,t.n,t.c,1::bigint<<(t.n-1),pow(10,t.x),pow(10,t.y) from t where t.n<=6
union all
select lv+1,b.n,nlist||','||c,blist+(1::bigint<<(b.n-1)),px+pow(10,b.x),py+pow(10,b.y)
from s,t b
where lv<10 and s.n<b.n
--and(blist%19<16)
and (position('3' in (px+pow(10,b.x))::varchar)=0 and position('3' in (py+pow(10,b.y))::varchar)=0)
--and(select max(sum(case when a.x=b.x then 1 end), sum(case when a.y=b.y then 1 end))from t a
--  where ((blist+(1::bigint<<(b.n-1))&(1::bigint<<(a.n-1)))>0))<=2
and (b.n  between lv/2*6+1 and lv/2*6+6*2)
)
select * from s where lv=10 and not exists(select 1 from b9 where  (blist & b9.b) =0)
;

SELECT 32400
时间：158262.389 ms (02:38.262)

〇〇 · 发表于 2021-10-18 10:40

本帖最后由〇〇于 2021-10-18 13:33 编辑

如果中间有空行的放置，一定不是最后的解，要是能加这个限制，结果还会好？
测试了，快了一点点
用x64编译源代码，D:\sqlite_src>cl shell.c sqlite3.c -Fesqlite36.exe -O2 -DSQLITE_ENABLE_MATH_FUNCTIONS
用于 x64 的 Microsoft (R) C/C++ 优化编译器 19.10.25017 版
版权所有(C) Microsoft Corporation。保留所有权利。

shell.c
shell.c(19802): warning C4819: 该文件包含不能在当前代码页(0)中表示的字符。请将该文件保存为 Unicode 格式以防止数据丢失
shell.c(19815): warning C4819: 该文件包含不能在当前代码页(0)中表示的字符。请将该文件保存为 Unicode 格式以防止数据丢失
sqlite3.c
正在生成代码...
Microsoft (R) Incremental Linker Version 14.10.25017.0
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:sqlite36.exe
shell.obj
sqlite3.obj

或者
D:\mingw32\bin>gcc D:\sqlite_src\shell.c D:\sqlite_src\sqlite3.c -lpthread  -lm -o D:\sqlite_src\a.exe -DSQLITE_ENABLE_MATH_FUNCTIONS -O2

exe比pypy3快了

create table chess6a as
with t6(n) as (select 1 union all select n+1 from t where n<6)
,
b3(a,b,c,bit)as(select a.n,b.n,c.n,(1<<(a.n-1))+(1<<(b.n-1))+(1<<(c.n-1)) from t6 a,t6 b,t6 c where a.n<b.n and b.n<c.n)
,
b9(b)as(select c.bit*((1<<(r.a-1)*6)+(1<<(r.b-1)*6)+(1<<(r.c-1)*6)) from b3 c,b3 r)
,
t(n,c,x,y)
as(select 1,'1',1,1 union all select n+1,cast(n+1 as varchar),n/6+1,n%6+1 from t where n<6*6)
,
s(lv,n,nlist,blist,px,py)
as(select 1,t.n,t.c,1<<(t.n-1),pow(10,t.x),pow(10,t.y) from t where t.n<=6
union all
select lv+1,b.n,nlist||','||c,blist+(1<<(b.n-1)),px+pow(10,b.x),py+pow(10,b.y)
from s,t b
where lv<10 and s.n<b.n and b.x- (s.n/6+1)< 2
--and(blist%19<14)
and (instr(px+pow(10,b.x),3)=0 and instr(py+pow(10,b.y),3)=0)
--and(select max(sum(case when a.x=b.x then 1 end), sum(case when a.y=b.y then 1 end))from t a
--  where ((blist+(1<<(b.n-1))&(1<<(a.n-1)))>0))<=2
and b.n  between lv/2*6+1 and lv/2*6+6*2
)
select * from s where lv=10 and (lv<3 or not exists(select 1 from b9 where  (blist & b9.b) =0))
;

Run Time: real 310.432 user 309.053581 sys 1.326008
sqlite> select count(*) from chess6a;
32400
Run Time: real 0.001 user 0.000000 sys 0.000000

原始的
Run Time: real 333.610 user 331.767327 sys 1.762811
sqlite> select count(*) from chess6;
32400
Run Time: real 0.000 user 0.000000 sys 0.000000

solomon_007 · 发表于 2021-10-18 22:32

〇〇发表于 2021-10-18 09:11
newkid的代码在同一个机器的VMware虚机win11的oracle 21cSQL*Plus: Release 21.0.0.0.0 - Production on 星 ...

OO，ORACLE 版本的，你发个完整版吧，sqlite/postgres 都没有环境

〇〇 · 发表于 2021-10-19 06:28

sqlite/postgres比oracle 小很多，我在本版提供了绿色版

[每日一题] puzzleup 2021

浏览过的版块