Problems with string and lists (searching and replaceing)

[jblazi]

I should like to search certain characters in a string and when they are
found, I want to replace other characters in other strings that are at
the same position (for a very simply mastermind game) for my pupils.

This very simple thing does not seem simple at all.

If I use strings, I cannot replace their parts (though I can use
string.find for the searching). I think it is a bad idea that strings are
not mutable, but I suspect that this has been discussed here for ages.

I can use sequences instead, but then first I have to 'split' and 'join'.
Additionally, there is no 'find' for sequences (who knows why not) and so
I can choose between using 'index' that raises an exception (and we have
not covered exceptions yet) or I can ask whether the character is in the
string before using 'index' which is a bit artificial from the point of
view of my pupils. (It is all right with me.)

Do I oversee something?

TIA,
JB

 

[Anton Vredegoor]

I should like to search certain characters in a string and when they are
found, I want to replace other characters in other strings that are at
the same position (for a very simply mastermind game) for my pupils.

This very simple thing does not seem simple at all.

If I use strings, I cannot replace their parts (though I can use
string.find for the searching). I think it is a bad idea that strings are
not mutable, but I suspect that this has been discussed here for ages.

I can use sequences instead, but then first I have to 'split' and 'join'.
Additionally, there is no 'find' for sequences (who knows why not) and so
I can choose between using 'index' that raises an exception (and we have
not covered exceptions yet) or I can ask whether the character is in the
string before using 'index' which is a bit artificial from the point of
view of my pupils. (It is all right with me.)

Do I oversee something?

Yes, UserString. The documentation is a bit sparse, but reading the
module itself provides additional information. Below is a quick test
script.

HTH,

Anton


from UserString import MutableString

def test():
s = MutableString("helo world")
print s
x = 'helo'
y = 'hello'
i = s.find(x)
s[i:i+len(x)] = y
print s

if __name__=='__main__':
test()

#output:
#helo world
#hello world

 

[Shu-Hsien Sheu]

I am not sure if this is what you want, but it seems that you can get around with it by assignments:

>>> x = 'test'
>>> y = 'yummy'
>>> a = x.index('e')
>>> y = y[:a] + 'a'+ y[a+1:]
>>> y
'yammy'

you can add try/except ValueError for the index method.

-shuhsien


I should like to search certain characters in a string and when they are found, I want to replace other characters in other strings that are at the same position (for a very simply mastermind game) for my pupils. This very simple thing does not seem simple at all. If I use strings, I cannot replace their parts (though I can use string.find for the searching). I think it is a bad idea that strings are not mutable, but I suspect that this has been discussed here for ages. I can use sequences instead, but then first I have to 'split' and 'join'. Additionally, there is no 'find' for sequences (who knows why not) and so I can choose between using 'index' that raises an exception (and we have not covered exceptions yet) or I can ask whether the character is in the string before using 'index' which is a bit artificial from the point of view of my pupils. (It is all right with me.) Do I oversee something?

 

[jblazi]

Do I oversee something?

Yes, UserString. The documentation is a bit sparse, but reading the
module itself provides additional information. Below is a quick test
script.

from UserString import MutableString

def test():
s = MutableString("helo world")
print s
x = 'helo'
y = 'hello'
i = s.find(x)
s[i:i+len(x)] = y
print s

if __name__=='__main__':
test()

#output:
#helo world
#hello world

Thx.
It would be quite diffcult to explain this akward procedure to beginners.
especially when they see that this can be done so simply in C.
It seems that I have stumbled upon one of the few cases when Python is
cumbersome and difficult to use.

JB

 

[Anton Vredegoor]

from UserString import MutableString

def test():
s = MutableString("helo world")
print s
x = 'helo'
y = 'hello'
i = s.find(x)
s[i:i+len(x)] = y
print s

if __name__=='__main__':
test()

#output:
#helo world
#hello world

Thx.
It would be quite diffcult to explain this akward procedure to beginners.
especially when they see that this can be done so simply in C.
It seems that I have stumbled upon one of the few cases when Python is
cumbersome and difficult to use.

