Stuck in Game Theory problem


#1

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?


#2

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[0] != x[1], 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 )
      also reads as,
    ( 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[2]
        x.ties += z[4]
        x.losses += z[3]
        x.gf += m
        x.ga += n
        x.pts += z[0]        
        y.wins += z[3]
        y.ties += z[4]
        y.losses += z[2]
        y.gf += n
        y.ga += m
        y.pts += z[1]
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.


#3

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?


#4

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

#5

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][1] == n: return a + 1
    return x[0][1] 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
>>> 

#6

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)