Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #106761
| Newsgroups | comp.lang.python |
|---|---|
| Date | 2016-04-09 12:41 -0700 |
| References | (1 earlier) <CALwzidkhCO0bK2XxP-BZ=aPxuSX-ZiSxq_Yn7pe+ehV8qTsN8Q@mail.gmail.com> <mailman.129.1460220245.2253.python-list@python.org> <e42777b0-fc2b-4f2c-8c2b-a53b41bfe3f7@googlegroups.com> <nebkro$8j2$1@ger.gmane.org> <mailman.137.1460229825.2253.python-list@python.org> |
| Message-ID | <4bdfe218-11a6-4866-b1c3-e3a2e0661e47@googlegroups.com> (permalink) |
| Subject | Re: Find the number of robots needed to walk through the rectangular grid |
| From | Joe <lildinho14@gmail.com> |
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
Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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