Optimal Duck Game Moves

Question

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 [0] or [2].

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 code-golf, 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]  ->  [0], [2]
[1, 1, 1, 1, 1, 1, 1]  ->  [1], [3], [5]
[1, 1, 0, 1, 1, 1, 1]  ->  [0,1], [3,4], [5,6]
[1, 0, 1, 1, 0, 1, 1]  ->  [0]
[1, 1, 1]  ->  [0,1], [1,2]
[1, 0, 0, 1, 1, 0, 0, 1]  ->  [3], [4]

Answer 1

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.

Answer 2

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!

Answer 3

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.

Answer 4

Haskell, 178 bytes

z f=zipWith f[0..]
n=Nothing
f x|and x=Just[]
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
f x=n

Attempt This Online!