7
\$\begingroup\$

This question already has an answer here:

Ninja Assassins - which ninja stays alive

some basic information

  • given an int N as the number of ninjas, return the number of the winning ninja.
  • At the end only 1 ninja survives,the question is which one? what was his number?.
  • Each ninja kills the ninja who stands after him. Afterwards, he passes the sword to the first alive ninja who stood after the killed one.

Explenation - How the Game Works

The ninjas are numbered from 1 to N and stand in a circle according to the numbers. The circle goes clockwise: ninja 2 is left to ninja 1, ninja 3 is left to ninja 2, ninja 4 is left to ninja 3.... ninja 1 is left to ninja N.
Ninja 1 gets a sword and the game begins:
Each ninja (starting from ninja 1) kills the closest and alive ninja he has to the left (clockwise) . Afterwards, he passes the sword to the 2nd closest and alive ninja he has to the left.The 2nd ninja does the same (kills and passes) (as an example: N=3(we have 3 ninjas), ninja 1 kills ninja 2 and gives the sword to ninja 3. Ninja 3 has ninja 1 as his closest and alive ninja to the left(clockwise - its a circle) so he kills ninja 1, stays the last ninja alive and wins (so the output\return is 3, as the number of the ninja)).
A more detailed example below

Example - Word-detailed scenario

N = 7 (we got 7 ninjas) :

1 2 3 4 5 6 7 (L=alive, D=dead)
L D L L L L L The first ninja gets the sword and kills the 2nd ninja.
              The first ninja passes the sword to the 3rd ninja.
L D L D L L L The 3rd ninja gets the sword and kills the 4th ninja.
              The 3rd Ninja passes the sword to the 5th ninja.
L D L D L D L The 5th ninja gets the sword and kills the 6th ninja.
              The 5th Ninja passes the sword to the 7th ninja.
D D L D L D L The 7th ninja gets the sword and kills the first(1st) ninja.
              The 7th ninja passes the sword to the 3rd ninja.
D D L D D D L The 3rd ninja gets the sword and kills the 5th ninja.
              The 3rd ninja passes the sword to the 7th ninja.
D D D D D D L The 7th ninja gets the sword and kills the 3rd ninja,
              stays as the last one alive and wins (the final result /
              the output is 7).

More scenarios without words

N=3 : 1 2 3 - 1 3 - 3 wins
N=4 : 1 2 3 4 - 1 3 - 1 wins
N=5 : 1 2 3 4 5 - 1 3 5 - 3 5 - 3 wins
N=6 : 1 2 3 4 5 6 - 1 3 5 - 1 5 - 5 wins
N=7 : 1 2 3 4 5 6 7 - 1 3 5 7 - 3 7 - 7 wins




Scoring is based on the least number of bytes used, as this is a code-golf question.

\$\endgroup\$

marked as duplicate by Peter Taylor code-golf Jun 26 '16 at 7:08

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • \$\begingroup\$ can it be 0-indexed, i.e. ninja 1 becomes ninja 0, etc.? \$\endgroup\$ – Leaky Nun Jun 26 '16 at 0:50
  • 4
    \$\begingroup\$ This is the Josephus Problem with constant k=2. \$\endgroup\$ – Geobits Jun 26 '16 at 0:51
  • \$\begingroup\$ Obligatory OEIS A006257. \$\endgroup\$ – Leaky Nun Jun 26 '16 at 1:25
  • 1
    \$\begingroup\$ The tags code golf, code challenge, and fastest code are mutually exclusive. You can only have one win criterion. I'd suggest code golf. \$\endgroup\$ – xnor Jun 26 '16 at 1:26
8
\$\begingroup\$

Python 2, 30 bytes

lambda n:int(bin(n)[3:]+'1',2)

Takes the binary expansion of n and moves the initial 1 to the end.

\$\endgroup\$
  • 4
    \$\begingroup\$ That is witchcraft. \$\endgroup\$ – Leaky Nun Jun 26 '16 at 1:40
  • 1
    \$\begingroup\$ ಠ_ಠ what is this \$\endgroup\$ – downrep_nation Jun 26 '16 at 5:41
4
\$\begingroup\$

Python 2, 32 bytes

a=lambda n:n and(n%2+a(n/2))*2-1

33 bytes:

a=lambda n:n and 2*a(n/2)-(-1)**n

Uses the recursive formula on the OEIS page.

  • a(2*n) = 2*a(n)-1
  • a(2*n+1) = 2*a(n)+1
\$\endgroup\$
  • \$\begingroup\$ Why a=? Do you need it? \$\endgroup\$ – NoOneIsHere Jun 26 '16 at 5:07
  • \$\begingroup\$ @NoOneIsHere To recurse. \$\endgroup\$ – xnor Jun 26 '16 at 6:34
