Wyzwanie związane z odniesieniem do Star Trek tuż po 4 maja może być zaskoczone, ale proszę bardzo.

Ty, Luke, Anakin, Palpatine, Yoda i Han Solo uczestniczycie w szalonym turnieju rocka, papieru, nożyczek, jaszczurki i Spocka.

Problem polega na tym, że możesz używać tylko stałej kolejności ruchów. Jeśli twoje zamówienie to „R”, musisz używać Skały, dopóki nie przegrasz lub nie wygrasz ze wszystkimi. Jeśli twoje zamówienie to RRV, musisz użyć 2 kamieni, a następnie Spocka i powtarzać, dopóki nie wygrasz lub przegrasz.

Luke, Anakin, Palpatine, Yoda i Han Solo złożyli odpowiednie zamówienia, a Ty jako ekspert hakerów dostałeś swoje zamówienia!

Mając tę ​​wiedzę, musisz zaprojektować swoje zamówienie na turniej. Ponieważ każdy chce wygrać, musisz stworzyć takie zamówienie, aby wygrać turniej, pokonując wszystkich. Ale może to nie być możliwe we wszystkich okolicznościach.

W przypadku możliwego zwycięskiego zamówienia wydrukuj je. Jeśli nie ma możliwości wygrania, wydrukuj -1 (lub 0 lub Fałsz lub „niemożliwe”)

Dane wejściowe : lista 5 zamówień

Wyjście : pojedyncze zamówienie lub -1

Przykładowe wejście 1

R
P
S
L
V

Przykładowe dane wyjściowe 1

-1

Wyjaśnienie 1

Bez względu na to, co zagrasz w swoim pierwszym ruchu, będzie co najmniej jedna osoba, która cię pokona, dlatego nie można wygrać.

Przykładowe wejście 2

RPS
RPP
R
SRR
L

Przykładowe wyjście 2

RPSP

Wyjaśnienie 2

Kiedy grasz w Rock w pierwszym ruchu, ostatecznie pokonujesz „L” i „SRR” i remisujesz z resztą. To dlatego, że Jaszczurka i Nożyce przegrywają z Kamieniem. Kiedy następnie zagrasz w Paper, pokonasz „R” i remisujesz z pozostałymi 2. To dlatego, że Rock przegrywa z Paper. Gdy następnie zagrasz w nożyczki, wygrasz przeciwko „RPP”, gdy Scissor pokona papier.

W końcu pokonasz „RPS” swoim Paper, ponieważ Paper pokonuje Rock.

Oto lista notacji (możesz użyć dowolnych 5 literałów, ale proszę podać w swojej odpowiedzi):

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

Oto lista wszystkich możliwych wyników:

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

To jest golf golfowy , więc wygrywa najmniej bajtów.

PS: Daj mi znać, jeśli potrzebujesz więcej przypadków testowych.

Galaretka , 29 bajtów