Interesting. Could you provide an example showing in which way it can
be done so simply in C ? Maybe I could come up with better Python code
if I knew what the problem is with my code. Anyway, it was just
something I typed in without thinking much about it, to show that
strings can be mutated. In Python everything is an object so if some
functionality is needed it is pretty standard to use a subclass. In
this case a fitting subclass already was present in the standard
distribution so it seemed like a piece of cake.

With respect to beginners I suppose it's possible to project ones own
sense of what is easy, instead of really checking what would be easy
for *them*.

Beginners are not supposed to know about C, but possibly you are, and
maybe you are thinking too much from your own perspective in judging
what would be easy.

Anton

 

[Bengt Richter]

Do I oversee something?

Yes, UserString. The documentation is a bit sparse, but reading the
module itself provides additional information. Below is a quick test
script.

from UserString import MutableString

def test():
s = MutableString("helo world")
print s
x = 'helo'
y = 'hello'
i = s.find(x)
s[i:i+len(x)] = y
print s

if __name__=='__main__':
test()

#output:
#helo world
#hello world

Thx.
It would be quite diffcult to explain this akward procedure to beginners.
especially when they see that this can be done so simply in C.
It seems that I have stumbled upon one of the few cases when Python is
cumbersome and difficult to use.

For the above, what is wrong with
... s = 'helo world'
... print s
... s = s.replace('helo','hello',1)
... print s
... helo world
hello world

?

Regards,
Bengt Richter

 

[jblazi]

For the above, what is wrong with

... s = 'helo world'
... print s
... s = s.replace('helo','hello',1)
... print s
...
helo world
hello world

Nothing is wrong with that, of course, but my code is something like this:


def vergleiche_woerter(eingabe,wort):
eing = mysplit(eingabe)
wo = mysplit(wort)
ergebnis=['-','-','-','-','-']

# Suche zuerst nach Bullen
for i in range(len(eing)):
if eing == wo:
ergebnis = '*'
eing=wo = None

for i in range(len(eing)):
if eing == None: continue
if eing in wo:
j = wo.index(eing)
ergebnis = '.'
wo[j] = None

return join(ergebnis,'')

 

[Anton Vredegoor]

For the above, what is wrong with

... s = 'helo world'
... print s
... s = s.replace('helo','hello',1)
... print s
...
helo world
hello world

Well, why use replace anyway. It would be better to print the string
right to begin with and be done with it But seriously, the OP
asked for a way to find a position in a string and to change another
string at the found position, without constructing a new string and by
using some familiar operations. Why all these restrictions were
necessary is not my concern. Let's just assume the OP has a C-style
brain and needs some trajectory to reach Python-i-City.

Your approach seems to be good in that it's better to do things the
right way in the first place, so that no wrong things have to be
unlearned. We all know that it's ten times more costly to change
habits than to forget them and start from scratch.

However there are also totally blank pupils waiting to be educated and
the only way to get educated is by absorbing knowledge from someone
with more knowledge, flawed as this knowledge may be.

My strategy in such circumstances is to accept the unavoidable and to
show that Python is an easier fit to the problem [1] -some mastermind
scheme I believe- than C, even if C is the way the OP would know best
and even if it would lead to Python code in a C-straitjacket. The
straitjacket can be removed someday, and while the result would not be
as good as never having been in it, it would be better than not having
been educated at all.

Come to think of it, since our educational system is nowhere perfect I
guess we all share this condition!

Anton

[1] UserString's MutableString is not a subclass of string but a
wrapper around it that mimics a mutable string more or less like if it
were a C-style array of chars, except that it's way more powerful and
flexible.

 

[jblazi]

I shall have a computer science class this year and I decided to use
Python. It is my favourite language and I have used it for many years. Now
I thought, one of our first "real" programs, in our pre-graphical and
pre-class state, would be to write simple program that works like this:

One of the pupils enters a word. It should be a valid German word
consisting of five letters, for example 'abcde' (which is not a German
word by the way).

The the other player may enter a guess which must be a five letter word as
well, for example 'xbxxx'. Then the system answers with the string '-*---'
as the 'b' in 'xbxxx' was correct and at the right place as well.

Had the second player entered 'xxxbx', the system had responded with
'---.-', as the 'b' is correct but not correctly positioned.

