Rock, Paper, Scissors, Lizard, Spock TournamentSay “Hello” to the world in ASCII artRock Paper ScissorsRock-paper-scissors competition simulatorCrosses, no NoughtsWho's the king of the tournament?Score rock-paper-scissorsRegex, Paper, Scissors, Lizard, SpockConstruct a tournament bracketWho will win a Rock, Paper, Scissors, Lizard, Spock game?Subset Sum Orderings

What is the meaning of 「隣のおじいさんは言いました」

Game artist computer workstation set-up – is this overkill?

How to preserve a rare version of a book?

Make me a minimum magic sum

Can a player choose to add detail and flavor to their character's spells and abilities?

Given a safe domain, are subdirectories safe as well?

What does the phrase "go for the pin" mean here?

What is more safe for browsing the web: PC or smartphone?

How to replace space with '+' symbol in a triangular array?

How to say something covers all the view up to the horizon line?

Picking a theme as a discovery writer

How can I obtain and work with a Platonic dodecahedron?

How to detect nM levels of Copper(I) Oxide in blood?

Convert Numbers To Emoji Math

What would happen if I combined this polymer and this metal (assuming I can)

How long did it take Captain Marvel to travel to Earth?

Was there a dinosaur-counter in the original Jurassic Park movie?

Dimmer switch not connected to ground

How would you join two twin beds?

Why does blending blueberries, milk, banana and vanilla extract cause the mixture to have a yogurty consistency?

Where did Lovecraft write about Carcosa?

How to deal with employer who keeps me at work after working hours

Is there any other simpler way to draw the following cross section?

Two denim hijabs



Rock, Paper, Scissors, Lizard, Spock Tournament


Say “Hello” to the world in ASCII artRock Paper ScissorsRock-paper-scissors competition simulatorCrosses, no NoughtsWho's the king of the tournament?Score rock-paper-scissorsRegex, Paper, Scissors, Lizard, SpockConstruct a tournament bracketWho will win a Rock, Paper, Scissors, Lizard, Spock game?Subset Sum Orderings













9












$begingroup$


Giving a challenge involving a Star Trek reference just after May the 4th may be frowned upon, but here goes.



You, Luke, Anakin, Palpatine, Yoda and Han Solo are involved in an insane tournament of Rock, Paper, Scissor, Lizard, Spock.



The catch here is that you are only allowed to use a fixed order of moves. If your order is "R", Then you have to use Rock, until you lose or win against everyone. If your order is RRV, then you have to use 2 Rocks followed by a Spock and keep repeating until you have won or lost.



Luke, Anakin, Palpatine, Yoda and Han Solo have submitted their respective orderings and you being an expert hacker got your hands on each of their orderings!



With this knowledge, you are to design your ordering for the tournament. Since everyone wants to win, you want to create an ordering such that you win the tournament by beating everyone.
But this may not be possible under all circumstances.



Incase there is a possible winning order, print that out. If there is no possible way for you to win, print out -1 (or 0 or False or "impossible")



Input: a list of 5 orders



Output: a single order or -1



Sample Input 1



R
P
S
L
V


Sample Output 1



-1


Explanation 1



No matter what you play in your first move, there will be at least one
person who beats you, hence it is not possible for you to win.


Sample Input 2



RPS
RPP
R
SRR
L


Sample Output 2



RPSP


Explanation 2



Once you play Rock in your first move, you end up beating "L" and "SRR" and
tie against the rest. This is because Lizard and Scissors lose to Rock.
When you play Paper next, you will beat "R" and tie against the remaining
2. This is because Rock loses to Paper.
When you play Scissors next, you will win against "RPP" as Scissor beats
Paper.
Finally, you will beat "RPS" with your Paper as Paper beats Rock.


Here are a list of notations (you may use any 5 literals, but please specify in your answer):



R : Rock
P : Paper
S : Scissor
L : Lizard
V : Spock


Here is a list of all possible outcomes:



winner('S', 'P') -> 'S'
winner('S', 'R') -> 'R'
winner('S', 'V') -> 'V'
winner('S', 'L') -> 'S'
winner('S', 'S') -> Tie
winner('P', 'R') -> 'P'
winner('P', 'V') -> 'P'
winner('P', 'L') -> 'L'
winner('P', 'S') -> 'S'
winner('P', 'P') -> Tie
winner('R', 'V') -> 'V'
winner('R', 'L') -> 'R'
winner('R', 'S') -> 'R'
winner('R', 'P') -> 'P'
winner('R', 'R') -> Tie
winner('L', 'R') -> 'R'
winner('L', 'V') -> 'L'
winner('L', 'S') -> 'S'
winner('L', 'P') -> 'L'
winner('L', 'L') -> Tie
winner('V', 'R') -> 'V'
winner('V', 'L') -> 'L'
winner('V', 'S') -> 'V'
winner('V', 'P') -> 'P'
winner('V', 'V') -> Tie


This is code-golf, so shortest bytes win.



P.S: Let me know if you need more test cases.










share|improve this question











$endgroup$







  • 2




    $begingroup$
    Please change "Star Trek" to "Star Wars" in your intro ;)
    $endgroup$
    – movatica
    9 hours ago






  • 1




    $begingroup$
    This is a pretty difficult problem. Well, or I am bad at this kind of programming.
    $endgroup$
    – CrabMan
    9 hours ago










  • $begingroup$
    @CrabMan This is a bit of a difficult problem to golf. especially in practical languages.
    $endgroup$
    – Koishore Roy
    8 hours ago










  • $begingroup$
    I think prolog would be very suitable for this problem
    $endgroup$
    – CrabMan
    7 hours ago










  • $begingroup$
    Does the solution need to be the shortest one?
    $endgroup$
    – Arnauld
    7 hours ago















9












$begingroup$


Giving a challenge involving a Star Trek reference just after May the 4th may be frowned upon, but here goes.



You, Luke, Anakin, Palpatine, Yoda and Han Solo are involved in an insane tournament of Rock, Paper, Scissor, Lizard, Spock.



The catch here is that you are only allowed to use a fixed order of moves. If your order is "R", Then you have to use Rock, until you lose or win against everyone. If your order is RRV, then you have to use 2 Rocks followed by a Spock and keep repeating until you have won or lost.



Luke, Anakin, Palpatine, Yoda and Han Solo have submitted their respective orderings and you being an expert hacker got your hands on each of their orderings!



With this knowledge, you are to design your ordering for the tournament. Since everyone wants to win, you want to create an ordering such that you win the tournament by beating everyone.
But this may not be possible under all circumstances.



Incase there is a possible winning order, print that out. If there is no possible way for you to win, print out -1 (or 0 or False or "impossible")



Input: a list of 5 orders



Output: a single order or -1



Sample Input 1



R
P
S
L
V


Sample Output 1



-1


Explanation 1



No matter what you play in your first move, there will be at least one
person who beats you, hence it is not possible for you to win.


Sample Input 2



RPS
RPP
R
SRR
L


Sample Output 2



RPSP


Explanation 2



Once you play Rock in your first move, you end up beating "L" and "SRR" and
tie against the rest. This is because Lizard and Scissors lose to Rock.
When you play Paper next, you will beat "R" and tie against the remaining
2. This is because Rock loses to Paper.
When you play Scissors next, you will win against "RPP" as Scissor beats
Paper.
Finally, you will beat "RPS" with your Paper as Paper beats Rock.


Here are a list of notations (you may use any 5 literals, but please specify in your answer):



R : Rock
P : Paper
S : Scissor
L : Lizard
V : Spock


Here is a list of all possible outcomes:



winner('S', 'P') -> 'S'
winner('S', 'R') -> 'R'
winner('S', 'V') -> 'V'
winner('S', 'L') -> 'S'
winner('S', 'S') -> Tie
winner('P', 'R') -> 'P'
winner('P', 'V') -> 'P'
winner('P', 'L') -> 'L'
winner('P', 'S') -> 'S'
winner('P', 'P') -> Tie
winner('R', 'V') -> 'V'
winner('R', 'L') -> 'R'
winner('R', 'S') -> 'R'
winner('R', 'P') -> 'P'
winner('R', 'R') -> Tie
winner('L', 'R') -> 'R'
winner('L', 'V') -> 'L'
winner('L', 'S') -> 'S'
winner('L', 'P') -> 'L'
winner('L', 'L') -> Tie
winner('V', 'R') -> 'V'
winner('V', 'L') -> 'L'
winner('V', 'S') -> 'V'
winner('V', 'P') -> 'P'
winner('V', 'V') -> Tie


This is code-golf, so shortest bytes win.



P.S: Let me know if you need more test cases.










share|improve this question











$endgroup$







  • 2




    $begingroup$
    Please change "Star Trek" to "Star Wars" in your intro ;)
    $endgroup$
    – movatica
    9 hours ago






  • 1




    $begingroup$
    This is a pretty difficult problem. Well, or I am bad at this kind of programming.
    $endgroup$
    – CrabMan
    9 hours ago










  • $begingroup$
    @CrabMan This is a bit of a difficult problem to golf. especially in practical languages.
    $endgroup$
    – Koishore Roy
    8 hours ago










  • $begingroup$
    I think prolog would be very suitable for this problem
    $endgroup$
    – CrabMan
    7 hours ago










  • $begingroup$
    Does the solution need to be the shortest one?
    $endgroup$
    – Arnauld
    7 hours ago













9












9








9





$begingroup$


Giving a challenge involving a Star Trek reference just after May the 4th may be frowned upon, but here goes.



You, Luke, Anakin, Palpatine, Yoda and Han Solo are involved in an insane tournament of Rock, Paper, Scissor, Lizard, Spock.



