Can my favourite team still become Football Champion?

Question

As a fan of an at most moderately successful football^BE team, towards the end of the season I often wonder whether my favourite team still has any theoretical chance left of becoming champion. Your task in this challenge is to answer that question for me.

Input

You will recieve three inputs: the current table, the list of remaining matches, and the current position of the team we are interested in.

Input 1: The current table, a sequence of numbers were the i-th number are the points gained by team i so far. For example, the input [93, 86, 78, 76, 75] encodes the following table (only the last column is of importance):

---

Input 2: The remaining matches, a sequence of tuples where each tuple (i,j) stands for a remaining match between team i and j. In the above example, a second input of [(1,2), (4,3), (2,3), (3,2), (1,2)] would mean that the remaining matches are:

Chelsea vs Tottenham, Liverpool vs Man. City, Tottenham vs Man. City, Man. City vs Tottenham, Chelsea vs Tottenham

---

Input 3: The current position of the team we are interested in. For example, an input of 2 for the above example would mean that we'd like to know whether Tottenham can still become champion.

Output

For each remaining match of the form (i,j), there are three possible outcomes:

• Team i wins: Team i gets 3 points, team j gets 0 points
• Team j wins: Team i gets 0 points, team j gets 3 points
• Draw: Team i and j both get 1 point

You must output a truthy value if there is some outcome for all remaining games such that at the end, no other team has more points than the team specified in the 3rd input. Otherwise, output a falsy value.

Example: Consider the exemplary input from the above section:

Input 1 = [93, 86, 78, 76, 75], Input 2 = [(1,2), (4,3), (2,3), (3,2), (1,2)], Input 3 = 2

If team 2 wins all its remaining matches (i.e. (1,2), (2,3), (3,2), (1,2)), it gets 4*3 = 12 additional points; none of the other teams gets any points from these matches. Let's say the other remaining match (i.e. (4,3)) is a draw. Then the final scores would be:

 Team 1: 93, Team 2: 86 + 12 = 98, Team 3: 78 + 1 = 79, Team 4: 76 + 1 = 77, Team 5: 75

This means that we have already found some outcome for the remaining matches such that no other team has more points than team 2, so the output for this input must be truthy.

Details

• You may assume the first input to be an ordered sequence, i.e. for i < j, the i-th entry is equal to or greater than the j-th entry. The first input may be taken as a list, a string or the like.
• You may take the second input as a string, a list of tuples or the like. Alternatively, you may take it as a two-dimensional array a where a[i][j] is the number of entries of the form (i,j) in the list of remaining matches. For example, a[1][2] = 2, a[2][3] = 1, a[3][2] = 1, a[4][3] = 1 corresponds to [(1,2), (4,3), (2,3), (3,2), (1,2)].
• For the second and third input, you may assume 0-indexing instead of 1-indexing.
• You may take the three inputs in any order.

Please specify the exact input format you chose in your answer.

_{Side node: The problem underlying this challenge was shown to be NP-complete in "Football Elimination is Hard to Decide Under the 3-Point-Rule". Interestingly, if only two points are awarded for a win, the problem becomes solvable in polynomial time.}

Test Cases

All test cases are in the format Input1, Input2, Input3.

Truthy:

• [93, 86, 78, 76, 75], [(1,2), (4,3), (2,3), (3,2), (1,2)], 2
• [50], [], 1
• [10, 10, 10], [], 3
• [15, 10, 8], [(2,3), (1,3), (1,3), (3,1), (2,1)], 2

Falsy:

• [10, 9, 8], [], 2
• [10, 9, 9], [(2,3), (3,2)], 1
• [21, 12, 11], [(2,1), (1,2), (2,3), (1,3), (1,3), (3,1), (3,1)], 2

Winner

This is code-golf, so the shortest correct answer (in bytes) wins. The winner will be chosen one week after the first correct answer is posted.

Answer 1

Haskell (Lambdabot), 84 bytes

Thanks to @bartavelle for saving me a byte.

Without Lambdabot, add 20 bytes for import Control.Lens plus a newline.

The function takes its arguments in the same order as described in the OP, 0-indexed. Its second argument (the list of remaining matchups) is a flat list of indexes (e.g. [1,2,4,1] corresponds to [(Team 1 vs Team 2), (Team 4 vs Team 1)]).

The rules are a little vague as to whether or not this is allowed. If it isn't allowed, the function can take input in the format provided by the examples – a list of tuples. In that case, add 2 bytes to this solution's score, due to replacing a:b:r with (a,b):r.

(!)=(+~).element
(t?(a:b:r))s=any(t?r)[a!3$s,b!3$s,b!1$a!1$s]
(t?_)s=s!!t==maximum s

Explanation:

