13
\$\begingroup\$

This challenge is inspired by the game No More Jockeys.

The input is a list of tuples of natural numbers (potentially including 0), in some appropriate input format. Starting with player 0 and alternating with player 1, each player chooses some number which is contained within at least one remaining tuple, and all tuples containing that number will be removed from the list. The first player who has no possible moves loses.

Your challenge is to implement a function to calculate the minimax value of a given input. Return a truthy value if it is player 1 to win given optimal play by both players, and a falsy value if it is player 0 to win. The converse is also acceptable.

This is , so fewest bytes wins.

Test Cases

((), (0, 1, 3), (1,)) -> 0
() -> 1
((0,), (1, 3), (2,)) -> 0
((), (0, 1), (0, 1, 2), (0, 2), (1,)) -> 1
((0,), (0, 1, 3), (0, 3), (2,)) -> 0
((), (0, 1), (0, 2, 3), (1,), (2,), (3,)) -> 1
((0, 1), (1, 2), (2, 3), (3,)) -> 0
((0, 2), (1,), (1, 3), (3,), (4,)) -> 1
((0, 2, 3), (0, 3), (1,), (2,), (2, 3)) -> 0
\$\endgroup\$
2
  • 1
    \$\begingroup\$ May we take the inner tuples as set objects? \$\endgroup\$
    – xnor
    Apr 20, 2021 at 22:25
  • 1
    \$\begingroup\$ @xnor OK, that's fine. \$\endgroup\$ Apr 20, 2021 at 22:34

5 Answers 5

6
\$\begingroup\$

Python 3, 62 bytes

f=lambda a:0in(f([x for x in a if{r}-{*x}])for r in sum(a,()))

Try it online!

Python 2, 61 bytes

f=lambda a:0in(f(filter({y}.__sub__,a))for x in a for y in x)

Try it online!

-5 bytes thanks to Unrelated String
-6 bytes thanks to dingledooper
-1 byte if we use Python 2 thanks to dingledooper
-2 bytes thanks to xnor

Outputs True for player 0 winning and False or () for player 1 winning (() is an empty tuple in Python, which is a falsey value in the language)

\$\endgroup\$
7
5
\$\begingroup\$

JavaScript (ES10), 54 bytes

Returns a Boolean value.

f=a=>!a.flat().some(v=>f(a.filter(b=>!b.includes(v))))

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Haskell, 41 bytes

f a=any(not.f.(`filter`a).notElem)$a>>=id

Try it online!

Was the same length as using nested list comprehensions, until I realized notElem exists, and is much shorter than (not.).elem. Still feels very golfable...

\$\endgroup\$
3
\$\begingroup\$

J, 37 bytes

(0=1#.]$:@#~1-~.@;e.&>/])`1:@.(''-:;)

Try it online!

Inspired by Arnauld's answer.

\$\endgroup\$
2
\$\begingroup\$

Jelly, 9 bytes

iÐḟⱮẎ߀0e

Try it online!

My first attempt repeatedly segfaulted, but now that I have a very close translation of hyper-neutrino's Python solution it seems to work fine.

I would be remiss to let this get accepted without an explanation!

   Ɱ         For each element of
    Ẏ        the input flattened a level,
 Ðḟ          yield the input without elements which
i            contain the element in question.
     ߀      Recur on each result.
       0e    Is one of those results 0?
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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