1
\$\begingroup\$

The question description: put a deck of cards in order by suit (in the order spades, heart, clubs, diamonds) and by rank within each suit, with the restriction that the card must be laid out face down in a row, and the only allowed operations are to check the values of two cards and to exchange two cards (keeping them face down).

My solution:

from enum import Enum
import random


class Suit(Enum):
    __order__ = "spade heart club diamond"
    spade = 1
    heart = 2
    club = 3
    diamond = 4


class Card(object):
    def __init__(self, suit, value):
        assert type(suit) == Suit
        assert value > 0 and value < 14
        self._suit = suit
        self._value = value
        self.value = self._get_value()

    def _get_value(self):
        return self._suit.value * 13 + self._value

    def __lt__(self, other):
        return self.value < other.value

    def __str__(self):
        return str((self._suit.name, self._value))

cards = []

for s in Suit:
    for i in range(13):
        cards.append(Card(s, i+1))


random.shuffle(cards)


def shell_sort(cards):
    h = 1
    while(h<52/3):
        h = 3*h + 1
    # h = 30
    # should be more than 29?
    while(h>0):
        for k in range(h, 52):
            j = k
            while(j >= h and cards[j] < cards[j-h]):
                cards[j], cards[j-h] = cards[j-h], cards[j]
                j -= h
        h = int(h / 3)
    return cards

sorted_cards = shell_sort(cards)

for c in sorted_cards:
    # how to consider the suit, can the suit decrease the compare times?
    print(c)

I think this can be further optimized since there should be no compares among different suits. Can that be integrated in the shell sort without firstly rank the suits (then the values inside)?

\$\endgroup\$
  • \$\begingroup\$ That is a silly constraint that forces you to use a sub-optimal method for sorting. Cards are so easy to sort, you only need to look at each once, and can immediately place it in its right location in the output. \$\endgroup\$ – Cris Luengo Dec 5 '18 at 1:44
  • \$\begingroup\$ Note that you can assign suits the values 0, 13, 26 and 39, then each card has the value suit+value. Might make the sorting routine easier to write. \$\endgroup\$ – Cris Luengo Dec 5 '18 at 1:46
  • 1
    \$\begingroup\$ @CrisLuengo You are right! But let's treat the algorithm exercise as an axercise. \$\endgroup\$ – Lerner Zhang Dec 5 '18 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.