python challenge question (string manipulation)

[John Salerno]

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]

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?

 

[Caleb Hattingh]

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

 

[John Salerno]

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.

 

[Felipe Almeida Lessa]

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,

 

[Terry Reedy]

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

 

[Caleb Hattingh]

Terry

That is very succint. Rewriting my shift function given earlier:
return [lst[(i+len(lst)-n)%len(lst)] for i,item in enumerate(lst)]
['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

 

[Felipe Almeida Lessa]

Em Qua, 2006-03-29 às 22:20 -0800, Caleb Hattingh escreveu:

That is very succint. Rewriting my shift function given earlier:
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,

 

[Caleb Hattingh]

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