14
1
In association football (also known as soccer), a penalty shoot-out is the second tie-breaker measure that may be used in a match which can't end in a tie, after extra time (i.e. association football overtime).
In a penalty shoot-out, the main referee tosses a coin to determine at which goal the shoot-out happens, and then tosses another coin to determine which team starts first. However, the only thing relevant to this challenge is what happens then, described below.
Each team has 5 penalties available at start, and the penalty score is 0-0. If, at any point, a team's remaining penalties aren't enough to change the currently winning team, the shoot-out stops.
If there are no remaining penalties, but both teams' points are equal, an additional penalty is granted to both teams. This is repeated until the points aren't equal.
After the shoot-out stops, the team with the largest penalty score wins the game.
Challenge
Your challenge is, given two lists A
and B
representing which penalties team A and team B scored respectively, to determine if they represent a valid penalty shoot-out. A shoot-out is valid if the state represented by the input can be reached, regardless of whether the winning team can be determined. Note that you possibly have to test for both scenarios (Team A starting, Team B starting), since, if the state described in the input is reachable for at least one scenario, the input is valid. If the lists' lengths are different, the team represented by the longer one starts first (it can only have one more element than the other one, and the shorter list's team can't start, since then the longer list's team would shoot two penalties in a row, as the shorter list will be prematurely depleted).
Detailed examples
You can skip to the Rules section below, these are only to help solving the challenge.
Suppose you get this shoot-out as input, where -
means no goal was scored and X
means a goal was scored (it's invalid):
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.
On the contrary, here is a valid example:
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.
Another example, this time with extra penalties:
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.
Here is a valid input where it's too early to determine the winner:
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.
Finally, here is an input where the lists' lengths differ:
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.
Rules
- The team that shoots first can be either A or B, you can't assume one will always shoot first.
- The lists will either have the same length, or their lengths will differ by one.
- You may choose any two distinct and consistent values to represent scored/unscored penalties.
- The lists can also be represented as integers converted from bijective base 2, strings or your language's native list format. If a bijective base 2 format is chosen, the input rules apply to the numbers converted to bijective base 2 (so digits
1
and2
can either mean scored and unscored or unscored and scored respectively). Regular binary is not allowed, as one can't determine the presence of leading zeroes in the intended binary representation. - This is code-golf, so the shortest solution wins. However, please don't be discouraged from answering even if it seems like your language can't "beat the specialized ones".
Test cases
In these test cases, a 0
will represent a no-goal, and a 1
will represent a goal.
Format:
[Team A], [Team B]
Valid inputs:
[], []
[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]
Invalid inputs:
[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]
Can I return 0 or false for for invalid, and return true for valid? – Embodiment of Ignorance – 2019-03-06T21:56:40.563
@EmbodimentofIgnorance "You may choose any two distinct and consistent values to represent scored/unscored penalties." The exact values don't matter, but there must only be two values. – Erik the Outgolfer – 2019-03-06T21:57:11.700
I assume
[[0,0],[1,1]]
(or any test case where one of the two inner lists has 2 items) is truthy, since the game is still going on (just like the test cases with[[0],[1]]
or[[0],[]]
are still in progress)? – Kevin Cruijssen – 2019-03-07T08:24:42.513@KevinCruijssen Yes, because nobody can determine who will win, the outcome might be 3-2. ;-) – Erik the Outgolfer – 2019-03-07T13:13:48.197