Design of Computer Programs Lesson 1

工作也一陣子,最近效率有比較穩定,可以開始考慮生活怎麼過。以前常聽到工作後就會開始懶得看書這種說法,這是大忌啊~因此首先最想要達成的,就是持續不斷的學習。除了之前就有開始讀以前蒐集到的一堆電子書外,還想嘗試看看線上學習網站,例如CourseraUdacityKhan Academy等等。就先挑個熟悉的主題來試試水溫吧。

挑上的是Udacity的Design of Computer Programs,除了因爲內容夠基礎外,還有另一原因就是教授者爲Peter Norvig,也就是頂頂大名的Artificial Intelligence: A Modern Approach的作者。修過AI的人一定有讀過這本書,藉此機會感受一下作者風範也是吸引我的一個動機。另外,語言主要用Python,也是趁此玩一下Python囉。以下記錄一下上完第一堂課的筆記:

第一堂課先從無到有實作一個撲克牌程式,玩的規則應該比較接近大老二,也就是當給兩組(一組五張)牌時,可以比較他們的大小,詳細的規則可以看Wikipedia

  1. 一開始問題就是要如何表達一張牌、一組牌:一張牌主要有分rank與face,rank就是簡單的從A、2 … 9、T(en)、J(ack)、Q(ueen)、K(ing)。而face就是四種花色,因此有S(pade)、H(eart)、C(lub)以及D(iamond),所以每張牌就可以表示成”JS”、”2C”。那麼我們要如何表示一組牌呢?可以有很多種,例如使用list of cards、set of cards。鑑於之後可能需要比較同rank時的大小,所以有序的方式方便我們比較。
  2. 有了每組牌的表示後,接著就要考慮如何表示牌與牌之間的大小。從規則我們可以知道,總共有九種組合,因此我們可以將每組牌加一個權重利於比較:最大的Straight flush爲8,最小的High card則是0,加上原本的五張牌,形成一個新的list。例如:
    1. [TC, JC, QC, KC, AC]是一個Straight flush,所以表示成[8, TC, JC, QC, KC, AC]
    2. [AC, AS, AH, 2S, QD]是一個Three of a kind,所以表示成[3, AC, AS, AH, 2S, QD] 這麼一來,兩個list一比較就可以從第一個元素判斷出大小。但如果他們是同種牌怎麼辦?那麼就需要比較牌組中最大的rank是多少。因此,五張牌組的部分也需要排序,也就是說,上面的兩組牌,其實應該表示成:[8, AC, KC, QC, JC, TC][3, AC, AS, AH, QD, 2S]
  3. 接著我們Top-down的開始設計程式

    1. 最主要的function,回傳包含牌組大小的list

      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)
      
    2. 補充hand_rank需要的function,包含判斷是不是flush或是straight等等

      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
      

對於如何轉換hand中的char(“2”)成爲一個我們可以比較的數字(int形態的2),我們可以直接利用int("2")手動轉換。但對於非數字的牌,如T、J、Q、K、A就會需要額外處理了。因此這裡包含了一個小技巧,定義一個包含每個rank的list,接著判斷hand中char的index位置就得到實際相對的數字,程式碼整個整潔很多。 這裡還要特別注意的是包含A的Straight flush狀況,此時是要以A爲最大的card才對。

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

定義上述function後,我們就可以對兩組牌,分別呼叫hand_rank,並藉由比較回傳值來判斷兩組牌大小。

在作業中,增加牌組至7張牌,要求從中找出可以組成最大牌的五張,這時利用itertools.combinations產生各種牌的組合,搭配先前定義好的hand_rank,就很簡單地完成了。

import itertools
def best_hand(hand):
    "From a 7-card hand, return the best 5 card hand."
    #return max(itertools.combinations(hand, 5), key=hand_rank)
    cardCombations = itertools.combinations(hand, 5)
    maxRank = [-1]
    answers = []
    for c in cardCombations:
        rank = hand_rank(c)
        if rank > maxRank:
            maxRank = rank
            answers = list(c)
    return answers

這個題目在以前程設的習題就看過,實作不算難,重點反而是如何一步步分析問題,並定義function。我們以top-down方式依序定義function,這樣的方式可以避免我們一下子進入太細節的東西。也因爲用的是Python,使得許多操作變得很簡單。像是card_rank中使用list index轉換成實際值,就利用了list composition。如果是用C++,不用lamda的話,肯定就需要有顯式的for-loop才行了。

ranks = ['--23456789TJQKA'.index(r) for r, s in hand]

另外還覺得很不錯的是,無論教學過程或是課堂練習,在寫真正的實作前,Norving都會先寫好test case以便於驗證。這種做法應該就是所謂的TDD (Test-Driven Development)吧。第一次體驗的感覺效果很不錯,可惜以前上課老師都不搞這個。 最後,寫Python果然很爽啊,繼續上第二堂吧。

cwouyang

IT software Engineer, Open source enthusiast.

Taipei, Taiwan https://cwouyang.cc