Google Foobar: Level 2A

I detailed in an early posting that I’m working to improve on a fear of failure. I don’t want to miss out on opportunities just because I’m afraid I might fail them. But that doesn’t mean I’m inviting failure itself, I’m still going to try hard not to fail. So after completing the first Foobar problem, I decided I would take some time to finish reviewing my data structures and algorithms fundamentals. I was expecting the next challenge would ramp up the difficulty, so I wanted to be better prepared before I kicked off the next problem.

After a few days I felt comfortable, so it was time to request the next one. This is what it gave me:

Bunny Worker Locations
======================

Keeping track of Commander Lambda's many bunny workers is starting to get tricky. You've been tasked with writing a program to match bunny worker 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 work areas have an unusual layout. They are stacked in a triangular shape, and the bunny workers 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 worker at (1, 1) has ID 1, the bunny worker at (3, 2) has ID 9, and the bunny worker at (2,3) has ID 8. This pattern of numbering continues indefinitely (Commander Lambda has been adding a LOT of workers). 

Write a function solution(x, y) which returns the worker 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 worker 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

Use verify [file] to test your solution and see how it does. When you are finished editing your code, use submit [file] to submit your answer. If your solution passes the test cases, it will be removed from your home folder.

I had to re-read it a few times before I realized what they were conveying with their diagram. But once it clicked, I expanded their diagram in a spreadsheet. I tried adding the distances between the numbers onto the diagram, hoping a pattern might show itself. It did. Increasing x with y == 1 was a straight up triangular number series, as was increasing y with x == 1. Combining those together could allow for an instant answer.

I wasn’t expecting to find a purely mathematical answer to a coding question. I suspect Google was testing to see if the challenge participant would just jump straight into the coding. But jumping straight to code has bitten me in the past. It’s worth taking a little extra time to step back and fully analyze the problem space. Sometimes a constant time and constant space solution is hiding not far below the surface:

# Author: Derek Moran, Level 2 Henchman @ Commander Lambda Space Station
# Date: 21-NOV-2022

def solution(x, y):
    # Your code here
    return str( getWorkerId(x, y) )

# Take as its input a space station cell location at ( distanceFromWall, heightFromGround )
# Returns the workerId for the provided location
# Provided distanceFromWall and heightFromGround must be integer between 1 and 100,000 inclusive
def getWorkerId( distanceFromWall, heightFromGround ):

    if not type(distanceFromWall) is int:
        raise TypeError("Provided distanceFromWall must be an integer")

    if not type(heightFromGround) is int:
        raise TypeError("Provided heightFromGround must be an integer")
        
    if distanceFromWall < 1 or distanceFromWall > 100000:
        raise Exception("Provided distanceFromWall must be between 1 and 100000 inclusive")
        
    if heightFromGround < 1 or heightFromGround > 100000:
        raise Exception("Provided heightFromGround must be between 1 and 100000 inclusive")

    # Given the space station's particular layout, getWorkerId( distanceFromWall, 1 )
    # = 1+2+3+ ... + (distanceFromWall-1) + distanceFromWall
    # = (distanceFromWall*(distanceFromWall+1))/2
    #
    # So getWorkerId( distanceFromWall, heightFromGround )
    # = getWorkerId( distanceFromWall, 1 )
    #   + ( (distanceFromWall+heightFromGround-2)*(distanceFromWall+heightFromGround-1) )/2
    #   - ( (distanceFromWall - 1)*distanceFromWall )/2
    #
    # i.e getWorkerId( distanceFromWall, heightFromGround ) can be obtained by starting with the result
    # of getWorkerId( distanceFromWall, 1 ) and then adding the same subseries starting at
    # distanceFromWall-1 and ending at distanceFromWall+heightFromGround-1
    #
    # Simplifying that equation, we can obtain the result in O(1):
    workerId = ( distanceFromWall + heightFromGround ) ** 2
    workerId -= 3 * heightFromGround
    workerId -= distanceFromWall - 2
    workerId /= 2

    return workerId