The second player must find out the original word.

Now I did not see how to do it as simply as posible, that was the problem.

JB

 

[Ulrich Petri]

I shall have a computer science class this year and I decided to use
Python. It is my favourite language and I have used it for many years. Now
I thought, one of our first "real" programs, in our pre-graphical and
pre-class state, would be to write simple program that works like this:

One of the pupils enters a word. It should be a valid German word
consisting of five letters, for example 'abcde' (which is not a German
word by the way).

The the other player may enter a guess which must be a five letter word as
well, for example 'xbxxx'. Then the system answers with the string '-*---'
as the 'b' in 'xbxxx' was correct and at the right place as well.

Had the second player entered 'xxxbx', the system had responded with
'---.-', as the 'b' is correct but not correctly positioned.

The second player must find out the original word.

Hm sth. like this?

-----code------
def mastermind(word, guess):
if len(word) != len(guess):
return "Error"
ret = ["-"]*len(word)
counter = 0
for lw, lg in zip(word, guess):
if lw == lg:
ret[counter] = "x"
else:
if lg in word:
ret[counter] = "."
counter += 1
return "".join(ret)
'xx-xxx'
-----code-----


HTH

Ciao Ulrich

 

[jblazi]

def mastermind(word, guess):
if len(word) != len(guess):
return "Error"
ret = ["-"]*len(word)
counter = 0
for lw, lg in zip(word, guess):
if lw == lg:
ret[counter] = "x"
else:
if lg in word:
ret[counter] = "."
counter += 1
return "".join(ret)

Thx.
The problem with this may be that for example

mastermind('xxaxx','ayayy')

returns

..-x--

but I should like to have --x-- instead (at least I think so).

JB

 

[Dennis Lee Bieber]

jblazi fed this fish to the penguins on Saturday 20 September 2003
11:55 pm:

One of the pupils enters a word. It should be a valid German word
consisting of five letters, for example 'abcde' (which is not a German
word by the way).

The the other player may enter a guess which must be a five letter
word as well, for example 'xbxxx'. Then the system answers with the
string '-*---' as the 'b' in 'xbxxx' was correct and at the right
place as well.

Had the second player entered 'xxxbx', the system had responded with
'---.-', as the 'b' is correct but not correctly positioned.

The second player must find out the original word.

Sounds like a variation of an old game called Mastermind. A Google
search for "Mastermind algorithm" brings up lots of links, though I
suspect these are all based on having the computer perform the
guessing. Using five slots, and the full alphabet, is going to expand
the possibilities drastically -- Mastermind, as I recall, normally used
four slots, with an "alphabet" of 6 colors, and granted something like
20 guesses.


---- mastermind.py -----

"""
Five-character word-based Mastermind control shell
Dennis Lee Bieber September 21 2003

This program performs the user input of the target word, and
the evaluation of the guesses. It does not create its own guesses
to solve a user selected target word.

Guess results are reported as a string containing:

- the letter in the guess at this position does not
appear anywhere in the target word

. the letter at this position does appear in the target,
but does not belong in this position

* the letter at this position is correct

"""

def GetWord(prompt):
while 1:
wd = raw_input(prompt)
if len(wd) != 5:
print "Please enter a five-letter word"
else:
break
return wd

def Evaluate(t, g):
tl = list(t)
gl = list(g)
rl = list("-----")

for i in range(5):
if gl in tl:
rl = "."
if gl == tl:
rl = "*"

return "".join(rl)


if __name__ == "__main__":
print __doc__
print ""

# get the target word from "player 1"
#
target = GetWord("Enter the target word> ")

# clear the screen; simplistic method
#
print "\n"*50

# process the guesses from "player 2"
#
gcount = 0
while 1:
# get a guess -- identical to getting the target
#
gcount += 1
guess = GetWord("Enter a word for guess %s> " % gcount)

# evaluate the guess against the target
#
result = Evaluate(target, guess)

# report results
if result == "*****":
print "\nCongratulations\n\tYou have guessed the word in %s
tries\n" % gcount
break
else:
print "\n%s\tPlease try again\n" % result




--

 

[Colin Fox]

