# Finding the position in a triangle for the given challenge

The LAMBCHOP doomsday device takes up much of the interior of Commander Lambda's space station, and as a result the prison blocks have an unusual layout. They are stacked in a triangular shape, and the bunny prisoners are given numerical IDs starting from the corner, as follows:

| 7

| 4 8

| 2 5 9

| 1 3 6 10

Each cell can be represented as points (x, y), with x being the distance from the vertical wall, and y being the height from the ground.

For example, the bunny prisoner at (1, 1) has ID 1, the bunny prisoner at (3, 2) has ID 9, and the bunny prisoner at (2,3) has ID 8. This pattern of numbering continues indefinitely (Commander Lambda has been taking a LOT of prisoners).

Write a function answer(x, y) which returns the prisoner ID of the bunny at location (x, y). Each value of x and y will be at least 1 and no greater than 100,000. Since the prisoner ID can be very large, return your answer as a string representation of the number.

Here is my solution:

y = int(input())
x = int(input())
sum_in_x = 1
for i in range(x):
sum_in_x = sum_in_x + range(x)[i]
in_sum =i + 2
sum_in_y = sum_in_x
for j in range(y - 1):
sum_in_y = sum_in_y + in_sum
in_sum += 1
print(sum_in_y)


It works and generates the needed solutions, but I am trying to understand if there are better ways of doing this.

Your current algorithm is very inefficient. I would use the following algorithmic approach:

def answer(x, y):
y_diff = y - 1
corner = x + y_diff
id = corner * (corner + 1) // 2
id -= y_diff
return str(id)


This method takes advantage of basic algebra. It uses the sum of the arithmetic progression of x to calculate the id of the bottom right corner, and then subtracts the difference of the input coordinate from the bottom right corner. The reason it take the y difference is because moving 45 degrees diagonally down right is equivalent to moving down (y-1) units and moving right (y-1) units. Is is much more efficient than your current method: instead of an increasing numbering of iterations through range, it does one multiplication.

# Benchmark

Testing your code compared to mine, mine runs about 10,000 to 100,000 times faster for random values of x and y between 1 and 100000. This is a very significant performance difference.

Additionally, in benchmarking, I discovered a slight bug in your current implementation. I didn't analyze your implementation deeply to understand it, but it seems that your current implementation returns an output corresponding to the reversed inputs (so for example, if I input (3, 2), the output is correct for (2, 3).) I suspect this may have been missed in your personal testing because the input is reversed of traditional coordinate order, i.e. you ask for y coordinate input before you ask for x coordinate input. I fixed this in my testing by switching all occurrences of x (and related variables) with y and vice versa.

# Some notes

Write a function answer(x, y) which returns the prisoner ID of the bunny at location (x, y).

def answer(x, y):
# ... algorithm
return str(output)


Also, use consistent spacing:

• in_sum =i + 2 to in_sum = i + 2

And take advantage of +=:

• sum_in_x = sum_in_x + range(x)[i] to sum_in_x += range(x)[i]
• sum_in_y = sum_in_y + in_sum to sum_in_y += in_sum

| 7

| 4 8

| 2 5 9

| 1 3 6 10

We can see patterns in the columns. We'll take $$\x\$$ as the input to the function. $$\x\$$ starts at 1, which will map to the bottom row of the triangle.

1. The first column, "1, 2, 4, 7", can be expressed as: $$\frac{(x+0)(x-1)}{2}+1$$

2. The second column, "3, 5, 8", can be expressed as: $$\frac{(x+1)(x+0)}{2}+2$$

3. The third column can be expressed as: $$\frac{(x+2)(x+1)}{2}+3$$

You should now be able to see that these equations are also making a pattern. Each of the $$\x\$$ in the numerator of the fraction are increasing by one each column. Additionally the amount added to the fraction increases by one each column.

And so we can use $$\y\$$ to denote the column, and just use the following equation.

$$\frac{(x+y-1)(x+y-2)}{2} + x$$

• This does not have enough contextual text to describe what that math means and why it applies. – Reinderien Jul 9 at 16:34
• @Peilonrayz Looks good :) – Reinderien Jul 22 at 19:15
• Hey hackvoip I've made a couple of changes to your answer to bring it up to spec. ① I changed your formatting to not feel as cluttered ② I explained what $x$ and $y$ are. This allows others coming to your answer to more easily follow your train of thought. ③ I added an explanation on where the formulas come from. In the the future if you you explain what things are you'll likely be met with a much more warm reception. – Peilonrayz Jul 22 at 19:48