PUZZLEUP 2015

newkid · 发表于 2015-10-30 10:26

lugionline 发表于 2015-10-30 10:03
这题用A*会快很多，不过我也没有用A*，用逐步推进大概20秒

你来写代码，我负责翻译成ORACLE。

newkid · 发表于 2015-10-30 23:01

本帖最后由 newkid 于 2015-11-1 03:37 编辑

算法来自这里：
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

1  function Dijkstra(Graph, source):
2
3    create vertex set Q
4
5    for each vertex v in Graph:          // Initialization
6       dist[v] ← INFINITY                // Unknown distance from source to v
7       prev[v] ← UNDEFINED                // Previous node in optimal path from source
8       add v to Q                         // All nodes initially in Q (unvisited nodes)
9
10    dist[source] ← 0                      // Distance from source to source
11
12    while Q is not empty:
13       u ← vertex in Q with min dist[ u ] // Source node will be selected first
14       remove u from Q
15
16       for each neighbor v of u:          // where v is still in Q.
17             alt ← dist[ u ] + length(u, v)
18             if alt < dist[v]:             // A shorter path to v has been found
19                dist[v] ← alt
20                prev[v] ← u
21
22    return dist[], prev[]

下面是PL/SQL版本。这里面比较有趣的是用规则表达式找出所有变化；此外从剩余节点中取出距离最小的点是利用了关联数组的自动排序。

DECLARE
TYPE pawn_num IS TABLE OF NUMBER INDEX BY VARCHAR2(40);
TYPE pawn_str IS TABLE OF VARCHAR2(40) INDEX BY VARCHAR2(40);
dist pawn_num;
Q pawn_num;
prev_str pawn_str;

TYPE neighbour IS TABLE OF VARCHAR2(40) INDEX BY PLS_INTEGER;
TYPE neighbour2 IS TABLE OF neighbour INDEX BY VARCHAR2(40);
v_next neighbour2;

u VARCHAR2(40);
v VARCHAR2(40);
alt NUMBER;
d NUMBER;
v_n NUMBER:=18;
v_m NUMBER:=9;
v_start VARCHAR2(40) :=RPAD(LPAD('1',v_m,'1'),v_n,'0');
v_end VARCHAR2(40) :=LPAD(LPAD('1',v_m,'1'),v_n,'0');
i NUMBER;
cnt NUMBER;
v_empty neighbour;
v_str VARCHAR2(40);
infinity NUMBER := 10;  ---- 无穷大距离，设为 10^10
BEGIN
FOR lv_rec IN (
      WITH b AS (SELECT POWER(10,LEVEL-1) b FROM DUAL CONNECT BY LEVEL<=v_n)
      ,t(lvl,bits,last_b) AS (
      SELECT 1,b,b FROM b
      UNION ALL
      SELECT lvl+1,t.bits+b.b,b.b
      FROM t,b
      WHERE lvl<v_m AND t.last_b<b.b
      )
      SELECT LPAD(bits,v_n,'0') as str
      FROM t
      WHERE lvl=v_m
)
LOOP
      IF lv_rec.str=v_start THEN
         dist(lv_rec.str):=0;
      ELSE
         dist(lv_rec.str):=POWER(10,infinity);
      END IF;
      Q(LPAD(dist(lv_rec.str),infinity)||lv_rec.str):=1;
      v_next(lv_rec.str) := v_empty;
      cnt :=0;
      LOOP ----找出所有移动的变化
         cnt := cnt+1;
         i := INSTR(lv_rec.str,'10',1,cnt);
         EXIT WHEN i=0;
         v_next(lv_rec.str)(v_next(lv_rec.str).COUNT+1):= REGEXP_REPLACE(lv_rec.str,'10','01',1,cnt) ; ---- 向左移动一格：10变成01
      END LOOP;

      cnt :=0;
      LOOP ----找出所有跳跃的变化
         cnt := cnt+1;
         v_str:=REGEXP_SUBSTR(lv_rec.str,'1(10)+',1,cnt);
         EXIT WHEN v_str IS NULL;
         v_next(lv_rec.str)(v_next(lv_rec.str).COUNT+1):= REGEXP_REPLACE(lv_rec.str,'1(10)+','0'||SUBSTR(v_str,2,LENGTH(v_str)-2)||'1',1,cnt) ; --- 跳跃：1101010...10 变成 0101010...11
      END LOOP;