I shall have a computer science class this year and I decided to use
Python. It is my favourite language and I have used it for many years. Now
I thought, one of our first "real" programs, in our pre-graphical and
pre-class state, would be to write simple program that works like this:

One of the pupils enters a word. It should be a valid German word
consisting of five letters, for example 'abcde' (which is not a German
word by the way).

The the other player may enter a guess which must be a five letter word as
well, for example 'xbxxx'. Then the system answers with the string '-*---'
as the 'b' in 'xbxxx' was correct and at the right place as well.

Had the second player entered 'xxxbx', the system had responded with
'---.-', as the 'b' is correct but not correctly positioned.

The second player must find out the original word.

Hm sth. like this?

-----code------
def mastermind(word, guess):
if len(word) != len(guess):
return "Error"
ret = ["-"]*len(word)
counter = 0
for lw, lg in zip(word, guess):
if lw == lg:
ret[counter] = "x"
else:
if lg in word:
ret[counter] = "."
counter += 1
return "".join(ret)
'xx-xxx'
-----code-----

Here's an alternative. I took out the 'if lg in word' logic,
since that doesn't take into account duplicates and therefore
would be misleading (ie 'jaguar','jaaaaa' would return 'x.....',
but there aren't 5 a's in the word).

#!/usr/bin/env python
import string

def wordcheck(word, guess):
outstr = []
if len(word) != len(guess):
raise "Wrong number of letters in guess."

for x in range(len(word)):
outstr.append( ['-','*'][(word[x]==guess[x])] )

return string.join(outstr,'')

res = wordcheck('Colin','Coolo')
print res

 

[Ulrich Petri]

Here's an alternative. I took out the 'if lg in word' logic,
since that doesn't take into account duplicates and therefore
would be misleading (ie 'jaguar','jaaaaa' would return 'x.....',
but there aren't 5 a's in the word).

#!/usr/bin/env python
import string

def wordcheck(word, guess):
outstr = []
if len(word) != len(guess):
raise "Wrong number of letters in guess."

for x in range(len(word)):
outstr.append( ['-','*'][(word[x]==guess[x])] )

return string.join(outstr,'')

res = wordcheck('Colin','Coolo')
print res

Yeah your right, but with your code there is no indication of a right letter
in the wrong position.
I guess one has to use a decorate-undecorate thing...
If i have some time later today i will test this...

Ciao Ulrich

 

[Alex Martelli]

I should like to search certain characters in a string and when they are
found, I want to replace other characters in other strings that are at
the same position (for a very simply mastermind game) for my pupils.

This very simple thing does not seem simple at all.

If I use strings, I cannot replace their parts (though I can use
string.find for the searching). I think it is a bad idea that strings are
not mutable, but I suspect that this has been discussed here for ages.

Not really (most of us appear to have no problems with immutable
strings). And indeed I don't see what's complicated with your task,
at all. Suppose the string you're "searching certain characters in"
is held by variable "searched_string", the characters you are
searching in (any sequence, list or other) variable "characters",
the "other strings" are (e.g.) all the items of list "otherstrings",
and finally the replacement characters are in dictionary "replacers"
indexed by the found characters and with a default of say '*' when
a found character is not a key in "replacers". Note that all of
these or similar hypotheses are obviously needed whether strings
are mutable or not.

Now, if strings were mutable, the obvious solution (avoiding
exceptions, as you asked) might be:

for c in characters:
where = searched_string.find(c)
if where<0: continue
replace_with = replacers.get(c, '*')
for another in otherstrings:
if where < len(another):
another[where] = replace_with

Now since strings are NOT mutable, you need to change this to:

for c in characters:
where = searched_string.find(c)
if where<0: continue
replace_with = replacers.get(c, '*')
for i, another in enumerate(otherstrings):
otherstrings = another[:where] + replace_with + another[where+1:]

i.e, keep track of the index and set there another string build of
three parts -- preceding, replace_with, succeeding. In this case
you do not have to ensure that where<len(another) -- if that
condition does not hold then replace_with will just be "appended"
to the "other string" (slicing is more tolerant than indexing). If
you want the same semantics as above (no change to "other strings"
that are shorter than the 'where' point requires) then you'll just
have to add the same guard in this second case, of course.

