[Python] 다른 사람 마음읽기 알고리즘

Srini Devadas의 '퍼즐로 배우는 알고리즘 with 파이썬' 3번째 퍼즐을 풀어보았습니다.

 

당신이 마술사이고, 관람객 5명이 52장의 카드 중 무작위로 뽑은 카드를 맞추고 싶다면 어떻게 해야할까요?

4개의 카드를 먼저 마술사에게 공개한다면, 그 나머지 한 장을 맞출 수 있을까요?

 

정답은 "그렇다"입니다.

 

나머지 한 장의 카드를 어떻게 알 수 있을까요?

트릭은 조수가 마술사에게 보여준 4장의 카드의 순서에 숨어있습니다.

 

먼저, 조수는 5개의 카드 중 기호가 같은 두개의 카드를 먼저 고릅니다.

카드의 종류는 하트, 다이아, 클로버, 스페이스밖에 없기 때문에 무조건 두개 이상의 같은 종류의 카드가 존재합니다.

 

예를 들어, 관람객이 뽑은 카드가 10♥, 9◆, 3♥, Q♠, J◆라고 하면 조수는 먼저 3♥, 10♥를 선택합니다.

 

 다음과 같은 원형 모양에서 3♥, 10♥은 3을 기준으로 보았을 때 시계방향으로 7만큼 떨어져 있으나, 10을 기준으로 보았을 때 시계방향으로 6만큼 떨어져 있습니다. 모양이 같은 두 개의 카드 중 6 또는 그보다 작은 거리에 있는 카드들 중 앞에 위치한 카드(A부터 시계방향으로 보았을 때 먼저 나오는 카드)를 가장 먼저 공개합니다.

 

 예시에서는 10♥를 먼저 공개하고, 3♥가 마술사가 5번째로 맞출 카드가 됩니다.

 즉, 마술사는 첫 번째 공개되는 10♥를 통해, 5번째 카드는 기호가 ♥이고, 10과 시계방향으로 1~6의 거리 만큼 떨어져 있다는 것을 알게 됩니다. 이제 조수는 마술사에게 이 구체적인 거리에 대한 정보를 전달해주면 됩니다.

 

 마술사와 조수는 사전에 미리 다음과 같은 순서로 카드가 커진다는 것을 정해두었습니다.

 A♣A◆A♥A♠2♣2◆2♥2♠...Q♣Q◆Q♥Q♠K♣K◆K♥K♠

 

 남은 세 개의 카드를 공개하는 순서가 크기 순서에 따라 아래 숫자를 의미한다는 것도 정해두었습니다.

 

(작음, 중간, 큼) = 1

(작음, 큼, 중간) = 2

(중간, 작음, 큼) = 3

(중간, 큼, 작음) = 4

(큼, 작음, 중간) = 5

(큼, 중간, 작음) = 6

 

조수가 마술사에게 전달해야 할 수는 6이므로, 10♥ Q♠ J◆ 9◆의 순서로 카드를 마술사에게 보여주게 됩니다.

그러면 마술사는 다섯 째 카드가 3♥임을 알 수 있습니다.

 

이를 코드로 표현하면 다음과 같습니다. 

 

deck = ['A_C', 'A_D', 'A_H', 'A_S', '2_C','2_D','2_H', '2_S','3_C','3_D','3_H','3_S', '4_C',
        '4_D', '4_H', '4_S', '5_C','5_D', '5_H', '5_S','6_C','6_D','6_H', '6_S', '7_C','7_D',
        '7_H','7_S', '8_C','8_D', '8_H', '8_S', '9_C','9_D','9_H','9_8', '10_C', '10_D', '10_H',
        '10_S', 'I_C','I_D','I_H','I_S', 'Q_C', 'Q_D', 'Q_H', 'Q_S', 'K_C', 'K_D', 'K_H', 'K_S']
 
def AssistantOrdersCards():
    print('Cards are character strings as shown below.')
    print('Ordering is:', deck)
    cards, cind, cardsuits, cnumbers = [], [], [], []
    numsuits = [0, 0, 0, 0]
    
    for i in range(5):
        print('Please give card', i+1, end=' ')
        card = input('in above format:')
        cards.append(card)
        n = deck.index(card)
        cind.append(n)
        cardsuits.append(n%4)
        cnumbers.append(n//4)
        numsuits[n%4] += 1
        if numsuits[n%4] > 1:
            pairsuit = n%4
        
    cardh = []     
    for i in range(5):
        if cardsuits[i] == pairsuit:
            cardh.append(i)
    hidden, other, encode = outputFirstCard(cnumbers, cardh, cards)
 
    remindices = []    
    for i in range(5):
        if i!=hidden and i != other:
            remindices.append(cind[i])
        
    sortList(remindices)    
    outputNext3Cards(encode, remindices)        
        
def outputFirstCard(ns, oneTwo, cards):
    encode = (ns[oneTwo[0]] - ns[oneTwo[1]]) % 13
    if encode > 0 and encode <= 6:
        hidden = oneTwo[0]
        other = oneTwo[1]
    else:
        hidden = oneTwo[1]
        otehr = oneTwo[0]
        encode = (ns[oneTwo[1]] - ns[oneTwo[0]]) % 13
    
    print('First card is:', cards[other])
    return hidden, other, encode
 
def outputNext3Cards(code, ind):
    if code == 1:
        s, t, f = ind[0], ind[1], ind[2]
    elif code == 2:
        s, t, f = ind[0], ind[2], ind[1]
    elif code == 3:
        s, t, f = ind[1], ind[0], ind[2]
    elif code == 4:
        s, t, f = ind[1], ind[2], ind[0]
    elif code == 5:
        s, t, f = ind[2], ind[0], ind[1]
    else:
        s, t, f = ind[2], ind[1], ind[0]
    print('Second card is:', deck[s])
    print('Third card is:', deck[t])
    print('Fourth card is:', deck[f])
 
def sortList(tlist):
    for ind in range(0, len(tlist)-1):
        iSm = ind
        for i in range(ind, len(tlist)):
            if tlist[iSm] > tlist[i]:
                iSm = i
        tlist[ind], tlist[iSm] = tlist[iSm], tlist[ind]