Czy to prawidłowy prefiks do rzutów karnych?

14

W piłce nożnej (zwanej także piłką nożną) rzut karny jest drugim środkiem rozstrzygającym, który może być zastosowany w meczu, który nie może zakończyć się remisem, po dogrywce (tj. Dogrywce w piłce nożnej w stowarzyszeniu).

W rzutach karnych sędzia główny rzuca monetą, aby ustalić, przy której bramce ma miejsce rzut karny, a następnie rzuca kolejną monetą, aby ustalić, która drużyna zaczyna jako pierwsza. Jednak jedyne istotne dla tego wyzwania jest to, co dzieje się wtedy, opisane poniżej.

Każda drużyna ma 5 kar dostępnych na starcie, a wynik karny to 0-0. Jeśli w dowolnym momencie pozostałe kary drużyny nie wystarczą, aby zmienić aktualnie zwycięską drużynę, strzelanie zostaje przerwane.

Jeśli nie ma już kar, ale punkty obu drużyn są równe, obie drużyny otrzymują dodatkową karę. Jest to powtarzane, dopóki punkty nie będą równe.

Po zatrzymaniu rzutów karnych drużyna z największym wynikiem karnym wygrywa.

Wyzwanie

Twoim wyzwaniem jest, biorąc pod uwagę dwie listy Ai Breprezentujące, które rzuty karne uzyskały odpowiednio drużyna A i drużyna B, aby ustalić, czy reprezentują one rzuty karne ważne. Rzuty rożne są ważne, jeśli można osiągnąć stan reprezentowany przez dane wejściowe, niezależnie od tego, czy można ustalić zwycięską drużynę. Należy pamiętać, że być może trzeba przetestować oba scenariusze (uruchomienie drużyny A, uruchomienie drużyny B), ponieważ jeśli stan opisany na wejściu jest osiągalny dla co najmniej jednego scenariusza, dane wejściowe są prawidłowe. Jeśli długości list są różne, drużyna reprezentowana przez dłuższą startuje jako pierwsza (może mieć tylko jeden element więcej niż drugi, a drużyna krótszej listy nie może się rozpocząć, ponieważ wtedy drużyna dłuższej listy strzeliłaby dwie kary z rzędu, ponieważ krótsza lista zostanie przedwcześnie wyczerpana).

Szczegółowe przykłady

Możesz przejść do sekcji Reguły poniżej, mają one jedynie pomóc w rozwiązaniu problemu.

Załóżmy, że otrzymujesz ten rzut karny jako wkład, w którym -oznacza to , że nie padła żadna bramka i Xże padła bramka (jest nieważna):

Team A: - X X X X
Team B: - - - - X

Assuming team A starts first:

Team A: - (0 - 0) (max possible score 4 - 5)
Team B: - (0 - 0) (max possible score 4 - 4)
Team A: X (1 - 0) (max possible score 4 - 4)
Team B: - (1 - 0) (max possible score 4 - 3)
Team A: X (2 - 0) (max possible score 4 - 3)
Team B: - (2 - 0) (max possible score 4 - 2)
Team A: X (3 - 0) (max possible score 4 - 2)
Team A already has a higher score than B could ever have, but the input hasn't
ended yet, so it's invalid if team A is first.

Assuming team B starts first:

Team B: - (0 - 0) (max possible score 5 - 4)
Team A: - (0 - 0) (max possible score 4 - 4)
Team B: - (0 - 0) (max possible score 4 - 3)
Team A: X (1 - 0) (max possible score 4 - 3)
Team B: - (1 - 0) (max possible score 4 - 2)
Team A: X (2 - 0) (max possible score 4 - 2)
Team B: - (2 - 0) (max possible score 4 - 1)
Team A already has a higher score than B could ever have, but the input hasn't
ended yet, so it's invalid if team B stars first.

The input is invalid no matter which team starts first, so it's considered
invalid.

Przeciwnie, oto poprawny przykład:

Team A: X X X
Team B: - - -

Assuming team A starts first:

Team A: X (1 - 0) (max possible score 5 - 5)
Team B: - (1 - 0) (max possible score 5 - 4)
Team A: X (2 - 0) (max possible score 5 - 4)
Team B: - (2 - 0) (max possible score 5 - 3)
Team A: X (3 - 0) (max possible score 5 - 3)
Team B: - (3 - 0) (max possible score 5 - 2)
It can be determined that team A wins, however the input has ended, so it's
valid if team A starts first. Therefore, the input is valid.

Kolejny przykład, tym razem z dodatkowymi karami:

Team A: X - X - - - X -
Team B: - X X - - - X X

Assuming team A starts first:

