Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #80259 > unrolled thread

I need algorithm for my task

Back to article view | Back to comp.lang.python

Contents

  I need algorithm for my task lordvital21@gmail.com - 2014-11-05 03:58 -0800
    Re: I need algorithm for my task Chris Angelico <rosuav@gmail.com> - 2014-11-05 23:29 +1100
      Re: I need algorithm for my task Darren Chen <ccylily1314@gmail.com> - 2014-11-06 17:42 -0800
    Re: I need algorithm for my task Peter Otten <__peter__@web.de> - 2014-11-05 13:36 +0100
    Re: I need algorithm for my task Denis McMahon <denismfmcmahon@gmail.com> - 2014-11-05 15:19 +0000
    Re: I need algorithm for my task MRAB <python@mrabarnett.plus.com> - 2014-11-05 17:53 +0000
    Re: I need algorithm for my task wxjmfauth@gmail.com - 2014-11-05 11:07 -0800
      Re: I need algorithm for my task wxjmfauth@gmail.com - 2014-11-05 11:29 -0800
        Re: I need algorithm for my task wxjmfauth@gmail.com - 2014-11-05 22:31 -0800

#80259 — I need algorithm for my task

I have line 'pythonpythonpyth'. How do I know which word is the foundation line?.
Other examples:
"pythonpythonpyth" is python
"DOLORIUMD" is DOLORIUM
"HELLOLHELLO" is HELLOL
"thewordword" is thewordword

I need to know whether the word in the text is repeated and get it. This will be the key.

[toc] | [next] | [standalone]

#80266

On Wed, Nov 5, 2014 at 10:58 PM,  <lordvital21@gmail.com> wrote:
> I have line 'pythonpythonpyth'. How do I know which word is the foundation line?.
> Other examples:
> "pythonpythonpyth" is python
> "DOLORIUMD" is DOLORIUM
> "HELLOLHELLO" is HELLOL
> "thewordword" is thewordword
>
> I need to know whether the word in the text is repeated and get it. This will be the key.

This sounds like it's probably homework, so I won't actually give you
the code, just a starting hint.

Python lets you slice a string to get back a substring. Start with a
really simple algorithm like "see if the first N letters are also the
next N letters and so on until you pass the end of the string", then
word that up into Python code. Later on, you can look into making it
less naive, but start simple and work up from there.

ChrisA

[toc] | [prev] | [next] | [standalone]

#80344

Probably homework, you are a  good man !

[toc] | [prev] | [next] | [standalone]

#80268

lordvital21@gmail.com wrote:

> I have line 'pythonpythonpyth'. How do I know which word is the foundation
> line?. Other examples:
> "pythonpythonpyth" is python
> "DOLORIUMD" is DOLORIUM
> "HELLOLHELLO" is HELLOL
> "thewordword" is thewordword
> 
> I need to know whether the word in the text is repeated and get it. This
> will be the key.

