Re: Confusing Algorithm
RBotha wrote: > >I'm facing the following problem: > >""" >In a city of towerblocks, Spiderman can >cover all the towers by connecting the >first tower with a spider-thread to the top >of a later tower and then to a next tower >and then to yet another tower until he >reaches the end of the city. ... > >-Example: >List of towers: 1 5 3 7 2 5 2 >Output: 4 >""" > >I'm not sure how a 'towerblock' could be defined. How square does a shape have >to be to qualify as a towerblock? Any help on solving this problem? Here's your city; [ ] [ ] [ ][ ][ ] [ ][ ][ ] [ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] -- A B C D E F G Once you see the picture, you can see that you'd thread from B to D without involving C. I think you'll go A to B to D to F to G -- 4 threads. -- Tim Roberts, t...@probo.com Providenza & Boekelheide, Inc. -- http://mail.python.org/mailman/listinfo/python-list
Re: Confusing Algorithm
On Mon, Apr 22, 2013 at 2:33 PM, Christian Gollwitzer wrote: > I'd agree with your interpretation. "Threads are straight lines and cannot > intersect towers" - I read it such that the answer is the "convex hull" of > the set of points given by the tower height. The convex hull can be computed > for this 1D problem by initializing with > line segments between every point and repeatedly pulling up every > non-convex piece, if I'm not mistaken. I agree that seems the likely intention. One also must assume that the towers are evenly spaced and have point width, neither of which are stated in the problem. -- http://mail.python.org/mailman/listinfo/python-list
Re: Confusing Algorithm
On 22/04/13 13:39, RBotha wrote: I'm facing the following problem: """ In a city of towerblocks, Spiderman can “cover” all the towers by connecting the first tower with a spider-thread to the top of a later tower and then to a next tower and then to yet another tower until he reaches the end of the city. Threads are straight lines and cannot intersect towers. Your task is to write a program that finds the minimal number of threads to cover all the towers. The list of towers is given as a list of single digits indicating their height. -Example: List of towers: 1 5 3 7 2 5 2 Output: 4 """ I'm not sure how a 'towerblock' could be defined. How square does a shape have to be to qualify as a towerblock? Any help on solving this problem? It's not the algorithm that's confusing, it's the problem. First clarify the problem. This appears to be a variation of the travelling-salesman problem. Except the position of the towers is not defined, only their height. So either the necessary information is missing or whoever set the problem intended something else. -- http://mail.python.org/mailman/listinfo/python-list
Re: Confusing Algorithm
Am 22.04.13 16:57, schrieb Oscar Benjamin: On 22 April 2013 13:56, Chris Angelico wrote: On Mon, Apr 22, 2013 at 10:39 PM, RBotha wrote: Threads are straight lines and cannot intersect towers. Your task is to write a program that finds the minimal number of threads to cover all the towers. >>> -Example: List of towers: 1 5 3 7 2 5 2 Output: 4 > I read it differently. I thought the threads would go 1->5->7->5->2. I'd agree with your interpretation. "Threads are straight lines and cannot intersect towers" - I read it such that the answer is the "convex hull" of the set of points given by the tower height. The convex hull can be computed for this 1D problem by initializing with line segments between every point and repeatedly pulling up every non-convex piece, if I'm not mistaken. Christian -- http://mail.python.org/mailman/listinfo/python-list
Re: Confusing Algorithm
On 22 April 2013 13:56, Chris Angelico wrote: > On Mon, Apr 22, 2013 at 10:39 PM, RBotha wrote: >> I'm facing the following problem: >> >> """ >> In a city of towerblocks, Spiderman can >> “cover” all the towers by connecting the >> first tower with a spider-thread to the top >> of a later tower and then to a next tower >> and then to yet another tower until he >> reaches the end of the city. Threads are >> straight lines and cannot intersect towers. >> Your task is to write a program that finds >> the minimal number of threads to cover all >> the towers. The list of towers is given as a >> list of single digits indicating their height. >> >> -Example: >> List of towers: 1 5 3 7 2 5 2 >> Output: 4 >> """ >> >> I'm not sure how a 'towerblock' could be defined. How square does a shape >> have to be to qualify as a towerblock? Any help on solving this problem? > > First start by clarifying the problem. My reading of this is that > Spiderman iterates over the towers, connecting his thread from one to > the next, but only so long as the towers get shorter: > >>-Example: >>List of towers: 1 5 3 7 2 5 2 >>Output: 4 > > First thread > 1 > New thread > 5-3 > New thread > 7-2 > New thread > 5-2 > > There are other possible readings of the problem. I read it differently. I thought the threads would go 1->5->7->5->2. Oscar -- http://mail.python.org/mailman/listinfo/python-list
Re: Confusing Algorithm
On Tue, Apr 23, 2013 at 12:57 AM, Oscar Benjamin wrote: > On 22 April 2013 13:56, Chris Angelico wrote: >> There are other possible readings of the problem. > > I read it differently. I thought the threads would go 1->5->7->5->2. I hadn't thought of that one, but agreed, that's also plausible, and it results in an answer of 4. It's a stronger contender than the one I posited, because the wording implies that there are multiple ways to do it and you have to pick/find the best. Seems to me the problem's a little under-specified, tbh. ChrisA -- http://mail.python.org/mailman/listinfo/python-list
Re: Confusing Algorithm
On Mon, Apr 22, 2013 at 10:39 PM, RBotha wrote: > I'm facing the following problem: > > """ > In a city of towerblocks, Spiderman can > “cover” all the towers by connecting the > first tower with a spider-thread to the top > of a later tower and then to a next tower > and then to yet another tower until he > reaches the end of the city. Threads are > straight lines and cannot intersect towers. > Your task is to write a program that finds > the minimal number of threads to cover all > the towers. The list of towers is given as a > list of single digits indicating their height. > > -Example: > List of towers: 1 5 3 7 2 5 2 > Output: 4 > """ > > I'm not sure how a 'towerblock' could be defined. How square does a shape > have to be to qualify as a towerblock? Any help on solving this problem? First start by clarifying the problem. My reading of this is that Spiderman iterates over the towers, connecting his thread from one to the next, but only so long as the towers get shorter: First thread 1 New thread 5-3 New thread 7-2 New thread 5-2 There are other possible readings of the problem. Once you fully understand the problem, write it out in pseudo-code - something like this: Iterate over towers sequentially If next tower is taller than current tower, new thread Report number of new threads And then turn it into code, and start running it and playing with it... and debugging it. (There's a small error in the pseudo-code I just posted; can you spot it?) Once you're at that point, if you get stuck, post your code and we can try to help. But fundamentally, I think you don't _need_ to define a towerblock. :) ChrisA -- http://mail.python.org/mailman/listinfo/python-list
Confusing Algorithm
I'm facing the following problem: """ In a city of towerblocks, Spiderman can “cover” all the towers by connecting the first tower with a spider-thread to the top of a later tower and then to a next tower and then to yet another tower until he reaches the end of the city. Threads are straight lines and cannot intersect towers. Your task is to write a program that finds the minimal number of threads to cover all the towers. The list of towers is given as a list of single digits indicating their height. -Example: List of towers: 1 5 3 7 2 5 2 Output: 4 """ I'm not sure how a 'towerblock' could be defined. How square does a shape have to be to qualify as a towerblock? Any help on solving this problem? Thank you. -- http://mail.python.org/mailman/listinfo/python-list
