2
\$\begingroup\$

Numbers are being stacked in the following manner:

7
4 8
2 5 9
1 3 6 10

The x-axis is horizontal and the y-axis is vertical. With that in mind, here are a few examples of the values and their coordinates:

  • 2, 3 (coordinate) ==> 8 (value)
  • 2, 2 (coordinate) ==> 5 (value)

I need to write a function \$fn(x, y)\$ which accepts a coordinate \$(x, y)\$ and returns the corresponding value. \$x\$ and \$y\$ can be any value between 1 and 100000 and I can only use standard python library.

Here is my brute force-ish attempt at solving this:

import time


def profile_it(fn, *args):
    start = time.time()
    result = fn(*args)
    end = time.time()
    print('{0} --> {1} in {2}sec(s)'.format(args, result, end-start))


def answer(x, y):
    result = 0
    max_limit = 100000
    x = max(min(x, max_limit), 1)
    y = max(min(y, max_limit), 1)
    counter = 1
    not_finished = True
    while not_finished:
        x_cord = 0
        y_cord = counter + 1
        for step in xrange(counter):
            result += 1
            x_cord += 1
            y_cord -= 1
            if x == x_cord and y == y_cord:
                return str(result)
        counter += 1


if __name__ == '__main__':
    profile_it(answer, 3, 2)
    profile_it(answer, 5, 10)
    profile_it(answer, 100, 100)
    profile_it(answer, 1000, 1000)
    profile_it(answer, 10000, 10000)

The above solution works reasonably well for smaller inputs. However, it takes too long to compute the result for larger inputs as evident from the following results:

(3, 2) --> 9 in 0.0sec(s)
(5, 10) --> 96 in 0.0sec(s)
(100, 100) --> 19801 in 0.0sec(s)
(1000, 1000) --> 1998001 in 0.148000001907sec(s)
(10000, 10000) --> 199980001 in 15.5760002136sec(s)

I'm sure there is a lot of room for improvement in my code. I'm looking for pointers on what kind of an algorithm I should use to solve this problem in a quicker fashion.

Based on some reading, I've attempted to use memoization using an OrderedDict to keep track of values that were computed, so for subsequent calls, I'm not re-calculating the values from scratch. However, that increased the time to solve this by a lot so I've discarded that approach.

\$\endgroup\$
3
\$\begingroup\$

I don't see why you should return the answer as a string. That makes your mathematical function weird.

You shouldn't use flag variables like not_finished = True; they are almost never necessary, and in this case not_finished is totally superfluous, since it is always True. Actually, this loop would be better written as

for counter in itertools.count(1):
    x_cord = 0
    …

Your solution is brute force. I would characterize it as \$O(\max(x^2, y^2))\$. Of course, performance is going to be a problem with large coordinates. The solution is not to use memoization, but to work out a formula for the answer.

First, note that the numbers along the bottom (\$\mathit{fn}(x, 1)\$) are recognizable as the triangular numbers, and even if you didn't recognize them, you could easily figure out the formula. Then, you can count backwards along the \$\nwarrow\$ diagonal.

$$\begin{align} \mathit{fn}(x, 1) =&\ 1 + 2 + 3 + \ldots + x = \frac{x\ (x+1)}{2} \\ \mathit{fn}(x - 1, 2) =&\ \mathit{fn}(x, 1) - 1 \\ \mathit{fn}(a - 2, 3) =&\ \mathit{fn}(a, 1) - 2 \\ \vdots& \\ \mathit{fn}(a - (y-1), y) =&\ \mathit{fn}(a, 1) - (y-1) \\ \vdots& \ \scriptstyle{a\ =\ x+y - 1} \\ \mathit{fn}(x, y) =&\ \mathit{fn}(x + y - 1, 1) - (y - 1) = \frac{(x + y)(x + y - 1)}{2} - (y - 1) \end{align}$$

\$\endgroup\$
  • \$\begingroup\$ I'm returning a string because that was the requirement. I forgot to mention that in my question. Thanks for pointing itertools.count() to me. I was looking for something that would give me that functionality but I couldn't find it. And lastly, thanks for the explanation on how to solve this. I have learnt a lot! \$\endgroup\$ – Karthic Raghupathi Oct 21 '16 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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