12
\$\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, 2023 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, 2023 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, 2023 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, 2023 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, 2023 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, 2023 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, 2023 at 7:43
  • 1
    \$\begingroup\$ Also, L=eval(str(l)) can be L=l.copy() \$\endgroup\$ Aug 18, 2023 at 9:43
  • 1
    \$\begingroup\$ @KevinCruijssen L=l.copy() can be L=l[:] \$\endgroup\$
    – The Thonnu
    Aug 18, 2023 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, 2023 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, 2023 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 you have read our privacy policy.

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