# Duck, Duck, Josephus

Given an Integer array:

1. Start from the first number
2. Jump forward n positions where n is the value of the current position
3. Delete the current position, making what was the next position the current position.
4. Goto step 2 until there is one number remaining
5. Print that number

Rules

The array wraps-around (the next number after the last number in the array is the first number).

A zero removes itself (Obviously).

Negative numbers are not allowed as input.

Test Cases

 => 1
[1,2] => 1
[1,2,3] => 3
[1,2,2] => 1
[1,2,3,4] => 1
[6,2,3,4] => 4
[1,2,3,4,5] => 5
[0,1] => 1
[0,0,2,0,0] => 0


Step-by-step example

[1,4,2,3,5]
^          start from the first position
^        jump 1 position (value of the position)
[1,  2,3,5] remove number in that position
^      take next position of the removed number (the 'new' 'current' position)
^  jump 2 positions
[1,  2,3  ] remove number in that position
^          take next position (looping on the end of the array)
^      jump 1 position
[1,    3  ] remove number in that position
^    take next position (looping)
^          jump 3 positions (looping on the end of the array)
[      3  ] remove number in that position
print 3


Example #2

[4,3,2,1,6,3]
^            start from the first position
^    jump 4 positions
[4,3,2,1,  3] remove number in that position
^  take next position
^        jump 3 positions
[4,3,  1,  3] remove number in that position
^      take next position
^  jump 1 positions
[4,3,  1    ] remove number in that position
^            take next position
^          jump 4 positions
[4,    1    ] remove number in that position
^      take next position
^            jump 1 position
[      1    ] remove number in that position
print 1


This is , the shortest answer in bytes wins!

• Nice first challenge! Dec 12 '17 at 13:49
• @LuisMendo Yes.. the "skip like a..." challenges Dec 12 '17 at 13:58
• @Jenny_mathy I didn't think there would be a similar one, but as Luis said, the wraparound array makes an interesting challenge for golfing. I think :/ Dec 12 '17 at 14:00
• @EriktheOutgolfer Not really a dupe. The elements there are indistinguishable and the step size is fixed. Luis's is much closer, but still sufficiently different I think. Dec 12 '17 at 14:12
• Does it need to actually print the final number, or can it just return it? Does it need to actually return the number, or can it just operate on the array in-place so the after the function is run, the array contains just the number? Dec 12 '17 at 16:48

# Husk, 7 bytes

This returns the result as a singleton list

ΩεSotṙ←


Try it online!

### Explanation

Ω               Until
ε              the result is a singleton list
ṙ          Rotate left by
S   ←         the first element
ot           Then remove the first element


f[x]=x
f(x:r)=f$snd<$>zip r(drop(x+1)$cycle$x:r)


Try it online!

Explanation:

• f[x]=x: If the given list is a singleton list, return its element.
• f(x:r)=f$...: Otherwise recursively apply f to the following list: • The elements of the current list cycled infinitely (cycle$x:r),
• with the first x+1 elements removed (drop(x+1)$), • and truncated to length of r. (snd<$>zip r is a shorter alternative to take(length r)).

### Previous 54 byte version:

f=(%)=<<head
_%[x]=x
n%(x:r)|n<1=f r|s<-r++[x]=(n-1)%s


Try it online!

# Ruby, 37 bytes

->r{r.rotate!(r).shift while r}


Modifies the array in-place, which appears to be acceptable as output. Try it online!

# Python 3, 54 51 bytes

f=lambda x:x and f((x+x*x)[x:][1:len(x)])or x


Output is a singleton list.

Try it online!

• Completely unrelated, but I like your unicorn hat, Dennis. xD (And nice answer of course, as always!) Dec 18 '17 at 10:02

## CJam, 15 bytes

