CodeFights: Frisbees

Question

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

Answer 1

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 < p1.range:
            yield p1, p2, dist
        if dist < 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)

Answer 2

1. Distance would be easier to read if you instead used def as per PEP8:

   Always use a def statement instead of an assignment statement that binds a lambda expression directly to an identifier.

2. You don't need to return both the distance and the player number. If you sort the inner comprehension by the reverse of the distance.

   This would mean you can just use frisbee_held.get, rather than a lambda.

This can get:

def distance(f, s):
    return (f[0] - s[0])**2 + (f[1] - s[1])**2

def make_player_throws_list(friends):
    throwable_friends = []
    for s in friends:
        reachable_friends = [
            (i, distance(f, s))
            for i, f in enumerate(friends)
            if s != f and distance(f, s) <= s[2]**2
        ]
        throwable_friends.append([
            i for i, _ in sorted(reachable_friends, key=lambda i: i[1], reverse=True)
        ])
    return throwable_friends

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

    for _ in range(number_of_passes):
        frisbee_held[player] += 1
        player = min(throwable_friends[player], key=frisbee_held.get)
    return player

---

Your code has a complexity of \$O(n^2 + tp)\$ where \$n\$ is friends.length, \$t\$ is friends that can be thrown to which is \$t \le n\$, and \$p\$ is numberOfPasses. The average case is also the worst case, and so this isn't great.

Depending on the sample you may be able to reduce the average case by using a quadtree. To insert into the tree takes \$O(\log(k))\$ where \$k\$ is the dimensions of the quadtree, \$400\$ here. And so you can create the tree in \$O(n\log(k))\$ time.

After creating the tree you may be able to get a better average speed, as you can take a square region in \$O(s\log(k))\$ time, where \$s\$ is the sample you get from the tree. Since \$s \le n\$ it has the same worst case, but allows for a better average case, depending on the sample.

You can then use \$s\$ to build \$t\$ making \$t \le s \le n\$. And so the worst case is worse at \$O(ns\log(k) + tp)\$, but due to potentially sampling a smaller selection can lead to a speed-up. And so this should be faster when, roughly, \$s \lt \frac{n}{\log(k)}\$. And so if each person can throw to less than one ninth of people it should be faster.