A simple approach that might work (I didn't implement it to verify):

Look for other occurences of the first letter. If there are none you have 
the "foundation", if there are any, split the line before them and check if 
the rest of the line can be constructed as a (possibly truncated) repetition 
of the beginning. For

fifafofifaf

you'd have to check

fi fafofifaf --> false
fifa fofifaf --> false
fifafo fifaf --> true

so we don't care about

fifafofi faf
fifafofifa f

[toc] | [prev] | [next] | [standalone]

#80272

On Wed, 05 Nov 2014 03:58:33 -0800, lordvital21 wrote:

> I have line 'pythonpythonpyth'. How do I know which word is the
> foundation line?.
> Other examples:
> "pythonpythonpyth" is python "DOLORIUMD" is DOLORIUM "HELLOLHELLO" is
> HELLOL "thewordword" is thewordword
> 
> I need to know whether the word in the text is repeated and get it. This
> will be the key.

Well, the way you describe it:

So first you want to check if the first letter is also the second letter
Then you want to check if the first 2 letters are also the 3rd and 4th
Then you want to check if the first 3 letters are also the 4th-6th
Then you want to check if the first 4 letters are also the 5th-8th

So generally you want to check if the first n letters are also the second 
n letters, increasing n by 1 at a time until you reach your terminating 
condition.

So what is your terminating condition? I can see two possibilities. You 
run out of letters in the second section, or you find a match.

Here are a few more hints to help get you started:

A string is a list of characters.
A list can be sliced.
You can measure the length of a list.
You can compare the lengths of two lists.
You can compare two lists.
You can get the length of a string.
The maximum length of a repeated word in a string can not be more than 
half the length of the string.

However, the examples you give do not match the way you describe it. The 
examples you give assume the first word ends when the letter that started 
it is found again.

-- 
Denis McMahon, denismfmcmahon@gmail.com

[toc] | [prev] | [next] | [standalone]

#80284

On 2014-11-05 11:58, lordvital21@gmail.com wrote:
> I have line 'pythonpythonpyth'. How do I know which word is the foundation line?.
> Other examples:
> "pythonpythonpyth" is python
> "DOLORIUMD" is DOLORIUM
> "HELLOLHELLO" is HELLOL
> "thewordword" is thewordword
>
> I need to know whether the word in the text is repeated and get it. This will be the key.
>
Consider the first example.

If the foundation is the first 1 character 'p' and you repeat it enough
times you'll get 'pppppppppppppppp'.

This is the same length as the line.

Does it match the line? No.

OK.

If the foundation is the first 2 characters 'py' and you repeat it
enough times you'll get 'pypypypypypypypy'.

This is the same length as the line.

Does it match the line? No.

OK.

If the foundation is the first 3 characters 'py' and you repeat it
enough times you'll get 'pytpytpytpytpytpyt'.

This is longer than as the line, so truncate it to 'pytpytpytpytpytpy'.

Does it match the line? No.

OK.

Continue in this vein until you'll get a match. (The foundation might
in fact be the entire line.)

[toc] | [prev] | [next] | [standalone]

#80290

Le mercredi 5 novembre 2014 12:58:44 UTC+1, lordv...@gmail.com a écrit :
> I have line 'pythonpythonpyth'. How do I know which word is the foundation line?.
> Other examples:
> "pythonpythonpyth" is python
> "DOLORIUMD" is DOLORIUM
> "HELLOLHELLO" is HELLOL
> "thewordword" is thewordword
> 
> I need to know whether the word in the text is repeated and get it. This will be the key.

From your examples: impossible, unsolvable. [*]

[*] unless using an "external" list of words.

[toc] | [prev] | [next] | [standalone]

#80291

Le mercredi 5 novembre 2014 20:08:03 UTC+1, wxjm...@gmail.com a écrit :
> Le mercredi 5 novembre 2014 12:58:44 UTC+1, lordv...@gmail.com a écrit :
> > I have line 'pythonpythonpyth'. How do I know which word is the foundation line?.
> > Other examples:
> > "pythonpythonpyth" is python
> > "DOLORIUMD" is DOLORIUM
> > "HELLOLHELLO" is HELLOL
> > "thewordword" is thewordword
> > 
> > I need to know whether the word in the text is repeated and get it. This will be the key.
> 
> From your examples: impossible, unsolvable. [*]
> 
> [*] unless using an "external" list of words.

Mea culpa. Sorry, I was wrong. (I "missread" one example).

[toc] | [prev] | [next] | [standalone]

#80316

Le mercredi 5 novembre 2014 20:29:34 UTC+1, wxjm...@gmail.com a écrit :
> Le mercredi 5 novembre 2014 20:08:03 UTC+1, wxjm...@gmail.com a écrit :
> > Le mercredi 5 novembre 2014 12:58:44 UTC+1, lordv...@gmail.com a écrit :
> > > I have line 'pythonpythonpyth'. How do I know which word is the foundation line?.
> > > Other examples:
> > > "pythonpythonpyth" is python
> > > "DOLORIUMD" is DOLORIUM
> > > "HELLOLHELLO" is HELLOL
> > > "thewordword" is thewordword
> > > 
> > > I need to know whether the word in the text is repeated and get it. This will be the key.
> > 
> > From your examples: impossible, unsolvable. [*]
> > 
> > [*] unless using an "external" list of words.
> 
> Mea culpa. Sorry, I was wrong. (I "missread" one example).

2nd erratum (?)
Thinking again. There is in my mind no solution.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web