l~_,({_0=m<1>}*


Try it online!

### Explanation

Instead of keeping track of a pointer, I just shift the array cyclically so that the current element is always at the front.

l~     e# Read and evaluate input.
_,(    e# Get its length L and decrement to L-1.
{      e# Run this block L-1 times...
_0=  e#   Get the first element X.
m<   e#   Rotate the array left by X positions.
1>   e#   Discard the first element.
}*
e# The final element remains on the stack and gets printed implicitly.


A fun alternative which unfortunately doesn't save any bytes:

l~_{;m<1>_0=}*;


# MATL, 21 bytes

1yy)+ynX\[]w(5Mynq]x


### Explanation

1        % Push 1: current position in the array
% Do...while
yy     %   Duplicate top two elements in the stack. Takes input implicitly
%   in the first iteration.
%   STACK: array, position, array, position
)      %   Get specified entry in the array
%   STACK: array, position, selected entry
%   STACK: array, position (updated)
y      %   Duplicate from below
%   STACK: array, position, array
n      %   Number of elements of array
%   STACK: array, position, number of elements or array
X\     %   1-based modulus
%   STACK: array, position (wrapped around)
[]     %   Push empty array
%   STACK: array, position, []
w      %   Swap
%   STACK: array, [], position
(      %   Write value into specified entry in array. Writing [] removes
%   the entry
%   STACK: array (with one entry removed)
5M     %   Push latest used position. Because of the removal, this now
%   points to the entry that was after the removed one
%   STACK: array, position
y      %   Duplicate from below
%   STACK: array, position, array
n      %   Number of elements of array
%   STACK: array, position, number of elements of array
q      %   Subtract 1
%   STACK: array, position, number of elements of array minus 1
]        % End. If top of the stack is nonzero, proceed with next iteration
% STACK: array (containing 1 entry), position
x        % Delete. Implicitly display
% STACK: array (containing 1 entry)

• Note: using list rotations instead of keeping a pointer will probably make this much shorter. Dec 12 '17 at 18:02
• @Erik Thanks. But now that I added the explanation I think I’ll leave it like this Dec 12 '17 at 19:18
• Well, you can always remove the explanation, it will be kept in the history :) Dec 12 '17 at 19:22

# Python 2, 55 bytes

def f(a):
while a[1:]:l=a%len(a);a[:]=a[-~l:]+a[:l]


Try it online!

Outputs as a singleton list, as allowed by default. Saved a few bytes thanks to Dennis, by reminding me that modifying the function argument is allowed.

### How it works

• def f(a) - Defines a function with a parameter a.

• while a[1:]: - While a with the first element removed is truthy, run the block of code to follow. A list with one element or more is truthy, and empty lists are falsy in Python, hence this will stop once a reaches a length of 1.

• l=a%len(a) - Take the first element, and get the remainder of its division by the length of a. Assign the result to l.

• a[:]=a[-~l:]+a[:l] - Rotate a to the left by l elements, and remove the first one, while assigning this to a in place.

Python 2, 63 bytes

f=lambda a,i=0:a[1:]and f(a,a.pop(((a*-~i)[i]+i)%len(a))+1)or a


Try it online!

Although longer, this seems much more elegant. Also thanks to ovs for helping in chat.

• Couldn't you do something like a,*b=input() (python3) and save few bytes? However I'm not sure how that would affect l and the slice
– Rod
Dec 12 '17 at 14:44
• @Rod I don't think so, I would need to evaluate the input too in Python 3 Dec 12 '17 at 14:46

# Jelly, 7 bytes

ṙḷ/ḊµḊ¿


Try it online!

Full program.

• That ḷ/ is damn clever. Dec 12 '17 at 15:20
• Could you add an explanation, please? I've now looked at the Quicks and Atoms on the linked GIT-pages, and +1-ed based on that, but I can imagine not everyone having the patients to do the same. ;) Dec 18 '17 at 10:10

