Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #106730

Find the number of robots needed to walk through the rectangular grid

Show all headers | View raw

How to find the number of robots needed to walk through the rectangular grid
The movement of a robot in the field is divided into successive steps

In one step a robot can move either horizontally or vertically (in one row or in one column of cells) by some number of cells

A robot can move in one step from cell X to cell Y if and only if the distance between the centers of the cells X and Y is equal to the sum of integers contained in X and Y

Cell X is reachable for robot A if either A is currently standing in the cell X or A can reach X after some number of steps. During the transfer the robot can choose the direction (horizontal or vertical) of each step arbitrarily
[![enter image description here][1]][1]

I started implementing it by first checking the row and print the index of the Cell X and Y where the distance is equal to the sum of integers contained in X and Y 

but after coding I found it difficult to remember the index when moving vertically

 So I thought to Build a graph where nodes are grid cells and edges are legal direct movements, then run any connected components algorithm to find which cells are reachable from each other


Can anyone implement it with graphs or queue?





Input 

    4 6
    3 1 3 2 0 0
    1 3 2 1 2 1
    3 3 1 0 1 2
    1 2 0 2 3 3

Output 

    6

My code so far

    def row_walk(inputstring):
        inputs = inputstring.split(" ")
        row_number, column_number = int(inputs[0]), int(inputs[1])      
        matrix = [list(map(int, input().split())) for _ in range(row_number)]
        matrix_transposed = (np.transpose(matrix)).tolist()     
    
        used = set()
        for i, r1 in enumerate(matrix[0]):
            for j, r2 in enumerate(matrix[0]):
                if j > i and  r1+r2 == j-i:
                    used.update((i, j))
            
        cell_movement = [x for x in range(len(matrix[0])) if x not in used]
        trivial_cell = [y for y in range(len(matrix[0])) if y in used]
        return cell_movement, trivial_cell
    
    
    if __name__=="__main__":
        print(row_walk(input()))

Back to comp.lang.python | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Find the number of robots needed to walk through the rectangular grid Joe <lildinho14@gmail.com> - 2016-04-09 07:18 -0700
  Re: Find the number of robots needed to walk through the rectangular grid Ian Kelly <ian.g.kelly@gmail.com> - 2016-04-09 10:43 -0600
    Re: Find the number of robots needed to walk through the rectangular grid Joe <lildinho14@gmail.com> - 2016-04-09 10:13 -0700
      Re: Find the number of robots needed to walk through the rectangular grid Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2016-04-09 15:10 -0400
      Re: Find the number of robots needed to walk through the rectangular grid Mark Lawrence <breamoreboy@yahoo.co.uk> - 2016-04-09 20:23 +0100
        Re: Find the number of robots needed to walk through the rectangular grid Joe <lildinho14@gmail.com> - 2016-04-09 12:41 -0700
          Re: Find the number of robots needed to walk through the rectangular grid Mark Lawrence <breamoreboy@yahoo.co.uk> - 2016-04-09 20:55 +0100
            Re: Find the number of robots needed to walk through the rectangular grid Joe <lildinho14@gmail.com> - 2016-04-09 14:28 -0700

csiph-web