The catch here is that you are only allowed to use a fixed order of moves. If your order is "R", Then you have to use Rock, until you lose or win against everyone. If your order is RRV, then you have to use 2 Rocks followed by a Spock and keep repeating until you have won or lost.



Luke, Anakin, Palpatine, Yoda and Han Solo have submitted their respective orderings and you being an expert hacker got your hands on each of their orderings!



With this knowledge, you are to design your ordering for the tournament. Since everyone wants to win, you want to create an ordering such that you win the tournament by beating everyone.
But this may not be possible under all circumstances.



Incase there is a possible winning order, print that out. If there is no possible way for you to win, print out -1 (or 0 or False or "impossible")



Input: a list of 5 orders



Output: a single order or -1



Sample Input 1



R
P
S
L
V


Sample Output 1



-1


Explanation 1



No matter what you play in your first move, there will be at least one
person who beats you, hence it is not possible for you to win.


Sample Input 2



RPS
RPP
R
SRR
L


Sample Output 2



RPSP


Explanation 2



Once you play Rock in your first move, you end up beating "L" and "SRR" and
tie against the rest. This is because Lizard and Scissors lose to Rock.
When you play Paper next, you will beat "R" and tie against the remaining
2. This is because Rock loses to Paper.
When you play Scissors next, you will win against "RPP" as Scissor beats
Paper.
Finally, you will beat "RPS" with your Paper as Paper beats Rock.


Here are a list of notations (you may use any 5 literals, but please specify in your answer):



R : Rock
P : Paper
S : Scissor
L : Lizard
V : Spock


Here is a list of all possible outcomes:



winner('S', 'P') -> 'S'
winner('S', 'R') -> 'R'
winner('S', 'V') -> 'V'
winner('S', 'L') -> 'S'
winner('S', 'S') -> Tie
winner('P', 'R') -> 'P'
winner('P', 'V') -> 'P'
winner('P', 'L') -> 'L'
winner('P', 'S') -> 'S'
winner('P', 'P') -> Tie
winner('R', 'V') -> 'V'
winner('R', 'L') -> 'R'
winner('R', 'S') -> 'R'
winner('R', 'P') -> 'P'
winner('R', 'R') -> Tie
winner('L', 'R') -> 'R'
winner('L', 'V') -> 'L'
winner('L', 'S') -> 'S'
winner('L', 'P') -> 'L'
winner('L', 'L') -> Tie
winner('V', 'R') -> 'V'
winner('V', 'L') -> 'L'
winner('V', 'S') -> 'V'
winner('V', 'P') -> 'P'
winner('V', 'V') -> Tie


This is code-golf, so shortest bytes win.



P.S: Let me know if you need more test cases.










share|improve this question











$endgroup$




Giving a challenge involving a Star Trek reference just after May the 4th may be frowned upon, but here goes.



You, Luke, Anakin, Palpatine, Yoda and Han Solo are involved in an insane tournament of Rock, Paper, Scissor, Lizard, Spock.



The catch here is that you are only allowed to use a fixed order of moves. If your order is "R", Then you have to use Rock, until you lose or win against everyone. If your order is RRV, then you have to use 2 Rocks followed by a Spock and keep repeating until you have won or lost.



Luke, Anakin, Palpatine, Yoda and Han Solo have submitted their respective orderings and you being an expert hacker got your hands on each of their orderings!



With this knowledge, you are to design your ordering for the tournament. Since everyone wants to win, you want to create an ordering such that you win the tournament by beating everyone.
But this may not be possible under all circumstances.



Incase there is a possible winning order, print that out. If there is no possible way for you to win, print out -1 (or 0 or False or "impossible")



Input: a list of 5 orders



Output: a single order or -1



Sample Input 1



R
P
S
L
V


Sample Output 1



-1


Explanation 1



No matter what you play in your first move, there will be at least one
person who beats you, hence it is not possible for you to win.


Sample Input 2



RPS
RPP
R
SRR
L


Sample Output 2



RPSP


Explanation 2



Once you play Rock in your first move, you end up beating "L" and "SRR" and
tie against the rest. This is because Lizard and Scissors lose to Rock.
When you play Paper next, you will beat "R" and tie against the remaining
2. This is because Rock loses to Paper.
When you play Scissors next, you will win against "RPP" as Scissor beats
Paper.
Finally, you will beat "RPS" with your Paper as Paper beats Rock.


Here are a list of notations (you may use any 5 literals, but please specify in your answer):



R : Rock
P : Paper
S : Scissor
L : Lizard
V : Spock


Here is a list of all possible outcomes:



winner('S', 'P') -> 'S'
winner('S', 'R') -> 'R'
winner('S', 'V') -> 'V'
winner('S', 'L') -> 'S'
winner('S', 'S') -> Tie
winner('P', 'R') -> 'P'
winner('P', 'V') -> 'P'
winner('P', 'L') -> 'L'
winner('P', 'S') -> 'S'
winner('P', 'P') -> Tie
winner('R', 'V') -> 'V'
winner('R', 'L') -> 'R'
winner('R', 'S') -> 'R'
winner('R', 'P') -> 'P'
winner('R', 'R') -> Tie
winner('L', 'R') -> 'R'
winner('L', 'V') -> 'L'
winner('L', 'S') -> 'S'
winner('L', 'P') -> 'L'
winner('L', 'L') -> Tie
winner('V', 'R') -> 'V'
winner('V', 'L') -> 'L'
winner('V', 'S') -> 'V'
winner('V', 'P') -> 'P'
winner('V', 'V') -> Tie


This is code-golf, so shortest bytes win.



P.S: Let me know if you need more test cases.







code-golf






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited 7 hours ago









Shaggy

19.3k21768




19.3k21768










asked 11 hours ago









Koishore RoyKoishore Roy

684212




684212







  • 2




    $begingroup$
    Please change "Star Trek" to "Star Wars" in your intro ;)
    $endgroup$
    – movatica
    9 hours ago






  • 1




    $begingroup$
    This is a pretty difficult problem. Well, or I am bad at this kind of programming.
    $endgroup$
    – CrabMan
    9 hours ago










  • $begingroup$
    @CrabMan This is a bit of a difficult problem to golf. especially in practical languages.
    $endgroup$
    – Koishore Roy
    8 hours ago










  • $begingroup$
    I think prolog would be very suitable for this problem
    $endgroup$
    – CrabMan
    7 hours ago










  • $begingroup$
    Does the solution need to be the shortest one?
    $endgroup$
    – Arnauld
    7 hours ago












  • 2




    $begingroup$
    Please change "Star Trek" to "Star Wars" in your intro ;)
    $endgroup$
    – movatica
    9 hours ago






  • 1




    $begingroup$
    This is a pretty difficult problem. Well, or I am bad at this kind of programming.
    $endgroup$
    – CrabMan
    9 hours ago










  • $begingroup$
    @CrabMan This is a bit of a difficult problem to golf. especially in practical languages.
    $endgroup$
    – Koishore Roy
    8 hours ago










  • $begingroup$
    I think prolog would be very suitable for this problem
    $endgroup$
    – CrabMan
    7 hours ago










  • $begingroup$
    Does the solution need to be the shortest one?
    $endgroup$
    – Arnauld
    7 hours ago







2




2




$begingroup$
Please change "Star Trek" to "Star Wars" in your intro ;)
$endgroup$
– movatica
9 hours ago




$begingroup$
Please change "Star Trek" to "Star Wars" in your intro ;)
$endgroup$
– movatica
9 hours ago




1




1




$begingroup$
This is a pretty difficult problem. Well, or I am bad at this kind of programming.
$endgroup$
– CrabMan
9 hours ago




$begingroup$
This is a pretty difficult problem. Well, or I am bad at this kind of programming.
$endgroup$
– CrabMan
9 hours ago












$begingroup$
@CrabMan This is a bit of a difficult problem to golf. especially in practical languages.
$endgroup$
– Koishore Roy
8 hours ago




$begingroup$
@CrabMan This is a bit of a difficult problem to golf. especially in practical languages.
$endgroup$
– Koishore Roy
8 hours ago












$begingroup$
I think prolog would be very suitable for this problem
$endgroup$
– CrabMan
7 hours ago




$begingroup$
I think prolog would be very suitable for this problem
$endgroup$
– CrabMan
7 hours ago












$begingroup$
Does the solution need to be the shortest one?
$endgroup$
– Arnauld
7 hours ago




$begingroup$
Does the solution need to be the shortest one?
$endgroup$
– Arnauld
7 hours ago










3 Answers
3






active

oldest

votes


















2












$begingroup$

JavaScript (ES6),  122  115 bytes



Takes input as an array of strings of digits, with:




  • $0$ = Scissors


  • $1$ = Paper


  • $2$ = Rock


  • $3$ = Lizard


  • $4$ = Spock

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=>(d=a[m.length%a.length]-x)?(d+5)%5&1?0:o=1: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.



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:



$$
beginarrayc
& textS & textP & textR & textL & textV\
& 0 & 1 & 2 & 3 & 4\
hline
textS 0 & - & colorgreen1 & colorred2 & colorgreen3 & colorred4\
textP 1 & colorred4 & - & colorgreen1 & colorred2 & colorgreen3\
textR 2 & colorgreen3 & colorred4 & - & colorgreen1 & colorred2\
textL 3 & colorred2 & colorgreen3 & colorred4 & - & colorgreen1\
textV 4 & colorgreen1 & colorred2 & colorgreen3 & colorred4 & -
endarray
$$



Commented



