Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!feeder2.ecngs.de!ecngs!feeder.ecngs.de!border1.nntp.ams.giganews.com!nntp.giganews.com!usenetcore.com!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!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.000 X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'author:': 0.03; 'else:': 0.03; 'algorithm': 0.03; 'essentially': 0.04; 'string.': 0.04; 'modified': 0.05; 'modify': 0.05; 'result,': 0.05; 'executed': 0.07; 'filename:fname piece:py': 0.07; 'sequences.': 0.07; 'skip:% 20': 0.07; 'strings.': 0.07; 'suppose': 0.07; 'python': 0.09; '#print': 0.09; "'''": 0.09; '32-bit': 0.09; '[];': 0.09; 'assumed': 0.09; 'behavior,': 0.09; 'enormous': 0.09; 'modifies': 0.09; 'skip:# 60': 0.09; 'toc': 0.09; 'def': 0.10; 'aug': 0.13; 'vista': 0.13; 'applies': 0.15; 'modification': 0.15; "'b',": 0.16; '(must': 0.16; '-1:': 0.16; "['a',": 0.16; 'code).': 0.16; 'downside': 0.16; 'mug': 0.16; 'mylist': 0.16; 'run.': 0.16; 'skip:[ 50': 0.16; 'true:': 0.16; 'typo': 0.16; 'string': 0.17; 'wrote:': 0.17; 'char': 0.17; 'element': 0.17; 'test.': 0.17; 'obviously': 0.18; 'solution.': 0.18; 'memory': 0.18; 'windows': 0.19; 'math': 0.20; 'parameters': 0.20; 'import': 0.21; 'assignment': 0.22; 'clock': 0.22; 'delta': 0.22; 'displayed': 0.22; 'modifying': 0.22; 'simpler': 0.22; 'skip:% 10': 0.22; 'sorry,': 0.22; 'runs': 0.22; 'example': 0.23; 'elements': 0.23; 'errors': 0.23; 'task': 0.23; '(this': 0.24; 'random': 0.24; 'testing': 0.24; 'header:In-Reply-To:1': 0.25; 'header:User- Agent:1': 0.26; '---': 0.26; 'charset:iso-8859-15': 0.26; 'fit': 0.26; 'values': 0.26; '(see': 0.27; 'possibility': 0.27; 'instead.': 0.27; 'list:': 0.27; 'correct': 0.28; 'initial': 0.28; 'run': 0.28; '100000': 0.29; 'cpu': 0.29; "d'aprano": 0.29; 'once,': 0.29; 'seed': 0.29; "skip:' 50": 0.29; 'steven': 0.29; 'character': 0.29; 'summary': 0.29; 'words': 0.29; '(from': 0.30; 'checks': 0.30; 'function': 0.30; 'resolution': 0.30; 'seconds': 0.30; 'lists': 0.31; 'code': 0.31; 'skip:- 30': 0.31; 'problem.': 0.32; 'print': 0.32; '+0200,': 0.33; 'that!': 0.33; 'to:addr :python-list': 0.33; 'times.': 0.33; 'another': 0.33; 'version': 0.34; 'list': 0.35; 'clear': 0.35; 'needed': 0.35; 'fail': 0.35; 'false': 0.35; 'faster': 0.35; 'follows:': 0.35; 'returning': 0.35; 'doing': 0.35; 'posting': 0.35; 'sometimes': 0.35; 'something': 0.35; 'there': 0.35; 'list.': 0.35; 'but': 0.36; 'characters': 0.36; 'generation': 0.36; 'skip:g 30': 0.36; 'email addr:python.org': 0.36; 'method': 0.36; 'note:': 0.64; 'here': 0.65; 'charset:windows-1252': 0.65; 'results': 0.65; '10,000': 0.65; '10000': 0.65; 'study': 0.66; 'stated': 0.69; 'soon': 0.70; 'obtained': 0.71; 'obvious': 0.71; '100': 0.78; 'inform': 0.78; 'completion': 0.78; '50%': 0.81; 'day!': 0.83; 'avg': 0.84; "d'aprano)": 0.84; 'irrelevant': 0.84; '100,000': 0.91; 'average': 0.93 X-SENDER-IP: [213.112.50.224] X-LISTENER: [smtp.bredband.net] X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AmYbAK3WLFDVcDLgPGdsb2JhbAANOItfrlwBAQEBN4JUAQEBAQMdWxELGAkWDwIHAwIBAgEPIgYBDRMGAgEBF4djA6Z0ihsNiU6KJWSGVwOOWoEghAKMX4dn X-IronPort-AV: E=Sophos;i="4.77,778,1336341600"; d="py'?scan'208,217";a="98105791" Date: Thu, 16 Aug 2012 13:18:59 +0200 From: Virgil Stokes User-Agent: Mozilla/5.0 (Windows NT 6.0; rv:15.0) Gecko/20120808 Thunderbird/15.0 MIME-Version: 1.0 To: python-list@python.org Subject: Re: Strange behavior References: <1a1834ae-2b4a-473f-b626-f37a17588199@googlegroups.com> <502aeb2b$0$29978$c3e8da3$5496439d@news.astraweb.com> In-Reply-To: <502aeb2b$0$29978$c3e8da3$5496439d@news.astraweb.com> Content-Type: multipart/mixed; boundary="------------000402070808050100070305" X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.12 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: 482 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1345117482 news.xs4all.nl 6982 [2001:888:2000:d::a6]:50644 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:27155 This is a multi-part message in MIME format. --------------000402070808050100070305 Content-Type: multipart/alternative; boundary="------------050104050108000908060905" --------------050104050108000908060905 Content-Type: text/plain; charset=ISO-8859-15; format=flowed Content-Transfer-Encoding: 7bit On 15-Aug-2012 02:19, Steven D'Aprano wrote: > On Tue, 14 Aug 2012 21:40:10 +0200, Virgil Stokes wrote: > >> You might find the following useful: >> >> def testFunc(startingList): >> xOnlyList = []; j = -1 >> for xl in startingList: >> if (xl[0] == 'x'): > That's going to fail in the starting list contains an empty string. Use > xl.startswith('x') instead. Yes, but this was by design (tacitly assumed that startingList was both a list and non-empty). > > >> xOnlyList.append(xl) >> else: >> j += 1 >> startingList[j] = xl > Very cunning, but I have to say that your algorithm fails the "is this > obviously correct without needing to study it?" test. Sometimes that is > unavoidable, but for something like this, there are simpler ways to solve > the same problem. Sorry, but I do not sure what you mean here. > > >> if j == -1: >> startingList = [] >> else: >> del startingList[j:-1] >> return(xOnlyList) > >> And here is another version using list comprehension that I prefer >> def testFunc2(startingList): >> return([x for x in startingList if x[0] == 'x'], [x for x in >> startingList if x[0] != 'x']) > This walks over the starting list twice, doing essentially the same thing > both times. It also fails to meet the stated requirement that > startingList is modified in place, by returning a new list instead. This can meet the requirement that startingList is modified in place via the call to this function (see the attached code). > Here's an example of what I mean: > > py> mylist = mylist2 = ['a', 'x', 'b', 'xx', 'cx'] # two names for one > list > py> result, mylist = testFunc2(mylist) > py> mylist > ['a', 'b', 'cx'] > py> mylist2 # should be same as mylist > ['a', 'x', 'b', 'xx', 'cx'] Yes, I had a typo in my original posting --- sorry about that! > > Here is the obvious algorithm for extracting and removing words starting > with 'x'. It walks the starting list only once, and modifies it in place. > The only trick needed is list slice assignment at the end. > > def extract_x_words(words): > words_with_x = [] > words_without_x = [] > for word in words: > if word.startswith('x'): > words_with_x.append(word) > else: > words_without_x.append(word) > words[:] = words_without_x # slice assignment > return words_with_x Suppose words was not a list --- you have tacitly assumed that words is a list. > > The only downside of this is that if the list of words is so enormous > that you can fit it in memory *once* but not *twice*, this may fail. But > the same applies to the list comprehension solution. But, this is not the only downside if speed is important --- it is slower than the list comprehension method (see results that follows). Here is a summary of three algorithms (algorithm-1, algorithm-2, algorithm-2A) that I tested (see attached code). Note, algorithm-2A was obtained by removing the slice assignment in the above code and modifying the return as follows def extract_x_words(words): words_with_x = [] words_without_x = [] for word in words: if word.startswith('x'): words_with_x.append(word) else: words_without_x.append(word) #words[:] = words_without_x # slice assignment return words_with_x, words_without_x Of course, one needs to modify the call for "in-place" update of startingList as follows: xOnlyList,startingList = extract_x_words(startingList) Here is a summary of my timing results obtained for 3 different algorithms for lists with 100,000 strings of length 4 in each list: Method average (sd) time in seconds algorithm-1 (list comprehension) 0.11630 (0.0014) algorithm-2 (S. D'Aprano) 0.17594 (0.0014) algorithm-2A (modified S. D'Aprano) 0.18217 (0.0023) These values were obtained from 100 independent runs (MC simulations) on lists that contain 100,000 strings. Approximately 50% of these strings contained a leading 'x'. Note, that the results show that algorithm-2 (suggested by S. D'Aprano) is approximately 51% slower than algorithm-1 (list comprehensions) and algorithm-2A (simple modification of algorithm-2) is approximately 57% slower than algorithm-1. Why is algorithm-2A slower than algorithm-2? I would be interested in seeing code that is faster than algorithm-1 --- any suggestions are welcomed. And of course, if there are any errors in my attached code please inform me of them and I will try to correct them as soon as possible. Note, some of the code is actually irrelevant for the original "Strange behavior" post. Have a good day! --------------050104050108000908060905 Content-Type: text/html; charset=ISO-8859-15 Content-Transfer-Encoding: 8bit
On 15-Aug-2012 02:19, Steven D'Aprano wrote:
On Tue, 14 Aug 2012 21:40:10 +0200, Virgil Stokes wrote:


You might find the following useful:

def testFunc(startingList):
     xOnlyList = []; j = -1
     for xl in startingList:
         if (xl[0] == 'x'):

That's going to fail in the starting list contains an empty string. Use 
xl.startswith('x') instead.
Yes, but this was by design (tacitly assumed that startingList was both a list and non-empty).



             xOnlyList.append(xl)
         else:
             j += 1
             startingList[j] = xl

Very cunning, but I have to say that your algorithm fails the "is this 
obviously correct without needing to study it?" test. Sometimes that is 
unavoidable, but for something like this, there are simpler ways to solve 
the same problem.
Sorry, but I do not sure what you mean here.



     if j == -1:
         startingList = []
     else:
         del startingList[j:-1]
     return(xOnlyList)



And here is another version using list comprehension that I prefer


      

        
def testFunc2(startingList):
     return([x for x in startingList if x[0] == 'x'], [x for x in
startingList if x[0] != 'x'])


      

      
This walks over the starting list twice, doing essentially the same thing 
both times. It also fails to meet the stated requirement that 
startingList is modified in place, by returning a new list instead. 

    

    This can meet the requirement that startingList is
    modified in place via the call to this function (see the attached
    code). 

    

      
Here's an example of what I mean:

py> mylist = mylist2 = ['a', 'x', 'b', 'xx', 'cx']  # two names for one 
list
py> result, mylist = testFunc2(mylist)
py> mylist
['a', 'b', 'cx']
py> mylist2  # should be same as mylist
['a', 'x', 'b', 'xx', 'cx']

    

    Yes, I had a typo in my original posting --- sorry about that!

    

      