The first line defines an infix function ! of three variables, of type (!) :: Int -> Int -> [Int] -> [Int], which increments the value at a given index in a list. Since, oftentimes, code is easier to understand than words (and since Haskell syntax can be weird), here's a Python translation:

def add(index, amount, items):
    items[index] += amount
    return items

The second line defines another infix function ?, also of three variables (the challenge input). I'll rewrite it more readably here:

(t ? a:b:r) s = any (t ? r) [a ! 3 $ s, b ! 3 $ s, (b ! 1 $ a) ! 1 $ s]
(t ? _) s = (s !! t) == maximum s

This is a recursive implementation of exhaustive search. It recurs over the list of remaining games, branching on the three possible outcomes, and then, once the list is empty, checking whether or not our team has the maximum number of points. Again in (non-idiomatic) Python, this is:

def can_still_win(standings, games_left, our_team):
    if games_left == []:
        return standings[our_team] == max(standings)
    team1, team2, other_games = games_left[0], games_left[1], games_left[2:]
    team1Wins, team2Wins, tie = standings.copy(), standings.copy(), standings.copy()
    team1Wins[team1] += 3
    team2Wins[team2] += 3
    tie[team1] += 1
    tie[team2] += 1
    return (can_still_win(team1Wins, other_games, our_team)
            or can_still_win(team2Wins, other_games, our_team)
            or can_still_win(tie, other_games, our_team))

Try it online!

^*Sadly, TiO doesn't support Lens, so this link won't actually run.

Answer 2

Microsoft SQL Server, 792 bytes

CREATE FUNCTION my.f(@s XML,@m XML,@ INT)RETURNS TABLE RETURN
WITH s AS(SELECT s.value('@p','INT')p FROM @s.nodes('S')s(s)),
m AS(SELECT m.value('@i','INT')i,m.value('@j','INT')j FROM @m.nodes('M')m(m)),
a AS(SELECT ROW_NUMBER()OVER(ORDER BY-p)t,p FROM s),
b AS(SELECT p+3*(SELECT COUNT(*)FROM m WHERE t IN(i,j))o FROM a WHERE t=@),
c AS(SELECT i,j,ROW_NUMBER()OVER(ORDER BY 1/0)k FROM m WHERE @ NOT IN(i,j)),
d AS(SELECT COUNT(*)u,POWER(3,COUNT(*))-1 v FROM c UNION ALL SELECT u,v-1 FROM d WHERE v>0),
e AS(SELECT v,u,v/3 q,v%3 r FROM d UNION ALL SELECT v,u-1,q/3,q%3 FROM e WHERE u>1),
f AS(SELECT v,p+SUM(IIF(t=i,r,(2-r))%3*3/2)s FROM a,c,e WHERE t IN(i,j)AND k=u GROUP BY v,t,p),
g AS(SELECT MAX(s)x FROM f GROUP BY v)SELECT SUM(IIF(o<ISNULL(x,p),0,1))f FROM a,(b OUTER APPLY g)WHERE t=1;

The function returns 0 for a false outcome and more than 0 for a truthy one.

The whole snippet:

SET NOCOUNT ON;
--USE tempdb;
USE rextester;
GO
IF SCHEMA_ID('my') IS NULL EXEC('CREATE SCHEMA my');
ELSE BEGIN
  IF OBJECT_ID('my.f', 'IF') IS NOT NULL DROP FUNCTION my.f;
  IF OBJECT_ID('my.s', 'U') IS NOT NULL DROP TABLE my.s;
  IF OBJECT_ID('my.m', 'U') IS NOT NULL DROP TABLE my.m;
  IF OBJECT_ID('my.c', 'U') IS NOT NULL DROP TABLE my.c;