Team A: X (1 - 0) (max possible score 5 - 5)
Team B: - (1 - 0) (max possible score 5 - 4)
Team A: - (1 - 0) (max possible score 4 - 4)
Team B: X (1 - 1) (max possible score 4 - 4)
Team A: X (2 - 1) (max possible score 4 - 4)
Team B: X (2 - 2) (max possible score 4 - 4)
Team A: - (2 - 2) (max possible score 3 - 4)
Team B: - (2 - 2) (max possible score 3 - 3)
Team A: - (2 - 2) (max possible score 2 - 3)
Team B: - (2 - 2) (max possible score 2 - 2)
First 5 penalties result in a tie, so we move on to extra penalties.
Team A: -, Team B: - (2 - 2)
Team A: X, Team B: X (3 - 3)
Team A: -, Team B: X (3 - 4)
It can be determined that team B wins, however the input has ended, so it's
valid if team A starts first. Therefore, the input is valid.

Oto prawidłowe dane wejściowe, w których jest zbyt wcześnie, aby określić zwycięzcę:

Team A: X X - -
Team B: - X - X

Assuming team A starts first:

Team A: X (1 - 0) (max possible score 5 - 5)
Team B: - (1 - 0) (max possible score 5 - 4)
Team A: X (2 - 0) (max possible score 5 - 4)
Team B: X (2 - 1) (max possible score 5 - 4)
Team A: - (2 - 1) (max possible score 4 - 4)
Team B: - (2 - 1) (max possible score 4 - 3)
Team A: - (2 - 1) (max possible score 3 - 3)
Team B: X (2 - 2) (max possible score 3 - 3)
The input has ended before the winner can be determined, so it's valid if team A
starts first. Therefore, the input is valid.

Wreszcie, oto dane wejściowe, w których długości list różnią się:

Team A: - - -
Team B: X X - X

Since team B shot more penalties, it starts first:

Team B: X (0 - 1) (max possible score 5 - 5)
Team A: - (0 - 1) (max possible score 4 - 5)
Team B: X (0 - 2) (max possible score 4 - 5)
Team A: - (0 - 2) (max possible score 3 - 5)
Team B: - (0 - 2) (max possible score 3 - 4)
Team A: - (0 - 2) (max possible score 2 - 4)
Team B: X (0 - 3) (max possible score 2 - 4)
It can be determined that team B wins, however the input has ended, so it's
valid.

Zasady

  • Drużyna, która strzela jako pierwsza, może być A lub B, nie można zakładać, że zawsze będzie strzelać jako pierwsza.
  • Listy będą miały tę samą długość lub ich długości będą się różnić o jeden.
  • Możesz wybrać dowolne dwie odrębne i spójne wartości, które będą reprezentować strzelone / niepunkcjonowane kary.
  • Listy mogą być również reprezentowane jako liczby całkowite przekonwertowane z bijective base 2, string lub rodzimego formatu listy twojego języka. Jeśli wybrany jest format bijective base 2, reguły wprowadzania mają zastosowanie do liczb przekonwertowanych na bijective base 2 (więc cyfry 1i 2mogą oznaczać odpowiednio ocenę punktową i nieprzypisaną lub nieprzypisaną i ocenę punktową). Zwykły plik binarny jest niedozwolony , ponieważ nie można określić obecności zer wiodących w zamierzonej reprezentacji binarnej.
  • To jest , więc wygrywa najkrótsze rozwiązanie. Prosimy jednak nie zniechęcać się do odbierania odpowiedzi, nawet jeśli wydaje się, że Twój język nie jest w stanie „pokonać języków specjalistycznych”.

Przypadki testowe

W tych przypadkach testowych a 0będzie stanowić cel bez celu, a a 1będzie stanowić cel.

Format:

[Team A], [Team B]

Prawidłowe dane wejściowe:

[], []
[0], [0]
[0], [1]
[1], [1]
[0], []
[1, 1, 1, 1], [0, 0, 1, 1]
[0, 1, 1, 1, 1], [0, 1, 1, 0]
[0, 0, 0, 0, 1], [0, 0, 0, 1, 0]
[0, 0, 0, 0, 1], [0, 0, 0, 1]
[1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1]
[0, 1, 1, 1, 1], [0, 1, 1, 0, 1]
[1, 1, 1], [0, 0, 0]
[1, 1, 1, 1], [0, 0, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Nieprawidłowe dane wejściowe:

[0, 1, 1, 1, 1], [0, 1, 1, 0, 0]
[0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 1]
[1, 1, 1, 0], [0, 0, 0]
[1, 1, 1, 1], [0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[1, 0, 1, 0, 1], [0, 1, 0, 1, 0, 1]
[0, 0, 0, 0, 1], [0, 1, 1, 1, 0]
Erik the Outgolfer
źródło
Czy mogę zwrócić 0 lub false dla niepoprawnego i zwrócić true dla ważnego?
Embodiment of Ignorance
@EmbodimentofIgnorance „Możesz wybrać dowolne dwie odrębne i spójne wartości, które będą reprezentować kary strzelone / niepunkcjonowane”. Dokładne wartości nie mają znaczenia, ale muszą być tylko dwie wartości.
Erik the Outgolfer
Zakładam [[0,0],[1,1]](lub jakikolwiek przypadek testowy, w którym jedna z dwóch wewnętrznych list zawiera 2 elementy) jest prawdą, ponieważ gra wciąż trwa (podobnie jak przypadki testowe z [[0],[1]]lub [[0],[]]wciąż trwają)?
Kevin Cruijssen
@KevinCruijssen Tak, ponieważ nikt nie może ustalić, kto wygra, wynik może wynosić 3-2. ;-)
Erik the Outgolfer

Odpowiedzi:

3

JavaScript (ES6),  117 112  109 bajtów

(a)(b)12)01

a=>b=>!(g=(a,b,P=Q=i=5)=>(p=a[5-i])|(q=b[5-i])&&(--i<0?P-Q:P-Q>i|Q+q-P-p>i&p<2)|g(a,b,P+p,Q+=q))(a,b)|!g(b,a)

Wypróbuj online!

Skomentował

a => b =>                   // given a[] and b[]
  !(g = (                   // g is a recursive function taking:
      a,                    //   the results a[] of the team that plays first
      b,                    //   the results b[] of the team that plays second
      P =                   //   the cumulated goals P of the 1st team (relative value)
      Q =                   //   the cumulated goals Q of the 2nd team (relative value)
      i = 5                 //   a counter i
    ) =>                    // and returning a truthy value if something goes wrong
      (p = a[5 - i]) |      // if either the first team
      (q = b[5 - i]) && (   // or the second team is playing this round:
        --i < 0 ?           //   decrement i; if we've played more than 5 penalties:
          P - Q             //     do we already have a goal difference?
        :                   //   else:
          P - Q > i |       //     was the 1st team already guaranteed to win?
          Q + q - P - p > i //     or is the 2nd team now guaranteed to win
          & p < 2           //     while the 1st team failed its last attempt?
      ) |                   //
      g(                    //   do a recursive call:
        a, b,               //     pass a[] and b[] unchanged
        P + p,              //     update P
        Q += q              //     update Q
      )                     //   end of recursive call
  )(a, b) |                 // try g(a, b)
  !g(b, a)                  // try g(b, a); return 1 if at least one of them is falsy
Arnauld
źródło
2

Python 2 , 176 169 171 169 bajtów

-2 bajty dzięki @Kevin Cruijssen

exec"h=lambda a,b,m:m-%s/2>abs(sum(a)-sum(b));f=lambda a,b:a[5#==b[5#and h(a[:5],b[:5],6)if %s>10else h(a,b,7)and h(a[#,b[#,6)".replace("#",":~-%s/2]")%(("len(a+b)",)*6)

Wypróbuj online! (W tym dodatkowe przypadki testowe niewymienione powyżej).

Tworzy funkcję, fktóra pobiera dwa argumenty (dwie listy kar punktowanych / nieskalowanych) i zwraca, Truejeśli wyniki są możliwe i Falseinne.

Częściowe wyjaśnienie:

Po pierwsze, execkonstrukcja jest tylko sposobem na zaoszczędzenie kilku bajtów, bez konieczności powtarzania wyrażenia len(a+b)więcej niż jeden raz. Powyższy fragment kodu odpowiada następującemu:

Aktualizacja: nowa i ulepszona odpowiedź ma tę samą liczbę bajtów z oszustwem lub bez exec, więc dla uproszczenia usunąłem go.

Aktualizacja 2: Nowa wersja z poprawioną usterką obejmuje jeszcze większą kompresję łańcuchów poprzez podstawienie i exec. Tak, używam %formatowania i a .replacena tym samym ciągu. Powyższy kod jest równoważny z:

h=lambda a,b,m:m-len(a+b)/2>abs(sum(a)-sum(b))
f=lambda a,b:a[5:(len(a+b)-1)/2]==b[5:~-len(a+b)/2]and h(a[:5],b[:5],6)if len(a+b)>10else h(a,b,7)and h(a[:(~-len(a+b)/2],b[:(len(a+b)-1)/2],6)

Główną ideą tej odpowiedzi jest sformułowanie pytania w kategoriach „pół punktu”: każde udane kopnięcie jest pół punktu, a każde nieudane jest ujemne pół punktu. Dla zestawu wyników o długości<=5aby zachować ciągłość ( not len(a+b)>10), całkowita liczba pozostałych rzutów musi być większa lub równa marginesowi połowy punktów między dwiema drużynami. Kiedy jedna drużyna wykopała dodatkowy czas, z różnych powodów należy odjąć pół punktu od marginesu, więc można to uprościć, dzieląc liczby całkowite po obu stronach równania na dwa. To jest funkcjah w kodzie (z argumentem mrównym 6).

Jednak aby być prawidłowym zestawem wyników, dane wejściowe nie muszą być ściśle kontynuowane, ale muszą być kontynuowane przed wykonaniem ostatniego rzutu. Ten warunek jest równoznaczny z twierdzeniem, że 1) musi być kontynuowany, gdy obie strony kopały tyle razy tyle razy, i 2) obecnie musi znajdować się w odległości dwóch pół punktu, aby być kontynuowanym - w tym miejscu pojawia się ostatni argument h: h(a[:~-len(a+b)/2],b[:~-len(a+b)/2],6)warunek testu 1) i h(a,b,7)(co 7stanowi dodatkowe dwa dopuszczalne pół punktu na marginesie) warunek testu 2).

Tym samym rozwiązano przypadek, w którym każda drużyna kopnęła maksymalnie pięć razy. (Wyjaśnienie będzie kontynuowane w drugim przypadku.)

Jeśli chodzi o grę w golfa na niskim poziomie, wątpię, aby było za dużo do ogolenia, ale algorytmicznie można by to zrobić o wiele prostiej.

Aidan F. Pierce
źródło
1
Możesz zagrać (%s-1)/2w golfa, ~-%s/2aby zaoszczędzić 2 bajty.
Kevin Cruijssen
@KevinCruijssen Thanks!
Aidan F. Pierce
1

Galaretka , 62 54 49 bajtów

ṫ⁵Ṗm2¬Ạ
N§ỤḢƊ¦LÞṚZFĵ12R:2U_ṁḣ⁵ṫ-N<Ø.ẠaÇoL<3
ṚÇoÇ

Wypróbuj online!

ṫ⁵Ṗm2¬Ạ # helper function to determine whether
        # even indices at or beyond 10 are zero
ṫ⁵      # tail - take every item from 10
  Ṗ     # remove last item
   m2   # take every second item
     ¬  # logical not, will return 1 for an empty list
      Ạ # all
# function to create cumulative score
# difference and check values
N§ỤḢƊ¦    # negate scores for team with lower score
          # (or one of them if both same score)
  LÞṚ     # sort by length, longest first
  ZF      # transpose lists and flatten
  Ä       # cumulative sum
  µ       # this cumulative score difference (CSD) 
          # now becomes left value
  12R:2U_ # subtract cumulative score difference from
          # 6,5,5,4,4,3,3,2,2,1
  ṁḣ⁵     # shorten to be no longer than 10 items
          # and no longer than CSD
  ṫ-N<Ø.Ạ # check last two values are greater than 0,-1
  aÇ      # check that helper function also TRUE
  oL<3    # handle very short scores
# main link that calls the above for scores in either order
ṚÇoÇ

Zauważ, że kod stopki w tio służy tylko do obsługi wielu przypadków testowych i drukowania wyników względem danych wejściowych.

Dzięki @EriktheOutgolfer za grę w golfa z 8 bajtów

Nick Kennedy
źródło
Niezła próba! To nie jest bardzo trywialne wyzwanie. Niektóre golfa.
Erik the Outgolfer
0

Perl 6 , 123 bajtów

{all map {@^b>@^a||[R,](map {abs(($+=$_)-++$ %2/2)>(5-++$ /2 max++$ %2)},flat roundrobin @a,-<<@b).skip.any},@^a,@^b,@b,@a}

Wypróbuj online!

Zwraca falsey dla ważnych rzutów, prawdę mówiąc dla nieważnych.

Wyjaśnienie

# Check whether block returns true (invalid shoot-out) for arguments (a, b) and (b, a)
{all map {...},@^a,@^b,@b,@a}
# Return true (invalid) if array b is longer than a
@^b>@^a||
# Return true (invalid) if any except the last value is true (shoot-out stopped)
[R,](...).skip.any
# Map values from a and negated b, interleaved
map {...},flat roundrobin @a,-<<@b
# Shoot out stopped?
abs(($+=$_)-++$ %2/2)>(5-++$ /2 max++$ %2)
    #     # Accumulator
           #        # Subtract 0.5 for first team
                      #                  # Sequence 4.5 4 3.5 3 2.5 2 1.5 1 1 0 1 0 1 0
nwellnhof
źródło