# Stuck in Game Theory problem

This is the link to the problem: http://www.spoj.com/problems/VECTAR13/

I cannot find a logical solution, I tried %2 and simple constant 1, but none of that is working. This should be done in O(1), but I am stuck. Can anyone please give an idea?

Clearly, I am no data scientist, or even mathematician, but the problem is intriguing. This may be way out in left field…

``````from random import randint

class Team:
id = 0
def set_id(self):
Team.id += 1
return self.id
def __init__(self):
self.id = self.set_id()
self.wins = 0
self.ties = 0
self.losses = 0
self.gf = 0
self.ga = 0
self.pts = 0
def __repr__(self):
return "id: {}, wins: {}, ties: {}, losses: {}, gf: {}, ga: {}, pts: {}\
".format(self.id, self.wins, self.ties, self.losses, self.gf, self.ga, self.pts)
``````
``````def slate(n):
return [Team() for i in range(n)]
``````
``````def get_draws(n):
d = []
for x in range(n):
for y in range(n):
d.append((x + 1, y + 1))
return list(filter(lambda x: x != x, d))
``````
``````def goals(x):
return (randint(0, 4),randint(0, 4))
``````
``````def run_draws(d):
return [goals(d[i]) for i in range(len(d))]
``````
``````def compare(a, b):
'''
Meaning of tuples...
( points_for_a, points_for_b, win_for_a, win_for_b, tie )
( points_for_a, points_for_b, loss_for_b, loss_for_a, tie )
'''
if a > b: return (3, 0, 1, 0, 0)
if b > a: return (0, 3, 0, 1, 0)
return (1, 1, 0, 0, 1)
``````
``````def crunch(s, t, u):
'''
crunch(outcomes, teams, draws)
'''
for i in range(len(s)):
a, b = u[i]
x, y = (t[a - 1], t[b - 1])
m, n = s[i]
z = compare(m, n)
x.wins += z
x.ties += z
x.losses += z
x.gf += m
x.ga += n
x.pts += z
y.wins += z
y.ties += z
y.losses += z
y.gf += n
y.ga += m
y.pts += z
``````
``````def results(t):
for x in t:
print (x)
``````
``````teams = []    # for inspection purposes

def main():
global teams
teams = slate(8)
draws = get_draws(len(teams))
outcomes = run_draws(draws)
crunch(outcomes, teams, draws)
results(teams)

main()
``````
``````id: 1, wins: 6, ties: 2, losses: 6, gf: 22, ga: 24, pts: 20
id: 2, wins: 4, ties: 4, losses: 6, gf: 31, ga: 35, pts: 16
id: 3, wins: 6, ties: 4, losses: 4, gf: 28, ga: 23, pts: 22
id: 4, wins: 2, ties: 4, losses: 8, gf: 24, ga: 36, pts: 10
id: 5, wins: 4, ties: 3, losses: 7, gf: 27, ga: 34, pts: 15
id: 6, wins: 10, ties: 0, losses: 4, gf: 43, ga: 26, pts: 30
id: 7, wins: 6, ties: 5, losses: 3, gf: 29, ga: 22, pts: 23
id: 8, wins: 5, ties: 4, losses: 5, gf: 23, ga: 27, pts: 19
>>>
``````

It remains to analyze the data for Rank (most points), Most Wins, Least Losses, etc.

Goals are not that much of a problem. You can always set that potential lucky team scored 3000 goals for example. The rank and number of wins are the key things. Anyone with an idea?

Here are some analysis tools for Highest Goals For, Lowest Goals Against, and Highest Points…

``````def hgf(t):
id = 0
gf = 0
for x in t:
if x.gf > gf: id = x.id; gf = x.gf
return id

def lga(t):
id = 0
ga = 4 * (len(t) - 1)
for x in t:
if x.ga < ga: id = x.id; ga = x.ga
return id

def hpt(t):
id = 0
pts = 0
for x in t:
if x.pts > pts: id = x.id; pts = x.pts
return id

def check_for_lucky(t):
id = hpt(t)
return id if lga(t) == hgf(t) == id else False
``````

Then to `main()` add this line at the end…

``````print (check_for_lucky(teams))
``````

Taking a swipe at brute forcing the output…

``````def sort_by_gf(array):
key_group = []
for x in array:
key_group.append((x.gf, x.id))
return sorted(key_group, reverse=True)
``````
``````def sort_by_ga(array):
key_group = []
for x in array:
key_group.append((x.ga, x.id))
return sorted(key_group, reverse=False)
``````
``````def sort_by_wins(array):
key_group = []
for x in array:
key_group.append((x.wins, x.id))
return sorted(key_group, reverse=True)
``````
``````def sort_by_ties(array):
key_group = []
for x in array:
key_group.append((x.ties, x.id))
return sorted(key_group, reverse=True)
``````
``````def sort_by_losses(array):
key_group = []
for x in array:
key_group.append((x.losses, x.id))
return sorted(key_group, reverse=False)
``````
``````def sort_by_pts(array):
key_group = []
for x in array:
key_group.append((x.pts, x.id))
return sorted(key_group, reverse=True)
``````

In `main()` (or the command line, for the present)

``````# rank
results(teams, sort_by_pts(teams))
# most wins
results(teams, sort_by_wins(teams))
``````

The return from sort_by_pts (and all the others) is a list of tuples. The value is first, the id second. Tuples are sorted by their first term. We can read a rank table from the return value…

``````# x is a list of tuples, y is an id
def get_rank(x, y=0):
def find(n):
for a in range(len(x)):
if x[a] == n: return a + 1
return x if not y else find(y)
``````
``````>>> get_rank(sort_by_pts(teams))
8
>>> get_rank(sort_by_pts(teams), 8)
1
>>> get_rank(sort_by_wins(teams))
8
>>> get_rank(sort_by_wins(teams), 8)
1
>>> get_rank(sort_by_losses(teams), 8)
2
>>> get_rank(sort_by_gf(teams))
8
>>> get_rank(sort_by_ga(teams))
4
>>> get_rank(sort_by_ga(teams), 8)
3
>>>
``````

Manually working through the solutions for low values of N might give you a better understanding of the problem, you’ll need something to reason about (not sure why you’d try modulus 2)