_%5ḟ0ḢḂ¬
ṁ€ZLḤƊçþ`Ạ€Tị;‘%5Ɗ$€

Monadyczny link, który akceptuje listę liczb całkowitych (z których każda jest strategią przeciwnika), która daje listę list liczb całkowitych - z których każda jest strategią wygrywającą (więc pusta lista, jeśli żadna nie jest możliwa).
_{(Wystarczy dodać, Ḣaby uzyskać tylko jedną listę strategii lub, 0jeśli to niemożliwe).}

Wypróbuj online! (formaty stopek, aby zawsze wyświetlać listy)

Rock  Paper  Scissors  Spock  Lizard
0     1      2         3      4

Lub wypróbuj wersję mapowaną na litery (w której strategie są podejmowane i wyświetlane w osobnych wierszach za pomocą RPSVLnotacji).

W jaki sposób?

Liczby są wybierane w taki sposób, że każda, która jest liczbą nieparzystą większą niż inny moduł pięciu wygranych (tj. Są ponumerowane, przechodzą wokół krawędzi wpisanego pięciokąta rzutów).

Kod odtwarza każdą strategię w stosunku do każdej strategii (włączając siebie) w celu uzyskania dwukrotnie większej liczby rzutów niż najdłuższa strategia, aby zapewnić znalezienie przegranych, którzy zatrzymają tych, którzy nie zostaną pokonani. Wynikowa lista strategii będzie zawierać pojedynczą strategię, jeśli zostanie zwycięzcą; brak strategii, jeśli nie byłoby zwycięzcy; lub wiele strategii, jeśli są losowani gracze. Następnie do każdej z tych strategii dołączany jest zwycięski zestaw ruchów.

_%5ḟ0ḢḂ¬ - Link 1, does B survive?: list A, list B (A & B of equal lengths)
                              e.g. RPSR vs RPVL ->  [0,1,2,0], [0,1,3,4]
_        - subtract (vectorises)                    [0,0,-1,-4]
 %5      - modulo five (vectorises)                 [0,0,4,1]   ...if all zeros:
   ḟ0    - filter discard zeros (ties)              [4,1]                       []
     Ḣ   - head (zero if an empty list)             4                           0
      Ḃ  - modulo two                               0                           0
       ¬ - logical NOT                              1                           1

ṁ€ZLḤƊçþ`Ạ€Tị;‘%5Ɗ$€ - Main Link: list of lists of integers
ṁ€                   - mould each list like:
     Ɗ               -   last three links as a monad
  Z                  -     transpose
   L                 -     length
    Ḥ                -     double  (i.e. 2 * throws in longest strategy)
        `            - use left as both arguments of:
       þ             -   table using:
      ç              -     last Link (1) as a dyad
         Ạ€          - all for each (1 if survives against all others, else 0)
           T         - truthy indices
            ị        - index into the input strategies
                  $€ - last two links as a monad for each:
             ;       -   concatenate with:
                 Ɗ   -     last three links as a monad:
              ‘      -       increment (vectorises)
               %5    -       modulo five (vectorises)

JavaScript (ES6),  122 115  112 bajtów

Pobiera dane wejściowe jako tablicę ciągów cyfr z:

• $0$
• $1$
• $2$
• $3$
• $4$

$false$

f=(a,m='',x=0,o,b=a.filter(a=>(y=a[m.length%a.length])-x?o|=y-x&1^x<y:1))=>b+b?x<4&&f(a,m,x+1)||!o&&f(b,m+x):m+x

Wypróbuj online!

W jaki sposób?

Jest to pierwsze wyszukiwanie: najpierw próbujemy wszystkich ruchów na danym etapie, aby sprawdzić, czy możemy wygrać grę. Jeśli nie możemy teraz wygrać, staramy się dodać kolejny ruch do każdego nie-przegranego ruchu.

$A$$B$$(B-A)\bmod 5$

$A$$B$

$$\begin{array}{cc|ccccc} & & \text{(S)} & \text{(P)} & \text{(R)} & \text{(L)} & \text{(V)}\\ & & 0 & 1 & 2 & 3 & 4\\ \hline \text{(S) }&0 & - & \color{green}1 & \color{red}2 & \color{green}3 & \color{red}4\\ \text{(P) }&1 & \color{red}4 & - & \color{green}1 & \color{red}2 & \color{green}3\\ \text{(R) }&2 & \color{green}3 & \color{red}4 & - & \color{green}1 & \color{red}2\\ \text{(L) }&3 & \color{red}2 & \color{green}3 & \color{red}4 & - & \color{green}1\\ \text{(V) }&4 & \color{green}1 & \color{red}2 & \color{green}3 & \color{red}4 & - \end{array}$$

$A$$B$$A\neq B$

((A - B) and 1) xor (B < A)

gdzie andi xorsą operatorami bitowymi.

Skomentował

f = (                        // f is a recursive function taking:
  a,                         //   a[] = input
  m = '',                    //   m   = string representing the list of moves
  x = 0,                     //   x   = next move to try (0 to 4)
  o,                         //   o   = flag set if we lose, initially undefined
  b =                        //   b[] = array of remaining opponents after the move x
    a.filter(s =>            //     for each entry s in a[]:
    ( y =                    //       define y as ...
      s[m.length % s.length] //         ... the next move of the current opponent
    ) - x                    //       subtract x from y
    ?                        //       if the difference is not equal to 0:
      o |=                   //         update o using the formula described above:
        y - x & 1 ^ x < y    //           set it to 1 if we lose; opponents are removed
                             //           while o = 0, and kept as soon as o = 1
    :                        //       else (this is a draw):
      1                      //         keep this opponent, but leave o unchanged
  )                          //     end of filter()
) =>                         //
  b + b ?                    // if b[] is not empty:
    x < 4 &&                 //   if x is less than 4:
      f(a, m, x + 1)         //     do a recursive call with x + 1 (going breadth-first)
    ||                       //   if this fails:
      !o &&                  //     if o is not set:
        f(b, m + x)          //       keep this move and do a recursive call with b[]
  :                          // else (success):
    m + x                    //   return m + x

R , 213 190 bajtów

-23 bajty dzięki Giuseppe.

function(L){m=matrix(rep(0:2,1:3),5,5)
m[1,4]=m[2,5]=1
v=combn(rep(1:5,n),n<-sum(lengths(L)))
v[,which(apply(v,2,function(z)all(sapply(L,function(x,y,r=m[cbind(x,y)])r[r>0][1]<2,z)))>0)[1]]}

Wypróbuj online!

Jeśli istnieje rozwiązanie, generuje je. Jeśli nie ma rozwiązania, wyświetla wiersz NA. Jeśli ten format wyjściowy jest nie do przyjęcia, mogę go zmienić kosztem kilku bajtów.

Ruchy są kodowane jako 1 = R, 2 = S, 3 = P, 4 = L, 5 = V, dzięki czemu macierz wyników jest

     [,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 = brak zwycięzcy; 1 = gracz 1 wygrywa; 2 = gracz 2 wygrywa)

Górną granicą długości rozwiązania, jeśli istnieje, jest miejsce, w n=sum(lengths(L))którym Lznajduje się lista ruchów przeciwników. Kod tworzy wszystkie możliwe strategie długości n(przechowywane w macierzy v), wypróbowuje je wszystkie i wyświetla wszystkie zwycięskie strategie.

Zauważ, że ta wartość npowoduje, że kod jest bardzo wolny na TIO, więc zapisałem na stałe w TIO, n=4co jest wystarczające dla przypadków testowych.

W pierwszym przypadku testowym wynikiem jest

     1 4 2 4

odpowiadające rozwiązaniu RLSL.

W drugim przypadku testowym wynikiem jest

 NA NA NA NA

co oznacza, że ​​nie ma rozwiązania.

Objaśnienie poprzedniej wersji (zaktualizuje się, gdy będę mógł):

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
}

Konieczne whichjest pozbycie się NA, które występują, gdy dwóch graczy losuje na zawsze.

Nie jestem przekonany, że jest to najbardziej skuteczna strategia. Nawet jeśli tak, jestem pewien, że kod dla mgolfa może być dość golfowy.

Emacs Lisp, 730 bajtów

(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)))

Nie znalazłem internetowego tłumacza Emacsa Lispa :( Jeśli masz zainstalowany Emacsa, możesz skopiować kod do .elpliku, skopiować kilka linii testowych poniżej

;; 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

i uruchom to $ emacs --script filename.el.

Jak to działa

Mój program najpierw dokonuje głębokiego wyszukiwania, czasami stwierdzając, że nie można wygrać i kończąc gałąź, w której działa.

Pełne wyjaśnienie można zobaczyć w nieskróconej wersji kodu:

(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, if it's possible to win from this gamestate,
;; then it's possible to win from that earlier game state,
;; hence we can stop exploring this branch

(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))