Bunny Prisoner Locating
Ayy !! You and I both know why you are here :D . Trust me you don't need my article to solve this problem.
All you need is to brush up on your high school math skills
But to make your life a bit easier I will drop a few hints to help you out so that you can go back to the problem and try to approach it based on the hints if you still can't solve it or wanted to know another way of solving the problem refer to the solution below.
Trust me its a one-liner
=======================
Keeping track of Commander Lambda’s many bunny prisoners is starting to get tricky. You’ve been tasked with writing a program to match bunny prisoner IDs to cell locations.
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 solution(x, y) which returns the prisoner ID of the bunny at the 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 solution as a string representation of the number.
Languages
=========
To provide a Java solution, edit Solution.java
To provide a Python solution, edit solution.py
Test cases
==========
Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.
— Java cases —
Input:
Solution.solution(3, 2)
Output:
9
Input:
Solution.solution(5, 10)
Output:
96
— Python cases —
Input:
solution.solution(5, 10)
Output:
96
Input:
solution.solution(3, 2)
Output:
9
Hint #1 convert the pattern into a 2D array
convert the pattern
| 7
| 4, 8
| 2, 5, 9
| 1 , 3 , 6 , 10
into
| 4 , 8 , 13 , 19
| 2 , 5 , 9 , 14
| 1 , 3 , 6 , 10
Can you guess why I did? what I did?
Nope?
Then let us go to Hint #2
Yep didn't expect this, did you? The good old n th term of Arithmetic Progression.
If you look clearly you can see 1,3,6,10 is in a sequence
1,3,6,10 …. = [(x-1)(x)]/2
Similarly, if you formulate for other rows you will find a pattern emerge
Now you are almost there !! See if you can do something with AP
if you see the formulas that you derived you can see a pattern like this
[(x - 1)(x)]/2 + 1, [(x)(x + 1)]/2 + 2, [(x + 1)(x + 2)]/2 + 3, …..1
I don't know about you but this shouts use AP , use AP to me so let’s
Normalize the above formula using AP
a| (x -1), (x), (x+1), ….. = (x + n - 2)
b| (x), (x +1), (x+2), …. = (x + n - 1)
c| 1, 2, 3, …. = x
Putting a b c together we get the desired equation that gives us the ID of the bunny at a give co-ordinate
Also if you notice n here is nothing but y
Not sure how ? ID 1 represent (1,1) and ID 3 represents (2,1) and so on.
Solution:
x + [(x + y - 2) * (x + y - 1) ] / 2
Yep it’s that Simple !!
Good Luck with your next challenges do brush up your math skills.
Congrats and thanks for reading it to the end !!
If you like it leave a clap and if you want to share your thought leave a message at anushkrishnav.rock
Follow me on GitHub: https://github.com/anushkrishnav
