11
\$\begingroup\$

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 , 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]
\$\endgroup\$
4
  • \$\begingroup\$ Sandbox \$\endgroup\$
    – The Thonnu
    Aug 17 at 16:13
  • 3
    \$\begingroup\$ 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). \$\endgroup\$ Aug 18 at 18:42
  • 1
    \$\begingroup\$ @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? \$\endgroup\$
    – Jonah
    Aug 19 at 20:15
  • \$\begingroup\$ I was disappointed to find that this question has nothing to do with store.steampowered.com/app/312530/Duck_Game lol \$\endgroup\$
    – SkySpiral7
    Aug 25 at 18:53

4 Answers 4

5
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ "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? \$\endgroup\$
    – Jonah
    Aug 19 at 4:31
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Neil
    Aug 19 at 5:47
4
\$\begingroup\$

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!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ You can remove 0<= in the check of function M, since i is always \$\geq0\$. \$\endgroup\$ Aug 18 at 7:43
  • 1
    \$\begingroup\$ Also, L=eval(str(l)) can be L=l.copy() \$\endgroup\$ Aug 18 at 9:43
  • 1
    \$\begingroup\$ @KevinCruijssen L=l.copy() can be L=l[:] \$\endgroup\$
    – The Thonnu
    Aug 18 at 9:51
  • \$\begingroup\$ 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)) \$\endgroup\$ Aug 18 at 16:16
3
\$\begingroup\$

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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ 78 bytes, I think (based on your initial version). \$\endgroup\$
    – Arnauld
    Aug 17 at 18:59
1
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking ā€œPost Your Answerā€, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.