CodeFights: Frisbees Description


  You and your friends are seizing another summer day, passing around the frisbee in the park. You have the most fun when the game is fair, so as much as possible, you would all like to ensure that everyone receives the disc an equal number of times. You also like to challenge yourselves, so when possible, you'll go for the longest pass you can throw.
  
  So each friend will throw according to the following rules:
  
  
  Pass to the friend who has held the frisbee the least amount of times.
  In the event of a tie, pass to the furthest among these friends.
  If there's also a tie for furthest, pass to the one of these friends with the lowest index.
  
  
  Given an array friends containing info about each player (where they're standing and how far they can throw), as well as the index of the starting player and the total number of passes, your task is to find which player will be holding the frisbee after all the passes are complete.
  
  NOTE: Because you and your friends are really good at frisbee, it's safe to assume that all passes will be completed successfully; none of you will fumble a throw or catch.


Example

For friends = [[152, 213, 276], [274, 259, 151], [40, 57, 130], [203, 87, 189], [43, 182, 163]], numberOfPasses = 19, and startingPlayer = 4, the output should be frisbees(friends, numberOfPasses, startingPlayer) = 4

Visual example



Constraints

2 ≤ friends.length ≤ 5000
friends[i].length = 3
0 ≤ friends[i][0] ≤ 400
0 ≤ friends[i][1] ≤ 400
0 ≤ friends[i][2] ≤ 500
0 ≤ numberOfPasses ≤ 2500
0 ≤ startingPlayer &lt; friends.length


Code

def make_player_throws_list(friends):
    distance = lambda f, s: (f[0] - s[0])**2 + (f[1] - s[1])**2
    return [
        [
            (i, distance(f, s))
            for i, f in enumerate(friends)
            if distance(f, s) &lt;= s[2]**2 and f != s
        ]
        for s in friends
    ]

def frisbees(friends, number_of_passes, starting_player):
    frisbee_held = {i: 0 for i in range(len(friends))}
    player_possible_throws_list = make_player_throws_list(friends)

    for _ in range(number_of_passes):
        frisbee_held[starting_player] += 1
        starting_player = min(
                                player_possible_throws_list[starting_player],
                                key = lambda x: (frisbee_held[x[0]], -x[1], x[0])
                             )[0]
    return starting_player
builtin

you can use some parts of the standard library:


math.hypot for the distance function
collections.defaultdict for the frisbees_held
itertools.combinations for generating the combinations in the distance matrix


imports:

from itertools import combinations, islice
from collections import namedtuple, defaultdict
from math import hypot


players

you can use a class, or even a namedtuple to represent a player, to simplify the building of the distance matrix

Player = namedtuple('Player', 'name x y range')
players = [[152, 213, 276], [274, 259, 151], [40, 57, 130], [203, 87, 189], [43, 182, 163]]
players = [Player(i, x, y, range_) for i, (x, y, range_) in enumerate(players)]



[Player(name=0, x=152, y=213, range=276),
 Player(name=1, x=274, y=259, range=151),
 Player(name=2, x=40, y=57, range=130),
 Player(name=3, x=203, y=87, range=189),
 Player(name=4, x=43, y=182, range=163)]



distance matrix

you calculate the distance between the players a few times, you can reduce that by doing something like this:

def distance_generator(players):
    for p1, p2 in combinations(players, 2):
        dist = hypot((p1.x - p2.x), (p1.y - p2.y))
        if dist &lt; p1.range:
            yield p1, p2, dist
        if dist &lt; p2.range:
            yield p2, p1, dist


here a dict of dicts might be a more appropriate data structure than a list of lists

def build_distance_matrix(players): 
    distance_matrix = defaultdict(dict)
    for p1, p2, dist in distance_generator(players):
        distance_matrix[p1.name][p2.name] = dist
    return dict(distance_matrix)



{
    0: 
    {
        1: 130.38404810405297,
        2: 192.04166214652486,
        3: 135.9301291105103,
        4: 113.3225485064645,
    },
    1: {0: 130.38404810405297},
    3: {
        0: 135.9301291105103,
        1: 186.07794065928394,
        2: 165.73774464496614,
        4: 186.07794065928394,
    },
     4: {0: 113.3225485064645, 2: 125.03599481749245},
     2: {4: 125.03599481749245},
}



throwing

you can model a game as an endless series of people throwing the frisbee to eachother. The min(...) you use is the correct way to do this, but can be formatted clearer

def game(distance_matrix, start_player):
    frisbees_held = defaultdict(int)
    target = start_player
    while True:
        frisbees_held[target] += 1
        targets = distance_matrix[target]
        yield target
        target = min(
            targets,
            key=lambda x: (
                frisbees_held[x], # number times held
                -targets[x], # furthest
                x # lowest index
            ) 
        )


final selection

then you can use the nth itertools recipe

def nth(iterable, n, default=None):
    "Returns the nth item or a default value"
    return next(islice(iterable, n, None), default)

def frisbees(friends, numberOfPasses, startingPlayer):
    players = [Player(i, x, y, range_) for i, (x, y, range_) in enumerate(friends)]
    distance_matrix = build_distance_matrix(players)
    g = game(distance_matrix, startingPlayer)
    return nth(g, numberOfPasses)