# Ninja Assassins - which ninja stays alive? [duplicate]

## 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.

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

## 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.

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

## 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
• Why a=? Do you need it? – NoOneIsHere Jun 26 '16 at 5:07
• @NoOneIsHere To recurse. – xnor Jun 26 '16 at 6:34

## 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.

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

# Pyth, 221312 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.

# 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


# 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


# 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


## 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