# 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} --> {1} in {2}sec(s)'.format(args, result, end-start))

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__':

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.

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}

• 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! – Karthic Raghupathi Oct 21 '16 at 13:48