why different result between max(list,key) and max(set(list), key) in python 3?

Question

I am learning the CS212 in Udacity and have the following code.

---

User Instructions: Write a function best_wild_hand(hand) that takes as input a 7-card hand and returns the best 5 card hand. In this problem, it is possible for a hand to include jokers. Jokers will be treated as 'wild cards' which can take any rank or suit of the same color. The black joker, '?B', can be used as any spade or club and the red joker, '?R', can be used as any heart or diamond.

---

here is the code:

import itertools

def best_wild_hand(hand):
    "Try all values for jokers in all 5-card selections."


    if '?B' not in hand and '?R' not in hand:
        return max(itertools.combinations(hand,5), key=hand_rank)


    black = [ i+j for i in list('23456789TJQKA') for j in ['S','C']]
    red = [ i+j for i in list('23456789TJQKA') for j in ['H','D']]

    cards = []
    hands = []


    if '?B' in hand and '?R' not in hand:
        for item in black:
            temp = hand[:]
            temp[temp.index('?B')] = item
            cards.append(temp) 
    elif '?R' in hand and '?B' not in hand:
        for item in red:
            temp = hand[:]
            temp[temp.index('?R')] = item
            cards.append(temp)
    else:
        for i in black:
            for j in red:
                temp = hand[:]
                temp[temp.index('?B')] = i
                temp[temp.index('?R')] = j
                cards.append(temp)
    #cards = set(cards)

    for card in cards:
        hands  += itertools.combinations(card, 5)

    #print(len(hands))
    #hands = set(hands)
    #print(len(hands))
    return max(hands, key=hand_rank)


def test_best_wild_hand():
    assert (sorted(best_wild_hand("6C 7C 8C 9C TC 5C ?B".split()))
            == ['7C', '8C', '9C', 'JC', 'TC'])
    assert (sorted(best_wild_hand("TD TC 5H 5C 7C ?R ?B".split()))
            == ['7C', 'TC', 'TD', 'TH', 'TS'])
    assert (sorted(best_wild_hand("JD TC TH 7C 7D 7S 7H".split()))
            == ['7C', '7D', '7H', '7S', 'JD'])
    return 'test_best_wild_hand passes'

# ------------------
# Provided Functions
# 
# You may want to use some of the functions which
# you have already defined in the unit to write 
# your best_hand function.

def hand_rank(hand):
    "Return a value indicating the ranking of a hand."
    ranks = card_ranks(hand) 
    if straight(ranks) and flush(hand):
        return (8, max(ranks))
    elif kind(4, ranks):
        return (7, kind(4, ranks), kind(1, ranks))
    elif kind(3, ranks) and kind(2, ranks):
        return (6, kind(3, ranks), kind(2, ranks))
    elif flush(hand):
        return (5, ranks)
    elif straight(ranks):
        return (4, max(ranks))
    elif kind(3, ranks):
        return (3, kind(3, ranks), ranks)
    elif two_pair(ranks):
        return (2, two_pair(ranks), ranks)
    elif kind(2, ranks):
        return (1, kind(2, ranks), ranks)
    else:
        return (0, ranks)

def card_ranks(hand):
    "Return a list of the ranks, sorted with higher first."
    ranks = ['--23456789TJQKA'.index(r) for r, s in hand]
    ranks.sort(reverse = True)
    return [5, 4, 3, 2, 1] if (ranks == [14, 5, 4, 3, 2]) else ranks

def flush(hand):
    "Return True if all the cards have the same suit."
    suits = [s for r,s in hand]
    return len(set(suits)) == 1

def straight(ranks):
    """Return True if the ordered 
    ranks form a 5-card straight."""
    return (max(ranks)-min(ranks) == 4) and len(set(ranks)) == 5

def kind(n, ranks):
    """Return the first rank that this hand has 
    exactly n-of-a-kind of. Return None if there 
    is no n-of-a-kind in the hand."""
    for r in ranks:
        if ranks.count(r) == n: return r
    return None

def two_pair(ranks):
    """If there are two pair here, return the two 
    ranks of the two pairs, else None."""
    pair = kind(2, ranks)
    lowpair = kind(2, list(reversed(ranks)))
    if pair and lowpair != pair:
        return (pair, lowpair)
    else:
        return None 


print(test_best_wild_hand())

---

Above code just works fine. However, when I change the last line in def best_wild_hand(hand) as

 return max(set(hands), key=hand_rank)

The result is wrong. Why I conver the list to set and the max() does not work? Thanks

Answer 1

TLDR

The lack of ordering in set makes the return of max(set(hands)) unstable, sometimes returning wrong answer, sometimes correct.

After a lot of digging, I think I have found the source of the bug. To begin with, your logic was correct: by calling set(), you removed duplicates, so the result should be the same with or without duplicates.

In the original code, if the second test case is commented out, using set(hands) would pass the other cases (at least in my environment). Thus, the problem might be with the second test case.

If you isolate the second test case out, and run the program with set(hands) for, say 20 times, the tricky thing happens: most of the time the test case fails, but in a few times it actually passes!

This is crazy! The same code gives different results. The correct output for the second test case is ('TD', 'TC', '7C', 'TH', 'TS'). But the max function would also return at least two other outputs ('TD', 'TC', '7C', 'TH', 'TC') and ('TD', 'TC', '7C', 'TD', 'TS').

If you inspect the return value of hand_rank() when called on all these three hands, the results are the same (7, 10, 7). In other words, these three hands are identical in their ranking. Thus, which one to return as max depends on whether it is a list or set that is passed to a max function.

If a list is passed, as in the case of hands, the first occurrence of the biggest value is returned. In this case, the index of ('TD', 'TC', '7C', 'TH', 'TS') is 9081, index of ('TD', 'TC', '7C', 'TH', 'TC') is 9627, and index of ('TD', 'TC', '7C', 'TD', 'TS') is 9102. Therefore, when hands is passed, the correct answer ('TD', 'TC', '7C', 'TH', 'TS') is always returned.

If a set is passed, since there is no internal ordering, the returned value could vary, which is exactly the behavior we have observed. For further testing, you can try this:

max([(2,'a'),(2,'b'),(2,'c')],key=lambda x:x[0]) # output (2, 'a')
max({(2,'a'),(2,'b'),(2,'c')},key=lambda x:x[0]) # output (2, 'c') or any of the other two depending on implementation

In conclusion, the cause of failed test when set(hands) is passed is the implementation-dependent behavior of calling max on set when multiple elements have the same ranking. But to push this issue further, it might be pure luck that the correct answer is returned with hands, because if during the combination step the wrong answer gets appended ahead of the correct answer, the wrong one would have been returned by max function. I would say the test case should be modified to include all these three hands as potential correct answer.