2
\$\begingroup\$

Java 7, 65 53 bytes

int f(int n){return(n-Integer.highestOneBit(n))*2+1;}

Using the algorithm for k=2 Josephus from Wikipedia. Thanks to Leaky Nun for finding the builtin.

\$\endgroup\$
  • \$\begingroup\$ i&i-1 saves 2 bytes \$\endgroup\$ – Leaky Nun Jun 26 '16 at 1:19
  • \$\begingroup\$ Spare parens ftw >_> \$\endgroup\$ – Geobits Jun 26 '16 at 1:20
  • \$\begingroup\$ int f(int n){return(n-Integer.highestOneBit(n))*2+1;} \$\endgroup\$ – Leaky Nun Jun 26 '16 at 1:30
  • \$\begingroup\$ Dammit, I was doing highestOneBit manually and got it to 56 just now. I didn't know there was a built-in for it :/ \$\endgroup\$ – Geobits Jun 26 '16 at 1:31
  • 2
    \$\begingroup\$ Yeah, I use Java 7 for golfing just to avoid shady (imo) lambda nonsense :P \$\endgroup\$ – Geobits Jun 26 '16 at 1:33
2
\$\begingroup\$

Pyth, 22 13 12 9 bytes

Credits to Geobit's algorithm for saving 9 bytes. It works like magic.

Credits to xnor's witchcraft for saving 3 bytes. It is simply witchcraft.

heu+G=Z%e.f!/G%ZQ2ZQQY
u?sIlH1+2GSQ1
hyaefgQT^L2
i.<.BQ1 2

Test suite.

\$\endgroup\$
2
\$\begingroup\$

Jelly, 4 bytes

Since xnor came up with this algorithm, I will make this community wiki.

Bṙ1Ḅ

Try it online!

Explanation

Bṙ1Ḅ
B     convert to binary
 ṙ1   left-rotate by 1
   Ḅ  convert from binary
\$\endgroup\$
1
\$\begingroup\$

VBA, 57 67 bytes

Well, this technically ought to work (57 bytes):

Function Z(N):Z=2*(N-2^Int(Log(N)/Log(2)))+1:End Function

But actually, because occasionally the log value of a power of two is not quite an exact multiple of the log of 2, we need a few more bytes:

Function Z(N):Z=2*(N-2^Int(Log(N)/Log(2))):Z=1-Z*(Z<N):End Function

If there were a built-in binary converter, it would be much shorter.

The recursion version is a tie, basically, but needs a line-feed for the IF

Function Y(N):Y=1:If N>1 Then Y=2*Y(N\2)+2*(N\2=N/2)+1
End Function
\$\endgroup\$
0
\$\begingroup\$

J, 10 bytes

(1&|.)&.#:

Using the formula where a(n) = n written in binary and rotated left by 1 place. Similar to what is used in @xnor's solution.

Using 19 bytes, we can play the game according to the rules in the challenge.

[:(2&}.,{.)^:_>:@i.

This solution only performs array manipulation in order to reach a final player.

Usage

Extra commands used for formatting multiple input/output with multiple functions.

   f =: (1&|.)&.#:
   g =: [:(2&}.,{.)^:_>:@i.
   (,.f"0,.g"0) i. 10
0 0 0
1 1 1
2 1 1
3 3 3
4 1 1
5 3 3
6 5 5
7 7 7
8 1 1
9 3 3

Explanation

(1&|.)&.#:  Input: n
        #:  Convert to binary
(    )&.    Compose next function on the binary value
 1&|.       Rotate left by 1 place
(    )&.    Compose the inverse of the previous function on the result
        #:  The inverse: convert from binary to decimal and return result

[:(2&}.,{.)^:_>:@i.  Input: n
                 i.  Creates the range [0, 1, ..., n-1]
              >:@    Increment each in the range to get [1, 2, ..., n]
[:(       )^:_       Nest the function until the result does not change and return
   2&}.              Drop the first two items in the list
        {.           Get the head of the list
       ,             Join them together. This makes it so that the head of the list
                     is always the current player and the one after the head is the
                     player to be removed
\$\endgroup\$
0
\$\begingroup\$

Python, 29 bytes

f=lambda n:n&n-1<1or f(n-1)+2

Outputs 1 as True when n is a power of 2, checked by n&n-1 being 0. Otherwise, outputs 2 higher than the previous value.


28 bytes:

Adapting grc's general solution to the case k=2 gives a better solution

f=lambda n:n and-~f(n-1)%n+1

Rather than explicitly checking for powers of 2, it zeroes out the result before incrementing each time f(n-1) catches up to n-1

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.