# Optimal Duck Game Moves

## How to play the duck game

This is a 2-player game.

First, we start with a line of blue rubber ducks (represented here as circles):

🔵🔵🔵🔵🔵🔵🔵


Now, in each turn, the current player can turn either one blue duck or two adjacent blue ducks red.

So, a valid move would be indexes 2 and 3 (0-indexed):

🔵🔵🔴🔴🔵🔵🔵


Then, the other player could choose index 0:

🔴🔵🔴🔴🔵🔵🔵


And so on. The last player to move loses.

### Example game

Starting with 7 blue ducks:

Initial board

🔵🔵🔵🔵🔵🔵🔵


Player 1 chooses 3,4

🔵🔵🔵🔴🔴🔵🔵


Player 2 chooses 0

🔴🔵🔵🔴🔴🔵🔵


Player 1 chooses 6

🔴🔵🔵🔴🔴🔵🔴


Player 2 chooses 1,2

🔴🔴🔴🔴🔴🔵🔴


Player 1 chooses 5

🔴🔴🔴🔴🔴🔴🔴


Player 1 was the last one to move, so Player 2 wins.

## Challenge

The duck game can be solved. Your challenge today is to accept a board state and output one of the moves which will guarantee a win for the current player.

For example, with the board state 🔵🔵🔵🔴🔴🔵🔵, choosing either index 0 or index 2 will guarantee a win for the current player (feel free to try it).

## Input/Output

• You should take in a list/array/etc. containing two distinct values representing blue and red ducks.
For example, 🔵🔵🔵🔴🔴🔵🔵 could be [1, 1, 1, 0, 0, 1, 1].

• You should output one or two integers representing the ducks which should be taken in the next move.
For example, the input 🔵🔵🔵🔴🔴🔵🔵 could have output  or .

## Clarifications

• The input board state will always have at least one move which guarantees a win for the current player.
• You may output any of the moves which guarantee a win.
• This is , so shortest solution in bytes wins.

## Test cases

These test cases use 1 for blue ducks and 0 for red ducks. The output side contains all possible outputs.

Input  ->  Output
[1, 1, 1, 0, 0, 1, 1]  ->  , 
[1, 1, 1, 1, 1, 1, 1]  ->  , , 
[1, 1, 0, 1, 1, 1, 1]  ->  [0,1], [3,4], [5,6]
[1, 0, 1, 1, 0, 1, 1]  ->  
[1, 1, 1]  ->  [0,1], [1,2]
[1, 0, 0, 1, 1, 0, 0, 1]  ->  , 

• Sandbox Aug 17 at 16:13
• This game is called (misère) Kayles. A solution was first published in W.L. Silbert, J.H. Conway, “Mathematical Kayles”, Int J Game Theory 20, 237–246 (1992). Aug 18 at 18:42
• @AndersKaseorg, I found the paper interesting but difficult. Re: the appearance of the phano plane -- is there some deeper connection to projective geometry, or was that merely a convenient visual aid? Also, if I understood correctly, the normal version game is almost trivial to solve and all of that analysis was to handle the misere version? Is that correct? Aug 19 at 20:15
• I was disappointed to find that this question has nothing to do with store.steampowered.com/app/312530/Duck_Game lol Aug 25 at 18:53

# Charcoal, 71 52 bytes

Ｆ⊕⍘⮌Ｓ²⊞υ⎇ιΦ⁺Ｅθ⟦λ⟧Ｅθ⟦λ⊕λ⟧∧⁼ΣＸ²κ＆ΣＸ²κι¬§υ⁻ιΣＸ²κ⟦⟦⟧⟧Ｉ⊟υ


Try it online! Link is to verbose version of code. Takes input as a string of 0s and 1s representing red and blue ducks respectively and outputs a double-spaced list of winning 0-indexed duck moves. Explanation: Uses dynamic programming to find winning moves.

Ｆ⊕⍘⮌Ｓ²


Loop over numeric positions indices from 0 to the input as a position index, some of which will be unreachable from the input position.

⊞υ⎇ιΦ⁺Ｅθ⟦λ⟧Ｅθ⟦λ⊕λ⟧∧⁼ΣＸ²κ＆ΣＸ²κι¬§υ⁻ιΣＸ²κ⟦⟦⟧⟧


Find all legal moves that result in forced losses from this position, but special case a list of an empty list for position index 0 which should really be a loss for the player to move (this would save 6 bytes).

Ｉ⊟υ


Output all winning moves from the input position.

• "but special case a list of an empty list for position index 0 which should really be a loss for the player to move" I think an empty list would be a loss for the player to move, and hence invalid input -- or did you mean something else? Aug 19 at 4:31
• @Jonah An empty list means that it's a loss for the player to move, as they have no winning moves, which is why I have to make it a list of an empty list, so that the player who moves to that position loses. This is because this version of the game is being played as a misère game. In a normal game, the empty position is a loss for the player to move, which avoids this special case.
– Neil
Aug 19 at 5:47

# Python3, 333 bytes:

def M(l):
for i,a in enumerate(l):
if a:
yield[i]
if i<len(l)-1and l[i+1]:yield[i,i+1]
def K(l):
for m in M(l):
L=l[:]
for i in m:L[i]=0
yield L,m
def P(l,p=1):
F=1
for L,_ in K(l):
if any(L):
if p in(u:=[*P(L,not p)]):yield from u;F=0
if F:yield not p
f=lambda l:[m for L,m in K(l)if any(L)and not any(P(L))]


Try it online!

• You can remove 0<= in the check of function M, since i is always $\geq0$. Aug 18 at 7:43
• Also, L=eval(str(l)) can be L=l.copy() Aug 18 at 9:43
• @KevinCruijssen L=l.copy() can be L=l[:] Aug 18 at 9:51
• Do you need the enumerate? using l[i] instead of a might be a bit shorter edit: nvm I forgot about the length of range(len(i)) Aug 18 at 16:16

# JavaScript (V8), 78 bytes

-5 bytes from Arnauld

f=x=>x.some(r=(v,i,[...e])=>v?r=f(e,e[i]=0)?f(e,e[i-1]=0)?0:[i-1,i]:[i]:0)?r:r


Try it online!

# JavaScript (V8), 81 bytes

f=(x,e)=>x.some((v,i)=>r=v?f(e=[...x],e[i]=0)?f(e,e[i-1]=0)?0:[i-1,i]:[i]:0)?r:!e


Try it online!

returns false if impossible, returns true if win immediately because of endgame.

• 78 bytes, I think (based on your initial version). Aug 17 at 18:59

z f=zipWith f[0..]
f x|h:_<-filter(\j->all(\k->k<length x&&not(x!!k))j&&n==f((\k->z(\i y->y||elem i k)x)j))$concat$z(\i _->[[i],[i,i+1]])x=Just h