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

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

Re: I need algorithm for my task

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

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: I need algorithm for my task MRAB <python@mrabarnett.plus.com> - 2014-11-05 18:49 +0000
    Re: I need algorithm for my task Denis McMahon <denismfmcmahon@gmail.com> - 2014-11-06 03:14 +0000
    Re: I need algorithm for my task Denis McMahon <denismfmcmahon@gmail.com> - 2014-11-06 03:36 +0000
      Re: I need algorithm for my task Chris Angelico <rosuav@gmail.com> - 2014-11-06 14:47 +1100
      Re: I need algorithm for my task Denis McMahon <denismfmcmahon@gmail.com> - 2014-11-06 04:00 +0000
        Re: I need algorithm for my task Chris Angelico <rosuav@gmail.com> - 2014-11-06 15:14 +1100
          Re: I need algorithm for my task Denis McMahon <denismfmcmahon@gmail.com> - 2014-11-06 04:39 +0000
            Re: I need algorithm for my task Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2014-11-06 09:59 +0200
              Re: I need algorithm for my task wxjmfauth@gmail.com - 2014-11-06 00:57 -0800

#80289 — Re: I need algorithm for my task

On 2014-11-05 18:05, C@rlos wrote:
> I thing this work:
>
> stg='pythonpython'
> foundationline=stg[ 0:( stg [ 1: ].index( stg[ 0 ])+1 ) ]
>
It doesn't work for the final example or "barbaz".

[toc] | [next] | [standalone]

#80305

On Wed, 05 Nov 2014 18:49:01 +0000, MRAB wrote:

> On 2014-11-05 18:05, C@rlos wrote:
>> I thing this work:
>>
>> stg='pythonpython'
>> foundationline=stg[ 0:( stg [ 1: ].index( stg[ 0 ])+1 ) ]
>>
> It doesn't work for the final example or "barbaz".

I have two algorithms I've implemented.

Still not sure exactly which algorithm he wants though. The first one is 
as he describes, in that the word is only reported if it's repeated, else 
report the whole string.

The second algorithm reads up until the first letter is repeated, or 
reports the whole string if no repeat found.

I did see a third algorithm suggested, I should add that and see what 
happens.

OK, implemented the third algorithm (repeat first n chars of s int(n/len
(s))+1 times, truncate to len(s) and compare with s), I also added 
another test case, now my test cases are:

t = ["pythonpythonpyth", "DOLORIUMD", "HELLOLHELLO", "thewordword", 
"barbaz", "dibdibdobdibdibdob"]

and my output is:

$ ./words.py

python DOLORIUMD HELLOLHELLO thewordword barbaz dib

python DOLORIUM HELLOL thewordword bar dib

python DOLORIUM HELLOL thewordword barbaz dibdibdob

$

I wonder which of these three is actually the algorithm the OP wants.

-- 
Denis McMahon, denismfmcmahon@gmail.com

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

#80308

On Wed, 05 Nov 2014 18:49:01 +0000, MRAB wrote:

> It doesn't work for the final example or "barbaz".

Oh, and we really need a private "python homework answers" list where we 
can discuss the most pythonic solution we can think of for all these 
homework / coursework questions without showing the solutions to the 
students.

I'm quite proud of a 2 line solution to the third algorithm that I 
implemented, although it might be considered as somewhat obfuscated code 
by some. ;)

-- 
Denis McMahon, denismfmcmahon@gmail.com

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

#80309

On Thu, Nov 6, 2014 at 2:36 PM, Denis McMahon <denismfmcmahon@gmail.com> wrote:
> On Wed, 05 Nov 2014 18:49:01 +0000, MRAB wrote:
>
>> It doesn't work for the final example or "barbaz".
>
> Oh, and we really need a private "python homework answers" list where we
> can discuss the most pythonic solution we can think of for all these
> homework / coursework questions without showing the solutions to the
> students.
>
> I'm quite proud of a 2 line solution to the third algorithm that I
> implemented, although it might be considered as somewhat obfuscated code
> by some. ;)

Fun way to handle that: You get access only when you demonstrate that
you can write a (mostly-)working version yourself.

ChrisA

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

#80310

On Thu, 06 Nov 2014 03:36:40 +0000, Denis McMahon wrote:

> On Wed, 05 Nov 2014 18:49:01 +0000, MRAB wrote:
> 
>> It doesn't work for the final example or "barbaz".
> 
> Oh, and we really need a private "python homework answers" list where we
> can discuss the most pythonic solution we can think of for all these
> homework / coursework questions without showing the solutions to the
> students.

> I'm quite proud of a 2 line solution to the third algorithm that I
> implemented, although it might be considered as somewhat obfuscated code
> by some. ;)

Even prouder of the 1 liner!

In fact I'm going to post it, because I think any student who can walk 
his instructor through how my one-liner works deserves the marks. Of 
course, any student who presents this as a solution and is unable to walk 
their instructor through it should be failed for stupidity and plagiarism!

t = ["pythonpythonpyth", "DOLORIUMD", "HELLOLHELLO", "thewordword", 
"barbaz", "dibdibdobdibdibdob"]

def baseword(s):
    """find shortest sequence which repeats to generate s"""
    return s[0:["".join([s[0:x]for k in range(int(len(s)/x)+1)])[0:len
(s)]for x in range(1,len(s)+1)].index(s)+1]

for w in t:

    print(baseword(w))

p.s. I really want to be in the room when the instructor asks this 
student to come up in front of the class and explain how his solution 
works!

