Is there a better way than a while loop to perform this function?-CodePudding

I was attempting some python exercises and I hit the 5s timeout on one of the tests. The function is pre-populated with the parameters and I am tasked with writing code that is fast enough to run within the max timeframe of 5s.

There are N dishes in a row on a kaiten belt, with the ith dish being of type Di. Some dishes may be of the same type as one another. The N dishes will arrive in front of you, one after another in order, and for each one you'll eat it as long as it isn't the same type as any of the previous K dishes you've eaten. You eat very fast, so you can consume a dish before the next one gets to you. Any dishes you choose not to eat as they pass will be eaten by others. Determine how many dishes you'll end up eating.

Issue

The code "works" but is not fast enough.

Code

The idea here is to add the D[i] entry if it is not in the pastDishes list (which can be of size K).

from typing import List
# Write any import statements here

def getMaximumEatenDishCount(N: int, D: List[int], K: int) -> int:
  # Write your code here
  numDishes=0
  pastDishes=[]
  i=0
  while (i<N):
    if(D[i] not in pastDishes):
      numDishes =1
      pastDishes.append(D[i])
      if len(pastDishes)>K:
        pastDishes.pop(0)
    i =1
  return numDishes

Is there a more effective way?

CodePudding user response：

You can use sets in combination with the method you have.

from collections import deque
def getMaximumEatenDishCount(N: int, D: List[int], K: int) -> int:
  uniqueDishSet = deque()
  eatenCount = 0

  for dish in D:
     if dish in uniqueDishSet:continue
     uniqueDishSet.append(dish)
     eatenCount  =1
     if len(uniqueDishSet) > K:
        uniqueDishSet.popleft()
   return eatenCount

You may also be able to just use a list comprehension and slice access insteead like so:

TestList = [1,2,3,4,3,2,1,1]
# 1,2,3,4,3,2,1,1, I would eat 1,2,3,4,2,1

def getMaximumEatenDishCount(D:list, K: int) -> int:
    uniqueDishesEaten = [dish for index, dish in enumerate(D) 
                            if dish not in D[index-K:index]]

    return len(uniqueDishesEaten)

print(getMaximumEatenDishCount(TestList, 2))
# OUTPUT:    [1, 2, 3, 4, 2, 1]

Which works by using enumerate to get a listitem and its index and checking if the dish is in the slice of D from index-K to K. It creates a list of all dishes eaten and you can just get its length

Edit:#20064

You dont actuially need a list comprehension, you should probably do it like so:

def getMaximumEatenDishCount2(D:list, K: int) -> int:
    dishesEaten = 0
    for dishInd in range(len(D)):
        if D[dishInd] not in D[dishInd-K:dishInd]:dishesEaten =1
    return (dishesEaten)

Too Many edits Later:

def getMaximumEatenDishCount2(D:list, K: int) -> int:
    dishesEaten = 0
    for dishInd in range(len(D)):
        KIndex = dishInd-K if dishInd >= K else 0
        if D[dishInd] not in D[KIndex :dishInd]:dishesEaten =1
    return (dishesEaten)

or you can do this:

 getMaximumEatenDishCount2(D:list, K: int) -> int:
    dishesEaten = 0
    KIndex = 0
    for dishInd in range(len(D)):
        if D[dishInd] not in D[KIndex:dishInd]:
            if dishInd >= K: KIndex =1
            dishesEaten =1
    return (dishesEaten)

This works by just using range to get a counter and then using that counter as in index into your list to do comparisons and slice notation.

CodePudding user response：

Can we use an appropriate data structure? If so:

Data structures

Seems like an ordered set which you have to shrink to a capacity restriction of K.

To meet that, if exceeds (len(ordered_set) > K) we have to remove the first n items where n = len(ordered_set) - K. Ideally the removal will perform in O(1).

However since removal on a set is in unordered fashion. We first transform it to a list. A list containing unique elements in the order of appearance in their original sequence.

From that ordered list we can then remove the first n elements.

For example: the function lru returns the least-recently-used items for a sequence seq limited by capacity-limit k.

def lru(seq, k):
    return list(set(seq))[:k]

To obtain the length we can simply call len() on that LRU return value:

maximumEatenDishCount = len(lru(seq, k))