Basically, the change from "x[y]=z" to "x=x[:y]+z+x[y+1:]" is just
not "traumatic" enough, in my opinion, to warrant considering this
a seriously complicated problem ("not seem simple at all"). If
you need to explain it to beginners by analogy: imagine you have an
original document that you're not allowed to alter, for example
because that document is bound and you don't want to, or cannot,
break its binding; despite this, you are requested to "change page
4 into this one" to make a new version. Then, just "photocopy"
pages 1 to 3, and pages 5 and following, and in the new version
collate (first) the copies of original pages 1 to 3, (then)
the new "this one", and (finally) the copies of pages 5 and
following of the original document. Since not all documents one
meets in real life come in "flexible" bindings where one can
remove and replace pages, the analogy should be quite clear, IMHO.


Alex

 

[jblazi]

Basically, the change from "x[y]=z" to "x=x[:y]+z+x[y+1:]" is just
not "traumatic" enough, in my opinion, to warrant considering this
a seriously complicated problem ("not seem simple at all").

Of course, you are right. The possibility to create a new string dawned
upon me later when I was already lying in my bed...
Of course, in this case a lot of activity takes place in the background
(memory objects have to be allocated and deallocated) and if efficiency
played a rôle... In this case it does not and your solution is the right
one.
In C strings are mutable and so you can work in situ but usually those
zero terminated strings have their disadvantages as well...

Thank you for your help.

 

[jblazi]

Yeah your right, but with your code there is no indication of a right letter
in the wrong position.
I guess one has to use a decorate-undecorate thing...

This is what I did in the code snippet I posted in this thread (though I
did it in a cumbersome way).

JB

 

[Alex Martelli]

Basically, the change from "x[y]=z" to "x=x[:y]+z+x[y+1:]" is just
not "traumatic" enough, in my opinion, to warrant considering this
a seriously complicated problem ("not seem simple at all").

Of course, you are right. The possibility to create a new string dawned
upon me later when I was already lying in my bed...
Of course, in this case a lot of activity takes place in the background
(memory objects have to be allocated and deallocated) and if efficiency
played a rôle... In this case it does not and your solution is the right
one.

Yes, you did indicate it was an exercise, so efficiency clearly could
not matter at this micro-level. If it did I might suggest array.array
or the like.

In C strings are mutable and so you can work in situ but usually those
zero terminated strings have their disadvantages as well...

Sure, they're lots of trouble (non-expandable, can't contain arbitrary
bytes, etc).

Thank you for your help.

You're welcome!


Alex

 

[Anton Vredegoor]

I shall have a computer science class this year and I decided to use
Python. It is my favourite language and I have used it for many years. Now
I thought, one of our first "real" programs, in our pre-graphical and
pre-class state, would be to write simple program that works like this:

One of the pupils enters a word. It should be a valid German word
consisting of five letters, for example 'abcde' (which is not a German
word by the way).

That may come as a surprise to non-German speakers ;-)

The the other player may enter a guess which must be a five letter word as
well, for example 'xbxxx'. Then the system answers with the string '-*---'
as the 'b' in 'xbxxx' was correct and at the right place as well.

Had the second player entered 'xxxbx', the system had responded with
'---.-', as the 'b' is correct but not correctly positioned.

The second player must find out the original word.

Now I did not see how to do it as simply as posible, that was the problem.

Part of the confusion arose because it was thought to be a simple
problem, but instead it proved to be harder than it seemed. I have
experienced this while playing with it and loosing track of what was
going on inside my code. Thanks for posting your algorithm, without
that as a reference I probably would have had wrong code, thinking the
problem was easily solved. (I'm not completely sure I got it right
*this time* even)

<tangent>

Another matter is whether Python makes programming simpler for newbies
or if it only complicates things for them by introducing a lot of high
level language constructs. This is reminiscent of discussions about
whether computer processors with reduced instruction set (RISC) are
better than processors with more -and more complex- instructions.

