Home » Other » General » Puzzle
Puzzle Thu, 23 July 2009 08:26
 sasnrock Messages: 19Registered: August 2007 Junior Member
hello guys. I've attended an interview in microsoft and they gave me a problem infact a puzzle to be solved in 1hr. And code in any language u wish.

I used pl/sql which is the only one I know )

Well ...here it goes

There are n number of persons standing in a circle. 1st person will have a gun. Now he kills a person in standing in his ACW direction and gives the gun next to him and this continues till only one is remaining.

for example if there are 5 people standing in a circle (say 1 to 5), 1kills 5 and gives gun to 4. 4 kills 3 and gives gun to 2. 2 kills 1 and gives it to 4. now 4 kills 2 and he is the one remaining. So we need to code such that we can find the one who is alive if we give n.

--- I'll post my code after 2 days. Meanwhile try for fun.

Re: Puzzle [message #414795 is a reply to message #414794] Thu, 23 July 2009 08:31
 Michel Cadot Messages: 68165Registered: March 2007 Location: Nanterre, France, http://... Senior MemberAccount Moderator
If you don't explain how is this an Oracle question, the topic will be locked.

Regards
Michel
Re: Puzzle [message #414796 is a reply to message #414795] Thu, 23 July 2009 08:38
 sasnrock Messages: 19Registered: August 2007 Junior Member
hi michel,

its not really a question in oracle. however my point is how u do this in oracle.
i've seen some earlier posts from people requesting for some things to try their skills in oracle. So I thought this would be better to try.
however, if u think its inappropriate, then you can lock it. sorry
Re: Puzzle [message #414802 is a reply to message #414796] Thu, 23 July 2009 09:31
 Michel Cadot Messages: 68165Registered: March 2007 Location: Nanterre, France, http://... Senior MemberAccount Moderator
OK, first exercise for YOU, explain it with Oracle words that is table, columns, rows...

Regards
Michel
Re: Puzzle [message #414806 is a reply to message #414802] Thu, 23 July 2009 09:43
 Frank Messages: 7892Registered: March 2000 Senior Member
There, moved it to the general forum
No need to provide tables, data etc.
Re: Puzzle [message #414826 is a reply to message #414794] Thu, 23 July 2009 12:56
 joy_division Messages: 4961Registered: February 2005 Location: East Coast USA Senior Member
 sasnrock wrote on Thu, 23 July 2009 09:26 Now he kills a person in standing in his ACW direction and gives the gun next to him...

What is ACW?

I personally like puzzle questions.

It also seems that Microsoft is planning some devious actions to take out some of their competition and getting others to plan it out for them.
Re: Puzzle [message #414834 is a reply to message #414794] Thu, 23 July 2009 13:58
 BlackSwan Messages: 26766Registered: January 2009 Location: SoCal Senior Member
>What is ACW?
Just guessing - anti-clock wise?

So what direction is clockwise on a digital timepiece?
Re: Puzzle [message #414836 is a reply to message #414834] Thu, 23 July 2009 14:18
 ThomasG Messages: 3211Registered: April 2005 Location: Heilbronn, Germany Senior Member
Interesting problem. Basically some sort of wrap-around analytical with a twist. ;-P

Here is my solution :

```SQL> set serverout on;

SQL> CREATE TABLE persons ( person NUMBER (10));

Table created.

SQL>
SQL> INSERT INTO persons
2  (SELECT rownum FROM dual CONNECT BY LEVEL <= 5);

5 rows created.

SQL>
SQL> SELECT * FROM persons;
PERSON
----------
1
2
3
4
5
SQL>
SQL> DECLARE
2    v_shooter       NUMBER:= 1;
3    v_killed        NUMBER;
4    v_next_shooter  NUMBER;
5  BEGIN
6
7    LOOP
8      SELECT shot    , NextShooter
9        INTO v_killed, v_next_shooter
10      FROM (
11        SELECT person,
12               Shooter,
13               Shot,
14               Nvl(Lag(shot) over (ORDER BY shot),
15                   Max(shot) over () )             NextShooter
16          FROM (
17            SELECT person,
18                   Decode(person, v_shooter,'Yes','No')      shooter,
19                   Nvl( Lag(person) over (ORDER BY person),
20                        (SELECT Max(person) FROM persons))   Shot
21                   FROM  persons)
22      )
23      WHERE Shooter = 'Yes';
24
25      IF (v_shooter != v_killed) THEN
26          Dbms_Output.put_line('Now ' || v_shooter || ' kills ' || v_killed);
27      ELSE
28          Dbms_Output.put_line('Last Man Standing ' || v_killed);
29          EXIT;
30      END IF;
31
32      DELETE FROM persons WHERE person = v_killed;
33
34      v_shooter := v_next_shooter;
35
36    END LOOP;
37
38  END;
39  /

Now 1 kills 5
Now 4 kills 3
Now 2 kills 1
Now 4 kills 2
Last Man Standing 4

PL/SQL procedure successfully completed.

SQL>
SQL>
SQL> DROP TABLE persons;
```

I basically decided to "kill them" by deleting them from the table, but I wonder If someone will pull some analytical-SQL-Only solution out of his sleeve.
Re: Puzzle [message #414851 is a reply to message #414826] Thu, 23 July 2009 16:03
 sasnrock Messages: 19Registered: August 2007 Junior Member
ACW - Anti clock wise
Re: Puzzle [message #414865 is a reply to message #414794] Thu, 23 July 2009 20:33
 BlackSwan Messages: 26766Registered: January 2009 Location: SoCal Senior Member
no explicit LOOP

```SQL> @lms
SQL> set serverout on;
SQL> DROP TABLE PERSONS;

Table dropped.

SQL> CREATE TABLE persons ( person NUMBER (10));

Table created.

SQL> INSERT INTO persons (SELECT rownum FROM dual CONNECT BY LEVEL <= 6);

6 rows created.

SQL> create or replace procedure recurse_dead(shooter IN number)
2  as
3  shot number;
4  REMCNT number;
5  PISTOL NUMBER;
6  begin
7  	DBMS_OUTPUT.ENABLE(100000);
8  	SELECT count(*) INTO REMCNT from persons;
9  	IF ( REMCNT > 1 )
10  	THEN
11  	   SELECT MAX(PERSON) INTO SHOT FROM PERSONS WHERE PERSON <> SHOOTER;
12  	   DBMS_OUTPUT.PUT_LINE('SHOOTER - ' || SHOOTER || ' SHOT - ' || SHOT);
13  	   DELETE FROM PERSONS WHERE PERSON = SHOT;
14  	   COMMIT;
15  	   SELECT count(*) INTO REMCNT from persons;
16  	   IF ( REMCNT > 1 )
17  	   THEN
18  	      SELECT MAX(PERSON) INTO PISTOL  FROM PERSONS WHERE PERSON <> SHOOTER;
20  	   ELSE
21  	      DBMS_OUTPUT.PUT_LINE('Last man standing is ' || SHOOTER);
22  	   END IF;
23  	ELSE
24  	   DBMS_OUTPUT.PUT_LINE('Last man standing is ' || SHOOTER);
25  	END IF;
27  /

Procedure created.

SHOOTER - 1 SHOT - 6
SHOOTER - 5 SHOT - 4
SHOOTER - 3 SHOT - 5
SHOOTER - 2 SHOT - 3
SHOOTER - 1 SHOT - 2
Last man standing is 1

PL/SQL procedure successfully completed.
```
Re: Puzzle [message #414894 is a reply to message #414865] Thu, 23 July 2009 23:47
 Frank Messages: 7892Registered: March 2000 Senior Member
 BlackSwan wrote on Fri, 24 July 2009 03:33 SQL> exec recurse_dead(1); SHOOTER - 1 SHOT - 6 SHOOTER - 5 SHOT - 4 SHOOTER - 3 SHOT - 5 SHOOTER - 2 SHOT - 3 SHOOTER - 1 SHOT - 2 Last man standing is 1 PL/SQL procedure successfully completed. [/code]

Nope, row 3: 3 shot 2, not 5
Re: Puzzle [message #414897 is a reply to message #414894] Thu, 23 July 2009 23:50
 Frank Messages: 7892Registered: March 2000 Senior Member
I think there's a structured outcome:

For a group of n people:
Find the largest x where 2^x + 1 < n
outcome is 2^x - (n - 2^x + 1)

I leave it to the math-people here to translate this to an algorithm
Re: Puzzle [message #415168 is a reply to message #414794] Sat, 25 July 2009 10:57
 Michel Cadot Messages: 68165Registered: March 2007 Location: Nanterre, France, http://... Senior MemberAccount Moderator
Here's a "pure" SQL solution. I used names instead of numbers, the initial gives the rank in the wheel of the fortune (you can get the numbers replacing "killer" by "ikiller" and "dead" by "idead").
```SQL> col res format a40 heading "Steps"
SQL> def N=5
SQL> with
2    humans as (
3                select 1 num,  'Abel'      human from dual
4      union all select 2 num,  'Bethany'   human from dual
5      union all select 3 num,  'Cain'      human from dual
6      union all select 4 num,  'Deborah'   human from dual
7      union all select 5 num,  'Esther'    human from dual
8      union all select 6 num,  'Felix'     human from dual
9      union all select 7 num,  'Gideon'    human from dual
10      union all select 8 num,  'Hillel'    human from dual
11      union all select 9 num,  'Isaiah'    human from dual
12      union all select 10 num, 'Jacob'     human from dual
13      union all select 11 num, 'Kolariah'  human from dual
14      union all select 12 num, 'Levi'      human from dual
15      union all select 13 num, 'Michaiah'  human from dual
16      union all select 14 num, 'Nathanael' human from dual
17      union all select 15 num, 'Ozias'     human from dual
18      union all select 16 num, 'Philemon'  human from dual
19      union all select 17 num, 'Quincy'    human from dual
20      union all select 18 num, 'Rebekah'   human from dual
21      union all select 19 num, 'Sarah'     human from dual
22      union all select 20 num, 'Thomas'    human from dual
23      union all select 21 num, 'Uriah'     human from dual
24      union all select 22 num, 'Vaniah'    human from dual
25      union all select 23 num, 'Wendy'     human from dual
26      union all select 24 num, 'Xena'      human from dual
27      union all select 25 num, 'Yanael'    human from dual
28      union all select 26 num, 'Zuriel'    human from dual
29    )
30  select decode(step,
31                &N, 'Last Person Standing: '||killer,
32                'Now '||killer||' kills '||dead) res
33  -- , debug
34  from ( select level rn, level step, 'N' killed from dual connect by level <= &N )
35  model
36    reference humans on ( select * from humans ) dimension by (num) measures (human)
37    dimension by (rn)
38    measures (step, killed,
39              cast(null as varchar2(20)) killer, cast(null as varchar2(20)) dead,
40              cast(null as number) ikiller, cast(null as number) idead,
41              cast(null as number) prev_killer
42  -- , cast(null as varchar2(50)) debug
43             )
44    rules upsert all sequential order iterate (&N) (
45  -- debug[iteration_number+1]='kd='||wm_concat(killed)[rn between 1 and &N],
46      -- Calculate new killer, first one (iteration 0) is number 1
47      ikiller[iteration_number+1] =
48        decode(iteration_number,
49               0, 1,
50               mod(max(decode(killed,'N',mod(step-nvl(prev_killer,0)+&N,&N)))[rn between 1 and &N]
51                    + nvl(prev_killer[1],0),&N)
52              ),
53      -- Grab new killer name
54      killer[iteration_number+1] = humans.human[ikiller[iteration_number+1]],
55  -- debug[iteration_number+1]=debug[iteration_number+1]||' pk='||prev_killer[1]||' k='||ikiller[iteration_number+1]||'/'||killer[iteration_number+1],
56      -- Set previous killer as new killer
57      prev_killer[rn between 1 and &N] = ikiller[iteration_number+1],
58  -- debug[iteration_number+1]=debug[iteration_number+1]||' pk2='||prev_killer[1],
59      -- Calculate new killed (dead), first one (iteration 0) is last number
61        decode(iteration_number,
62               0, &N,
63               mod(max(decode(killed,'N',mod(step-prev_killer+&N,&N)))[rn between 1 and &N]
64                    + prev_killer[1], &N)
65              ),
66      -- Grab new dead human name
69      -- Flag human as killed
71    )
72  order by step
73  /
Steps
----------------------------------------
Now Abel kills Esther
Now Deborah kills Cain
Now Bethany kills Abel
Now Deborah kills Bethany
Last Person Standing: Deborah

5 rows selected.

SQL> def N=6
SQL> /
Steps
----------------------------------------
Now Abel kills Felix
Now Esther kills Deborah
Now Cain kills Bethany
Now Abel kills Esther
Now Cain kills Abel
Last Person Standing: Cain

6 rows selected.```

Sorry for long lines, I keep them to allow you to see how it works uncommenting "debug" lines.

Regards
Michel
 Previous Topic: Oracle profiler Next Topic: Releasing Row Level Locks Manually
Goto Forum:

Current Time: Mon May 16 22:32:30 CDT 2022