Evenly spaced code clear solution for Evenly Spaced Trees by veky - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

Evenly spaced code solution in Clear category for Evenly Spaced Trees by veky

import operator, functools, math

def evenly_spaced_trees(trees):
    spaces = [*map(operator.sub, trees[1:], trees)]
    delta = functools.reduce(math.gcd, spaces)
    return sum(d // delta - 1 for d in spaces)

April 4, 2019

Comments:

piter239 on April 28, 2020, 6:43 a.m.
I had the same idea, but in my variant the result is computed without loop. I'm still trying to understand how your <pre class='brush: python'>return sum(d // delta - 1 for d in spaces) </pre> is equivalent to <a href="https://py.checkio.org/mission/evenly-spaced-trees/publications/piter239/python-3/reducegcd-trees/">my</a>: <pre class='brush: python'>return trees[-1] // reduce(gcd, trees[1:]) - (len(trees) - 1) </pre> But the look of your code is an inspiration!

veky on April 28, 2020, 8:39 a.m.
sum(x-1 for x in xs) is of course same as sum(xs)-len(xs), if that's what you meant. And you still have a loop inside of reduce, of course:-).

piter239 on April 28, 2020, 8:48 a.m.
well, my complete solution (with perhaps unnecessary checks) is <pre class='brush: python'>def evenly_spaced_trees(trees: List[int]) -> int: if len(trees) < 3: return 0 if trees[0]: trees = [x - trees[0] for x in trees] return trees[-1] // reduce(gcd, trees[1:]) - (len(trees) - 1) </pre> it has 2 loops in total, instead of 3. I totally get it affects only the c in O(N), of course

veky on April 28, 2020, 5:18 p.m.
Yes, a nice idea is just looking at the offsets from first, instead of intermediate differences.

ruslan92mv on May 13, 2020, 9:29 a.m.
Nice idea

vvm70 on March 20, 2021, 11:49 a.m.
Nice! You could use <pre class='brush: python'>int.__sub__ </pre> instead of operator module.

veky on March 20, 2021, 1:35 p.m.
Of course. But since I already imported two things, a third wasn't far away. :-)

joffroy on Aug. 28, 2022, 7:09 p.m.
very efficient

veky on Aug. 29, 2022, 2:06 a.m.
Not really - see @piter239's comment above.

Rock

0 %

PyCharm The Python IDE for Professional Developers. Enjoy productive Python, web and scientific development with PyCharm. Download it now!