-- 
Denis McMahon, denismfmcmahon@gmail.com

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

#80313

On Thu, Nov 6, 2014 at 3:00 PM, Denis McMahon <denismfmcmahon@gmail.com> wrote:
> def baseword(s):
>     """find shortest sequence which repeats to generate s"""
>     return s[0:["".join([s[0:x]for k in range(int(len(s)/x)+1)])[0:len
> (s)]for x in range(1,len(s)+1)].index(s)+1]

That's hardly a PEP-8 compliant line, but I can help out a bit.

return s[0:[(s[0:x]*(len(s)//x+1))[0:len(s)]for x in
range(1,len(s)+1)].index(s)+1]

That's still 83 characters without indentation, but it's close now.

I love the algorithm. Took me a bit of analysis (and inspection of
partial results) to understand what your code's doing, but it's
stupidly elegant and elegantly stupid.

ChrisA

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

#80314

On Thu, 06 Nov 2014 15:14:05 +1100, Chris Angelico wrote:

> On Thu, Nov 6, 2014 at 3:00 PM, Denis McMahon <denismfmcmahon@gmail.com>
> wrote:
>> def baseword(s):
>>     """find shortest sequence which repeats to generate s"""
>>     return s[0:["".join([s[0:x]for k in range(int(len(s)/x)+1)])[0:len
>> (s)]for x in range(1,len(s)+1)].index(s)+1]
> 
> That's hardly a PEP-8 compliant line, but I can help out a bit.
> 
> return s[0:[(s[0:x]*(len(s)//x+1))[0:len(s)]for x in
> range(1,len(s)+1)].index(s)+1]
> 
> That's still 83 characters without indentation, but it's close now.

l = len
r = range

but technically then it's no longer a one liner.

> I love the algorithm. Took me a bit of analysis (and inspection of
> partial results) to understand what your code's doing, but it's stupidly
> elegant and elegantly stupid.

:)

Well yes, building that list is a stupid way to solve the problem, but I 
can't see another way to do it in one line. It's an implementation of my 
algorithm 3 (which I think you described) but working from the other end 
as it were.

-- 
Denis McMahon, denismfmcmahon@gmail.com

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

#80318

Denis McMahon writes:
> On Thu, 06 Nov 2014 15:14:05 +1100, Chris Angelico wrote:
> > On Thu, Nov 6, 2014 at 3:00 PM, Denis McMahon wrote:
> >> def baseword(s):
> >>     """find shortest sequence which repeats to generate s"""
> >>     return s[0:["".join([s[0:x]for k in range(int(len(s)/x)+1)])[0:len
> >> (s)]for x in range(1,len(s)+1)].index(s)+1]
> > 
> > That's hardly a PEP-8 compliant line, but I can help out a bit.
> > 
> > return s[0:[(s[0:x]*(len(s)//x+1))[0:len(s)]for x in
> > range(1,len(s)+1)].index(s)+1]
> > 
> > That's still 83 characters without indentation, but it's close now.
> 
> l = len
> r = range
> 
> but technically then it's no longer a one liner.
> 
> > I love the algorithm. Took me a bit of analysis (and inspection of
> > partial results) to understand what your code's doing, but it's stupidly
> > elegant and elegantly stupid.
> 
> :)
> 
> Well yes, building that list is a stupid way to solve the problem, but I 
> can't see another way to do it in one line. It's an implementation of my 
> algorithm 3 (which I think you described) but working from the other end 
> as it were.

70-character expression, even with the spaces:

 >>> x = 'tästäkötästäkötästä'
 >>> x[:min(k for k in range(len(x) + 1) if x == (x[:k] * len(x))[:len(x)])]
 'tästäkö'

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

#80321

Le jeudi 6 novembre 2014 08:59:22 UTC+1, Jussi Piitulainen a écrit :
> Denis McMahon writes:
> > On Thu, 06 Nov 2014 15:14:05 +1100, Chris Angelico wrote:
> > > On Thu, Nov 6, 2014 at 3:00 PM, Denis McMahon wrote:
> > >> def baseword(s):
> > >>     """find shortest sequence which repeats to generate s"""
> > >>     return s[0:["".join([s[0:x]for k in range(int(len(s)/x)+1)])[0:len
> > >> (s)]for x in range(1,len(s)+1)].index(s)+1]
> > > 
> > > That's hardly a PEP-8 compliant line, but I can help out a bit.
> > > 
> > > return s[0:[(s[0:x]*(len(s)//x+1))[0:len(s)]for x in
> > > range(1,len(s)+1)].index(s)+1]
> > > 
> > > That's still 83 characters without indentation, but it's close now.
> > 
> > l = len
> > r = range
> > 
> > but technically then it's no longer a one liner.
> > 
> > > I love the algorithm. Took me a bit of analysis (and inspection of
> > > partial results) to understand what your code's doing, but it's stupidly
> > > elegant and elegantly stupid.
> > 
> > :)
> > 
> > Well yes, building that list is a stupid way to solve the problem, but I 
> > can't see another way to do it in one line. It's an implementation of my 
> > algorithm 3 (which I think you described) but working from the other end 
> > as it were.
> 
> 70-character expression, even with the spaces:
> 
>  >>> x = 'tästäkötästäkötästä'
>  >>> x[:min(k for k in range(len(x) + 1) if x == (x[:k] * len(x))[:len(x)])]
>  'tästäkö'

Well. Congratulations.

[toc] | [prev] | [standalone]

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

csiph-web