f = ( // f = 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
b = // b[] = array of remaining opponents after the move x
a.filter(s => // for each entry s in a[]:
( d = // define d as the difference between
s[m.length % s.length] // the next move of the current opponent
- x // and x
) ? // if d is not equal to 0:
(d + 5) % 5 & 1 ? // if we win:
0 // remove this opponent
: // else (we lose):
o = 1 // keep this opponent and set o to 1
: // else (this is a draw):
1 // keep this opponent (but don't set o to 1)
) // 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
|| // 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





share|improve this answer











$endgroup$












  • $begingroup$
    your code fails for the test case: test(['P','P','S','P','P']) The answer should be "SR" or "SV".
    $endgroup$
    – Koishore Roy
    7 hours ago











  • $begingroup$
    @KoishoreRoy Now fixed.
    $endgroup$
    – Arnauld
    5 hours ago


















2












$begingroup$


R, 215 bytes





function(L)m = matrix(rep(0:2,1:3),5,5);m[1,4]=m[2,5]=1
v=as.matrix(expand.grid(replicate(n<-sum(lengths(L)),1:5,F)))
v[which(apply(v,1,function(z)all(sapply(L,function(x,y)r=m[cbind(x,y)];r[r>0][1]<2,z)))>0),]



Try it online!



If a solution exists, it outputs one or several solutions. If there is no solution, it outputs an empty matrix (only column names). 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



 Var1 Var2 Var3 Var4
[1,] 1 4 2 4
[2,] 1 4 2 5


corresponding to the solutions RLSL and RLSV.



For the second test case, the output is



 Var1 Var2 Var3 Var4


i.e. an empty matrix, meaning that there is no solution.



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.






share|improve this answer









$endgroup$




















    0












    $begingroup$

    Emacs Lisp, 730 bytes



    (require 'cl-extra)
    (require 'seq)
    (defun N (g) (length (nth 1 g)))
    (defun M (g) (mapcar (lambda (o) (nth (% (N g) (length o)) o)) (car g)))
    (defun B (x y) (or (eq (% (1+ x) 5) y) (eq (% (+ y 2) 5) x)))
    (defun S (g) (seq-filter (lambda (m) (not (seq-some (lambda (v) (B v m)) (M g)))) '(0 1 2 3 4)))
    (defun F (g) (cond ((null (car g)) (reverse (nth 1 g))) ((null (S g)) nil) ((>= (nth 3 g) (seq-reduce (lambda (x y) (calc-eval "lcm($,$$)" 'raw x y)) (mapcar 'length (car g)) 1)) nil) (t (cl-some (lambda (m) (F (let ((r (seq-filter 'identity (mapcar* (lambda (v o) (and (not (B m v)) o)) (M g) (car g))))) (list r (cons m (nth 1 g)) (1+ (N g)) (if (eq (car g) r) (1+ (nth 3 g)) 0))))) (S g)))))
    (defun Z (s) (F (list s () 0 0)))


    I didn't find an online interpreter of Emacs Lisp :( If you have Emacs installed, you can copy code into a .el file, copy some testing lines below



    ;; 0 = rock, 1 = lizard; 2 = spock;
    ;; 3 = scissors; 4 = paper
    (print (Z '((0) (1) (2) (3) (4))))
    ; output: nil
    (print (Z '((0) (4) (3) (1))))
    ; output: nil
    (print (Z '((0 4 3) (0 4 4) (0) (3 0 0) (1))))
    ; output: (0 4 3 0 1)
    (print (Z '((4) (4) (3) (4) (4))))
    ; output: (3 0)
    (print (Z '((4 3 2 1 0) (2 1 0 4 3))))
    ; output: (1)
    (print (Z '((2) (2) (3) (0) (2) (3) (0) (0))))
    ; output: (2 1)
    (print (Z '((2) (2 0) (3) (0) (2 1) (3) (0) (0))))
    ; output: nil


    and run it $ emacs --script filename.el.



    How it works



    My program does depth first search with sometimes figuring out that it's impossible to win and terminating the branch it's on.



    You can see full explanation in the unshortened version of the code:



    (require 'seq)
    (require 'cl-extra)

    ;; This program does depth first search with sometimes figuring out
    ;; that it's impossible to win and terminating the branch it's on.
    ;;

    ;; A move is a number from 0 to 4.
    ;; https://d3qdvvkm3r2z1i.cloudfront.net/media/catalog/product/cache/1/image/1800x/6b9ffbf72458f4fd2d3cb995d92e8889/r/o/rockpaperscissorslizardspock_newthumb.png
    ;; this is a nice visualization of what beats what.
    ;; Rock = 0, lizard = 1, spock = 2, scissors = 3, paper = 4.

    (defun beats (x y) "Calculates whether move x beats move y"
    (or (eq (% (1+ x) 5) y)
    (eq (% (+ y 2) 5) x)))

    ;; A gamestate is a list with the following elements:
    (defun get-orders (gamestate)
    "A list of orders of players who haven't lost yet. Each order is a list of moves.
    For example, ((2) (2 0) (3) (0) (2 1) (3) (0) (0)) is a valid orders list.
    This function gets orders from the gamestate."
    (car gamestate))

    ;; At index 1 of the gamestate lies a list of all moves we have made so far in reverse order
    ;; (because lists are singly linked, we can't push back quickly)
    (defun get-num-moves-done (gamestate)
    "Returns the number of moves the player has done so far"
    (length (nth 1 gamestate)))

    (defun get-rounds-since-last-elim (gamestate)
    "The last element of a gamestate is the number of rounds passed since an opponent
    was eliminated. We use this to determine if it's possible to win from current
    gamestate (more about it later)."
    (nth 2 gamestate))

    ;; next go some utility functions
    ;; you can skip their descriptions, they are not very interesting
    ;; I suggest you skip until the next ;; comment

    (defun get-next-move (order num-rounds-done)
    "Arguments: an order (e.g. (1 0 1)); how many rounds have passed total.
    Returns the move this opponent will make next"
    (nth (% num-rounds-done (length order)) order))

    (defun moves-of-opponents-this-round (gamestate)
    "Returns a list of moves the opponents will make next"
    (mapcar (lambda (order) (get-next-move order (get-num-moves-done gamestate)))
    (get-orders gamestate)))

    (defun is-non-losing (move opponents-moves)
    "Calculates if we lose right away by playing move against opponents-moves"
    (not (seq-some (lambda (opponent-move) (beats opponent-move move))
    opponents-moves)))

    (defun non-losing-moves (gamestate)
    "Returns a list of moves which we can play without losing right away."
    (seq-filter
    (lambda (move) (is-non-losing move (moves-of-opponents-this-round gamestate)))
    '(0 1 2 3 4)))

    (defun advance-gamestate (gamestate move)
    "If this move in this gamestate is non-losing, returns the next game state"
    (let ((new-orders (seq-filter
    'identity (mapcar* (lambda (opp-move order)
    (and (not (beats move opp-move)) order))
    (moves-of-opponents-this-round gamestate)
    (get-orders gamestate)))))
    (list new-orders
    (cons move (nth 1 gamestate))
    (if (eq (get-orders gamestate) new-orders) (1+ (get-rounds-since-last-elim gamestate)) 0))))

    ;; How do we prevent our depth first search from continuing without halting?
    ;; Suppose 3 players (except us) are still in the game and they have orders of lengths a, b, c
    ;; In this situation, if least_common_multiple(a, b, c) rounds pass without an elimination
    ;; we will be in the same situation (because they will be playing the same moves they played
    ;; lcm(a, b, c) rounds ago)
    ;; therefore the course of play that we took was not an optimal one - if it is even possible
    ;; to win from this position, then it is possible to win from an earlier position
    ;; before we made this full cycle

    (defun get-cycle-len (gamestate)
    "Returns a number of rounds which is enough for the situation to become the same
    if the game goes this long without an elimination."
    (seq-reduce (lambda (x y) (calc-eval "lcm($,$$)" 'raw x y))
    (mapcar 'length (get-orders gamestate)) 1))

    (defun unwinnable-cycle (gamestate)
    "Using the aforementioned information, returns t if we are in such a
    suboptimal course of play."
    (>= (get-rounds-since-last-elim gamestate) (get-cycle-len gamestate)))

    (defun find-good-moves (gamestate)
    "Given gamestate, if it's possible to win
    returns a list of moves, containing all moves already done + additional moves which lead to win.
    Otherwise returns nil"
    (cond ((null (get-orders gamestate)) ; if no opponents left, we won, return the list of moves
    (reverse (nth 1 gamestate)))
    ((null (non-losing-moves gamestate)) ; if no non-losing moves available, this gamestate
    nil) ; doesn't lead to a win, return nil
    ((unwinnable-cycle gamestate) ; either it's impossible to win, or
    nil) ; it's possible to win from an earlier position, return nil
    (t (cl-some (lambda (move) ; otherwise return the first non-losing move which leads
    (find-good-moves (advance-gamestate gamestate move))) ; to a non-nil result
    (non-losing-moves gamestate)))))

    (defun make-initial-gamestate (orders)
    "Given an orders list, create initial gamestate"
    (list orders () 0))





    share|improve this answer








    New contributor




    CrabMan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.






    $endgroup$













      Your Answer






      StackExchange.ifUsing("editor", function ()
      StackExchange.using("externalEditor", function ()
      StackExchange.using("snippets", function ()
      StackExchange.snippets.init();
      );
      );
      , "code-snippets");

      StackExchange.ready(function()
      var channelOptions =
      tags: "".split(" "),
      id: "200"
      ;
      initTagRenderer("".split(" "), "".split(" "), channelOptions);

      StackExchange.using("externalEditor", function()
      // Have to fire editor after snippets, if snippets enabled
      if (StackExchange.settings.snippets.snippetsEnabled)
      StackExchange.using("snippets", function()
      createEditor();
      );

      else
      createEditor();

      );

      function createEditor()
      StackExchange.prepareEditor(
      heartbeatType: 'answer',
      autoActivateHeartbeat: false,
      convertImagesToLinks: false,
      noModals: true,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: null,
      bindNavPrevention: true,
      postfix: "",
      imageUploader:
      brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
      contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
      allowUrls: true
      ,
      onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      );



      );













      draft saved

      draft discarded


















      StackExchange.ready(
      function ()
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f185203%2frock-paper-scissors-lizard-spock-tournament%23new-answer', 'question_page');

      );

      Post as a guest















      Required, but never shown

























      3 Answers
      3






      active

      oldest

      votes








      3 Answers
      3






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes









      2












      $begingroup$

      JavaScript (ES6),  122  115 bytes



      Takes input as an array of strings of digits, with:




      • $0$ = Scissors


      • $1$ = Paper


      • $2$ = Rock


      • $3$ = Lizard


      • $4$ = Spock

      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=>(d=a[m.length%a.length]-x)?(d+5)%5&1?0:o=1: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.



      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:



      $$
      beginarrayc
      & textS & textP & textR & textL & textV\
      & 0 & 1 & 2 & 3 & 4\
      hline
      textS 0 & - & colorgreen1 & colorred2 & colorgreen3 & colorred4\
      textP 1 & colorred4 & - & colorgreen1 & colorred2 & colorgreen3\
      textR 2 & colorgreen3 & colorred4 & - & colorgreen1 & colorred2\
      textL 3 & colorred2 & colorgreen3 & colorred4 & - & colorgreen1\
      textV 4 & colorgreen1 & colorred2 & colorgreen3 & colorred4 & -
      endarray
      $$



      Commented



      f = ( // f = 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
      b = // b[] = array of remaining opponents after the move x
      a.filter(s => // for each entry s in a[]:
      ( d = // define d as the difference between
      s[m.length % s.length] // the next move of the current opponent
      - x // and x
      ) ? // if d is not equal to 0:
      (d + 5) % 5 & 1 ? // if we win:
      0 // remove this opponent
      : // else (we lose):
      o = 1 // keep this opponent and set o to 1
      : // else (this is a draw):
      1 // keep this opponent (but don't set o to 1)
      ) // 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
      || // 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





      share|improve this answer











      $endgroup$












      • $begingroup$
        your code fails for the test case: test(['P','P','S','P','P']) The answer should be "SR" or "SV".
        $endgroup$
        – Koishore Roy
        7 hours ago











      • $begingroup$
        @KoishoreRoy Now fixed.
        $endgroup$
        – Arnauld
        5 hours ago















      2












      $begingroup$

      JavaScript (ES6),  122  115 bytes



      Takes input as an array of strings of digits, with:




      • $0$ = Scissors


      • $1$ = Paper


      • $2$ = Rock


      • $3$ = Lizard


      • $4$ = Spock

      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=>(d=a[m.length%a.length]-x)?(d+5)%5&1?0:o=1: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.



      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:



      $$
      beginarrayc
      & textS & textP & textR & textL & textV\
      & 0 & 1 & 2 & 3 & 4\
      hline
      textS 0 & - & colorgreen1 & colorred2 & colorgreen3 & colorred4\
      textP 1 & colorred4 & - & colorgreen1 & colorred2 & colorgreen3\
      textR 2 & colorgreen3 & colorred4 & - & colorgreen1 & colorred2\
      textL 3 & colorred2 & colorgreen3 & colorred4 & - & colorgreen1\
      textV 4 & colorgreen1 & colorred2 & colorgreen3 & colorred4 & -
      endarray
      $$



      Commented



      f = ( // f = 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
      b = // b[] = array of remaining opponents after the move x
      a.filter(s => // for each entry s in a[]:
      ( d = // define d as the difference between
      s[m.length % s.length] // the next move of the current opponent
      - x // and x
      ) ? // if d is not equal to 0:
      (d + 5) % 5 & 1 ? // if we win:
      0 // remove this opponent
      : // else (we lose):
      o = 1 // keep this opponent and set o to 1
      : // else (this is a draw):
      1 // keep this opponent (but don't set o to 1)
      ) // 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
      || // 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





      share|improve this answer











      $endgroup$












      • $begingroup$
        your code fails for the test case: test(['P','P','S','P','P']) The answer should be "SR" or "SV".
        $endgroup$
        – Koishore Roy
        7 hours ago











      • $begingroup$
        @KoishoreRoy Now fixed.
        $endgroup$
        – Arnauld
        5 hours ago













      2












      2








      2





      $begingroup$

      JavaScript (ES6),  122  115 bytes



      Takes input as an array of strings of digits, with:




      • $0$ = Scissors


      • $1$ = Paper


      • $2$ = Rock


      • $3$ = Lizard


      • $4$ = Spock

      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=>(d=a[m.length%a.length]-x)?(d+5)%5&1?0:o=1: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.



      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:



      $$
      beginarrayc
      & textS & textP & textR & textL & textV\
      & 0 & 1 & 2 & 3 & 4\
      hline
      textS 0 & - & colorgreen1 & colorred2 & colorgreen3 & colorred4\
      textP 1 & colorred4 & - & colorgreen1 & colorred2 & colorgreen3\
      textR 2 & colorgreen3 & colorred4 & - & colorgreen1 & colorred2\
      textL 3 & colorred2 & colorgreen3 & colorred4 & - & colorgreen1\
      textV 4 & colorgreen1 & colorred2 & colorgreen3 & colorred4 & -
      endarray
      $$



      Commented



      f = ( // f = 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
      b = // b[] = array of remaining opponents after the move x
      a.filter(s => // for each entry s in a[]:
      ( d = // define d as the difference between
      s[m.length % s.length] // the next move of the current opponent
      - x // and x
      ) ? // if d is not equal to 0:
      (d + 5) % 5 & 1 ? // if we win:
      0 // remove this opponent
      : // else (we lose):
      o = 1 // keep this opponent and set o to 1
      : // else (this is a draw):
      1 // keep this opponent (but don't set o to 1)
      ) // 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
      || // 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





      share|improve this answer











      $endgroup$



      JavaScript (ES6),  122  115 bytes



      Takes input as an array of strings of digits, with:




      • $0$ = Scissors


      • $1$ = Paper


      • $2$ = Rock


      • $3$ = Lizard


      • $4$ = Spock

      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=>(d=a[m.length%a.length]-x)?(d+5)%5&1?0:o=1: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.



      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:



      $$
      beginarrayc
      & textS & textP & textR & textL & textV\
      & 0 & 1 & 2 & 3 & 4\
      hline
      textS 0 & - & colorgreen1 & colorred2 & colorgreen3 & colorred4\
      textP 1 & colorred4 & - & colorgreen1 & colorred2 & colorgreen3\
      textR 2 & colorgreen3 & colorred4 & - & colorgreen1 & colorred2\
      textL 3 & colorred2 & colorgreen3 & colorred4 & - & colorgreen1\
      textV 4 & colorgreen1 & colorred2 & colorgreen3 & colorred4 & -
      endarray
      $$



      Commented



      f = ( // f = 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
      b = // b[] = array of remaining opponents after the move x
      a.filter(s => // for each entry s in a[]:
      ( d = // define d as the difference between
      s[m.length % s.length] // the next move of the current opponent
      - x // and x
      ) ? // if d is not equal to 0:
      (d + 5) % 5 & 1 ? // if we win:
      0 // remove this opponent
      : // else (we lose):
      o = 1 // keep this opponent and set o to 1
      : // else (this is a draw):
      1 // keep this opponent (but don't set o to 1)
      ) // 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
      || // 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






      share|improve this answer














      share|improve this answer



      share|improve this answer








      edited 4 hours ago

























      answered 7 hours ago









      ArnauldArnauld

      83k798340




      83k798340











      • $begingroup$
        your code fails for the test case: test(['P','P','S','P','P']) The answer should be "SR" or "SV".
        $endgroup$
        – Koishore Roy
        7 hours ago











      • $begingroup$
        @KoishoreRoy Now fixed.
        $endgroup$
        – Arnauld
        5 hours ago
















      • $begingroup$
        your code fails for the test case: test(['P','P','S','P','P']) The answer should be "SR" or "SV".
        $endgroup$
        – Koishore Roy
        7 hours ago











      • $begingroup$
        @KoishoreRoy Now fixed.
        $endgroup$
        – Arnauld
        5 hours ago















      $begingroup$
      your code fails for the test case: test(['P','P','S','P','P']) The answer should be "SR" or "SV".
      $endgroup$
      – Koishore Roy
      7 hours ago





      $begingroup$
      your code fails for the test case: test(['P','P','S','P','P']) The answer should be "SR" or "SV".
      $endgroup$
      – Koishore Roy
      7 hours ago













      $begingroup$
      @KoishoreRoy Now fixed.
      $endgroup$
      – Arnauld
      5 hours ago




      $begingroup$
      @KoishoreRoy Now fixed.
      $endgroup$
      – Arnauld
      5 hours ago











      2












      $begingroup$


      R, 215 bytes





      function(L)m = matrix(rep(0:2,1:3),5,5);m[1,4]=m[2,5]=1
      v=as.matrix(expand.grid(replicate(n<-sum(lengths(L)),1:5,F)))
      v[which(apply(v,1,function(z)all(sapply(L,function(x,y)r=m[cbind(x,y)];r[r>0][1]<2,z)))>0),]



      Try it online!



      If a solution exists, it outputs one or several solutions. If there is no solution, it outputs an empty matrix (only column names). 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



       Var1 Var2 Var3 Var4
      [1,] 1 4 2 4
      [2,] 1 4 2 5


      corresponding to the solutions RLSL and RLSV.



      For the second test case, the output is



       Var1 Var2 Var3 Var4


      i.e. an empty matrix, meaning that there is no solution.



      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.






      share|improve this answer









      $endgroup$

















        2












        $begingroup$


        R, 215 bytes





        function(L)m = matrix(rep(0:2,1:3),5,5);m[1,4]=m[2,5]=1
        v=as.matrix(expand.grid(replicate(n<-sum(lengths(L)),1:5,F)))
        v[which(apply(v,1,function(z)all(sapply(L,function(x,y)r=m[cbind(x,y)];r[r>0][1]<2,z)))>0),]



        Try it online!



        If a solution exists, it outputs one or several solutions. If there is no solution, it outputs an empty matrix (only column names). 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



         Var1 Var2 Var3 Var4
        [1,] 1 4 2 4
        [2,] 1 4 2 5


        corresponding to the solutions RLSL and RLSV.



        For the second test case, the output is



         Var1 Var2 Var3 Var4


        i.e. an empty matrix, meaning that there is no solution.



        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.






        share|improve this answer









        $endgroup$















          2












          2








          2





          $begingroup$


          R, 215 bytes





          function(L)m = matrix(rep(0:2,1:3),5,5);m[1,4]=m[2,5]=1
          v=as.matrix(expand.grid(replicate(n<-sum(lengths(L)),1:5,F)))
          v[which(apply(v,1,function(z)all(sapply(L,function(x,y)r=m[cbind(x,y)];r[r>0][1]<2,z)))>0),]



          Try it online!



          If a solution exists, it outputs one or several solutions. If there is no solution, it outputs an empty matrix (only column names). 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



           Var1 Var2 Var3 Var4
          [1,] 1 4 2 4
          [2,] 1 4 2 5


          corresponding to the solutions RLSL and RLSV.



          For the second test case, the output is



           Var1 Var2 Var3 Var4


          i.e. an empty matrix, meaning that there is no solution.



          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.






          share|improve this answer









          $endgroup$




          R, 215 bytes





          function(L)m = matrix(rep(0:2,1:3),5,5);m[1,4]=m[2,5]=1
          v=as.matrix(expand.grid(replicate(n<-sum(lengths(L)),1:5,F)))
          v[which(apply(v,1,function(z)all(sapply(L,function(x,y)r=m[cbind(x,y)];r[r>0][1]<2,z)))>0),]



          Try it online!



          If a solution exists, it outputs one or several solutions. If there is no solution, it outputs an empty matrix (only column names). 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



           Var1 Var2 Var3 Var4
          [1,] 1 4 2 4
          [2,] 1 4 2 5


          corresponding to the solutions RLSL and RLSV.



          For the second test case, the output is



           Var1 Var2 Var3 Var4


          i.e. an empty matrix, meaning that there is no solution.



          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.







          share|improve this answer












          share|improve this answer



          share|improve this answer










          answered 2 hours ago









          Robin RyderRobin Ryder

          1,039113




          1,039113





















              0












              $begingroup$

              Emacs Lisp, 730 bytes



              (require 'cl-extra)
              (require 'seq)
              (defun N (g) (length (nth 1 g)))
              (defun M (g) (mapcar (lambda (o) (nth (% (N g) (length o)) o)) (car g)))
              (defun B (x y) (or (eq (% (1+ x) 5) y) (eq (% (+ y 2) 5) x)))
              (defun S (g) (seq-filter (lambda (m) (not (seq-some (lambda (v) (B v m)) (M g)))) '(0 1 2 3 4)))
              (defun F (g) (cond ((null (car g)) (reverse (nth 1 g))) ((null (S g)) nil) ((>= (nth 3 g) (seq-reduce (lambda (x y) (calc-eval "lcm($,$$)" 'raw x y)) (mapcar 'length (car g)) 1)) nil) (t (cl-some (lambda (m) (F (let ((r (seq-filter 'identity (mapcar* (lambda (v o) (and (not (B m v)) o)) (M g) (car g))))) (list r (cons m (nth 1 g)) (1+ (N g)) (if (eq (car g) r) (1+ (nth 3 g)) 0))))) (S g)))))
              (defun Z (s) (F (list s () 0 0)))


              I didn't find an online interpreter of Emacs Lisp :( If you have Emacs installed, you can copy code into a .el file, copy some testing lines below



              ;; 0 = rock, 1 = lizard; 2 = spock;
              ;; 3 = scissors; 4 = paper
              (print (Z '((0) (1) (2) (3) (4))))
              ; output: nil
              (print (Z '((0) (4) (3) (1))))
              ; output: nil
              (print (Z '((0 4 3) (0 4 4) (0) (3 0 0) (1))))
              ; output: (0 4 3 0 1)
              (print (Z '((4) (4) (3) (4) (4))))
              ; output: (3 0)
              (print (Z '((4 3 2 1 0) (2 1 0 4 3))))
              ; output: (1)
              (print (Z '((2) (2) (3) (0) (2) (3) (0) (0))))
              ; output: (2 1)
              (print (Z '((2) (2 0) (3) (0) (2 1) (3) (0) (0))))
              ; output: nil


              and run it $ emacs --script filename.el.



              How it works



              My program does depth first search with sometimes figuring out that it's impossible to win and terminating the branch it's on.



              You can see full explanation in the unshortened version of the code:



              (require 'seq)
              (require 'cl-extra)

              ;; This program does depth first search with sometimes figuring out
              ;; that it's impossible to win and terminating the branch it's on.
              ;;

              ;; A move is a number from 0 to 4.
              ;; https://d3qdvvkm3r2z1i.cloudfront.net/media/catalog/product/cache/1/image/1800x/6b9ffbf72458f4fd2d3cb995d92e8889/r/o/rockpaperscissorslizardspock_newthumb.png
              ;; this is a nice visualization of what beats what.
              ;; Rock = 0, lizard = 1, spock = 2, scissors = 3, paper = 4.

              (defun beats (x y) "Calculates whether move x beats move y"
              (or (eq (% (1+ x) 5) y)
              (eq (% (+ y 2) 5) x)))

              ;; A gamestate is a list with the following elements:
              (defun get-orders (gamestate)
              "A list of orders of players who haven't lost yet. Each order is a list of moves.
              For example, ((2) (2 0) (3) (0) (2 1) (3) (0) (0)) is a valid orders list.
              This function gets orders from the gamestate."
              (car gamestate))

              ;; At index 1 of the gamestate lies a list of all moves we have made so far in reverse order
              ;; (because lists are singly linked, we can't push back quickly)
              (defun get-num-moves-done (gamestate)
              "Returns the number of moves the player has done so far"
              (length (nth 1 gamestate)))

              (defun get-rounds-since-last-elim (gamestate)
              "The last element of a gamestate is the number of rounds passed since an opponent
              was eliminated. We use this to determine if it's possible to win from current
              gamestate (more about it later)."
              (nth 2 gamestate))

              ;; next go some utility functions
              ;; you can skip their descriptions, they are not very interesting
              ;; I suggest you skip until the next ;; comment

              (defun get-next-move (order num-rounds-done)
              "Arguments: an order (e.g. (1 0 1)); how many rounds have passed total.
              Returns the move this opponent will make next"
              (nth (% num-rounds-done (length order)) order))

              (defun moves-of-opponents-this-round (gamestate)
              "Returns a list of moves the opponents will make next"
              (mapcar (lambda (order) (get-next-move order (get-num-moves-done gamestate)))
              (get-orders gamestate)))

              (defun is-non-losing (move opponents-moves)
              "Calculates if we lose right away by playing move against opponents-moves"
              (not (seq-some (lambda (opponent-move) (beats opponent-move move))
              opponents-moves)))

              (defun non-losing-moves (gamestate)
              "Returns a list of moves which we can play without losing right away."
              (seq-filter
              (lambda (move) (is-non-losing move (moves-of-opponents-this-round gamestate)))
              '(0 1 2 3 4)))

              (defun advance-gamestate (gamestate move)
              "If this move in this gamestate is non-losing, returns the next game state"
              (let ((new-orders (seq-filter
              'identity (mapcar* (lambda (opp-move order)
              (and (not (beats move opp-move)) order))
              (moves-of-opponents-this-round gamestate)
              (get-orders gamestate)))))
              (list new-orders
              (cons move (nth 1 gamestate))
              (if (eq (get-orders gamestate) new-orders) (1+ (get-rounds-since-last-elim gamestate)) 0))))

              ;; How do we prevent our depth first search from continuing without halting?
              ;; Suppose 3 players (except us) are still in the game and they have orders of lengths a, b, c
              ;; In this situation, if least_common_multiple(a, b, c) rounds pass without an elimination
              ;; we will be in the same situation (because they will be playing the same moves they played
              ;; lcm(a, b, c) rounds ago)
              ;; therefore the course of play that we took was not an optimal one - if it is even possible
              ;; to win from this position, then it is possible to win from an earlier position
              ;; before we made this full cycle

              (defun get-cycle-len (gamestate)
              "Returns a number of rounds which is enough for the situation to become the same
              if the game goes this long without an elimination."
              (seq-reduce (lambda (x y) (calc-eval "lcm($,$$)" 'raw x y))
              (mapcar 'length (get-orders gamestate)) 1))

              (defun unwinnable-cycle (gamestate)
              "Using the aforementioned information, returns t if we are in such a
              suboptimal course of play."
              (>= (get-rounds-since-last-elim gamestate) (get-cycle-len gamestate)))

              (defun find-good-moves (gamestate)
              "Given gamestate, if it's possible to win
              returns a list of moves, containing all moves already done + additional moves which lead to win.
              Otherwise returns nil"
              (cond ((null (get-orders gamestate)) ; if no opponents left, we won, return the list of moves
              (reverse (nth 1 gamestate)))
              ((null (non-losing-moves gamestate)) ; if no non-losing moves available, this gamestate
              nil) ; doesn't lead to a win, return nil
              ((unwinnable-cycle gamestate) ; either it's impossible to win, or
              nil) ; it's possible to win from an earlier position, return nil
              (t (cl-some (lambda (move) ; otherwise return the first non-losing move which leads
              (find-good-moves (advance-gamestate gamestate move))) ; to a non-nil result
              (non-losing-moves gamestate)))))

              (defun make-initial-gamestate (orders)
              "Given an orders list, create initial gamestate"
              (list orders () 0))





              share|improve this answer








              New contributor




              CrabMan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.






              $endgroup$

















                0












                $begingroup$

                Emacs Lisp, 730 bytes



                (require 'cl-extra)
                (require 'seq)
                (defun N (g) (length (nth 1 g)))
                (defun M (g) (mapcar (lambda (o) (nth (% (N g) (length o)) o)) (car g)))
                (defun B (x y) (or (eq (% (1+ x) 5) y) (eq (% (+ y 2) 5) x)))
                (defun S (g) (seq-filter (lambda (m) (not (seq-some (lambda (v) (B v m)) (M g)))) '(0 1 2 3 4)))
                (defun F (g) (cond ((null (car g)) (reverse (nth 1 g))) ((null (S g)) nil) ((>= (nth 3 g) (seq-reduce (lambda (x y) (calc-eval "lcm($,$$)" 'raw x y)) (mapcar 'length (car g)) 1)) nil) (t (cl-some (lambda (m) (F (let ((r (seq-filter 'identity (mapcar* (lambda (v o) (and (not (B m v)) o)) (M g) (car g))))) (list r (cons m (nth 1 g)) (1+ (N g)) (if (eq (car g) r) (1+ (nth 3 g)) 0))))) (S g)))))
                (defun Z (s) (F (list s () 0 0)))


                I didn't find an online interpreter of Emacs Lisp :( If you have Emacs installed, you can copy code into a .el file, copy some testing lines below



                ;; 0 = rock, 1 = lizard; 2 = spock;
                ;; 3 = scissors; 4 = paper
                (print (Z '((0) (1) (2) (3) (4))))
                ; output: nil
                (print (Z '((0) (4) (3) (1))))
                ; output: nil
                (print (Z '((0 4 3) (0 4 4) (0) (3 0 0) (1))))
                ; output: (0 4 3 0 1)
                (print (Z '((4) (4) (3) (4) (4))))
                ; output: (3 0)
                (print (Z '((4 3 2 1 0) (2 1 0 4 3))))
                ; output: (1)
                (print (Z '((2) (2) (3) (0) (2) (3) (0) (0))))
                ; output: (2 1)
                (print (Z '((2) (2 0) (3) (0) (2 1) (3) (0) (0))))
                ; output: nil


                and run it $ emacs --script filename.el.



                How it works



                My program does depth first search with sometimes figuring out that it's impossible to win and terminating the branch it's on.



                You can see full explanation in the unshortened version of the code:



                (require 'seq)
                (require 'cl-extra)

                ;; This program does depth first search with sometimes figuring out
                ;; that it's impossible to win and terminating the branch it's on.
                ;;

                ;; A move is a number from 0 to 4.
                ;; https://d3qdvvkm3r2z1i.cloudfront.net/media/catalog/product/cache/1/image/1800x/6b9ffbf72458f4fd2d3cb995d92e8889/r/o/rockpaperscissorslizardspock_newthumb.png
                ;; this is a nice visualization of what beats what.
                ;; Rock = 0, lizard = 1, spock = 2, scissors = 3, paper = 4.

                (defun beats (x y) "Calculates whether move x beats move y"
                (or (eq (% (1+ x) 5) y)
                (eq (% (+ y 2) 5) x)))

                ;; A gamestate is a list with the following elements:
                (defun get-orders (gamestate)
                "A list of orders of players who haven't lost yet. Each order is a list of moves.
                For example, ((2) (2 0) (3) (0) (2 1) (3) (0) (0)) is a valid orders list.
                This function gets orders from the gamestate."
                (car gamestate))

                ;; At index 1 of the gamestate lies a list of all moves we have made so far in reverse order
                ;; (because lists are singly linked, we can't push back quickly)
                (defun get-num-moves-done (gamestate)
                "Returns the number of moves the player has done so far"
                (length (nth 1 gamestate)))

                (defun get-rounds-since-last-elim (gamestate)
                "The last element of a gamestate is the number of rounds passed since an opponent
                was eliminated. We use this to determine if it's possible to win from current
                gamestate (more about it later)."
                (nth 2 gamestate))

                ;; next go some utility functions
                ;; you can skip their descriptions, they are not very interesting
                ;; I suggest you skip until the next ;; comment

                (defun get-next-move (order num-rounds-done)
                "Arguments: an order (e.g. (1 0 1)); how many rounds have passed total.
                Returns the move this opponent will make next"
                (nth (% num-rounds-done (length order)) order))

                (defun moves-of-opponents-this-round (gamestate)
                "Returns a list of moves the opponents will make next"
                (mapcar (lambda (order) (get-next-move order (get-num-moves-done gamestate)))
                (get-orders gamestate)))

                (defun is-non-losing (move opponents-moves)
                "Calculates if we lose right away by playing move against opponents-moves"
                (not (seq-some (lambda (opponent-move) (beats opponent-move move))
                opponents-moves)))

                (defun non-losing-moves (gamestate)
                "Returns a list of moves which we can play without losing right away."
                (seq-filter
                (lambda (move) (is-non-losing move (moves-of-opponents-this-round gamestate)))
                '(0 1 2 3 4)))

                (defun advance-gamestate (gamestate move)
                "If this move in this gamestate is non-losing, returns the next game state"
                (let ((new-orders (seq-filter
                'identity (mapcar* (lambda (opp-move order)
                (and (not (beats move opp-move)) order))
                (moves-of-opponents-this-round gamestate)
                (get-orders gamestate)))))
                (list new-orders
                (cons move (nth 1 gamestate))
                (if (eq (get-orders gamestate) new-orders) (1+ (get-rounds-since-last-elim gamestate)) 0))))

                ;; How do we prevent our depth first search from continuing without halting?
                ;; Suppose 3 players (except us) are still in the game and they have orders of lengths a, b, c
                ;; In this situation, if least_common_multiple(a, b, c) rounds pass without an elimination
                ;; we will be in the same situation (because they will be playing the same moves they played
                ;; lcm(a, b, c) rounds ago)
                ;; therefore the course of play that we took was not an optimal one - if it is even possible
                ;; to win from this position, then it is possible to win from an earlier position
                ;; before we made this full cycle

                (defun get-cycle-len (gamestate)
                "Returns a number of rounds which is enough for the situation to become the same
                if the game goes this long without an elimination."
                (seq-reduce (lambda (x y) (calc-eval "lcm($,$$)" 'raw x y))
                (mapcar 'length (get-orders gamestate)) 1))

                (defun unwinnable-cycle (gamestate)
                "Using the aforementioned information, returns t if we are in such a
                suboptimal course of play."
                (>= (get-rounds-since-last-elim gamestate) (get-cycle-len gamestate)))

                (defun find-good-moves (gamestate)
                "Given gamestate, if it's possible to win
                returns a list of moves, containing all moves already done + additional moves which lead to win.
                Otherwise returns nil"
                (cond ((null (get-orders gamestate)) ; if no opponents left, we won, return the list of moves
                (reverse (nth 1 gamestate)))
                ((null (non-losing-moves gamestate)) ; if no non-losing moves available, this gamestate
                nil) ; doesn't lead to a win, return nil
                ((unwinnable-cycle gamestate) ; either it's impossible to win, or
                nil) ; it's possible to win from an earlier position, return nil
                (t (cl-some (lambda (move) ; otherwise return the first non-losing move which leads
                (find-good-moves (advance-gamestate gamestate move))) ; to a non-nil result
                (non-losing-moves gamestate)))))

                (defun make-initial-gamestate (orders)
                "Given an orders list, create initial gamestate"
                (list orders () 0))





                share|improve this answer








                New contributor




                CrabMan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                Check out our Code of Conduct.






                $endgroup$















                  0












                  0








                  0





                  $begingroup$

                  Emacs Lisp, 730 bytes



                  (require 'cl-extra)
                  (require 'seq)
                  (defun N (g) (length (nth 1 g)))
                  (defun M (g) (mapcar (lambda (o) (nth (% (N g) (length o)) o)) (car g)))
                  (defun B (x y) (or (eq (% (1+ x) 5) y) (eq (% (+ y 2) 5) x)))
                  (defun S (g) (seq-filter (lambda (m) (not (seq-some (lambda (v) (B v m)) (M g)))) '(0 1 2 3 4)))
                  (defun F (g) (cond ((null (car g)) (reverse (nth 1 g))) ((null (S g)) nil) ((>= (nth 3 g) (seq-reduce (lambda (x y) (calc-eval "lcm($,$$)" 'raw x y)) (mapcar 'length (car g)) 1)) nil) (t (cl-some (lambda (m) (F (let ((r (seq-filter 'identity (mapcar* (lambda (v o) (and (not (B m v)) o)) (M g) (car g))))) (list r (cons m (nth 1 g)) (1+ (N g)) (if (eq (car g) r) (1+ (nth 3 g)) 0))))) (S g)))))
                  (defun Z (s) (F (list s () 0 0)))


                  I didn't find an online interpreter of Emacs Lisp :( If you have Emacs installed, you can copy code into a .el file, copy some testing lines below



                  ;; 0 = rock, 1 = lizard; 2 = spock;
                  ;; 3 = scissors; 4 = paper
                  (print (Z '((0) (1) (2) (3) (4))))
                  ; output: nil
                  (print (Z '((0) (4) (3) (1))))
                  ; output: nil
                  (print (Z '((0 4 3) (0 4 4) (0) (3 0 0) (1))))
                  ; output: (0 4 3 0 1)
                  (print (Z '((4) (4) (3) (4) (4))))
                  ; output: (3 0)
                  (print (Z '((4 3 2 1 0) (2 1 0 4 3))))
                  ; output: (1)
                  (print (Z '((2) (2) (3) (0) (2) (3) (0) (0))))
                  ; output: (2 1)
                  (print (Z '((2) (2 0) (3) (0) (2 1) (3) (0) (0))))
                  ; output: nil


                  and run it $ emacs --script filename.el.



                  How it works



                  My program does depth first search with sometimes figuring out that it's impossible to win and terminating the branch it's on.



                  You can see full explanation in the unshortened version of the code:



                  (require 'seq)
                  (require 'cl-extra)

                  ;; This program does depth first search with sometimes figuring out
                  ;; that it's impossible to win and terminating the branch it's on.
                  ;;

                  ;; A move is a number from 0 to 4.
                  ;; https://d3qdvvkm3r2z1i.cloudfront.net/media/catalog/product/cache/1/image/1800x/6b9ffbf72458f4fd2d3cb995d92e8889/r/o/rockpaperscissorslizardspock_newthumb.png
                  ;; this is a nice visualization of what beats what.
                  ;; Rock = 0, lizard = 1, spock = 2, scissors = 3, paper = 4.

                  (defun beats (x y) "Calculates whether move x beats move y"
                  (or (eq (% (1+ x) 5) y)
                  (eq (% (+ y 2) 5) x)))

                  ;; A gamestate is a list with the following elements:
                  (defun get-orders (gamestate)
                  "A list of orders of players who haven't lost yet. Each order is a list of moves.
                  For example, ((2) (2 0) (3) (0) (2 1) (3) (0) (0)) is a valid orders list.
                  This function gets orders from the gamestate."
                  (car gamestate))

                  ;; At index 1 of the gamestate lies a list of all moves we have made so far in reverse order
                  ;; (because lists are singly linked, we can't push back quickly)
                  (defun get-num-moves-done (gamestate)
                  "Returns the number of moves the player has done so far"
                  (length (nth 1 gamestate)))

                  (defun get-rounds-since-last-elim (gamestate)
                  "The last element of a gamestate is the number of rounds passed since an opponent
                  was eliminated. We use this to determine if it's possible to win from current
                  gamestate (more about it later)."
                  (nth 2 gamestate))

                  ;; next go some utility functions
                  ;; you can skip their descriptions, they are not very interesting
                  ;; I suggest you skip until the next ;; comment

                  (defun get-next-move (order num-rounds-done)
                  "Arguments: an order (e.g. (1 0 1)); how many rounds have passed total.
                  Returns the move this opponent will make next"
                  (nth (% num-rounds-done (length order)) order))

                  (defun moves-of-opponents-this-round (gamestate)
                  "Returns a list of moves the opponents will make next"
                  (mapcar (lambda (order) (get-next-move order (get-num-moves-done gamestate)))
                  (get-orders gamestate)))

                  (defun is-non-losing (move opponents-moves)
                  "Calculates if we lose right away by playing move against opponents-moves"
                  (not (seq-some (lambda (opponent-move) (beats opponent-move move))
                  opponents-moves)))

                  (defun non-losing-moves (gamestate)
                  "Returns a list of moves which we can play without losing right away."
                  (seq-filter
                  (lambda (move) (is-non-losing move (moves-of-opponents-this-round gamestate)))
                  '(0 1 2 3 4)))

                  (defun advance-gamestate (gamestate move)
                  "If this move in this gamestate is non-losing, returns the next game state"
                  (let ((new-orders (seq-filter
                  'identity (mapcar* (lambda (opp-move order)
                  (and (not (beats move opp-move)) order))
                  (moves-of-opponents-this-round gamestate)
                  (get-orders gamestate)))))
                  (list new-orders
                  (cons move (nth 1 gamestate))
                  (if (eq (get-orders gamestate) new-orders) (1+ (get-rounds-since-last-elim gamestate)) 0))))

                  ;; How do we prevent our depth first search from continuing without halting?
                  ;; Suppose 3 players (except us) are still in the game and they have orders of lengths a, b, c
                  ;; In this situation, if least_common_multiple(a, b, c) rounds pass without an elimination
                  ;; we will be in the same situation (because they will be playing the same moves they played
                  ;; lcm(a, b, c) rounds ago)
                  ;; therefore the course of play that we took was not an optimal one - if it is even possible
                  ;; to win from this position, then it is possible to win from an earlier position
                  ;; before we made this full cycle

                  (defun get-cycle-len (gamestate)
                  "Returns a number of rounds which is enough for the situation to become the same
                  if the game goes this long without an elimination."
                  (seq-reduce (lambda (x y) (calc-eval "lcm($,$$)" 'raw x y))
                  (mapcar 'length (get-orders gamestate)) 1))

                  (defun unwinnable-cycle (gamestate)
                  "Using the aforementioned information, returns t if we are in such a
                  suboptimal course of play."
                  (>= (get-rounds-since-last-elim gamestate) (get-cycle-len gamestate)))

                  (defun find-good-moves (gamestate)
                  "Given gamestate, if it's possible to win
                  returns a list of moves, containing all moves already done + additional moves which lead to win.
                  Otherwise returns nil"
                  (cond ((null (get-orders gamestate)) ; if no opponents left, we won, return the list of moves
                  (reverse (nth 1 gamestate)))
                  ((null (non-losing-moves gamestate)) ; if no non-losing moves available, this gamestate
                  nil) ; doesn't lead to a win, return nil
                  ((unwinnable-cycle gamestate) ; either it's impossible to win, or
                  nil) ; it's possible to win from an earlier position, return nil
                  (t (cl-some (lambda (move) ; otherwise return the first non-losing move which leads
                  (find-good-moves (advance-gamestate gamestate move))) ; to a non-nil result
                  (non-losing-moves gamestate)))))

                  (defun make-initial-gamestate (orders)
                  "Given an orders list, create initial gamestate"
                  (list orders () 0))





                  share|improve this answer








                  New contributor




                  CrabMan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                  Check out our Code of Conduct.






                  $endgroup$



                  Emacs Lisp, 730 bytes



                  (require 'cl-extra)
                  (require 'seq)
                  (defun N (g) (length (nth 1 g)))
                  (defun M (g) (mapcar (lambda (o) (nth (% (N g) (length o)) o)) (car g)))
                  (defun B (x y) (or (eq (% (1+ x) 5) y) (eq (% (+ y 2) 5) x)))
                  (defun S (g) (seq-filter (lambda (m) (not (seq-some (lambda (v) (B v m)) (M g)))) '(0 1 2 3 4)))
                  (defun F (g) (cond ((null (car g)) (reverse (nth 1 g))) ((null (S g)) nil) ((>= (nth 3 g) (seq-reduce (lambda (x y) (calc-eval "lcm($,$$)" 'raw x y)) (mapcar 'length (car g)) 1)) nil) (t (cl-some (lambda (m) (F (let ((r (seq-filter 'identity (mapcar* (lambda (v o) (and (not (B m v)) o)) (M g) (car g))))) (list r (cons m (nth 1 g)) (1+ (N g)) (if (eq (car g) r) (1+ (nth 3 g)) 0))))) (S g)))))
                  (defun Z (s) (F (list s () 0 0)))


                  I didn't find an online interpreter of Emacs Lisp :( If you have Emacs installed, you can copy code into a .el file, copy some testing lines below



                  ;; 0 = rock, 1 = lizard; 2 = spock;
                  ;; 3 = scissors; 4 = paper
                  (print (Z '((0) (1) (2) (3) (4))))
                  ; output: nil
                  (print (Z '((0) (4) (3) (1))))
                  ; output: nil
                  (print (Z '((0 4 3) (0 4 4) (0) (3 0 0) (1))))
                  ; output: (0 4 3 0 1)
                  (print (Z '((4) (4) (3) (4) (4))))
                  ; output: (3 0)
                  (print (Z '((4 3 2 1 0) (2 1 0 4 3))))
                  ; output: (1)
                  (print (Z '((2) (2) (3) (0) (2) (3) (0) (0))))
                  ; output: (2 1)
                  (print (Z '((2) (2 0) (3) (0) (2 1) (3) (0) (0))))
                  ; output: nil


                  and run it $ emacs --script filename.el.



                  How it works



                  My program does depth first search with sometimes figuring out that it's impossible to win and terminating the branch it's on.



                  You can see full explanation in the unshortened version of the code:



                  (require 'seq)
                  (require 'cl-extra)

                  ;; This program does depth first search with sometimes figuring out
                  ;; that it's impossible to win and terminating the branch it's on.
                  ;;

                  ;; A move is a number from 0 to 4.
                  ;; https://d3qdvvkm3r2z1i.cloudfront.net/media/catalog/product/cache/1/image/1800x/6b9ffbf72458f4fd2d3cb995d92e8889/r/o/rockpaperscissorslizardspock_newthumb.png
                  ;; this is a nice visualization of what beats what.
                  ;; Rock = 0, lizard = 1, spock = 2, scissors = 3, paper = 4.

                  (defun beats (x y) "Calculates whether move x beats move y"
                  (or (eq (% (1+ x) 5) y)
                  (eq (% (+ y 2) 5) x)))

                  ;; A gamestate is a list with the following elements:
                  (defun get-orders (gamestate)
                  "A list of orders of players who haven't lost yet. Each order is a list of moves.
                  For example, ((2) (2 0) (3) (0) (2 1) (3) (0) (0)) is a valid orders list.
                  This function gets orders from the gamestate."
                  (car gamestate))

                  ;; At index 1 of the gamestate lies a list of all moves we have made so far in reverse order
                  ;; (because lists are singly linked, we can't push back quickly)
                  (defun get-num-moves-done (gamestate)
                  "Returns the number of moves the player has done so far"
                  (length (nth 1 gamestate)))

                  (defun get-rounds-since-last-elim (gamestate)
                  "The last element of a gamestate is the number of rounds passed since an opponent
                  was eliminated. We use this to determine if it's possible to win from current
                  gamestate (more about it later)."
                  (nth 2 gamestate))

                  ;; next go some utility functions
                  ;; you can skip their descriptions, they are not very interesting
                  ;; I suggest you skip until the next ;; comment

                  (defun get-next-move (order num-rounds-done)
                  "Arguments: an order (e.g. (1 0 1)); how many rounds have passed total.
                  Returns the move this opponent will make next"
                  (nth (% num-rounds-done (length order)) order))

                  (defun moves-of-opponents-this-round (gamestate)
                  "Returns a list of moves the opponents will make next"
                  (mapcar (lambda (order) (get-next-move order (get-num-moves-done gamestate)))
                  (get-orders gamestate)))

                  (defun is-non-losing (move opponents-moves)
                  "Calculates if we lose right away by playing move against opponents-moves"
                  (not (seq-some (lambda (opponent-move) (beats opponent-move move))
                  opponents-moves)))

                  (defun non-losing-moves (gamestate)
                  "Returns a list of moves which we can play without losing right away."
                  (seq-filter
                  (lambda (move) (is-non-losing move (moves-of-opponents-this-round gamestate)))
                  '(0 1 2 3 4)))

                  (defun advance-gamestate (gamestate move)
                  "If this move in this gamestate is non-losing, returns the next game state"
                  (let ((new-orders (seq-filter
                  'identity (mapcar* (lambda (opp-move order)
                  (and (not (beats move opp-move)) order))
                  (moves-of-opponents-this-round gamestate)
                  (get-orders gamestate)))))
                  (list new-orders
                  (cons move (nth 1 gamestate))
                  (if (eq (get-orders gamestate) new-orders) (1+ (get-rounds-since-last-elim gamestate)) 0))))

                  ;; How do we prevent our depth first search from continuing without halting?
                  ;; Suppose 3 players (except us) are still in the game and they have orders of lengths a, b, c
                  ;; In this situation, if least_common_multiple(a, b, c) rounds pass without an elimination
                  ;; we will be in the same situation (because they will be playing the same moves they played
                  ;; lcm(a, b, c) rounds ago)
                  ;; therefore the course of play that we took was not an optimal one - if it is even possible
                  ;; to win from this position, then it is possible to win from an earlier position
                  ;; before we made this full cycle

                  (defun get-cycle-len (gamestate)
                  "Returns a number of rounds which is enough for the situation to become the same
                  if the game goes this long without an elimination."
                  (seq-reduce (lambda (x y) (calc-eval "lcm($,$$)" 'raw x y))
                  (mapcar 'length (get-orders gamestate)) 1))

                  (defun unwinnable-cycle (gamestate)
                  "Using the aforementioned information, returns t if we are in such a
                  suboptimal course of play."
                  (>= (get-rounds-since-last-elim gamestate) (get-cycle-len gamestate)))

                  (defun find-good-moves (gamestate)
                  "Given gamestate, if it's possible to win
                  returns a list of moves, containing all moves already done + additional moves which lead to win.
                  Otherwise returns nil"
                  (cond ((null (get-orders gamestate)) ; if no opponents left, we won, return the list of moves
                  (reverse (nth 1 gamestate)))
                  ((null (non-losing-moves gamestate)) ; if no non-losing moves available, this gamestate
                  nil) ; doesn't lead to a win, return nil
                  ((unwinnable-cycle gamestate) ; either it's impossible to win, or
                  nil) ; it's possible to win from an earlier position, return nil
                  (t (cl-some (lambda (move) ; otherwise return the first non-losing move which leads
                  (find-good-moves (advance-gamestate gamestate move))) ; to a non-nil result
                  (non-losing-moves gamestate)))))

                  (defun make-initial-gamestate (orders)
                  "Given an orders list, create initial gamestate"
                  (list orders () 0))






                  share|improve this answer








                  New contributor




                  CrabMan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                  Check out our Code of Conduct.









                  share|improve this answer



                  share|improve this answer






                  New contributor




                  CrabMan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                  Check out our Code of Conduct.









                  answered 15 mins ago









                  CrabManCrabMan

                  1011




                  1011




                  New contributor




                  CrabMan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                  Check out our Code of Conduct.





                  New contributor





                  CrabMan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                  Check out our Code of Conduct.






                  CrabMan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                  Check out our Code of Conduct.



























                      draft saved

                      draft discarded
















































                      If this is an answer to a challenge…



                      • …Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.


                      • …Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
                        Explanations of your answer make it more interesting to read and are very much encouraged.


                      • …Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.


                      More generally…



                      • …Please make sure to answer the question and provide sufficient detail.


                      • …Avoid asking for help, clarification or responding to other answers (use comments instead).




                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function ()
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f185203%2frock-paper-scissors-lizard-spock-tournament%23new-answer', 'question_page');

                      );

                      Post as a guest















                      Required, but never shown





















































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown

































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown







                      Popular posts from this blog

                      Invision Community Contents History See also References External links Navigation menuProprietaryinvisioncommunity.comIPS Community ForumsIPS Community Forumsthis blog entry"License Changes, IP.Board 3.4, and the Future""Interview -- Matt Mecham of Ibforums""CEO Invision Power Board, Matt Mecham Is a Liar, Thief!"IPB License Explanation 1.3, 1.3.1, 2.0, and 2.1ArchivedSecurity Fixes, Updates And Enhancements For IPB 1.3.1Archived"New Demo Accounts - Invision Power Services"the original"New Default Skin"the original"Invision Power Board 3.0.0 and Applications Released"the original"Archived copy"the original"Perpetual licenses being done away with""Release Notes - Invision Power Services""Introducing: IPS Community Suite 4!"Invision Community Release Notes

                      Canceling a color specificationRandomly assigning color to Graphics3D objects?Default color for Filling in Mathematica 9Coloring specific elements of sets with a prime modified order in an array plotHow to pick a color differing significantly from the colors already in a given color list?Detection of the text colorColor numbers based on their valueCan color schemes for use with ColorData include opacity specification?My dynamic color schemes

                      Tom Holland Mục lục Đầu đời và giáo dục | Sự nghiệp | Cuộc sống cá nhân | Phim tham gia | Giải thưởng và đề cử | Chú thích | Liên kết ngoài | Trình đơn chuyển hướngProfile“Person Details for Thomas Stanley Holland, "England and Wales Birth Registration Index, 1837-2008" — FamilySearch.org”"Meet Tom Holland... the 16-year-old star of The Impossible""Schoolboy actor Tom Holland finds himself in Oscar contention for role in tsunami drama"“Naomi Watts on the Prince William and Harry's reaction to her film about the late Princess Diana”lưu trữ"Holland and Pflueger Are West End's Two New 'Billy Elliots'""I'm so envious of my son, the movie star! British writer Dominic Holland's spent 20 years trying to crack Hollywood - but he's been beaten to it by a very unlikely rival"“Richard and Margaret Povey of Jersey, Channel Islands, UK: Information about Thomas Stanley Holland”"Tom Holland to play Billy Elliot""New Billy Elliot leaving the garage"Billy Elliot the Musical - Tom Holland - Billy"A Tale of four Billys: Tom Holland""The Feel Good Factor""Thames Christian College schoolboys join Myleene Klass for The Feelgood Factor""Government launches £600,000 arts bursaries pilot""BILLY's Chapman, Holland, Gardner & Jackson-Keen Visit Prime Minister""Elton John 'blown away' by Billy Elliot fifth birthday" (video with John's interview and fragments of Holland's performance)"First News interviews Arrietty's Tom Holland"“33rd Critics' Circle Film Awards winners”“National Board of Review Current Awards”Bản gốc"Ron Howard Whaling Tale 'In The Heart Of The Sea' Casts Tom Holland"“'Spider-Man' Finds Tom Holland to Star as New Web-Slinger”lưu trữ“Captain America: Civil War (2016)”“Film Review: ‘Captain America: Civil War’”lưu trữ“‘Captain America: Civil War’ review: Choose your own avenger”lưu trữ“The Lost City of Z reviews”“Sony Pictures and Marvel Studios Find Their 'Spider-Man' Star and Director”“‘Mary Magdalene’, ‘Current War’ & ‘Wind River’ Get 2017 Release Dates From Weinstein”“Lionsgate Unleashing Daisy Ridley & Tom Holland Starrer ‘Chaos Walking’ In Cannes”“PTA's 'Master' Leads Chicago Film Critics Nominations, UPDATED: Houston and Indiana Critics Nominations”“Nominaciones Goya 2013 Telecinco Cinema – ENG”“Jameson Empire Film Awards: Martin Freeman wins best actor for performance in The Hobbit”“34th Annual Young Artist Awards”Bản gốc“Teen Choice Awards 2016—Captain America: Civil War Leads Second Wave of Nominations”“BAFTA Film Award Nominations: ‘La La Land’ Leads Race”“Saturn Awards Nominations 2017: 'Rogue One,' 'Walking Dead' Lead”Tom HollandTom HollandTom HollandTom Hollandmedia.gettyimages.comWorldCat Identities300279794no20130442900000 0004 0355 42791085670554170004732cb16706349t(data)XX5557367