The argument of the RISC philosophers is that higher functions could
be build using the few basic instructions and since higher functions
are subject to market fluctuations (sometimes they are used a lot and
sometimes not) it is preferable to only keep the basic set and to
build from that. This way of thinking is not limited to processor
developers but can also be observed in higher languages that pride
themselves in being flexible and fast (e.g. Lisp).

Of course the complex instruction set advocates remind us that we need
to cater to the needs of the programmers and that it is better to
provide batteries in order to prevent people making their own
sublanguage each time a commonly needed procedure has to be coded.
This way we get a coherent community and readable sourcecode.

The problem gets to the rockbottom of decision making if one is
presented with the need to teach newbies how to program. Of course
newbies are better off learning only a few basic functions and to
develop their own solutions as they go. It is even not uncommon for
teachers to have to face the raw uninterestedness that newbies tend to
express for complex instructions that they do not see the advantages
of. Sometimes later it is seen that it was good to learn all that
stuff, but more often than not it proves to be useless since history
has proven that higher functions are subject to popular demand anyway.

Now being a member of a community of programmers that all via one way
or another have come to understand different coding requirements and
seeing that all in all Python delivers a lot of the things one will
reach anyway after hard years of reinventing the wheel each time, the
question can be asked whether this knowledge can be found only by
having done it the hard way, and -only after that- recognizing the
elegance of the solutions offered, or if it is also possible to
transfer these insights directly to untrained programmers.

One problem that arises is that for newbies things make no difference
that for experienced Pythoneers are considered different. For example
are zip and enumerate really more difficult than using range and len
for iterating ? A newbie couldn't care less since they're both new.
The same goes for using dict.get versus dict. So it could well be
that *experienced* Pythoneers are the real newbies here.

At the eve of introducing new language features like the ternary
operator, iterator tools, metaclasses, backward iterators, generators
etcetera, this discussion becomes a bit heated sometimes, because
every new function that is accepted adds to the constant threat of
total redesign of all Python functions using only a few basic
instructions. Projects like Pypy that try to rebuild Python using the
higher level constructs only are like someone having found a last
crate of beer at a very late hour of a garden party. It's good for
some fun but everybody knows that the end is near.

There is just no way around rebuilding the basic structure from the
ground up sometimes and IMO it would be advisable to rebuild Pythons
functionality not using Pypy -although it's a nice project- but by
making very small basic building blocks -like bitfields- and instead
of having all functions inside one mega-dll (pythonxx.dll) it would be
better to have each function inside its own dll and to access these
dlls using Ctypes or something like it.

This way it would be possible to construct a Python from the ground
up, and instead of having a new release each time it would be possible
to just update a single dll. For an analogy of what I mean see the way
Cygwin distributes updates. It would create huge compatibility
problems for sure, but the gains would be even greater because new
higher order functions could be created on the fly, and newbies and
Pythoneers would be working side by side, with the newbies having the
advantage.

</tangent>

Ok, back to reality, here's some code I produced about your specific
problem, you can decide for yourself whether newbies would like it
more than the script you provided (I changed your script minimally in
order to be able to run it from my interpreter). It depends a lot on
dict.get returning "None" when an item is not found and on having the
value "0" in a dictionary being evaluated as "False" just as well as
"None" and on being able to specify a default value for dict.get that
it can return if there is no corresponding key in the dictionary. It
can handle strings of different size.

Anton

def vergleiche_woerter(wort,eingabe):
eing = list(eingabe)
wo = list(wort)
ergebnis=list('_'*len(wort))

# Suche zuerst nach Bullen
for i in range(len(eing)):
if eing == wo:
ergebnis = '*'
eing=wo = None

for i in range(len(eing)):
if eing == None: continue
if eing in wo:
j = wo.index(eing)
ergebnis = '.'
wo[j] = None

return "".join(ergebnis)

def hint(word,guess):
res,cnt = [],{}
for w,g in zip(word,guess):
if w == g:
res.append('*')
else:
res.append('_')
cnt[w] = cnt.get(w,0)+1
for i,g in enumerate(guess):
if cnt.get(g):
res = '.'
cnt[g] -= 1
return "".join(res)

def test():
a,b = 'aabbab','aaaaaa'
print a,b
print vergleiche_woerter(a,b)
print hint(a,b)

if __name__=='__main__':
test()