
# https://leetcode.com/discuss/interview-question/762546/
# Amazon Fresh is running a promotion in which customers receive prizes for purchasing 
# a secret combination of fruits. The combination will change each day, and the team 
# running the promotion wants to use a code list to make it easy to change the combination. 
# The code list contains groups of fruits. Both the order of the groups within the code 
# list and the order of the fruits within the groups matter. However, between the groups 
# of fruits, any number, and type of fruit is allowable. The term "anything" is used to 
# allow for any type of fruit to appear in that location within the group.

# Consider the following secret code list: [[apple, apple], [banana, anything, banana]]
# Based on the above secret code list, a customer who made either of the following 
# purchases would win the prize:
# orange, apple, apple, banana, orange, banana
# apple, apple, orange, orange, banana, apple, banana, banana
# Write an algorithm to output 1 if the customer is a winner else output 0.

# Input
# The input to the function/method consists of two arguments:
# codeList, a list of lists of strings representing the order and grouping of specific 
# fruits that must be purchased in order to win the prize for the day.
# shoppingCart, a list of strings representing the order in which a customer purchases fruit.

# Output
# Return an integer 1 if the customer is a winner else return 0.

# Note
# 'anything' in the codeList represents that any fruit can be ordered in place of 'anything' 
# in the group. 'anything' has to be something, it cannot be "nothing."
# 'anything' must represent one and only one fruit.
# If secret code list is empty then it is assumed that the customer is a winner.

# Example 1:
# Input: 
# codeList = [[apple, apple], [banana, anything, banana]] 
# shoppingCart = [orange, apple, apple, banana, orange, banana]
# Output: 1
# Explanation:
# codeList contains two groups - [apple, apple] and [banana, anything, banana].
# The second group contains 'anything' so any fruit can be ordered in place of 'anything' 
# in the shoppingCart. The customer is a winner as the customer has added fruits in the 
# order of fruits in the groups and the order of groups in the codeList is also maintained 
# in the shoppingCart.

# Example 2:
# Input: codeList = [[apple, apple], [banana, anything, banana]]
# shoppingCart = [banana, orange, banana, apple, apple]
# Output: 0
# Explanation:
# The customer is not a winner as the customer has added the fruits in order of groups 
# but group [banana, orange, banana] is not following the group [apple, apple] in the codeList.

# Example 3:
# Input: 
# codeList = [[apple, apple], [banana, anything, banana]] 
# shoppingCart = [apple, banana, apple, banana, orange, banana]
# Output: 0
# Explanation:
# The customer is not a winner as the customer has added the fruits in an order which 
# is not following the order of fruit names in the first group.

# Example 4:
# Input: 
# codeList = [[apple, apple], [apple, apple, banana]] 
# shoppingCart = [apple, apple, apple, banana]
# Output: 0
# Explanation:
# The customer is not a winner as the first 2 fruits form group 1, all three fruits 
# would form group 2, but can't because it would contain all fruits of group 1.
from typing import List
debugPrints = False
class Solution:
    def checkForWinner(self, codeList:List[List], shoppingCart:List)->int:
        winnerResult = 0
        
        # if list (or list of list) is empty, then already a winner
        if not codeList or len(codeList) == 0 or len(codeList) == 1 and len(codeList[0]) == 0:
            winnerResult = 1
            return winnerResult
        if not shoppingCart or len(shoppingCart) == 0:
            winnerResult = 0
            return winnerResult

        # if debugPrints:
        print("codeList = %s" % codeList)
        print("shopping = %s" % shoppingCart)
        
        indexStart = 0
        foundAllItems = True
        for code in codeList:
            firstItem = True
            startingItemIndex = -1
            previousItemIndex = -1
            if debugPrints:
                print("starting search of code = %s" % code)
            if foundAllItems:
                # find first item in specific codeList
                for i in range(len(code)):
                    if (indexStart >= len(shoppingCart)):
                        if debugPrints:
                            print("indexStart (%d) > len(shoppingCart) (%d)" % (indexStart, len(shoppingCart)))
                            foundAllItems = False
                            break
                    if code[i] in shoppingCart:
                        try:
                            itemIndex = shoppingCart.index(code[i], indexStart)
                        except:
                            foundAllItems = False
                            break
                        if debugPrints:
                            print("found %s @ %d" % (code[i], itemIndex))
                        if firstItem:
                            if debugPrints:
                                print("first item recorded")
                            startingItemIndex = itemIndex
                            previousItemIndex = itemIndex
                            indexStart = itemIndex + 1
                            firstItem = False
                        else:
                            if (itemIndex - previousItemIndex) == 1:
                                if debugPrints:
                                    print("+1 index")
                                startingItemIndex += 1
                                indexStart += 1
                            else:
                                if debugPrints:
                                    print(">+1 index... starting search over :(")
                                i = 0
                                indexStart = startingItemIndex + 1
                                firstItem = True
                    elif code[i] == 'anything':
                        if debugPrints:
                            print("found anything")
                        if firstItem:
                            if debugPrints:
                                print("first item recorded")
                            startingItemIndex = indexStart
                            previousItemIndex = indexStart
                            indexStart = indexStart + 1
                            firstItem = False
                        else:    
                            previousItemIndex += 1
                            indexStart += 1      
                    else:
                        if debugPrints:
                            print("code[%d] = %s not found" % (i, code[i]))
                        winnerResult = 0
                        return winnerResult
                    
            else:
                winnerResult = 0
                return winnerResult

        if foundAllItems:
            winnerResult = 1

        return winnerResult
        

