7
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ For anyone wondering what this is called, and why this expression comes to place, such series for example: 1,2,4,7.... is called a Consecutive Integer Series. \$\endgroup\$
    – Atharv Pal
    Commented Dec 23, 2023 at 21:03

3 Answers 3

7
\$\begingroup\$

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).

So it seems your answer should be in the form:

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
\$\endgroup\$
1
  • \$\begingroup\$ Could you please explain it? What's the definition of "corner" and how did you get into those formulas? I am having a hard time understanding it. Would appreciate your help. \$\endgroup\$ Commented Nov 14, 2022 at 17:14
7
\$\begingroup\$

| 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$$

\$\endgroup\$
0
1
\$\begingroup\$

I solved this problem using 'move along the axes approach'. Here's an explanation:

Y Axis
| 7
| 4 8
| 2 5 9
| 1 3 6 10
--------> X Axis

Moving along x Axis is nothing but sum of n natural numbers

X_pos = x(x+1)/2

And moving from X_pos in vertical direction would be

Ypos= Xpos +( (x*(y-1)) + (y-1) *(y-2)/2)

Intuitively, from X-pos, the sequence in vertical direction is x + (x+1) +(x+2) ... y times to reach the y position.

def solution(x, y):
    # walk from the wall
    xpos = (x *(x+1))/2
    # climb from the ground
    ypos_from_x = xpos + ( (x*(y-1)) + ((y-1) *(y-2))/2   ) 
    return ypos_from_x
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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