Path: csiph.com!usenet.pasdenom.info!news.albasani.net!newsfeed.freenet.ag!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.012 X-Spam-Evidence: '*H*': 0.98; '*S*': 0.00; '"""': 0.07; 'indicating': 0.07; 'problem:': 0.07; 'problem?': 0.07; '22,': 0.09; 'differently.': 0.09; 'next,': 0.09; 'cc:addr:python-list': 0.11; 'thread': 0.14; 'defined.': 0.16; 'finds': 0.16; 'iterates': 0.16; 'wrote:': 0.18; 'shape': 0.19; 'later': 0.20; 'cc:addr:python.org': 0.22; 'mon,': 0.24; 'cc:2**0': 0.24; 'cc:no real name:2**0': 0.24; 'task': 0.26; 'header:In-Reply-To:1': 0.27; 'chris': 0.29; 'reaches': 0.30; 'message-id:@mail.gmail.com': 0.30; "i'm": 0.30; 'lines': 0.31; 'another': 0.32; 'minimal': 0.33; 'could': 0.34; 'problem.': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'there': 0.35; 'next': 0.36; 'possible': 0.36; 'list': 0.37; 'city.': 0.38; 'solving': 0.38; 'pm,': 0.38; 'does': 0.39; 'sure': 0.39; 'how': 0.40; 'read': 0.60; 'new': 0.61; 'first': 0.61; 'connecting': 0.64; 'to:addr:gmail.com': 0.65; 'charset:windows-1252': 0.65; 'city': 0.66; 'square': 0.74; 'oscar': 0.84; '2013': 0.98 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=x-received:mime-version:in-reply-to:references:from:date:message-id :subject:to:cc:content-type:content-transfer-encoding; bh=BzREFnEOPAE7r8SiZeq3qzDpjlx/+Qhb7s3Xu2uuAUY=; b=iqCVLKkc7I8qjqRPFK5z5AP3HvZ8h0efWvK3GZYthKFBkxgVjkfliyMOWxY8ew9Sey nHH3v+9nk5p7joQaUWU5uLyI5r+o3H9gmvj3GJeLkljGn240+xSKeAM2z0w+RGr0K//G ZplTQG4SUkHUkOpyzHDBlmAAljYXuOjfUjvlPIn57ZR9walvCUp3jLAZby6V8ELD+4MG 2lJ61PNoxxTXUwrHJyNLVWL2rqO731bTk/8YBHhmQe6MencfkHrTSqSJa+jqFF8NUd3Z PkT2XRiwYg5BJiDWEi8jTUVKOF/SJLx5FLu+JfwwkhtGi4XeZGiSX4AOSzcs956yw1z7 hcAw== X-Received: by 10.52.100.193 with SMTP id fa1mr4219039vdb.46.1366642693199; Mon, 22 Apr 2013 07:58:13 -0700 (PDT) MIME-Version: 1.0 In-Reply-To: References: <09f7da52-b0d6-4167-957f-d207faf33d07@googlegroups.com> From: Oscar Benjamin Date: Mon, 22 Apr 2013 15:57:52 +0100 Subject: Re: Confusing Algorithm To: Chris Angelico Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: quoted-printable Cc: python-list@python.org X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 48 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1366643091 news.xs4all.nl 2170 [2001:888:2000:d::a6]:36589 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:44084 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 >> =93cover=94 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 shap= e 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