END LOOP;

---- 以下为Dijkstra算法
WHILE Q.COUNT>0 LOOP
      u := Q.FIRST; ----- 取出距离最小的点，利用关联数组的自动排序
      Q.DELETE(u);
      u := SUBSTR(u,infinity+1);
      d := dist(u);
      IF U=v_end THEN
         EXIT;
      END IF;
      FOR i IN 1..v_next(u).count LOOP
            v := v_next(u)(i);
            alt := dist(u) + 1;
            IF alt < dist(v) THEN
               Q.DELETE(LPAD(dist(v),infinity)||v);
               dist(v) := alt;
               Q(LPAD(dist(v),infinity)||v):=1;
               prev_str(v):=u;
            END IF;
      END LOOP;
END LOOP;

DBMS_OUTPUT.PUT_LINE('dist='||dist(v_end));

v_str := v_end;
LOOP
      DBMS_OUTPUT.PUT_LINE(v_str);
      EXIT WHEN NOT prev_str.EXISTS(v_str);
      v_str := prev_str(v_str);
END LOOP;

END;
/

从答案可看出其移动类似毛毛虫，先尽量伸长，变成松散的101010...形状，然后从尾部往前凑。

solomon_007 · 发表于 2015-10-31 21:17

#14

--这里先给出棋盘长度为6的情况:
--我的解法:-----------------------------------------------------------------------------------------------------
create or replace function fn_one_step(p_str in varchar2) --这个是节点走一步,输出所有的邻居节点
return t_str pipelined
is
  j int:=0;
  l_cnt int:=0;
begin
  for i in 1..length(p_str) loop
if substr(p_str,i,1)=1 and i<length(p_str) then
   if substr(p_str,i+1,1) = 0 then
      pipe row(substr(p_str,1,i-1)||'01'||substr(p_str,i+2));
   else
      if substr(p_str,i+2,1) = 0 then

      --从第i+1开始,判断后面连续出现的'10'的个数
      j:=i+1;
      loop
         exit when j>length(p_str);

         if substr(p_str,j,2)='10' then
            l_cnt := l_cnt +1;
         else
            exit;
         end if;

         j:=j+2;
      end loop;

      pipe row(substr(p_str,1,i-1)||'0'
               ||replace(rpad('$',(l_cnt-1)*2+1,'10'),'$')
               ||'11'
               ||substr(p_str,i+l_cnt*2+1));
      end if;
   end if;
end if;
  end loop;
  return;
end;

with t as (select level-1 n from dual connect by level <=2),
   s(lvl,str) as ( select 1 lvl,
                        cast(n as varchar2(6)) str
                     from t
                  union all
                  select s.lvl+1,
                        s.str||t.n
                     from s,t
                  where lvl<6),
   r as ( select str
            from s
         where lvl=6
            and regexp_count(str,'1',1)=3),
   p as (
         select r.str,
               sub.column_value as sub_str
            from r,table(fn_one_step(r.str)) sub)
select substr(sys_connect_by_path(str,',')||','||sub_str,2) as res
  from p
where sub_str='000111'
and level = (select min(level)
               from p
               where sub_str='000111'
               start with str='111000'
            connect by prior sub_str = str)
  and rownum =1
start with str='111000'
connect by prior sub_str = str;

SQL> with t as (select level-1 n from dual connect by level <=2),
  2    s(lvl,str) as ( select 1 lvl,
  3                            cast(n as varchar2(6)) str
  4                      from t
  5                      union all
  6                      select s.lvl+1,
  7                            s.str||t.n
  8                      from s,t
  9                      where lvl<6),
10    r as ( select str
11             from s
12             where lvl=6
13                and regexp_count(str,'1',1)=3),
14    p as (
15             select r.str,
16                   sub.column_value as sub_str
17             from r,table(fn_one_step(r.str)) sub)
18  select substr(sys_connect_by_path(str,',')||','||sub_str,2) as res
19 from p
20 where sub_str='000111'
21    and level = (select min(level)
22                   from p
23                where sub_str='000111'
24                start with str='111000'
25                connect by prior sub_str = str)
26 and rownum =1
27 start with str='111000'
28  connect by prior sub_str = str;
RES
--------------------------------------------------------------------------------
111000,101100,011100,011010,001011,000111

