Confusing Algorithm

R

RBotha

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.
 
C

Chris Angelico

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 shapehave 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
 
O

Oscar Benjamin

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.

I read it differently. I thought the threads would go 1->5->7->5->2.


Oscar
 
C

Chris Angelico

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
 
D

DJC

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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,902
Latest member
Elena68X5

Latest Threads

Top