[Community Puzzle] 🤖 Robot Reach

Puzzles
#1

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.

#2

Continuing the discussion from [Community Puzzle] :robot: Robot Reach:

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

1 Like
#3

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

#4 
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

#5

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

1 Like
#6

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
#9

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.

#10

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]
4 Likes
#11

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” :wink:

#13

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

#14

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).

#15

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

#16

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

#17

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.