ṙḷ/ḊµL’$¡  Try it online! -2 bytes thanks to user202729 # Explanation ṙḷ/ḊµL’$¡  Main Link
L’$¡ Repeat <length - 1> times ṙ Rotate left by ḷ/ The first element (from JHT; thanks to user202729) Ḋ Take all but the first element  # Brain-Flak, 88 bytes ([[]]()){({}<(({})){({}<({}<([]){({}{}<>)<>([])}{}>)<>{({}[<>[]])<>}<>>[()])}{}{}>())}{}  Try it online! ### Explanation ([[]]()) Push negative N: the stack height - 1 {({}< … >())}{} Do N times (({})) Duplicate M: the top of the stack {({}< … >[()])}{} Do M times Rotate the stack by 1: ({}< … >) Pop the top of the stack and put it back down after ([]){({}{}<>)<>([])}{} Pushing the rest of the stack on to the other one, in reverse, with the stack height added to each element (to ensure that all are positive) <>{({}[<>[]])<>}<> Push the rest of the stack back, unreversing, and subtracting the stack height from each element {} Pop the top of stack  • A very strange golf but here it is in 88 bytes. Dec 12 '17 at 18:35 • @WheatWizard Nice, surprisingly I tried something like that earlier on. Dec 12 '17 at 18:37 • I can never know how people can code like that! is there a pseudo-code translator or something? Dec 18 '17 at 13:16 • @workoverflow no, it's honestly easier than it looks. It was very daunting before I actually started , but the when the commands are this simple, it's easy to learn. Dec 18 '17 at 13:22 # APL (Dyalog), 20 18 bytes {1<≢⍵:∇1↓⊖∘⍵⊃⍵⋄⊃⍵}  Try it online! # Python 3, 60 bytes def f(a):b=a%len(a);return f(a[-~b:]+a[:b])if a[1:]else a  Try it online! -3 bytes thanks to ovs # J, 21 17 bytes -4 bytes thanks to FrownyFrog ((1<#)}.{.|.])^:_  Try it online! Original: ([:}.{.|.])^:(1<#)^:_ # How it works: ^:_ repeat until the result stops changing ^:(1<#) if the length of the list is greater than 1 {.|.] rotate the list to the left its first item times [:}. drop the first element and cap the fork Try it online! • @ FrownyFrog Thanks, I didn't try this - it's much better! Dec 13 '17 at 11:52 # JavaScript (ES6), 54 60 bytes Saved 1 byte thanks to @Shaggy Fixed version (+6 bytes) Modifies the input array, which is reduced to a singleton. f=(a,p=0)=>1/a||f(a,p=(p+a[p%(l=a.length)])%l,a.splice(p,1))  ### Test cases f=(a,p=0)=>1/a||f(a,p=(p+a[p%(l=a.length)])%l,a.splice(p,1)) ;[ , //  [1,2], //  [1,2,3], //  [1,2,2], //  [1,2,3,4], //  [6,2,3,4], //  [1,2,3,4,5], //  [0,1], //  [0,0,2,0,0], //  [3,5,7,9] //  ].forEach(a => f(a) && console.log(JSON.stringify(a))) ### How? We recursively apply the algorithm described in the challenge. Only the stop condition 1/a may seem a bit weird. When applying an arithmetic operator: • Arrays of more than one element are coerced to NaN and 1/NaN is also NaN (falsy). • Arrays of exactly one integer are coerced to that integer, leading to either 1/0 = +Infinity or 1/N = positive float for N > 0 (both truthy). f = (a, p = 0) => // a = input array, p = pointer into this array 1 / a || // if a is not yet a singleton: f( // do a recursive call with: a, // a p = ( // the updated pointer p + a[p % (l = a.length)] // ) % l, // a.splice(p, 1) // the element at the new position removed ) // end of recursive call  • Seeing as splice modifies the original array, you could do f=(a,p=0)=>1/a||f(a,p=p+a[p]%a.length,a.splice(p,1)) for 52 bytes Dec 12 '17 at 17:06 • it seems it doesn't give the right result for the second step by step example, f=(a,p=0)=>1/a?a:f(a,p=(p%a.length+a[p%a.length])%a.length,a.splice(p,1)) is ok but may be optimized Dec 12 '17 at 17:13 • @NahuelFouilleul Oops. I thought at some point that the parentheses around p+a[p] could be removed. Which -- of course -- is not the case. Thanks for reporting this! Dec 12 '17 at 17:19 • See this consensus, which @Neil brought to my attention here. Dec 12 '17 at 17:20 • @Shaggy Oh, I see. Thank you! (I missed your TIO link the 1st time...) Dec 12 '17 at 17:26 # Julia 0.6, 46 42 bytes !x=length(x)>1?!circshift(x,-x[])[2:end]:x  Try it online! Straightforward recursive Julia version. x[] accesses the first element of x. # Java 8, 79 bytes This lambda accepts a Stack<Integer> and returns an int or Integer. l->{for(int i=0,s=l.size();s>1;)l.remove(i=(i+l.get(i%s))%s--);return l.pop();}  Try It Online ## Ungolfed l -> { for ( int i = 0, s = l.size() ; s > 1 ; ) l.remove( i = (i + l.get(i % s)) % s-- ); return l.pop(); }  ## Acknowledgments • -2 bytes thanks to Nahuel Fouilleul • i%=s may be removed if l.get(i) changed by l.get(i%s) Dec 13 '17 at 8:54 # Pyth, 9 bytes .WtHt.<Zh  Try it here! This outputs the result as a singleton list, as allowed by default. ### How it works .WtHt.<Zh ~ Full program. .W ~ Functional while. It takes three arguments, two functions: A and B and a starting value, which in this case is automatically assigned to the input. While A(value) is truthy, value is set to B(value). Returns the ending value. A's argument is H and B's is Z. tH ~ A (argument H): Remove the first element of H. A singleton list turns into [], which is falsy and thus breaks the loop. Otherwise, it is truthy and the loops goes on until the list reaches length 1. .<Zh ~ B (argument Z): Cyclically rotate Z by Z places, whereas Z represents the first element of Z. t ~ And remove the first element.  Note: If you don't want to see those brackets, just add h or e in front of the whole code. # Swift, 87 bytes func f(a:inout[Int]){var i=0,c=0;while(c=a.count,c>1).1{i=(i+a[i%c])%c;a.remove(at:i)}}  Returns as a singleton list by modifying the input. Try it online! ## Explanation func f(a:inout[Int]){ var i=0,c=0; // Set the index i to 0 while(c=a.count,c>1).1{ // While the length of the list > 0: i=(i+a[i%c])%c; // Add a[i] to i and loop back using modulo a.remove(at:i) // Remove a[i] } }  # Mathematica, 36 bytes uses Martin's algorithm #//.l:{x_,__}:>Rest@RotateLeft[l,x]&  -5 bytes from Misha Lavrov && Martin Ender Try it online! • You can save two bytes by using the pattern to pick out the first element #//.{x_,y__}:>Rest@RotateLeft[{x,y},x]&. (This stops when there is only one element because {a} no longer matches the pattern {x_,y__}.) Dec 12 '17 at 22:12 • @MishaLavrov can't test right now, but you can probably shorten that further by dropping the y, calling the entire list l and then using l instead of {x,y}. Dec 12 '17 at 23:08 • @MartinEnder You mean like this - #//.l:{x_,__}:>Rest@RotateLeft[l,x]&? Dec 12 '17 at 23:14 • @MishaLavrov yep. Dec 12 '17 at 23:27 # Perl 6, 46 45 bytes (-1 byte thanks to Brad Gilbert) {($_,{(|$_ xx*)[.+(1..^$_)]}...1)[*-1]}


