Mixing
CodeFights: Frisbees
Clash Royale CLAN TAG#URR8PPP
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;
up vote
7
down vote
favorite
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
python python-3.x time-limit-exceeded
asked Aug 17 at 9:55
Ludisposed
6,10621758
add a comment |Â
up vote
7
down vote
favorite
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
python python-3.x time-limit-exceeded
asked Aug 17 at 9:55
Ludisposed
6,10621758
add a comment |Â
up vote
7
down vote
favorite
up vote
7
down vote
favorite
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
python python-3.x time-limit-exceeded
asked Aug 17 at 9:55
Ludisposed
6,10621758
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
python python-3.x time-limit-exceeded
asked Aug 17 at 9:55
Ludisposed
6,10621758
asked Aug 17 at 9:55
Ludisposed
6,10621758
asked Aug 17 at 9:55
Ludisposed
6,10621758
asked Aug 17 at 9:55
Ludisposed
6,10621758
6,10621758
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
7
down vote
accepted
builtin
you can use some parts of the standard library:
math.hypotfor the distance functioncollections.defaultdictfor the frisbees_helditertools.combinationsfor 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)
answered Aug 17 at 11:20
Maarten Fabré
3,434214
You post some great suggestions, although this maybe is a bit over-engineering. Thatwhile Truewith ayieldseems unnecessary to me since, I'm only interested in the player afterxthrows.
– Ludisposed
Aug 17 at 11:44
1
I used the generator because it allowed me to easily see whether the logic was correct and returned the correct order of throws
– Maarten Fabré
Aug 17 at 11:46
frisbees_held.get(x, 0)could just befrisbees_held[x], since it is adefaultdict.
– Graipher
Aug 17 at 12:19
add a comment |Â
up vote
4
down vote
Distance would be easier to read if you instead used
defas per PEP8:
Always use a def statement instead of an assignment statement that binds a lambda expression directly to an identifier.
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(nlog(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(slog(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(nslog(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 fracnlog(k)$. And so if each person can throw to less than one ninth of people it should be faster.
answered Aug 17 at 11:21
Peilonrayz
24.7k336103
If I were carrying out this analysis I would write, "the code in the post has runtime $O(nmax(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(nlog 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(nlog n + (sqrt n + phi n) p) = O(nmax(log n, p))$."
– Gareth Rees
Aug 17 at 14:25
So in fact the quadtree does help (asymptotically) in the event that $p < n$.
– Gareth Rees
Aug 17 at 14:28
@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(sqrtn + m)$?
– Peilonrayz
Aug 17 at 14:32
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$.)
– Gareth Rees
Aug 17 at 14:36
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 :)
– Ludisposed
Aug 20 at 9:43
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
7
down vote
accepted
builtin
you can use some parts of the standard library:
math.hypotfor the distance functioncollections.defaultdictfor the frisbees_helditertools.combinationsfor 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)
answered Aug 17 at 11:20
Maarten Fabré
3,434214
You post some great suggestions, although this maybe is a bit over-engineering. Thatwhile Truewith ayieldseems unnecessary to me since, I'm only interested in the player afterxthrows.
– Ludisposed
Aug 17 at 11:44
1
I used the generator because it allowed me to easily see whether the logic was correct and returned the correct order of throws
– Maarten Fabré
Aug 17 at 11:46
frisbees_held.get(x, 0)could just befrisbees_held[x], since it is adefaultdict.
– Graipher
Aug 17 at 12:19
add a comment |Â
up vote
7
down vote
accepted
builtin
you can use some parts of the standard library:
math.hypotfor the distance functioncollections.defaultdictfor the frisbees_helditertools.combinationsfor 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)
answered Aug 17 at 11:20
Maarten Fabré
3,434214
You post some great suggestions, although this maybe is a bit over-engineering. Thatwhile Truewith ayieldseems unnecessary to me since, I'm only interested in the player afterxthrows.
– Ludisposed
Aug 17 at 11:44
1
I used the generator because it allowed me to easily see whether the logic was correct and returned the correct order of throws
– Maarten Fabré
Aug 17 at 11:46
frisbees_held.get(x, 0)could just befrisbees_held[x], since it is adefaultdict.
– Graipher
Aug 17 at 12:19
add a comment |Â
up vote
7
down vote
accepted
up vote
7
down vote
accepted
builtin
you can use some parts of the standard library:
math.hypotfor the distance functioncollections.defaultdictfor the frisbees_helditertools.combinationsfor 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)
answered Aug 17 at 11:20
Maarten Fabré
3,434214
builtin
you can use some parts of the standard library:
math.hypotfor the distance functioncollections.defaultdictfor the frisbees_helditertools.combinationsfor 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)
answered Aug 17 at 11:20
Maarten Fabré
3,434214
edited Aug 17 at 13:30
answered Aug 17 at 11:20
Maarten Fabré
3,434214
answered Aug 17 at 11:20
Maarten Fabré
3,434214
answered Aug 17 at 11:20
Maarten Fabré
3,434214
3,434214
You post some great suggestions, although this maybe is a bit over-engineering. Thatwhile Truewith ayieldseems unnecessary to me since, I'm only interested in the player afterxthrows.
– Ludisposed
Aug 17 at 11:44
1
I used the generator because it allowed me to easily see whether the logic was correct and returned the correct order of throws
– Maarten Fabré
Aug 17 at 11:46
frisbees_held.get(x, 0)could just befrisbees_held[x], since it is adefaultdict.
– Graipher
Aug 17 at 12:19
add a comment |Â
You post some great suggestions, although this maybe is a bit over-engineering. Thatwhile Truewith ayieldseems unnecessary to me since, I'm only interested in the player afterxthrows.
– Ludisposed
Aug 17 at 11:44
1
I used the generator because it allowed me to easily see whether the logic was correct and returned the correct order of throws
– Maarten Fabré
Aug 17 at 11:46
frisbees_held.get(x, 0)could just befrisbees_held[x], since it is adefaultdict.
– Graipher
Aug 17 at 12:19
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.– Ludisposed
Aug 17 at 11:44
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.– Ludisposed
Aug 17 at 11:44
1
1
I used the generator because it allowed me to easily see whether the logic was correct and returned the correct order of throws
– Maarten Fabré
Aug 17 at 11:46
I used the generator because it allowed me to easily see whether the logic was correct and returned the correct order of throws
– Maarten Fabré
Aug 17 at 11:46
frisbees_held.get(x, 0) could just be frisbees_held[x], since it is a defaultdict.– Graipher
Aug 17 at 12:19
frisbees_held.get(x, 0) could just be frisbees_held[x], since it is a defaultdict.– Graipher
Aug 17 at 12:19
add a comment |Â
up vote
4
down vote
Distance would be easier to read if you instead used
defas per PEP8:
Always use a def statement instead of an assignment statement that binds a lambda expression directly to an identifier.
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(nlog(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(slog(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(nslog(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 fracnlog(k)$. And so if each person can throw to less than one ninth of people it should be faster.
answered Aug 17 at 11:21
Peilonrayz
24.7k336103
If I were carrying out this analysis I would write, "the code in the post has runtime $O(nmax(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(nlog 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(nlog n + (sqrt n + phi n) p) = O(nmax(log n, p))$."
– Gareth Rees
Aug 17 at 14:25
So in fact the quadtree does help (asymptotically) in the event that $p < n$.
– Gareth Rees
Aug 17 at 14:28
@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(sqrtn + m)$?
– Peilonrayz
Aug 17 at 14:32
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$.)
– Gareth Rees
Aug 17 at 14:36
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 :)
– Ludisposed
Aug 20 at 9:43
add a comment |Â
up vote
4
down vote
Distance would be easier to read if you instead used
defas per PEP8:
Always use a def statement instead of an assignment statement that binds a lambda expression directly to an identifier.
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(nlog(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(slog(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(nslog(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 fracnlog(k)$. And so if each person can throw to less than one ninth of people it should be faster.
answered Aug 17 at 11:21
Peilonrayz
24.7k336103
If I were carrying out this analysis I would write, "the code in the post has runtime $O(nmax(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(nlog 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(nlog n + (sqrt n + phi n) p) = O(nmax(log n, p))$."
– Gareth Rees
Aug 17 at 14:25
So in fact the quadtree does help (asymptotically) in the event that $p < n$.
– Gareth Rees
Aug 17 at 14:28
@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(sqrtn + m)$?
– Peilonrayz
Aug 17 at 14:32
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$.)
– Gareth Rees
Aug 17 at 14:36
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 :)
– Ludisposed
Aug 20 at 9:43
add a comment |Â
up vote
4
down vote
up vote
4
down vote
Distance would be easier to read if you instead used
defas per PEP8:
Always use a def statement instead of an assignment statement that binds a lambda expression directly to an identifier.
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(nlog(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(slog(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(nslog(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 fracnlog(k)$. And so if each person can throw to less than one ninth of people it should be faster.
answered Aug 17 at 11:21
Peilonrayz
24.7k336103
Distance would be easier to read if you instead used
defas per PEP8:
Always use a def statement instead of an assignment statement that binds a lambda expression directly to an identifier.
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(nlog(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(slog(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(nslog(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 fracnlog(k)$. And so if each person can throw to less than one ninth of people it should be faster.
answered Aug 17 at 11:21
Peilonrayz
24.7k336103
edited Aug 17 at 14:25
answered Aug 17 at 11:21
Peilonrayz
24.7k336103
answered Aug 17 at 11:21
Peilonrayz
24.7k336103
answered Aug 17 at 11:21
Peilonrayz
24.7k336103
24.7k336103
If I were carrying out this analysis I would write, "the code in the post has runtime $O(nmax(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(nlog 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(nlog n + (sqrt n + phi n) p) = O(nmax(log n, p))$."
– Gareth Rees
Aug 17 at 14:25
So in fact the quadtree does help (asymptotically) in the event that $p < n$.
– Gareth Rees
Aug 17 at 14:28
@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(sqrtn + m)$?
– Peilonrayz
Aug 17 at 14:32
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$.)
– Gareth Rees
Aug 17 at 14:36
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 :)
– Ludisposed
Aug 20 at 9:43
add a comment |Â
If I were carrying out this analysis I would write, "the code in the post has runtime $O(nmax(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(nlog 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(nlog n + (sqrt n + phi n) p) = O(nmax(log n, p))$."
– Gareth Rees
Aug 17 at 14:25
So in fact the quadtree does help (asymptotically) in the event that $p < n$.
– Gareth Rees
Aug 17 at 14:28
@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(sqrtn + m)$?
– Peilonrayz
Aug 17 at 14:32
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$.)
– Gareth Rees
Aug 17 at 14:36
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 :)
– Ludisposed
Aug 20 at 9:43
If I were carrying out this analysis I would write, "the code in the post has runtime $O(nmax(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(nlog 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(nlog n + (sqrt n + phi n) p) = O(nmax(log n, p))$."
– Gareth Rees
Aug 17 at 14:25
If I were carrying out this analysis I would write, "the code in the post has runtime $O(nmax(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(nlog 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(nlog n + (sqrt n + phi n) p) = O(nmax(log n, p))$."
– Gareth Rees
Aug 17 at 14:25
So in fact the quadtree does help (asymptotically) in the event that $p < n$.
– Gareth Rees
Aug 17 at 14:28
So in fact the quadtree does help (asymptotically) in the event that $p < n$.
– Gareth Rees
Aug 17 at 14:28
@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(sqrtn + m)$?
– Peilonrayz
Aug 17 at 14:32
@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(sqrtn + m)$?
– Peilonrayz
Aug 17 at 14:32
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$.)
– Gareth Rees
Aug 17 at 14:36
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$.)
– Gareth Rees
Aug 17 at 14:36
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 :)
– Ludisposed
Aug 20 at 9:43
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 :)
– Ludisposed
Aug 20 at 9:43
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f201867%2fcodefights-frisbees%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
