2
\$\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\$
3
\$\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\$

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.