Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
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
- Create the matrix with row index + column index values
- For all the row,column create a dictionary with False
- 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…
Thank you for your help
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