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

Groups > comp.lang.python > #106730 > unrolled thread

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

Back to article view | Back to comp.lang.python

Contents

  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

#106730 — Find the number of robots needed to walk through the rectangular grid

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

[toc] | [next] | [standalone]

#106746

On Sat, Apr 9, 2016 at 8:18 AM, Joe <lildinho14@gmail.com> wrote:
> 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?

I'd use a disjoint-set data structure. The number of robots needed is
equal to the number of disjoint subsets.

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

[toc] | [prev] | [next] | [standalone]

#106747

On Saturday, 9 April 2016 18:44:20 UTC+2, Ian  wrote:
> On Sat, Apr 9, 2016 at 8:18 AM, Joe  wrote:
> > 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?
> 
> I'd use a disjoint-set data structure. The number of robots needed is
> equal to the number of disjoint subsets.
> 
> https://en.wikipedia.org/wiki/Disjoint-set_data_structure

Could you post a formal solution of disjoint-set using my algorithm  

[toc] | [prev] | [next] | [standalone]

#106755

On Sat, 9 Apr 2016 10:13:04 -0700 (PDT), Joe <lildinho14@gmail.com>
declaimed the following:
>Could you post a formal solution of disjoint-set using my algorithm  

	You've been given a suggestion to a possible means of solving the
assignment -- researching that solution is now on your side of the fence.

	We don't do homework... And likely your algorithm is incompatible with
the concept (I've not bothered to google "disjoint set").

	Especially as nothing in this is Python specific -- working out the
algorithm IS the assignment; Python is just the means of implementing the
algorithm. When something doesn't work in your Python implementation, we
might offer further advice about how the language works.

{My birthday was a few days ago -- I'm transitioning in the "crotchety old
man stage")
-- 
	Wulfraed                 Dennis Lee Bieber         AF6VN
    wlfraed@ix.netcom.com    HTTP://wlfraed.home.netcom.com/

[toc] | [prev] | [next] | [standalone]

#106757

On 09/04/2016 18:13, Joe wrote:
> On Saturday, 9 April 2016 18:44:20 UTC+2, Ian  wrote:
>> On Sat, Apr 9, 2016 at 8:18 AM, Joe  wrote:
>>> 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?
>>
>> I'd use a disjoint-set data structure. The number of robots needed is
>> equal to the number of disjoint subsets.
>>
>> https://en.wikipedia.org/wiki/Disjoint-set_data_structure
>
> Could you post a formal solution of disjoint-set using my algorithm
>

You write the code, we comment on it.  No code, no comment.  Got the 
message?

-- 
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence

[toc] | [prev] | [next] | [standalone]

#106761

On Saturday, 9 April 2016 21:24:02 UTC+2, Mark Lawrence  wrote:
> On 09/04/2016 18:13, Joe wrote:
> > On Saturday, 9 April 2016 18:44:20 UTC+2, Ian  wrote:
> >> On Sat, Apr 9, 2016 at 8:18 AM, Joe  wrote:
> >>> 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?
> >>
> >> I'd use a disjoint-set data structure. The number of robots needed is
> >> equal to the number of disjoint subsets.
> >>
> >> https://en.wikipedia.org/wiki/Disjoint-set_data_structure
> >
> > Could you post a formal solution of disjoint-set using my algorithm
> >
> 
> You write the code, we comment on it.  No code, no comment.  Got the 
> message?
> 
> -- 
> My fellow Pythonistas, ask not what our language can do for you, ask
> what you can do for our language.
> 
> Mark Lawrence

Sorry, I was desperate 
I deleted the post

[toc] | [prev] | [next] | [standalone]

#106762

On 09/04/2016 20:41, Joe wrote:
>
> Sorry, I was desperate
> I deleted the post
>

You didn't.  This will be showing in the archives in several places, e.g 
https://mail.python.org/pipermail/python-list/2016-April/707160.html

-- 
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence

[toc] | [prev] | [next] | [standalone]

#106765

On Saturday, 9 April 2016 21:55:50 UTC+2, Mark Lawrence  wrote:
> On 09/04/2016 20:41, Joe wrote:
> >
> > Sorry, I was desperate
> > I deleted the post
> >
> 
> You didn't.  This will be showing in the archives in several places, e.g 
> https://mail.python.org/pipermail/python-list/2016-April/707160.html
> 
> -- 
> My fellow Pythonistas, ask not what our language can do for you, ask
> what you can do for our language.
> 
> Mark Lawrence

Well its still there, next time I'll not make the same mistake hopefully

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web