solomon_007 · 发表于 2015-10-31 21:37

我的写法太垃圾了, N=10就算不出来了,路径太多;

还是得按 NEWKID说的用 Dijkstra 算法

lugionline · 发表于 2015-10-31 22:46

本帖最后由 lugionline 于 2015-11-1 08:45 编辑

不写A*

，采用逐级推进的办法依次算出1步，2步，3步 ... 可以到达的节点，我觉得SQL应当也可行
A* 要计算的点数不会比这个更少

改了下删除了重复记录，这下又和已开始一样快了

这次的代码有点长，要表达跳这个事情有点困难，想不出好的办法

newkid · 发表于 2015-11-1 03:42

SQL算出所有能到达的点是没问题的。但是C(20,10)是一个很大的数字，里面还有很多重复的路径，SQL没法及时丢弃那些不够优化的路径，PL/SQL可以做到。
能不能把这个事情分两步，先证明M-1步一定能到达，然后证明不存在更少步骤的答案？

newkid · 发表于 2015-11-1 07:36

模拟爬行的程序是很好写的：

declare
v_n NUMBER:=20;
v_m NUMBER:=10;

v_start VARCHAR2(40) :=RPAD(LPAD('1',v_m,'1'),v_n,'0');
v_end VARCHAR2(40) :=LPAD(LPAD('1',v_m,'1'),v_n,'0');
v_str VARCHAR2(40) := v_start;

v_cnt NUMBER :=0;
v_substr VARCHAR2(40) ;
BEGIN

WHILE v_str<>v_end LOOP
      v_cnt := v_cnt+1;
      IF SUBSTR(v_str,-1,1)='0' AND RTRIM(v_str,'0') LIKE '%1011' THEN
         v_str := RTRIM(v_str,'0');
         v_str := RPAD(SUBSTR(v_str,1,LENGTH(v_str)-1)||'01',v_n,'0');
      ELSIF LTRIM(v_str,'0') LIKE '10%' THEN
         v_str := LTRIM(v_str,'0');
         v_str := LPAD('01'||SUBSTR(v_str,3),v_n,'0');
      ELSE
         v_substr:=REGEXP_SUBSTR(v_str,'1(10)+');
         v_str := REGEXP_REPLACE(v_str,'1(10)+','0'||SUBSTR(v_substr,2,LENGTH(v_substr)-2)||'1',1,1); --- 跳跃：1101010...10 变成 0101010...11
      END IF;
      DBMS_OUTPUT.PUT_LINE(v_cnt||':'||v_str);
END LOOP;

END;
/

1:11111111011000000000
2:11111111010100000000
3:11111101010110000000
4:11111101010101000000
5:11110101010101100000
6:11110101010101010000
7:11010101010101011000
8:11010101010101010100
9:01010101010101010110
10:01010101010101010101
11:00110101010101010101
12:00010101010101010111
13:00001101010101010111
14:00000101010101011111
15:00000011010101011111
16:00000001010101111111
17:00000000110101111111
18:00000000010111111111
19:00000000001111111111

要归纳出步骤数为M-1似乎也不难。

lugionline · 发表于 2015-11-1 09:04

本帖最后由 lugionline 于 2015-11-1 10:41 编辑

newkid 发表于 2015-11-1 07:36
模拟爬行的程序是很好写的：

declare

你用正则表达式来找 1010 模式真的很方便，但慢可能也就慢在这一块，如果用c来算，也就是几个bit 操作，C(20, 10) 真心不多，才20万

newkid · 发表于 2015-11-5 00:58

#15 HANDS OF A CLOCK

How many times at least two of the three hands (hour, minute, second) of a clock exactly overlap between 10:30 and 22:30?

Note: All hands move in a continuous motion with no discrete jumps.

在10:30和22:30之间，一个钟的三个指针（时，分，秒）至少有两个重叠的次数是多少？

注：所有的指针都是连续移动，没有不连续的跳跃。

-----------------
这个应该不难, 可能有几个坑得注意一下，比如三针全部重叠的情况。

〇〇 · 发表于 2015-11-5 09:17

newkid 发表于 2015-11-5 00:58
#15 HANDS OF A CLOCK

How many times at least two of the three hands (hour, minute, second) of a c ...

12个小时，时分针重叠11次，秒针就不知道了

[每日一题] PUZZLEUP 2015