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

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

Confusing Algorithm

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

Contents

  Confusing Algorithm RBotha <r@ymond.co.za> - 2013-04-22 05:39 -0700
    Re: Confusing Algorithm Chris Angelico <rosuav@gmail.com> - 2013-04-22 22:56 +1000
    Re: Confusing Algorithm Chris Angelico <rosuav@gmail.com> - 2013-04-23 01:02 +1000
    Re: Confusing Algorithm Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-04-22 15:57 +0100
      Re: Confusing Algorithm Christian Gollwitzer <auriocus@gmx.de> - 2013-04-22 22:33 +0200
        Re: Confusing Algorithm Ian Kelly <ian.g.kelly@gmail.com> - 2013-04-22 16:36 -0600
    Re: Confusing Algorithm DJC <djc@news.invalid> - 2013-04-22 22:38 +0100
    Re: Confusing Algorithm Tim Roberts <timr@probo.com> - 2013-04-23 23:18 -0700

#44056 — 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.

[toc] | [next] | [standalone]

#44059

On Mon, Apr 22, 2013 at 10:39 PM, RBotha <r@ymond.co.za> 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

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

#44083

On Tue, Apr 23, 2013 at 12:57 AM, Oscar Benjamin
<oscar.j.benjamin@gmail.com> wrote:
> On 22 April 2013 13:56, Chris Angelico <rosuav@gmail.com> 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

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

#44084

On 22 April 2013 13:56, Chris Angelico <rosuav@gmail.com> wrote:
> On Mon, Apr 22, 2013 at 10:39 PM, RBotha <r@ymond.co.za> 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

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

#44110

Am 22.04.13 16:57, schrieb Oscar Benjamin:
> On 22 April 2013 13:56, Chris Angelico <rosuav@gmail.com> wrote:
>> On Mon, Apr 22, 2013 at 10:39 PM, RBotha <r@ymond.co.za> 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

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

#44119

On Mon, Apr 22, 2013 at 2:33 PM, Christian Gollwitzer <auriocus@gmx.de> 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.

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

#44118

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.

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

#44245

RBotha <r@ymond.co.za> 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, timr@probo.com
Providenza & Boekelheide, Inc.

[toc] | [prev] | [standalone]

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

csiph-web