7
\$\begingroup\$

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

enter image description here

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
\$\endgroup\$

2 Answers 2

7
\$\begingroup\$

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)
\$\endgroup\$
3
  • \$\begingroup\$ You post some great suggestions, although this maybe is a bit over-engineering. That while True with a yield seems unnecessary to me since, I'm only interested in the player after x throws. \$\endgroup\$
    – Ludisposed
    Aug 17, 2018 at 11:44
  • 1
    \$\begingroup\$ I used the generator because it allowed me to easily see whether the logic was correct and returned the correct order of throws \$\endgroup\$ Aug 17, 2018 at 11:46
  • \$\begingroup\$ frisbees_held.get(x, 0) could just be frisbees_held[x], since it is a defaultdict. \$\endgroup\$
    – Graipher
    Aug 17, 2018 at 12:19
4
\$\begingroup\$
  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.

\$\endgroup\$
5
  • \$\begingroup\$ If I were carrying out this analysis I would write, "the code in the post has runtime \$O(n\max(n,p))\$ where \$n\$ is the number of players and \$p\$ is the number of passes. Construction of a quadtree with \$n\$ items takes \$O(n\log n)\$, and querying a quadtree for the \$m\$ points within a circle takes \$O(\sqrt n + m)\$ so if on average each player can throw to \$\phi n\$ other players for some constant \$\phi\$, the quadtree-based algorithm will take on average \$O(n\log n + (\sqrt n + \phi n) p) = O(n\max(\log n, p))\$." \$\endgroup\$ Aug 17, 2018 at 14:25
  • \$\begingroup\$ So in fact the quadtree does help (asymptotically) in the event that \$p < n\$. \$\endgroup\$ Aug 17, 2018 at 14:28
  • \$\begingroup\$ @GarethRees I don't think it takes \$O(n \log n )\$, as we know the max size of the tree, at 400. Also why is querying \$O(\sqrt{n} + m)\$? \$\endgroup\$
    – Peilonrayz
    Aug 17, 2018 at 14:32
  • \$\begingroup\$ See Wikipedia's \$k\$-d tree article for the complexities of these operations. (Quadtree operations have the same complexities as \$k\$-d tree operations for \$k=2\$.) \$\endgroup\$ Aug 17, 2018 at 14:36
  • \$\begingroup\$ I've tried the QuadTree route and it got me a speedup of 2/3 time, which was still not enough to pass the Time constraints. But it was a good suggestion nonetheless :) \$\endgroup\$
    – Ludisposed
    Aug 20, 2018 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.