Try it online!

($_, { ... } ... 1) generates a sequence of lists, starting with the input list $_, each successive element being generated by the brace expression, and terminating when the list smart-matches 1--ie, has a length of 1. The trailing [* - 1] obtains the final element, and the final  takes the sole element out of that singleton list.

(|$_ xx *) generates a flat, infinitely replicated copy of the current element. This list is indexed with the range . + (1 ..^$_) to extract the next finite list in the series.

• mind blown o.O Dec 12 '17 at 20:01
• [*-1] can be combined into [*-1;0] saving a byte. Also 1..$_-1 is better written as 1..^$_ again saving a byte. Dec 17 '17 at 22:47
• @BradGilbertb2gills I tried [*-1;0], but it seems not to be equivalent somehow. The function then returns a list rather than a number.
– Sean
Dec 18 '17 at 0:02
• That doesn't stop the 1..^$_ optimization Dec 21 '17 at 22:53 # Perl 5, 4743 41 + 2 (-ap) = 43 bytes $\=splice@F,($_+=$F[$_%@F])%@F,1while@F}{  Try it online! Takes input as space separated numbers. • it seems it does not exactly the same as the step by step example following does but is longer $x%=@F,splice@F,$x=($x+$F[$x])%@F,1while$#F;$_="@F" Dec 12 '17 at 16:55
• wow o.O Need to get my game up. Dec 12 '17 at 20:00

