Rock, Paper, Scissors, Lizard, Spock Tournament
JavaScript (ES6), 122 115 112 bytes
Takes input as an array of strings of digits, with:
- \$0\$ = Scissors (S)
- \$1\$ = Paper (P)
- \$2\$ = Rock (R)
- \$3\$ = Lizard (L)
- \$4\$ = Spock (V)
Returns either a string in the same format or \$false\$ if there's no solution.
f=(a,m='',x=0,o,b=a.filter(a=>(y=a[m.length%a.length])-x?o|=y-x&1^x<y:1))=>b+b?x<4&&f(a,m,x+1)||!o&&f(b,m+x):m+x
Try it online!
How?
This is a breadth-first search: we first try all moves at a given step to see if we can win the game. If we can't win right now, we try to add another move to each non-losing move.
The move identifiers were chosen in such a way that a move \$A\$ wins against a move \$B\$ if and only if \$(B-A)\bmod 5\$ is odd.
With \$A\$ on the left and \$B\$ on the top:
$$ \begin{array}{cc|ccccc} & & \text{(S)} & \text{(P)} & \text{(R)} & \text{(L)} & \text{(V)}\\ & & 0 & 1 & 2 & 3 & 4\\ \hline \text{(S) }&0 & - & \color{green}1 & \color{red}2 & \color{green}3 & \color{red}4\\ \text{(P) }&1 & \color{red}4 & - & \color{green}1 & \color{red}2 & \color{green}3\\ \text{(R) }&2 & \color{green}3 & \color{red}4 & - & \color{green}1 & \color{red}2\\ \text{(L) }&3 & \color{red}2 & \color{green}3 & \color{red}4 & - & \color{green}1\\ \text{(V) }&4 & \color{green}1 & \color{red}2 & \color{green}3 & \color{red}4 & - \end{array} $$
From there, we can deduce another way of testing if \$A\$ wins against \$B\$ for \$A\neq B\$:
((A - B) and 1) xor (B < A)
where and and xor are bitwise operators.
Commented
f = ( // f is a recursive function taking:
a, // a[] = input
m = '', // m = string representing the list of moves
x = 0, // x = next move to try (0 to 4)
o, // o = flag set if we lose, initially undefined
b = // b[] = array of remaining opponents after the move x
a.filter(s => // for each entry s in a[]:
( y = // define y as ...
s[m.length % s.length] // ... the next move of the current opponent
) - x // subtract x from y
? // if the difference is not equal to 0:
o |= // update o using the formula described above:
y - x & 1 ^ x < y // set it to 1 if we lose; opponents are removed
// while o = 0, and kept as soon as o = 1
: // else (this is a draw):
1 // keep this opponent, but leave o unchanged
) // end of filter()
) => //
b + b ? // if b[] is not empty:
x < 4 && // if x is less than 4:
f(a, m, x + 1) // do a recursive call with x + 1 (going breadth-first)
|| // if this fails:
!o && // if o is not set:
f(b, m + x) // keep this move and do a recursive call with b[]
: // else (success):
m + x // return m + x
R, 213 190 bytes
-23 bytes thanks to Giuseppe.
function(L){m=matrix(rep(0:2,1:3),5,5)
m[1,4]=m[2,5]=1
v=combn(rep(1:5,n),n<-sum(lengths(L)))
v[,which(apply(v,2,function(z)all(sapply(L,function(x,y,r=m[cbind(x,y)])r[r>0][1]<2,z)))>0)[1]]}
Try it online!
If a solution exists, it outputs one. If there is no solution, it outputs a row of NA. If this output format is not acceptable, I can change it at a cost of a few bytes.
Moves are coded as 1=R, 2=S, 3=P, 4=L, 5=V, so that the matrix of outcomes is
[,1] [,2] [,3] [,4] [,5]
[1,] 0 2 2 1 1
[2,] 1 0 2 2 1
[3,] 1 1 0 2 2
[4,] 2 1 1 0 2
[5,] 2 2 1 1 0
(0=no winner; 1=player 1 wins; 2=player 2 wins)
An upper bound on the length of the solution if it exists is n=sum(lengths(L)) where L is the list of opponents' moves. The code creates all possible strategies of length n (stored in matrix v), tries all of them, and displays all winning strategies.
Note that this value of n makes the code very slow on TIO, so I have hardcoded in the TIO n=4 which is enough for the test cases.
For the first test case, the output is
1 4 2 4
corresponding to the solution RLSL.
For the second test case, the output is
NA NA NA NA
meaning that there is no solution.
Explanation of a previous version (will update when I can):
function(L){
m = matrix(rep(0:2,1:3),5,5);
m[1,4]=m[2,5]=1 # create matrix of outcomes
v=as.matrix(expand.grid(replicate( # all possible strategies of length n
n<-sum(lengths(L)) # where n is the upper bound on solution length
,1:5,F)))
v[which(
apply(v,1, # for each strategy
function(z) # check whether it wins
all( # against all opponents
sapply(L,function(x,y){ # function to simulate one game
r=m[cbind(x,y)]; # vector of pair-wise outcomes
r[r>0][1]<2 # keep the first non-draw outcome, and verify that it is a win
}
,z)))
>0),] # keep only winning strategies
}
The which is necessary to get rid of NAs which occur when the two players draw forever.
I am not convinced this is the most efficient strategy. Even if it is, I am sure that the code for m could be golfed quite a bit.
Jelly, 29 bytes
_%5ḟ0ḢḂ¬
ṁ€ZLḤƊçþ`Ạ€Tị;‘%5Ɗ$€
A monadic Link that accepts a list of lists of integers (each of which is an opponent's strategy) which yields a list of lists of integers - each of which is a winning strategy (so an empty list if none are possible).
(Just add Ḣ to only yield a single strategy list or 0 if impossible.)
Try it online! (the footer formats to always show the lists)
Rock Paper Scissors Spock Lizard
0 1 2 3 4
Or try a letter mapped version (where strategies are taken and shown on their own lines using RPSVL notation).
How?
The numbers are chosen such that any which are an odd number greater than another modulo five win (i.e. they are numbered going around the edge of an inscribed pentagon of the throws).
The code plays each strategy off against every strategy (including themselves) for twice as many throws as the longest strategy so as to ensure finding any losers keeping those which are not defeated. The resulting list of strategies will contain a single strategy if there is an outright winner; no strategies if there was no winner; or multiple strategies if there are drawing players. After this a winning set of moves is appended to each of these strategies.
_%5ḟ0ḢḂ¬ - Link 1, does B survive?: list A, list B (A & B of equal lengths)
e.g. RPSR vs RPVL -> [0,1,2,0], [0,1,3,4]
_ - subtract (vectorises) [0,0,-1,-4]
%5 - modulo five (vectorises) [0,0,4,1] ...if all zeros:
ḟ0 - filter discard zeros (ties) [4,1] []
Ḣ - head (zero if an empty list) 4 0
Ḃ - modulo two 0 0
¬ - logical NOT 1 1
ṁ€ZLḤƊçþ`Ạ€Tị;‘%5Ɗ$€ - Main Link: list of lists of integers
ṁ€ - mould each list like:
Ɗ - last three links as a monad
Z - transpose
L - length
Ḥ - double (i.e. 2 * throws in longest strategy)
` - use left as both arguments of:
þ - table using:
ç - last Link (1) as a dyad
Ạ€ - all for each (1 if survives against all others, else 0)
T - truthy indices
ị - index into the input strategies
$€ - last two links as a monad for each:
; - concatenate with:
Ɗ - last three links as a monad:
‘ - increment (vectorises)
%5 - modulo five (vectorises)