This is a solution to problem 3 that should not be used. It’s horrible, bad practise, and generally incomprehensible. The general problem is to return the (first in the case of a tie) longest substring from a lowercase string s where all the characters are in alphabetical order.
I won’t share by submitted solution, but there’s a secondary challenge in the discussion, to achieve this in the least number of lines, most solutions ranging from 10 to 20 lines. I think mine was 11, and very readable.
I’m only sharing this version of the solution because it is so far removed from an acceptable answer as you can get, so hopefully this does not breach the honor code.
However, this is a single line solution to the problem. Note it assumes the string s is declared outside the solution as per the submission requirements:
1
|
print('Longest substring in alphabetical order is: '+next(filter(lambda x: len(x) == max(map(len,list(filter(lambda l: all(l[i] <= l[i+1] for i in range(len(l)-1)), [item for sublist in [[s[x:y+1] for x in range(len(s)) if y>=x] for y in range(len(s))] for item in sublist])))),list(filter(lambda l: all(l[i] <= l[i+1] for i in range(len(l)-1)), [item for sublist in [[s[x:y+1] for x in range(len(s)) if y>=x] for y in range(len(s))] for item in sublist])))))
|
The general structure is as follows:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
s = 'pngwgjjkemywjogkkikymn'
# function to return bool if the string is in alphabetical order
is_sorted = lambda l: all(l[i] <= l[i+1] for i in range(len(l)-1))
# function to the list of lists into a single list
flatten = lambda l: [item for sublist in l for item in sublist]
# returns a list of lists containing the various possible substrings
substrings = [[s[x:y+1] for x in range(len(s)) if y>=x] for y in range(len(s))]
#flatten the list and filter on only those that are sorted
solutions = list(filter(is_sorted, flatten(substrings)))
# find the max length of all the lists, and filter the solutions down to only
# those of max length, and select the first
result = next(filter(lambda x: len(x) == max(map(len,solutions)),solutions))
|
It’s then just a case of substituting the expressions to make this a single line solution. It is a very innefficient solution and difficult to read, and is not recommended at all!
Okay, the TA tells me there’s a 75 char one line solution! Can’t find it yet, but another more efficient and smaller variation of mine is…
1
2
3
4
5
6
|
s = 'pngwgjjkemywjogkkikymn'
breaks = ([0]+[i for i,c in enumerate(s) if c<s[i-1]]+[len(s)]) # These are characters that break the streak
substrings = [s[breaks[i]:b] for i,b in enumerate(breaks[1:])] # make the substrings
result = sorted(substrings, key=len, reverse=True)[0] # sort longest first and get first
print('Longest substring in alphabetical order is: '+result)
|
which reduces to 233 chars, so about half the size, but still a long way from 75!
1
|
print('Longest substring in alphabetical order is: '+sorted([s[([0]+[i for i,c in enumerate(s) if c<s[i-1]]+[len(s)])[i]:b] for i,b in enumerate(([0]+[i for i,c in enumerate(s) if c<s[i-1]]+[len(s)])[1:])], key=len, reverse=True)[0])
|
another attempt, but this one needs Python 3.8 as it uses the wallrus (assignment) operator :=. This approach looks to generate a list of tuples containing the start and end index of the substrings.
1
2
3
4
5
|
def test(s):
breaks = list((p:=[0]+[i for i,c in enumerate(s) if c<s[i-1]]+[len(s)]) and zip(p,p[1:]))
substrings = [s[x:y] for x,y in breaks] # make the substrings
result = sorted(substrings, key=len, reverse=True)[0]
return('Longest substring in alphabetical order is: '+result)
|
which simplifies(?) to… (note the way you have to use the assignment in an and statement to calculate the value and not as a direct replacement for the variable in the list comprehension - that’s not supported)
1
2
|
def test(s): # Best so far
return('Longest substring in alphabetical order is: '+ (((b:=(p:=[0]+[i for i,c in enumerate(s) if c<s[i-1]]+[len(s)]) and zip(p,p[1:])) and sorted([s[x:y] for x,y in b], key=len, reverse=1)[0])))
|
This is never going to reduce to 75 chars, so time for a complete re-think of the approach.
Step 1 - generate a list of all substrings:
a = [s[x:y] for x in range(len(s)) for y in range(len(s)+1)]
Step 2 - only include those that are ‘sorted’; Various attempts at getting this, the third was is the shortest.
1
2
3
|
a = [s[x:y] for x in range(len(s)+1) for y in range(len(s)+1) if ''.join(sorted(s[x:y]))==s[x:y]]
a = [s[x:y] for x in range(len(s)+1) for y in range(len(s)+1) if sorted(s[x:y])==list(s[x:y])]
a = [s[x:y] for x in range(len(s)) for y in range(len(s)+1) if sorted(s[x:y])==[*s[x:y]]]
|
Step 3 - get the first largest element from that list. Made some progress is making this more succinct too.
1
2
|
result = sorted(substrings, key=len, reverse=True)[0] # Original
result = max(a,key=len) # Better
|
Put it all together:
1
2
|
a = [s[x:y] for x in range(len(s)) for y in range(len(s)+1) if sorted(s[x:y])==[*s[x:y]]]
r = max(a,key=len) # sort longest first and get first
|
and finally to one line:
1
|
print('Longest substring in alphabetical order is: '+max((s[x:y] for x in range(len(s)) for y in range(len(s)+1) if sorted(s[x:y])==[*s[x:y]]),key=len))
|
You can still make it shorter if you use the assignment operator := to avoid the repeat of s[x:y]
1
|
print('Longest substring in alphabetical order is: '+ max([z for x in range(len(s)) for y in range(len(s)+1) if sorted(z:=s[x:y])==[*z]],key=len))
|
and you can make it shorter still, one line but two expressions if you use some substition bringing it down to 137 chars (83 if we exclude the print):
1
2
|
r=range(len(s)+1);print('Longest substring in alphabetical order is: '+max([z for x in r for y in r if sorted(z:=s[x:y])==[*z]],key=len))
python
|