f[x]=x
f l|m<-head lmodlength l=f\$drop(m+1)l++take m l


Try it online!

• 55 bytes Dec 13 '17 at 1:01

# Python 3, 57 56 bytes

f=lambda a,*b:f(*([a,*b]*-~a)[a+1:a-~len(b)])if b else a


Try it online!

# Java 8, 325 Bytes

Golfed:

static void n(Integer[]j){Integer[]h;int a=0;h=j;for(int i=0;i<j.length-1;i++){if(h.length==a){a=0;}a=(a+h[a])%h.length;h[a]=null;h=m(h);}System.out.print(h);}static Integer[] m(Integer[]array){Integer[]x=new Integer[array.length-1];int z=0;for(int i=0;i<array.length;i++){if(array[i]!=null){x[z]=array[i];z++;}}return x;}


Ungolfed:

 interface ArrayLeapFrog {
static void main(String[] z) throws Exception {
Integer[] j = {6, 2, 3, 4};
n(j);
}

static void n(Integer[] j) {
Integer[] h;
int a = 0;
h = j;
for (int i = 0; i < j.length - 1; i++) {
if (h.length == a) {
a = 0;
}
a = (a + h[a]) % h.length;
h[a] = null;
h = m(h);
}
System.out.print(h);
}

static Integer[] m(Integer[] array) {
Integer[] x = new Integer[array.length - 1];
int z = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] != null) {
x[z] = array[i];
z++;
}
}
return x;
}
}

• Welcome! A couple tips: No need to count the static keywords here. Typically multi-method solutions are implemented as non-static members of a class, and main creates an instance for testing. Also, if you do it that way you support Java 7 and can submit as simply a "Java" solution. For future reference, input format tends to be quite flexible here, so for example you could choose to take input as a List (which is quite helpful for this problem). Dec 13 '17 at 0:43

# APL+WIN, 36 bytes

¯1↑⍎¨(1⌈¯1+⍴v←,⎕)⍴⊂'v←(1<⍴v)↓v⌽v'


Explanation:

Prompts for screen input.

'v←(1<⍴v)↓v⌽v' Loop logic as a string

(1<⍴v)↓ only drop the first when number of elements n>1

(1⌈¯1+⍴v←,⎕)⍴⊂ create a nested vector of logic of length 1 max n-1

⍎¨ execute each element of the nested vector in turn

¯1↑ take answer from executing final element


# Python 2, 61 bytes

def f(x):
while x[1:]:y=x%len(x);x=x[y+1:]+x[:y]
print x

• I know a bunch of python answers exist, but I figured I might as well add my own. Dec 13 '17 at 3:10

# JavaScript, 5856 59 bytes

let f =