END;
GO
CREATE TABLE my.c( -- Test cases
  c INT PRIMARY KEY CLUSTERED CHECK(c > 0), -- Test Case Id
  n INT CHECK(n > 0), -- Current position of the team of interest
);
CREATE TABLE my.s( -- Standings
  a INT FOREIGN KEY REFERENCES my.c(c) CHECK(a > 0), -- Test cAse Id
  p INT CHECK(p > 0) -- Team pts
);
CREATE TABLE my.m( -- Matches
  s INT FOREIGN KEY REFERENCES my.c(c) CHECK(s > 0), -- Test caSe Id
  i INT CHECK(i > 0), -- Team i
  j INT CHECK(j > 0), -- Team j
  CHECK(i != j)
);
GO
INSERT my.c(c, n) VALUES (1, 2), (2, 1), (3, 3), (4, 2), (5, 2), (6, 1), (7, 2);
INSERT my.s(a, p) VALUES (1, 93), (1, 86), (1, 78), (1, 76), (1, 75),
(2, 50), (3, 10), (3, 10), (3, 10), (4, 15), (4, 10), (4, 8),
(5, 10), (5, 9), (5, 8), (6, 10), (6, 9), (6, 9), (7, 21), (7, 12), (7, 11);
INSERT my.m(s, i, j) VALUES (1, 1, 2), (1, 4, 3), (1, 2, 3), (1, 3, 2), (1, 1, 2),
(4, 2, 3), (4, 1, 3), (4, 1, 3),(4, 3, 1), (4, 2, 1), (6, 2, 3), (6, 3, 2),
(7, 2, 1), (7, 1, 2), (7, 2, 3), (7, 1, 3), (7, 1, 3), (7, 3, 1), (7, 3, 1);
GO
CREATE FUNCTION my.f(@s XML,@m XML,@ INT)RETURNS TABLE RETURN
WITH s AS(SELECT s.value('@p','INT')p FROM @s.nodes('S')s(s)),
m AS(SELECT m.value('@i','INT')i,m.value('@j','INT')j FROM @m.nodes('M')m(m)),
a AS(SELECT ROW_NUMBER()OVER(ORDER BY-p)t,p FROM s),
b AS(SELECT p+3*(SELECT COUNT(*)FROM m WHERE t IN(i,j))o FROM a WHERE t=@),
c AS(SELECT i,j,ROW_NUMBER()OVER(ORDER BY 1/0)k FROM m WHERE @ NOT IN(i,j)),
d AS(SELECT COUNT(*)u,POWER(3,COUNT(*))-1 v FROM c UNION ALL SELECT u,v-1 FROM d WHERE v>0),
e AS(SELECT v,u,v/3 q,v%3 r FROM d UNION ALL SELECT v,u-1,q/3,q%3 FROM e WHERE u>1),
f AS(SELECT v,p+SUM(IIF(t=i,r,(2-r))%3*3/2)s FROM a,c,e WHERE t IN(i,j)AND k=u GROUP BY v,t,p),
g AS(SELECT MAX(s)x FROM f GROUP BY v)SELECT SUM(IIF(o<ISNULL(x,p),0,1))f FROM a,(b OUTER APPLY g)WHERE t=1;
GO
SELECT c, f
FROM my.c
OUTER APPLY(SELECT p FROM my.s S WHERE a = c FOR XML AUTO)S(s)
OUTER APPLY(SELECT i, j FROM my.m M WHERE s = c FOR XML AUTO)M(m)
OUTER APPLY my.f(s, m, n)
ORDER BY c
OPTION(MAXRECURSION 0);

Check It Online!

Answer 3

Python 2, 242 221 bytes

from itertools import*
def u(S,M,t,O):
 for m,o in zip(M,O):
  if t in m:S[t]+=3
  else:S[m[0]]+=(1,3,0)[o];S[m[1]]+=(1,0,3)[o]
 return S[t]>=max(S)
f=lambda s,m,t:any(u(s[:],m,t,O)for O in product([0,1,2],repeat=len(m)))

Try it online!

After a first pass with basic golf-thinking. Takes input with 0-based indexing; test cases in TIO adjust for this via the function F.

The product([0,1,2],repeat=len(m)) iteration evaluates the possible outcomes over tie/win/loss for each match unless the team-of-interest (TOI) is a part of the match (in which, the TOI is always assumed to win).

Answer 4

JavaScript (ES6), 145 bytes

(s,d,t,o=[],g=(c=s,i=0)=>d[i]?[3,,0,3,1,1].map((a,j)=>(j%=2,r=j?r:[...c],r[d[i][j]]+=a,g(r,i+1))):o.push(c))=>o.some(r=>r[t]==Math.max(...r),g())

Takes score input as an array ([93,86,78,76,75]), upcoming games as an array of 2-value arrays ([[0,1],[3,2],[1,2],[2,1],[0,1]]), and team index as an integer (1). Everything is 0-indexed.

Test Snippet

let f=
(s,d,t,o=[],g=(c=s,i=0)=>d[i]?[3,,0,3,1,1].map((a,j)=>(j%=2,r=j?r:[...c],r[d[i][j]]+=a,g(r,i+1))):o.push(c))=>o.some(r=>r[t]==Math.max(...r),g())

console.log("---Truthy---")
console.log(f([93, 86, 78, 76, 75], [[0,1], [3,2], [1,2], [2,1], [0,1]], 1))
console.log(f([50], [], 0))
console.log(f([10, 10, 10], [], 2))
console.log(f([15, 10, 8], [[1,2], [0,2], [0,2], [2,0], [1,0]], 1))
console.log("---Falsy---")
console.log(f([10, 9, 8], [], 1))
console.log(f([10, 9, 9], [[1,2],[2,1]], 0))
console.log(f([21, 12, 11], [[1,0], [0,1], [1,2], [0,2], [0,2], [2,0], [2,0]], 1))

.as-console-wrapper{max-height:100%!important}