Could this be solve with list comprehension?

Hello,

This is my solution:

41

How can I turn it into a list comprehension? (Perhaps it is for some reason not possible? / requires some knowledge I don’t have as a beginner…)
Any tips would be very welcome, as I seem to be stuck.

A comprehension will result in a list, not a value. We want the function to return a value. The method you have used is effective enough. It goes through the list once, then exits with the maximum.

6 Likes

Thank you very much for the prompt and clear reply.

2 Likes

For some silliness, that does employ a list comprehension…

a =  [95, 39, 76, 84, 19, 97, 26, 34]
while len(a) > 1:
    a = [x for x in a if x > a[0]]
print (a)    # [97]

This code is frought with flaws, which means it is unreliable. As a skeleton, it is useful, but only as a that. More logic is required.

a =  [19, 98, 95, 39, 76, 84, 19, 97, 26, 34, 98]
while len(a) > 1:
    a = [x for x in a if x > a[0]] or [a[0]]
print (a)    # [98]

Test the above. It may have less flaws, but I’m not yet convinced it is letter perfect. Remove 19 from the first position, and run again. That was the flaw of the first version, which now seems repaired. We need more test scenarios to be sure that actually addresses the issue. Logically it is sound, to my mind, but we’re not standing on solid ground, as it were.

As complexity is concerned, we would be iterating a list which is getting progressively shorter each time, but it would still mean re-iteration, which would be a factor of more than 1 on N values in the original list. Since it is a constant, Big O would remain, O(N), but we can see it would still take more steps than once through the list.


Addendum

a =  [19, 98, 95, 39, 76, 84, 19, 97, 26, 34, 98]
while len(a) > 1:
  u, v = a[0], a[1]    # symbolize as early as possible
  if v > u:
    a.pop(0)
  else:
    a.pop(1)
b =  [19, 98, 95, 39, 76, 84, 19, 97, 26, 34, 98]
while len(b) > 1:
  u, v = b[0], b[1]
  if v > u:
    b.remove(u)
  else:
    b.remove(v)
>>> a, b
([98], [98])
>>> 

Further Addendum

a =  [19, 98, 95, 39, 76, 84, 19, 97, 26, 34, 98]
while len(a) > 1:
  u, v = a[0], a[1]
  a.pop(0 if v > u else 1)

b =  [19, 98, 95, 39, 76, 84, 19, 97, 26, 34, 98]
while len(b) > 1:
  u, v = b[0], b[1]
  b.remove(u if v > u else v)

def max(sample):
  s = sample[:]
  while len(s) > 1:
    u, v = s[0], s[1]
    s.remove(u if v > u else v)
  return s[0]

Addendum: June 17 0400 UTC

This last function has everything we need, given we’ve called upon a built-in. It chomps down a list in N - 1 iterations. Safely an O(N) as complexity goes.

As we can see, there is no suggestion of equality. When two numbers are equal, the one is not greater than the other so is removed. One cannot think how to tinker with this code any further.

def min(sample):
  s = sample[:]
  while len(s) > 1:
    u, v = s[0], s[1]
    s.remove(u if v < u else v)
  return s[0]

But using no methods at all we get to the bottom very quickly…

def maximum(sample):
  s = sample[0]
  for x in sample:
    s = x if x > s else s
  return s
# maximum([19, 98, 95, 39, 76, 84, 19, 97, 26, 34, 98])
# 98
def minimum(sample):
  s = sample[0]
  for x in sample:
    s = x if x < s else s
  return s
# minimum([19, 98, 95, 39, 76, 84, 19, 97, 26, 34, 98])
# 19

Still O(N) but much faster, I would conclude. Time it with large lists and see how the two compare.

Bottom line, list comprehensions don’t really fit this type of problem. Comprehension and reduction are one way to see the picture. Brute force is the other. MIN and MAX seem to fit the brute force template.

2 Likes

This worked for me, but I feel like there might be a better solution. Probably could use a few more safeties.

def max_num(nums):
  maximum = [nums[i] for i in range(0,len(nums)) if (i == 0) or (nums[i-1] < nums[i])]
  return maximum[-1]

Update:

def max_num(nums):
  return [nums[i] for i in range(0,len(nums)) if (i == 0) or (nums[i-1] < nums[i])][-1]

Comparing adjacent numbers isn’t enough, consider [100,0,1]
1 is greater than 0, but it isn’t the maximum

1 Like

Yep, account for. My code adds the first regardless and starts comparing from there. It is only adding if greater than the previous.

Your code does not account for that. It will return 1 for that list

I’ll check again when I have time, but it definietly worked for the activity and it should account for that with the first side of the or statement. It will add the 100 from the list and continue from there.

It’ll compare num[1] num[2]
num[2] is larger and gets included
You’re looking at the wrong list, the one you meant to look at doesn’t exist yet, you’re still creating it.

You can have some tests which do pass without it being overall correct.
A broken clock tells the right time twice a day.

So first off my code mostly works. as I mentioned I could use a few more safeties and I didn’t thoroughly check out all conditions. My code does work in a majority of cases except when the highest number is the first in the list. It works in all other cases I’ thrown at it so far. It is also clear from your early responses you did not understand what I was doing until later. My code does work in a majority of cases and I might ponder how to fix the ONE case you found that it doesn’t work in. Good job on finding a bug on mostly working code. My clock is correct except twice a day it seems. I will look into a patch.

Revised code that fixes the first item bug.

def max_num(nums):
  maximum = [nums[i] for i in range(0,len(nums)) if (nums[i-1] < nums[i])]
  return maximum[-1]

Update:

def max_num(nums):
  return [nums[i] for i in range(0,len(nums)) if (nums[i-1] < nums[i])][-1]

If you create lists with values picked between 1 and 1000 with a random length between 2 and 100 then your code will produce the wrong answer for most of those.

Another example where it returns 1:
[100,100,100,100,100,100,100,100,0,1]

The problem isn’t with the first element. The problem is that your code only considers the last two values, if the maximum is not found among the last two values, then the wrong result is produced.

The updated version still answers with 1

how about?
def max_num(nums):
nums.sort()
return nums[-1]

It’s important to do as little to disrupt our data structure as possible, namely preserve the original order. Once we sort we can never be sure to restore it.

There is a way to use sorting without affecting the original, sort a copy.

nums_sort = sorted(nums)
return nums_sort[-1]

The main problem though is that sorting is of higher abstraction level than max, should probably implement max in terms of things that are simpler than itself rather than something that does the whole task and more.

So for example part of max is iteration. PART - it’s a subproblem, doesn’t eclipse it.

An appropriate iteration pattern to use is reduce (combine values into an accumulated value using a specified action between the accumulator and each value to be combined into it)

the combining action would be max for two values, which is simpler than max for many values, again, a small part

def max_of_2(a, b):
    if a >= b:
        return a
    return b

def max_num(nums):
    return reduce(max_of_2, nums)

Don’t necessarily need to use function statements for it, since it’s combining functions, it could as well be an expression:

max_num = partial(reduce, lambda a, b: a if a >= b else b)
1 Like

Hi there! I am learning loop at the moment and having trouble with understanding the code below:
def max_num(nums):
maximum=nums[0]
for number in nums:
if number>maximum:
maximum=number

Could someone help me to understand how this loop works to find maximum number? Thank you very much.

return maxium

This initializes the variable to the first value in the list.

Iterate over the list

Replace the value with current number. Maximum is growing in value.

At the end of iteration, maximum will be the greatest value found in the list. There may be duplicates, but this method won’t be able to tell us that.

1 Like

I think there may be a problem with my console. My code returns the correct answer (75), but when it does I get the following error:

max_num([-50, -20]) should have returned -20, and it returned 0

When the nums list is:

max_num([50, -10, 0, 75, 20]

If I return the wrong answer, I get the correct error with the correct list:

max_num([50, -10, 0, 75, 20]) should have returned 75, and it returned 50

Again, just to reiterate, if I return the right answer the console changes the list and says I’ve returned the wrong answer.

EDIT: I just viewed the Solution and it was EXACTLY the same as my own code, which gave the weird error with the different list.

That would suggest that max was initialized to 0 rather than nums[0].

Expect the SCT to run multiple tests using different lists.