Ninja Assassins - which ninja stays alive? [duplicate]

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

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