Here is the obvious algorithm for extracting and removing words starting 
with 'x'. It walks the starting list only once, and modifies it in place. 
The only trick needed is list slice assignment at the end.

def extract_x_words(words):
    words_with_x = []
    words_without_x = []
    for word in words:
        if word.startswith('x'):
            words_with_x.append(word)
        else:
            words_without_x.append(word)
    words[:] = words_without_x  # slice assignment
    return words_with_x


    

    Suppose words was not a list --- you have tacitly assumed
    that words is a list.

    

      

The only downside of this is that if the list of words is so enormous 
that you can fit it in memory *once* but not *twice*, this may fail. But 
the same applies to the list comprehension solution.

    

    But, this is not the only downside if speed is important --- it is
    slower than the list comprehension method (see results that
    follows).

    

    Here is a summary of three algorithms (algorithm-1, algorithm-2,
    algorithm-2A) that I tested (see attached code). Note, algorithm-2A
    was obtained by removing the slice assignment in the above code and
    modifying the return as follows 

    
def extract_x_words(words):
    words_with_x = []
    words_without_x = []
    for word in words:
        if word.startswith('x'):
            words_with_x.append(word)
        else:
            words_without_x.append(word)
    #words[:] = words_without_x  # slice assignment
    return words_with_x, words_without_x



    Of course, one needs to modify the call for "in-place" update of startingList
    as follows:

    

       xOnlyList,startingList = extract_x_words(startingList)  

    

    Here is a summary of my timing results obtained for 3 different
    algorithms for lists with 100,000 strings of length 4 in each list:

    

    

      
        

          Method

          		
          average (sd) time in seconds

          		
        

        

          algorithm-1 (list comprehension)

          		
          0.11630 (0.0014)

          		
        

        

          algorithm-2 (S. D'Aprano)

          		
          0.17594 (0.0014)

          		
        

        

          algorithm-2A (modified S. D'Aprano)

          		
          0.18217 (0.0023)

          		
        

      
    

    

    These values  were obtained from 100 independent runs (MC
    simulations) on lists that contain 100,000 strings. Approximately
    50% of these strings contained a leading 'x'. Note, that the results
    show that algorithm-2 (suggested by S. D'Aprano) is approximately
    51% slower than algorithm-1 (list comprehensions) and algorithm-2A
    (simple modification of algorithm-2) is approximately 57% slower
    than algorithm-1. Why is algorithm-2A slower than algorithm-2?

    

    I would be interested in seeing code that is faster than algorithm-1
    --- any suggestions are welcomed.  And of course, if there are any
    errors in my attached code please inform me of them and I will try
    to correct them as soon as possible. Note, some of the code is
    actually irrelevant for the original "Strange behavior" post.

    

    Have a good day!

    

  


--------------050104050108000908060905--

--------------000402070808050100070305
Content-Type: text/plain; charset=windows-1252;
 name="testList4.py"
Content-Transfer-Encoding: base64
Content-Disposition: attachment;
 filename="testList4.py"

JycnDQogIFB1cnBvc2U6IFRpbWUgdGhyZWUgZGlmZmVyZW50IGFsZ29yaXRobXMgZm9yIHRo
ZSBzYW1lIHRhc2sNCiAgDQogIEF1dGhvcjogVi4gU3Rva2VzICh2c0BpdC51dS5zZSwgMjAx
Mi0wOC0xNikNCiAgUmVmczoNCiAgIHB5dGhvbi1saXN0QHB5dGhvbi5vcmcgbGlzdA0KICAg
ICogU3RyYW5nZSBiZWhhdmlvciwgMTQtQXVnLTIwMTIgMTc6MzgsIGxpZ2h0MXF1YXJrQGdt
YWlsLmNvbQ0KICAgICogUmU6IFN0cmFuZ2UgYmVoYXZpb3IsIDE0LUF1Zy0yMDEyIDIxOjQw
LCBTdG9rZXMsIFZpcmdpbA0KICAgICogUmU6IFN0cmFuZ2UgYmVoYXZpb3IsIDE1LUF1Zy0y
MDEyIDAyOjE5LCBTdGV2ZW4gRCdBcHJhbm8NCiAgDQogIE5vdGU6DQogICAxLiBUaGUgbWVh
biBhbmQgc3RhbmRhcmQgZGV2aWF0aW9uIG92ZXIgdGhlIHJ1bnMgKE1DIHNpbXVsYXRpb25z
KQ0KICAgICAgYXJlIGVzdGltYXRlZCB1c2luZyByZWN1cnNpdmUgZXF1YXRpb25zLg0KICAg
Mi4gQSBzZWVkIChzeWQpIGlzIHVzZWQgd2l0aCB0aGUgUk5HIGZvciByZXBlYXRhYmlsaXR5
LiBFYWNoIHJ1biBpcyANCiAgICAgIHN0YXJ0ZWQgd2l0aCBhIG5ldyBzZWVkIHRvIGZvcmNl
IHRoZSBnZW5lcmF0aW9uIG9mIGluZGVwZW5kZW50IA0KICAgICAgcmFuZG9tIHNlcXVlbmNl
cy4NCiAgIDMuIFdhcm5pbmchIE5vIGNoZWNrcyBhcmUgbWFkZSBvbiB0aGUgcGFyYW1ldGVy
cyBwYXNzZWQgdG8NCiAgICAgIHRoZSBmdW5jdGlvbnMgKHRoaXMgd2FzIGJ5IGRlc2lnbiku
DQogICA0LiBObyBlZmZvcnQgaGFzIGJlZW4gbWFkZSB0byBtYWtlIHRoaXMgY29kZSBlbGVn
YW50LiBNeSBmb2N1cyB3YXMNCiAgICAgIHRvIG1ha2UgdGhlIGNvZGUgY2xlYXIgYW5kIGVh
c3kgdG8gdW5kZXJzdGFuZC4NCiAgIDUuIFRoaXMgd2FzIGV4ZWN1dGVkIG9uIGEgV2luZG93
cyBWaXN0YSAzMi1iaXQgcGxhdGZvcm0gd2l0aCBQeXRob24gMi42LjYNCiAgICAgICBQcm9j
ZXNzb3I6IEludGVsKFIpIGNvcmUoVE0pMiBEdW8gQ1BVIEU4NTAwQDMuMTZHSHogMy4xN0dI
eg0KICAgNi4gVGhlIGVzdGltYXRlZCB0aW1lIHRvIGNvbXBsZXRpb24gaXMgZGlzcGxheWVk
IGFmdGVyIGVhY2ggcnVuLiAgICANCiAgICAgIA0KJycnDQppbXBvcnQgcmFuZG9tIGFzIHJh
bmRvbQ0KaW1wb3J0IG1hdGggYXMgbWF0aA0KZnJvbSB0aW1lIGltcG9ydCBjbG9jayAjIGNs
b2NrIGdpdmVzIGdvb2QgcmVzb2x1dGlvbiBvbiBNUyBXaW5kb3dzDQoNCmRlZiB0ZXN0RnVu
YzEoc3RhcnRpbmdMaXN0KTogDQogICAgJycnDQogICAgICBBbGdvcml0aG0tMQ0KICAgICAg
Tm90ZTogDQogICAgICAgIE9uZSBzaG91bGQgY2hlY2sgZm9yIGFuIGVtcHR5IHN0YXJ0aW5n
TGlzdCBiZWZvcmUgDQogICAgICAgIGNhbGxpbmcgdGVzdEZ1bmMxIC0tIElmIHRoaXMgcG9z
c2liaWxpdHkgZXhpc3RzIQ0KICAgICcnJw0KICAgIHJldHVybihbeCBmb3IgeCBpbiBzdGFy
dGluZ0xpc3QgaWYgeFswXSA9PSAneCddLCANCiAgICAgICAgICAgW3ggZm9yIHggaW4gc3Rh
cnRpbmdMaXN0IGlmIHhbMF0gIT0gJ3gnXSkNCg0KZGVmIHRlc3RGdW5jMih3b3Jkcyk6DQog
ICAgJycnDQogICAgICBBbGdvcml0aG0tMg0KICAgICcnJw0KICAgIHdvcmRzX3dpdGhfeCA9
IFtdDQogICAgd29yZHNfd2l0aG91dF94ID0gW10NCiAgICBmb3Igd29yZCBpbiB3b3JkczoN
CiAgICAgICAgaWYgd29yZC5zdGFydHN3aXRoKCd4Jyk6DQogICAgICAgICAgICB3b3Jkc193
aXRoX3guYXBwZW5kKHdvcmQpDQogICAgICAgIGVsc2U6DQogICAgICAgICAgICB3b3Jkc193
aXRob3V0X3guYXBwZW5kKHdvcmQpDQogICAgd29yZHNbOl0gPSB3b3Jkc193aXRob3V0X3gg
ICMgc2xpY2UgYXNzaWdubWVudA0KICAgIHJldHVybiB3b3Jkc193aXRoX3gNCg0KZGVmIHRl
c3RGdW5jMkEod29yZHMpOg0KICAgICcnJw0KICAgICAgQWxnb3JpdGhtLTJBDQogICAgJycn
DQogICAgd29yZHNfd2l0aF94ID0gW10NCiAgICB3b3Jkc193aXRob3V0X3ggPSBbXQ0KICAg
IGZvciB3b3JkIGluIHdvcmRzOg0KICAgICAgICBpZiB3b3JkLnN0YXJ0c3dpdGgoJ3gnKToN
CiAgICAgICAgICAgIHdvcmRzX3dpdGhfeC5hcHBlbmQod29yZCkNCiAgICAgICAgZWxzZToN
CiAgICAgICAgICAgIHdvcmRzX3dpdGhvdXRfeC5hcHBlbmQod29yZCkNCiAgICAjd29yZHNb
Ol0gPSB3b3Jkc193aXRob3V0X3ggICMgc2xpY2UgYXNzaWdubWVudA0KICAgIHJldHVybiB3
b3Jkc193aXRoX3gsIHdvcmRzX3dpdGhvdXRfeA0KDQoNCmRlZiBnZW5TdHJMaXN0KE5DaGFy
LE5TdHJuZyxBbHBoLGxlYWRDaHIpOg0KICAgICcnJw0KICAgICBQdXJwb3NlOiBHZW5lcmF0
ZSBhIGxpc3Qgb2YgTlN0cm5nIGVsZW1lbnRzIHdpdGggZWFjaCBlbGVtZW50IGEgc3RyaW5n
DQogICAgICAgICAgICAgIG9mIGxlbmd0aCBOQ2hhciBhbmQgY29uc3RyYWluZWQgc3VjaCB0
aGF0IGFwcHJveC4gNTAlIG9mIHRoZSANCiAgICAgICAgICAgICAgc3RyaW5ncyB3aWxsIGJl
Z2luIHdpdGggdGhlIGNoYXJhY3RlciAoc3ltYm9sKSBsZWFkQ2hyDQogICAgICAgSW5wdXRz
OiANCiAgICAgICAgICAgTkNoYXIgLS0gbnVtYmVyIG9mIGNoYXJhY3RlcnMgaW4gZWFjaCBl
bGVtZW50DQogICAgICAgICAgTlN0cm5nIC0tIG51bWJlciBvZiBlbGVtZW50cyBpbiBsaXN0
IChzdHJnTGlzdCkNCiAgICAgICAgICAgIEFscGggLS0gbGlzdCBvZiBjaGFyYWN0ZXJzIHRv
IGJlIHVzZWQgKG11c3QgY29udGFpbiB0aGUgbGVhZENocikNCiAgICAgICAgIGxlYWRDaHIg
LS0gbGVhZGluZyBjaGFyYWN0ZXIgZm9yIHN0cmluZ3MgdG8gYmUgZ2VuZXJhdGVkIGZyb20g
QWxwaA0KICAgICAgIE90cHV0czoNCiAgICAgICAgc3RyZ0xpc3QgLS0gbGlzdCB3aXRoIE5T
dHJpbmcgc3RyaW5ncyBvZiBOQ2hhciBjaGFyYWN0ZXJzIChmcm9tIEFscGgpIGluIGVhY2gg
ICAgICAgICAgICAgICAgICAgIA0KICAgICcnJw0KICAgIE5TeW0gPSBsZW4oQWxwaCkNCiAg
ICBzdHJnTGlzdCA9IFtdDQogICAgZm9yIGkgaW4gcmFuZ2UoTlN0cm5nKTogDQogICAgICAg
IGlmIHJhbmRvbS5yYW5kb20oKSA8IDAuNTogDQogICAgICAgICAgICBjaGFyID0gbGVhZENo
cg0KICAgICAgICBlbHNlOiANCiAgICAgICAgICAgIHdoaWxlIFRydWU6DQogICAgICAgICAg
ICAgICAgaW5keCA9IHJhbmRvbS5yYW5kaW50KDAsTlN5bS0xKSAgICAgICAgICAgIA0KICAg
ICAgICAgICAgICAgIGNoYXIgPSBBbHBoW2luZHhdDQogICAgICAgICAgICAgICAgaWYgY2hh
ciAhPSBsZWFkQ2hyOiBicmVhaw0KICAgICAgICAgICAgDQogICAgICAgIGZvciBqIGluIHJh
bmdlKDEsTkNoYXIpOg0KICAgICAgICAgICAgaW5keCA9IHJhbmRvbS5yYW5kaW50KDAsTlN5
bS0xKSAgICAgICAgICAgIA0KICAgICAgICAgICAgY2hhciA9IGNoYXIgKyBBbHBoW2luZHhd
DQogICAgICAgICAgICANCiAgICAgICAgc3RyZ0xpc3QuYXBwZW5kKGNoYXIpICAgDQogICAg
ICAgIA0KICAgIHJldHVybiBzdHJnTGlzdA0KDQojKysrKysrKysrKysrKysrKysrKysrKysr
KysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysNCkFscGggPSBbJ2EnLCdi
JywnYycsJ2QnLCdlJywnZicsJ2cnLCdoJywnaScsJ2onLCdrJywnbCcsJ20nLA0KICAgICAg
ICAnbicsJ28nLCdwJywncScsJ3InLCdzJywndCcsJ3UnLCd2JywndycsJ3gnLCd5Jywneidd
DQoNCk5DaGFyID0gNCAgICAgICAgICMgNCBjaGFycyBwZXIgc3RyaW5nDQpOU3RybmcgPSAx
MDAwMDAgICAjIDEwMCwwMDAgc3RyaW5ncyBpbiBsaXN0IA0KTlJ1bnMgPSAxMDAgICAgICAg
IyAxMDAgcmFuZG9tIGxpc3RzIChudW1iZXIgb2YgTUMgc2ltdWxhdGlvbnMpDQoNCiMgRm9y
IHF1aWNrIHRlc3RpbmcNCiNOQ2hhciA9IDQgICAgICAgICMgNCBjaGFycyBwZXIgc3RyaW5n
DQojTlN0cm5nID0gMTAwMDAgICAjIDEwLDAwMCBzdHJpbmdzIGluIGxpc3QgDQojTlJ1bnMg
PSAyMCAgICAgICAjIDIwIHJhbmRvbSBsaXN0cw0KDQpzeWQgPSAxMDcxICAgICAgICMgaW5p
dGlhbCBzZWVkIGZvciBSTkcgKGZvciByZXBlYXRhYmlsaXR5KQ0KDQpwcmludFJ1bm5pbmdN
ZWFuID0gRmFsc2UNCg0KbXUxLG11MixtdTMsbXVnID0gMC4wLDAuMCwwLjAsMC4wDQp4MSx4
Mix4MyA9IDAuMCwwLjAsMC4wDQpwcmludCAnJTVkIHJ1bnMgd2l0aCBsaXN0cyBjb250YWlu
aW5nICU3ZCBlbGVtZW50cycgJShOUnVucyxOU3RybmcpDQpmb3IgaXJ1biBpbiByYW5nZShO
UnVucyk6DQogICAgdGljID0gY2xvY2soKQ0KICAgIGsgPSBpcnVuICsgMQ0KICAgIHByaW50
ICcgcnVuIC0gJTJkJyAlaw0KICAgIHN5ZCArPSAxOSAgICAjIG5ldyBzZWVkIGZvciBlYWNo
IHJ1bg0KICAgIHJhbmRvbS5zZWVkKHN5ZCkNCiAgICAjcHJpbnQgJ0dlbnJhdGluZyBsaXN0
IG9mICU3ZCBzdHJpbmdzLi4uJyAlTlN0cm5nDQogICAgc3RyZ0xpc3QgPSBnZW5TdHJMaXN0
KE5DaGFyLE5TdHJuZyxBbHBoLCd4JykgICANCiAgICANCiAgICB0MCA9IGNsb2NrKCkNCiAg
ICB4T25seUxpc3Qsc3RyZ0xpc3QgPSB0ZXN0RnVuYzEoc3RyZ0xpc3QpICMgYWxnb3JpdGht
LTENCiAgICB0MSA9IGNsb2NrKCkgICAgDQogICAgDQogICAgI3ByaW50ICdMZW5ndGggb2Yg
eE9ubHlMaXN0ID0gJTdkJyAlbGVuKHhPbmx5TGlzdCkNCiAgICAjcHJpbnQgJyBMZW5ndGgg
b2Ygc3RyZ0xpc3QgPSAlN2QnICVsZW4oc3RyZ0xpc3QpICAgIA0KICAgIGV0aW1lID0gdDEg
LSB0MA0KICAgIGRlbHRhID0gZXRpbWUgLSBtdTENCiAgICBtdTEgKz0gZGVsdGEvaw0KICAg
IGlmIHByaW50UnVubmluZ01lYW46DQogICAgICAgIHByaW50ICcgIGFsZ29yaXRobS0xIC0t
ICU5LjVmJyAlbXUxDQogICAgeDEgKz0gZGVsdGEqKGV0aW1lLW11MSkNCiAgICANCiAgICAj
cHJpbnQNCiAgICByYW5kb20uc2VlZChzeWQpDQogICAgI3ByaW50ICdHZW5yYXRpbmcgbGlz
dCBvZiAlN2Qgc3RyaW5ncy4uLicgJU5TdHJuZw0KICAgIHN0cmdMaXN0ID0gZ2VuU3RyTGlz
dChOQ2hhcixOU3RybmcsQWxwaCwneCcpDQogICAgDQogICAgdDAgPSBjbG9jaygpDQogICAg
eE9ubHlMaXN0ID0gdGVzdEZ1bmMyKHN0cmdMaXN0KSAgICAgICAgICAjIGFsZ29yaXRobS0y
ICAgDQogICAgdDEgPSBjbG9jaygpDQogICAgDQogICAgI3ByaW50ICdMZW5ndGggb2YgeE9u
bHlMaXN0ID0gJTdkJyAlbGVuKHhPbmx5TGlzdCkNCiAgICAjcHJpbnQgJyBMZW5ndGggb2Yg
c3RyZ0xpc3QgPSAlN2QnICVsZW4oc3RyZ0xpc3QpICAgIA0KICAgIGV0aW1lID0gdDEgLSB0
MA0KICAgIGRlbHRhID0gZXRpbWUgLSBtdTINCiAgICBtdTIgKz0gZGVsdGEvaw0KICAgIGlm
IHByaW50UnVubmluZ01lYW46DQogICAgICAgIHByaW50ICcgIGFsZ29yaXRobS0yIC0tICU5
LjVmJyAlbXUyDQogICAgeDIgKz0gZGVsdGEqKGV0aW1lLW11MikgICAgDQogICAgDQogICAg
cmFuZG9tLnNlZWQoc3lkKSAgICANCiAgICAjcHJpbnQgJ0dlbnJhdGluZyBsaXN0IG9mICU3
ZCBzdHJpbmdzLi4uJyAlTlN0cm5nDQogICAgc3RyZ0xpc3QgPSBnZW5TdHJMaXN0KE5DaGFy
LE5TdHJuZyxBbHBoLCd4JykNCiAgICANCiAgICB0MCA9IGNsb2NrKCkNCiAgICB4T25seUxp
c3Qsc3RyZ0xpc3QgPSB0ZXN0RnVuYzJBKHN0cmdMaXN0KSAgICAgICAgICAjIGFsZ29yaXRo
bS0yQQ0KICAgIHQxID0gY2xvY2soKQ0KICAgIA0KICAgICNwcmludCAnTGVuZ3RoIG9mIHhP
bmx5TGlzdCA9ICU3ZCcgJWxlbih4T25seUxpc3QpDQogICAgI3ByaW50ICcgTGVuZ3RoIG9m
IHN0cmdMaXN0ID0gJTdkJyAlbGVuKHN0cmdMaXN0KSAgICANCiAgICBldGltZSA9IHQxIC0g
dDANCiAgICBkZWx0YSA9IGV0aW1lIC0gbXUzDQogICAgbXUzICs9IGRlbHRhL2sNCiAgICBp
ZiBwcmludFJ1bm5pbmdNZWFuOg0KICAgICAgICBwcmludCAnICBhbGdvcml0aG0tMkEgLS0g
JTkuNWYnICVtdTMNCiAgICB4MyArPSBkZWx0YSooZXRpbWUtbXUzKQ0KICAgIA0KICAgIHRv
YyA9IGNsb2NrKCkNCiAgICBsb29wVGltZSA9IHRvYyAtIHRpYw0KICAgIGRlbHRhID0gbG9v
cFRpbWUgLSBtdWcNCiAgICBtdWcgKz0gZGVsdGEvaw0KICAgIHJ1bnNSID0gTlJ1bnMgLSBr
DQogICAgZXN0VG9Db21wbGV0ZSA9IG11ZypydW5zUg0KICAgIHByaW50ICcgICBFVFRDID0g
JTguMmYgc2Vjb25kcycgJWVzdFRvQ29tcGxldGUNCiAgICANCg0KcHJpbnQNCnByaW50ICcg
ICAgICAgIFRpbWluZyBpbiBzZWNvbmRzJw0KcHJpbnQgJyAqKioqKioqKioqKioqKioqKioq
KioqKioqKioqKioqKioqKionDQpwcmludCAnICAgIG1ldGhvZCAgICAgfCAgICAgYXZnIHRp
bWUgKHNkKScNCnByaW50ICcgLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t
Jw0KcHJpbnQgJyBhbGdvcml0aG0tMSAgIHwgJTkuNWYgKCU4LjZmKScgJShtdTEsbWF0aC5z
cXJ0KHgxL05SdW5zKSkNCnByaW50ICcgYWxnb3JpdGhtLTIgICB8ICU5LjVmICglOC42Zikn
ICUobXUyLG1hdGguc3FydCh4Mi9OUnVucykpDQpwcmludCAnIGFsZ29yaXRobS0yQSAgfCAl
OS41ZiAoJTguNmYpJyAlKG11MyxtYXRoLnNxcnQoeDMvTlJ1bnMpKQ0KDQpwcmludA0KcHJp
bnQgIlRoLXRoYS10aGEtdGhhdCdzIGFsbCBmb2xrcyEi
--------------000402070808050100070305--