Determining a value given the coordinates for numbers arranged in a triangular fashion 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} --&gt; {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) --&gt; 9 in 0.0sec(s)
(5, 10) --&gt; 96 in 0.0sec(s)
(100, 100) --&gt; 19801 in 0.0sec(s)
(1000, 1000) --&gt; 1998001 in 0.148000001907sec(s)
(10000, 10000) --&gt; 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.
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) =&amp;\ 1 + 2 + 3 + \ldots + x = \frac{x\ (x+1)}{2} \\
\mathit{fn}(x - 1, 2) =&amp;\ \mathit{fn}(x, 1) - 1 \\
\mathit{fn}(a - 2, 3) =&amp;\ \mathit{fn}(a, 1) - 2 \\
 \vdots&amp; \\
\mathit{fn}(a - (y-1), y) =&amp;\ \mathit{fn}(a, 1) - (y-1) \\
 \vdots&amp; \ \scriptstyle{a\ =\ x+y - 1} \\
\mathit{fn}(x, y) =&amp;\ \mathit{fn}(x + y - 1, 1) - (y - 1) = \frac{(x + y)(x + y - 1)}{2} - (y - 1)
\end{align}$$