a=>{for(i=0,k=a.length;k>1;)i+=a[i%=k],a.splice(i%=k--,1)}
<h2>Test</h2>
Enter or paste a valid array literal within square brackets and click Run.
<blockquote>
<input id = "array" type="text" length="20">
<button type="button" onclick="run()">Run</button>
</blockquote>
Result: <pre id="o"></pre>

<script>
function run() {
let a = JSON.parse(array.value);
f(a);
o.textContent = a;
}
</script>

Returns the result as the only element remaining in the input array which is updated in place.

Two bytes saved by using a comma separated statement instead of a block statement in the for loop body! Three bytes lost to skip from an element deleted at end of array (:

Less golfed:

a => {
for(i=0,k=a.length;k>1;) // once less than array length
i+=a[i%=k],          // the new index
a.splice(            // delete an element
i%=k--,           // ensuring index is within array,
// and post decrement loop count
1
)
}

• This seems to give the wrong answer for [3, 5, 7, 9].
– Neil
Dec 13 '17 at 9:56
• Wrong for [3,5,7,9]. Expected value 5 Dec 13 '17 at 10:02
• The function does not return the value, i'm not sure if the byte count is proper keeping that in mind, since it can't work on it's own... Dec 13 '17 at 11:40
• @edc65 and Neil , thanks - the index of an element deleted at end of array was not being adjusted to the start of the shortened array. Dec 13 '17 at 22:35
• @BrianH. the function modify its parameter, there is consensus about that codegolf.meta.stackexchange.com/a/4942/21348 Dec 13 '17 at 22:40

# Brain-Flak, 104 bytes

H.PWiz has a shorter answer here that I helped to make, you should check it out.

([[]]()){({}()<(({})){({}[()]<({}<(([])<{{}({}<>)<>([])}{}<>>)<>>)<>{({}[()]<({}<>)<>>)}{}<>>)}{}{}>)}{}


Try it online!

## Explanation

([[]]())   #Push 1 minus stackheight
{({}()<    #N times
(({}))    #Get a copy of the top
{({}[()]< #N times
({}<(([])<{{}({}<>)<>([])}{}<>>)<>>)<>{({}[()]<({}<>)<>>)}{}<>
#Roll the top to the bottom (From the wiki)
>)}{}     #End loop
{}        #Remove one value
>)}{}      #End loop

• I thought I would compete. Then I realised that mine was almost exactly the same as yours, apart from a different "top roll" Dec 12 '17 at 18:24
• I saw that ;). Using the fact that everything is non-negative is rather clever. Dec 12 '17 at 18:25

# Clean, 78 bytes

import StdEnv
f[e]=e
f[x:r]=f(take(length r)(drop(x+1)(flatten(repeat[x:r]))))


Try it online!

# R, 111 117126 bytes

Thanks to @Giuseppe for golfing off 11 bytes by changing to a while loop, got another 4 by removing the function and reading user input directly.

I don't feel great about what it took to get there - I'm sure a more elegant solution exists.

i=scan();m=1;while((l=sum(i|1))-1){j=i[m];p=if(j+m>l,j%%l+!m-1,j+m);p=if(!p,m,p);i=i[-p];m=if(p-l,p,1)};i


Try it online!

Ungolfed code

i=scan()
m=1
while((l=sum(i|1))-1){
j=i[m]
p=if(j+m>l,j%%l+!m-1,j+m)
p=if(!p,m,p)
i=i[-p]
m=if(p-l,p,1)
}
i

• 117 bytes -- note that since this is a recursive function, the name f= needs to be included Dec 15 '17 at 15:45
• I found this quite a difficult challenge with a 1 based-index language without array rotations; this is potentially 1-3 bytes shorter with a while loop, I think. Dec 15 '17 at 15:46
• 115 bytes with a while loop Dec 15 '17 at 15:50
• my previous 115 byter was invalid since we both forgot the f= part of the recursive function. :( Dec 15 '17 at 15:51
• I updated the old score and the new score to reflect the recursiveness :) With the 'while' loop I golfed off another 4 bytes using scan.
– Mark
Dec 15 '17 at 15:59