OraQA

The following is an interesting problem posted by Jsoftware:

With n people numbered 1 to n in a circle, every second one is eliminated until only one survives. Determine the elimination order and the survivor’s number.

—————————————–SQL Solution——————-

variable input_num  number
exec :input_num  := 10;
set timing on

SELECT trim(BOTH ','FROM regexp_replace(XMLAgg(XMLElement(X,
               CASE WHEN iteration IS NOT NULL THEN data END)
               ORDER BY rank),'<X>|</X><X>|</X>',',')) AS elimination_order,
              max(CASE WHEN iteration IS NULL THEN data END)
                      KEEP (DENSE_RANK LAST ORDER BY rank) survive_num
FROM
(SELECT row_number() OVER (ORDER BY iteration NULLS LAST, rn) rank,
                 data, iteration
 FROM
 (SELECT rn, data, iteration
   FROM
  (SELECT num, rn FROM
   (SELECT LEVEL num, LEVEL rn FROM dual CONNECT BY LEVEL <=:input_num)
  )
MODEL
DIMENSION BY (rn)
MEASURES
(num, num new_rank, CAST(NULL AS NUMBER) old_num,
 CAST(NULL AS VARCHAR2(1)) flag, num data,
 CAST(NULL AS NUMBER)  iteration, CAST(NULL AS NUMBER) cnt
)
 RULES ITERATE(1000) UNTIL (cnt[1] = 1)
( flag[ANY]     = CASE iteration_number
                                       WHEN 0 THEN 'T'
                                      ELSE flag[CV()] END,
  new_rank[ANY] = CASE WHEN flag[cv()] = 'T'
                                               THEN CASE WHEN mod(new_rank[cv()],2) = 1
                                                                      THEN ceil(new_rank[cv()]/2) END
                                               ELSE CASE WHEN mod(new_rank[cv()],2) = 0
                                                                      THEN ceil(new_rank[cv()]/2) END
                                    END,
  old_num[ANY] = CASE WHEN new_rank[cv()] IS NULL AND
                                                         num[cv()] IS NOT NULL
                                            THEN num[cv()] END,
  num[ANY]     = CASE WHEN new_rank[cv()] IS NOT NULL
                                         THEN num[cv()] END,
  flag[ANY]    =   CASE WHEN max(old_num)[ANY] > max(num)[ANY]
                                      THEN 'T'
                                     ELSE 'F' END,
  cnt[1]       = count(num)[ANY],
  iteration[ANY] = CASE WHEN old_num[cv()] IS NOT NULL
                                            THEN iteration_number
                                            ELSE iteration[cv()]
                                 END
      )
   )
 );
ELIMINATION_ORDER        SURVIVE_NUM
--------------------------        ------------
2,4,6,8,10,3,7,1,9                       5

Elapsed: 00:00:00.31

Filed under SQL. Follow any responses to this entry through this RSS 2.0 feed.