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

Groups > comp.lang.python > #44110

Re: Confusing Algorithm

From Christian Gollwitzer <auriocus@gmx.de>
Newsgroups comp.lang.python
Subject Re: Confusing Algorithm
Date 2013-04-22 22:33 +0200
Organization A noiseless patient Spider
Message-ID <kl46ko$ej8$1@dont-email.me> (permalink)
References <09f7da52-b0d6-4167-957f-d207faf33d07@googlegroups.com> <CAPTjJmpE1pxnxqkjBWeVAFpyNEcEnWU-tCTnnJnQbJpwjTpY9A@mail.gmail.com> <mailman.923.1366643091.3114.python-list@python.org>

Show all headers | View raw

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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web