python challenge question (string manipulation)

Discussion in 'Python' started by John Salerno, Mar 29, 2006.

  1. John Salerno

    John Salerno Guest

    Ok, for those who have gotten as far as level 2 (don't laugh!), I have a
    question. I did the translation as such:

    import string

    alphabet = string.lowercase[:26]
    code = string.lowercase[2:26] + 'ab'
    clue = "g fmnc wms bgblr rpylqjyrc gr zw fylb. rfyrq ufyr amknsrcpq ypc
    dmp. bmgle gr gl zw fylb gq glcddgagclr ylb rfyr'q ufw rfgq rcvr gq qm
    jmle. sqgle qrpgle.kyicrpylq() gq pcamkkclbcb. lmu ynnjw ml rfc spj."

    trans = string.maketrans(alphabet, code)
    clue = clue.translate(trans)

    print clue
    raw_input()



    It works, but is there a better way to shift the letters of the alphabet
    for 'code'? I remember a method that did this for lists, I think, but I
    can't remember what it was or if it worked for strings.

    Thanks.
     
    John Salerno, Mar 29, 2006
    #1
    1. Advertising

  2. John Salerno

    John Salerno Guest

    John Salerno wrote:

    > It works, but is there a better way to shift the letters of the alphabet
    > for 'code'? I remember a method that did this for lists, I think, but I
    > can't remember what it was or if it worked for strings.


    Ah ha! This is cleaner:

    alphabet = string.ascii_lowercase
    code = string.ascii_lowercase[2:] + string.ascii_lowercase[:2]

    Yet it still seems kind of verbose. But since that's the official
    solution, I guess there's no other way to shift the characters in a string?
     
    John Salerno, Mar 29, 2006
    #2
    1. Advertising

  3. John

    In python, strings are immutable - you have to create a new string no
    matter what you do.

    Also, I suspect you meant to say:

    >>> alphabet = string.ascii_lowercase
    >>> code = alphabet[2:] + alphabet[:2]


    I had a similar need recently for a guitar chord generator program I've
    been working on. Here is a "shift" function from my utilities module:

    def shift(list,num):
    '''Shifts sequence "list" by "num" places.
    if num is positive, list scrolls forwards,
    otherwise, backwards.'''
    if abs(num) > len(list):
    num=num%len(list) # Use mod to remove full list entry rotations
    newlist=list[-num:]+list[:-num]
    return newlist

    I actually create a new list here, although since lists are mutable, I
    could probably just change items in-place. There is very likely
    something already in the builtins or the standard library for this, but
    I just haven't searched hard enough.

    Interesting trap I kept falling into: calling a guitar string a
    "string" and then having collisions with the python type of the same
    name. Over and over again :)

    Regards
    Caleb
     
    Caleb Hattingh, Mar 29, 2006
    #3
  4. John Salerno

    John Salerno Guest

    Caleb Hattingh wrote:

    > Also, I suspect you meant to say:
    >
    >>>> alphabet = string.ascii_lowercase
    >>>> code = alphabet[2:] + alphabet[:2]


    Ah yes, I see what you did there. :)

    > I actually create a new list here, although since lists are mutable, I
    > could probably just change items in-place. There is very likely
    > something already in the builtins or the standard library for this, but
    > I just haven't searched hard enough.



    I'm pretty sure I read about a method for moving the items in lists
    around like that, so that you can shift the beginning to the end and
    vice versa. If I can find it, I'll let you know.
     
    John Salerno, Mar 29, 2006
    #4
  5. Em Qua, 2006-03-29 às 19:34 +0000, John Salerno escreveu:
    > alphabet = string.ascii_lowercase
    > code = string.ascii_lowercase[2:] + string.ascii_lowercase[:2]
    >
    > Yet it still seems kind of verbose. But since that's the official
    > solution, I guess there's no other way to shift the characters in a string?


    -----------

    from collections import deque
    from string import ascii_lowercase

    a = deque(ascii_lowercase)
    a.rotate(-2)
    print list(a)
    # prints ['c', 'd', ..., 'z', 'a', 'b']

    -----------

    But mind the performance! (as an exercise, time the performance of mine
    and your approach using the timeit module and post back to the list)

    HTH,

    --
    Felipe.
     
    Felipe Almeida Lessa, Mar 29, 2006
    #5
  6. John Salerno

    Terry Reedy Guest

    "John Salerno" <> wrote in message
    news:LiBWf.1856$...
    > John Salerno wrote:
    >
    >> It works, but is there a better way to shift the letters of the alphabet
    >> for 'code'? I remember a method that did this for lists, I think, but I
    >> can't remember what it was or if it worked for strings.

    >
    > Ah ha! This is cleaner:
    >
    > alphabet = string.ascii_lowercase
    > code = string.ascii_lowercase[2:] + string.ascii_lowercase[:2]
    >
    > Yet it still seems kind of verbose. But since that's the official
    > solution, I guess there's no other way to shift the characters in a
    > string?


    The above would look less verbose if the second line 'paid attention' to
    the first and were written as the slightly more efficient

    code = alphabet[2:] + alphabet[:2]

    An alternative is shifted access. alphabet[(i+24)%26]

    Terry Jan Reedy
     
    Terry Reedy, Mar 29, 2006
    #6
  7. Terry

    That is very succint. Rewriting my shift function given earlier:

    >>> import string
    >>> alpha = string.ascii_lowercase
    >>> print alpha

    abcdefghijklmnopqrstuvwxyz
    >>> def shift(lst, n):

    return [lst[(i+len(lst)-n)%len(lst)] for i,item in enumerate(lst)]

    >>> print shift(alpha,2)

    ['y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l',
    'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x']

    Shorter and possibly as clear too; thanks!

    Keep well
    Caleb
     
    Caleb Hattingh, Mar 30, 2006
    #7
  8. Em Qua, 2006-03-29 às 22:20 -0800, Caleb Hattingh escreveu:
    > That is very succint. Rewriting my shift function given earlier:
    >
    > >>> import string
    > >>> alpha = string.ascii_lowercase
    > >>> print alpha

    > abcdefghijklmnopqrstuvwxyz
    > >>> def shift(lst, n):

    > return [lst[(i+len(lst)-n)%len(lst)] for i,item in enumerate(lst)]


    It sure is short, but is it fast? Compare to the function below (the
    fastest I can think of ATM):

    def shift(lst, n):
    first = (-n) % len(lst)
    result = list(lst[first:]) # if lst is a iterable but not a list
    result.extend(lst[:first])
    return result

    Now benchmarking:

    $ python2.4 -mtimeit -s "def shift(lst, n): return [lst[(i+len(lst)-n)%
    len(lst)] for i,item in enumerate(lst)]"
    "shift('abcdefghijklmnopqrstuvwxyz',2)"
    10000 loops, best of 3: 21.5 usec per loop
    $ python2.4 -mtimeit -s "def shift(lst, n): length = len(lst); first =
    (-n) % length; result = list(lst[first:]); result.extend(lst[:first]);
    return result" "shift('abcdefghijklmnopqrstuvwxyz',2)"
    100000 loops, best of 3: 3.98 usec per loop

    The five-line version is more than five times faster than the two-line
    counterpart. But it scales better too:

    $ python2.4 -mtimeit -s "string = 'abcdefghijklmnopqrstuvwxyz'*10000 def
    shift(lst, n): length = len(lst); first = (-n) % length; result =
    list(lst[first:]); result.extend(lst[:first]); return result"
    "shift(string,2)"
    100 loops, best of 3: 10.6 msec per loop
    $ python2.4 -mtimeit -s "string = 'abcdefghijklmnopqrstuvwxyz'*10000
    def shift(lst, n): return [lst[(i+len(lst)-n)%len(lst)] for i,item in
    enumerate(lst)]" "shift(string,2)"
    10 loops, best of 3: 206 msec per loop

    With a 10 000 times larger list it takes almost 20 times less time.

    Of course a human can't perceive a 17.52 usec difference in time, but
    I'd like to make it clear that the two-line function shouldn't be used
    on a real system.

    What we learn from this? When it's not needed (like now), please don't
    iterate over all items of a list.

    HTH,

    --
    Felipe.
     
    Felipe Almeida Lessa, Mar 30, 2006
    #8
  9. Felipe

    I get the same results as you. You make a good point about not
    iterating when it's not needed. I played around with your test code
    and found some interesting things:

    1. enumerate vs. range(len()) has very little overhead (something I
    have wondered about)

    In my code, making the change causes the timing to go from 27.5 usec to
    24.6 usec: basically nothing.

    2. I combined the two result statements into one, and your code as
    written still appears consistently faster, albeit only slightly:

    One-line assignment to result: 6.98; 7.18; 6.49; 7.1 (code below)
    Your way via extend: 5.24; 5.26; 5.09; 5.3; 5.26; 5.21 (code further
    below)

    Is this because of "+" concatenation?

    My one-line assignment to result:

    [caleb@localhost ~]$ python2.4 -mtimeit -s "def shift(lst, n): length =
    len(lst); first =(-n) % length; result = list(lst[first:]) +
    list(lst[:first]); return result"
    "shift('abcdefghijklmnopqrstuvwxyz',2)" 100000 loops, best of 3: 6.98
    usec per loop
    [caleb@localhost ~]$ python2.4 -mtimeit -s "def shift(lst, n): length =
    len(lst); first =(-n) % length; result = list(lst[first:]) +
    list(lst[:first]); return result"
    "shift('abcdefghijklmnopqrstuvwxyz',2)"
    100000 loops, best of 3: 7.18 usec per loop
    [caleb@localhost ~]$ python2.4 -mtimeit -s "def shift(lst, n): length =
    len(lst); first =(-n) % length; result = list(lst[first:]) +
    list(lst[:first]); return result"
    "shift('abcdefghijklmnopqrstuvwxyz',2)"
    100000 loops, best of 3: 6.49 usec per loop
    [caleb@localhost ~]$ python2.4 -mtimeit -s "def shift(lst, n): length =
    len(lst); first =(-n) % length; result = list(lst[first:]) +
    list(lst[:first]); return result"
    "shift('abcdefghijklmnopqrstuvwxyz',2)"
    100000 loops, best of 3: 7.1 usec per loop

    Your code:

    [caleb@localhost ~]$ python2.4 -mtimeit -s "def shift(lst, n): length =
    len(lst); first =(-n) % length; result = list(lst[first:]);
    result.extend(lst[:first]); return result"
    "shift('abcdefghijklmnopqrstuvwxyz',2)"
    100000 loops, best of 3: 5.24 usec per loop
    [caleb@localhost ~]$ python2.4 -mtimeit -s "def shift(lst, n): length =
    len(lst); first =(-n) % length; result = list(lst[first:]);
    result.extend(lst[:first]); return result"
    "shift('abcdefghijklmnopqrstuvwxyz',2)"
    100000 loops, best of 3: 5.26 usec per loop
    [caleb@localhost ~]$ python2.4 -mtimeit -s "def shift(lst, n): length =
    len(lst); first =(-n) % length; result = list(lst[first:]);
    result.extend(lst[:first]); return result"
    "shift('abcdefghijklmnopqrstuvwxyz',2)"
    100000 loops, best of 3: 5.09 usec per loop
    [caleb@localhost ~]$ python2.4 -mtimeit -s "def shift(lst, n): length =
    len(lst); first =(-n) % length; result = list(lst[first:]);
    result.extend(lst[:first]); return result"
    "shift('abcdefghijklmnopqrstuvwxyz',2)"
    100000 loops, best of 3: 5.3 usec per loop
    [caleb@localhost ~]$ python2.4 -mtimeit -s "def shift(lst, n): length =
    len(lst); first =(-n) % length; result = list(lst[first:]);
    result.extend(lst[:first]); return result"
    "shift('abcdefghijklmnopqrstuvwxyz',2)"
    100000 loops, best of 3: 5.26 usec per loop
    [caleb@localhost ~]$ python2.4 -mtimeit -s "def shift(lst, n): length =
    len(lst); first =(-n) % length; result = list(lst[first:]);
    result.extend(lst[:first]); return result"
    "shift('abcdefghijklmnopqrstuvwxyz',2)"
    100000 loops, best of 3: 5.21 usec per loop

    Caleb
     
    Caleb Hattingh, Mar 30, 2006
    #9
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Morris.C
    Replies:
    4
    Views:
    377
    Maxim Yegorushkin
    Sep 8, 2005
  2. Franklin
    Replies:
    5
    Views:
    357
    Franklin
    Feb 28, 2009
  3. Chris Roos

    String Manipulation Nuby Question

    Chris Roos, May 6, 2005, in forum: Ruby
    Replies:
    12
    Views:
    211
    James Britt
    May 6, 2005
  4. John Yoo

    A string manipulation question

    John Yoo, Apr 11, 2006, in forum: Perl Misc
    Replies:
    3
    Views:
    138
    Dr.Ruud
    Apr 11, 2006
  5. Replies:
    8
    Views:
    226
    Peter Pearson
    Dec 11, 2012
Loading...

Share This Page