# ''' Helper Test Functions '''
s = Solution()

winner = s.checkForWinner([], [])
print("Winner0.1 = %d\n" % winner)
winner = s.checkForWinner([[]], [])
print("Winner0.2 = %d\n" % winner)
winner = s.checkForWinner([["round"]], [])
print("Winner0.3 = %d\n" % winner)
winner = s.checkForWinner([["round"]], None)
print("Winner0.4 = %d\n" % winner)

codeList = [["apple", "apple"], ["banana", "anything", "banana"]]
shoppingCart = ["orange", "apple", "apple", "banana", "orange", "banana"]
winner = s.checkForWinner(codeList, shoppingCart)
print("Winner0.9 = %d\n" % winner)


# test cases
codeList = [["apple", "apple"], ["banana", "anything", "banana"]]
shoppingCart = ["orange", "apple", "apple", "banana", "orange", "banana"]
winner = s.checkForWinner(codeList, shoppingCart)
print("Winner1 = %d\n" % winner)

codeList = [["apple", "apple"], ["banana", "anything", "banana"]]
shoppingCart = ["banana", "orange", "banana", "apple", "apple"]
winner = s.checkForWinner(codeList, shoppingCart)
print("Winner2 = %d\n" % winner)

codeList = [["apple", "apple"], ["banana", "anything", "banana"]]
shoppingCart = ["apple", "banana", "apple", "banana", "orange", "banana"]
winner = s.checkForWinner(codeList, shoppingCart)
print("Winner3 = %d\n" % winner)

codeList = [["apple", "apple"], ["apple", "apple", "banana"]]
shoppingCart = ["apple", "apple", "apple", "banana"]
winner = s.checkForWinner(codeList, shoppingCart)
print("Winner4 = %d\n" % winner)

codeList = [["apple", "apple"], ["banana", "anything", "banana"]]
shoppingCart = ["orange", "apple", "apple", "banana", "orange", "banana"]
winner = s.checkForWinner(codeList, shoppingCart)
print("Winner5 = %d\n" % winner)

codeList = [["apple", "apple"], ["banana", "anything", "banana"]]
shoppingCart = ["apple", "apple", "orange", "orange", "banana", "apple", "banana", "banana"]
winner = s.checkForWinner(codeList, shoppingCart)
print("Winner6 = %d\n" % winner)

codeList = [["anything", "apple"], ["banana", "anything", "banana"]]
shoppingCart = ["orange", "grapes", "apple", "orange", "orange", "banana", "apple", "banana", "banana"]
winner = s.checkForWinner(codeList, shoppingCart)
print("Winner7 = %d\n" % winner)

codeList = [["apple", "orange"], ["orange", "banana", "orange"]]
shoppingCart = ["apple", "orange", "banana", "orange", "orange", "banana", "orange", "grape"]
winner = s.checkForWinner(codeList, shoppingCart)
print("Winner8 = %d\n" % winner)

codeList = [["anything", "anything", "anything", "apple"], ["banana", "anything", "banana"]]
shoppingCart = ["orange", "apple", "banana", "orange", "apple", "orange", "orange", "banana", "apple", "banana"]
winner = s.checkForWinner(codeList, shoppingCart)
print("Winner9 = %d\n" % winner)
