# [Community Puzzle] đź¤– Robot Reach

Coding Games and Programming Challenges to Code Better

Created by @smhb,validated by @Konstant,@Westicles and @Palmipedus.
If you have any issues, feel free to ping them.

Continuing the discussion from [Community Puzzle] Robot Reach:

I am not able to solve this problem. Any hints appreciated

1 Like

We need more informations to help you â€¦ did you understand the problem ? did you try something ? does it work partially or not at all ?

``````import sys
import math

# Auto-generated code below aims at helping you parse
# the standard input according to the problem statement.
def sum_of_digits(v):
res = 0
while v >0:
s = v%10
v = v//10
res+=s
return res

def find_val(r,c):
row_value = sum_of_digits(r)
col_value = sum_of_digits(c)
return row_value + col_value

r = int(input())
c = int(input())
t = int(input())

ar = [[find_val(i,j) for j in range(c)] for i in range(r)]
places = []
for i in range(r):
for j in range(c):
if ar[i][j] <= t:
places.append([i,j])
count = 0

my_dict = {}

for p in places:
my_dict[tuple(p)]= False

for i in range(0,len(places)):
r = [places[i][0]+0, places[i][1]+1]
l = [places[i][0]+0, places[i][1]-1]
t = [places[i][0]-1, places[i][1]+0]
b = [places[i][0]+1, places[i][1]+1]
if r in places or l in places or t in places or b in places:
my_dict[tuple(places[i])] = True

print(sum(my_dict.values()))
``````

This is what I came up with. It has shortcomings. Not sure how to use recursion to solve this problem

Please format your code by using the </> button on the formatting toolbar, so that the indentation in your code is preserved.

1 Like

I donâ€™t read python â€¦ i didnâ€™t excpect a copy/past of your code â€¦ but some explanations about what you wanted to do, what you tried â€¦ i canâ€™t help you, i let someone else (knowing python of course)

1 Like

Thanks for the suggestion. This is what I have done

1. Create the matrix with row index + column index values
2. For all the row,column create a dictionary with False
3. Loop through all the elements in the matrix and check for left, right, top and bottom elements and mark that as True (which means it is reachable)

I am really not sure how to approach this using Recursion.

Try this test:

``````12
10
2
``````

The answer should be 6. You can only reach the 6 points near the start, that is (0,0), (1,0), (2,0), (0,1), (1,1), (0,2), but your code gives 9. Now thereâ€™s an explanation of the why, donâ€™t read it if you want to try to debug it yourself first:

Spoiler: It counts (11, 0), (11,1) and (12,0). Your code basically iterates over the whole 2D array, checks if the value of the square (i,j) is <= t and if so, when it enters the last for loop**, if it finds a neighbor with value <= t it changes the value (i,j) to true, even if the robot canâ€™t reach it. You are not doing what the statement is asking you to do.

I am really not sure how to approach this using Recursion.

Try googling DFS or Flood Fill (here there are pretty much equivalent). A tuned BFS will also work but itâ€™s not properly recursive.

**it doesnâ€™t change anything but your last for loop has also this bug:

``````b = [places[i][0]+1, places[i][1]+1]
``````

Should be

``````b = [places[i][0]+1, places[i][1]+0]
``````
5 Likes

You may use the spoiler tag if you think it is appropriate. Click the last button on the formatting toolbar, then look for â€śHide Detailsâ€ť

I think I donâ€™t understand this problem. The robot starts at (0,0) and canâ€™t make more than 7 moves and each move is just a 1 cell move (without diagonals).
For the test 3 inputs are:
R : 20
C : 3
T : 11

So the table is:
| 0 1 2
/////////////
0 | 0 1 2
1 | 1 2 3
2 | 2 3 4
3 | 3 4 5
4 | 4 5 6
5 | 5 6 7
6 | 6 7 8
7 | 7 8 9
8 | 8 9 10
9 | 9 10 11
10 | 1 2 3
11 | 2 3 4
12 | 3 4 5
13 | 4 5 6
14 | 5 6 7
15 | 6 7 8
16 | 7 8 9
17 | 8 9 10
18 | 9 10 11
19 | 10 11 12

For me the answer should be 18 and the device is waiting for 59â€¦ How the robot can run through 59 cells? For me the max of cells it can go through is18 in that case (as it has to start at 0)

Plus I donâ€™t understand the link with recursifâ€¦

In your table, there are 60 values, and only one of them (12) is greater than T (11). Hence the answer is 59. The robot can reach those 59 cells (not necessarily in a single path).

My code passes all test cases but fails on validator 4. Can you share what might be special about it?

It is similar to test 4; only one input number has been changed.

Thanks. I ended up just do a straight map walk recursion and it worked. so there definitely was some weird bug in my last code.

why is the 2nd test case equal to 8?

Every cell except row 2 col 2 can be visited by the robot - thats 8 cells. Row 2 col 2 cannot be visited because its value is 4 which is larger than the given threshold (T) of 3.

I completely understand the reason this problem was marked as a recursion one while it can be solved with simple row,column loops.
When looping that matrix/dictionary and filling the values, you are able to check the top and left values while bottom and right are still not calculated!
To address this issue we were supposed to use a fill algorithm (using recursion) to fill all reachable cells on a matrix like this

``````M
M M
MMM
``````

But the thing is that on this problem, reachable cells matrix has a pattern where all reachable cells are always connected to the top or left cell! See here the example for r=40,c=40,t=10:

``````MMMMMMMMMMMMMMMMMMMMMMMMMMMMM MMMMMMMM
MMMMMMMMMMMMMMMMMMM MMMMMMMM  MMMMMMM
MMMMMMMMM MMMMMMMM  MMMMMMM   MMMMMM
MMMMMMMM  MMMMMMM   MMMMMM    MMMMM
MMMMMMM   MMMMMM    MMMMM     MMMM
MMMMMM    MMMMM     MMMM      MMM
MMMMM     MMMM      MMM       MM
MMMM      MMM       MM        M
MMM       MM        M
MM        M
MMMMMMMMMMMMMMMMMMM MMMMMMMM  MMMMMMM
MMMMMMMMM MMMMMMMM  MMMMMMM   MMMMMM
MMMMMMMM  MMMMMMM   MMMMMM    MMMMM
MMMMMMM   MMMMMM    MMMMM     MMMM
MMMMMM    MMMMM     MMMM      MMM
MMMMM     MMMM      MMM       MM
MMMM      MMM       MM        M
MMM       MM        M
MM        M
M
MMMMMMMMM MMMMMMMM  MMMMMMM   MMMMMM
MMMMMMMM  MMMMMMM   MMMMMM    MMMMM
MMMMMMM   MMMMMM    MMMMM     MMMM
MMMMMM    MMMMM     MMMM      MMM
MMMMM     MMMM      MMM       MM
MMMM      MMM       MM        M
MMM       MM        M
MM        M
M

MMMMMMMM  MMMMMMM   MMMMMM    MMMMM
MMMMMMM   MMMMMM    MMMMM     MMMM
MMMMMM    MMMMM     MMMM      MMM
MMMMM     MMMM      MMM       MM
MMMM      MMM       MM        M
MMM       MM        M
MM        M
M

``````