CODEWITHSUNDEEP
python
EI-01
EI-01

Reputation: 1095

Find the largest area where a robot can access points on a grid safely

I came across an interesting problem today and i'm kinda stomped on a solution. The question is:

A robot can move around a grid. The robot starts from the origin i.e. (0, 0) and can move up, down, left and right i.e. (x, y+1), (x, y-1), (x-1, y), and (x+1, y) but there are obstacles where it won't be safe to move the robot. To check if a point is safe on the grid, take the absolute sum of the digit x and the absolute sum of the digit y and check if it's less or equal to 23. i.e if the point is (39, 39) => 3+9+3+9 is 24 and the point is not safe or if (-51, 7) => 5+1+7 is 13 then it's safe. The problem statement is find how large the area the robot can access.

Thought process:

The main takeaway after reading this problem is finding the cartesian coordinates whose digits are less than or equal to 23 and based on the coordinates return the area. Now there are a lot of cartesian coordinates that can qualify and make either a rectangle or a square but nevertheless all of them will have the same area. Now i chose to make a square from the origin such that x==y and sum of digits of x and y (which is x) < 23, this might look like

i = 0 
   while True:
       units, tens = i%10, (i/10)%10
       x =  units+tens
       y =  units+tens
       if x + y > 23:
           break;
       i+=1

But i think i might be wrong as i returns 39 and x, y coordinates returns (12, 12). Then i will have to calculate the area between (x,y), (-x,y), (-x, -y), and (x, -y). I think my approach is wrong and would like anyones thoughts on how to find the largest access area on the grid

Upvotes: 1

Views: 858

Answers (2)

Matthew
Matthew

Reputation: 125

import matplotlib.pyplot as plt
def sum_of_digit(num):
    sum = 0
    while(num > 0):
        remainder = num % 10
        num = num // 10
        sum = sum + remainder
    return sum

memo = [[0] * 2000 for _ in range(2000)]
dp = [None] * 2000

area = 0
for i in range(-1000, 1000):
    for j in range(-1000, 1000):
        if dp[abs(i)] == None:
           dp[abs(i)] = sum_of_digit(abs(i))
        if dp[abs(j)] == None:
            dp[abs(j)] = sum_of_digit(abs(j))

        if dp[abs(i)] + dp[abs(j)] <= 23:
            memo[i+1000][j+1000] = 1
            area += 1
print(area)
plt.imshow(memo)
plt.gca().invert_yaxis()
plt.show()

result

1253892

enter image description here

How about this? but I think this code is not correct. Because the result is too large.

Upvotes: 0

Benedictanjw
Benedictanjw

Reputation: 838

Edit: Account for negative coordinates, as pointed out by @David Choweller. Also made the solution cleaner by removing some unnecessary indexing. Edit: Fixed an error in total area calculation, thanks @polapts!

extent = 750
x_s = np.arange(-extent, extent+1, 1)
y_s = np.arange(-extent, extent+1, 1)

### Loop through each point and check if safe
coords = []
for y in y_s:
    x_coords = []
    for x in x_s:
        coords_digits_sum = sum([int(i) for i in str(abs(x))]) + sum([int(i) for i in str(abs(y))])
        if coords_digits_sum <= 23:
            safe = True
        else:
            safe = False
        x_coords.append(safe)
    coords.append(x_coords)


### Initialize the origin as `really_safe` point
coords[extent][extent] = 'really_safe' # Origin

### Iteratively check if a safe point is beside a `really_safe` point
changing = True
while changing == True:
    changing = False
    # Skip the first and last rows and columns because these are just paddings for looking up/down/left/right
    for y,x_coords in enumerate(coords[1:-1], start=1):
        for x,is_safe in enumerate(x_coords[1:-1], start=1):
            if is_safe == 'really_safe':
                continue
            ### look up, down, left, right of the point being checked
            elif is_safe and ('really_safe' in [coords[y-1][x], coords[y+1][x], coords[y][x-1], coords[y][x+1]]):
                coords[y][x] = 'really_safe'
                changing = True

### Count the number of "really safe" points only
really_safe_points = [[1 if safety == 'really_safe' else 0 for safety in x_coords[1:-1]] for x_coords in coords[1:-1]]
plt.imshow(really_safe_points)
plt.gca().invert_yaxis()

### Exclude first and last rows and columns in total area calculation since those were not iterated over 
plt.title(f"Accessible area: {sum([sum(i) for i in really_safe_points])}. Total area: {((extent-1)*2)**2}")
plt.show()

This is the outcome (accessible areas shown in yellow): enter image description here

Seems to me like it is not necessary to compute for an infinite board :)

Upvotes: 2

Related Questions