오일러 프로젝트 84

이번 문제는 문제가 길고 복잡하기 때문에 풀이 위주로 갑니다.

문제 그대로의 규칙을 사용해서 ‘간이 모노폴리’ 시뮬레이터를 잘 작성한다음, 이를 충분히 여러번 돌려서 최종적으로 말이 도착하는 위치에 대한 데이터를 생성하면 된다.

게임판 정의하기

게임판은 총 40개의 칸으로 이루어지며 각 칸의 이름이 모두 정해져있으므로 이를 문자열의 튜플로 정의해둔다.

rooms = ('GO', 'A1', 'CC1', 'A2', 'T1', 'R1', 'B1', 'CH1', 'B2', 'B3',
        'JAIL', 'C1', 'U1', 'C2', 'C3', 'R2', 'D1', 'CC2', 'D2', 'D3',
        'FP', 'E1', 'CH2', 'E2', 'E3', 'R3', 'F1', 'F2', 'U2', 'F3',
        'G2J', 'G1', 'G2', 'C3', 'G3', 'R4', 'CH3', 'H1', 'T2', 'H2')

주사위 던지기

주사위 2개를 던지는 규칙은 다음과 같다.

1. 주사위 2개를 던져 두 주사위 눈의 합계만큼의 칸 의 수를 전진한다.
2. 이 때, 주사위 2개의 눈이 같다면 (더블) 한 번 더 던질 수 있다.
3. 만약 더블이 3번 연속 나온다면 바로 감옥으로 직행한다.

주사위는 1~6의 눈이 각각 랜덤하게 나오는 2개를 사용한다. 따라서 한 번 주사위를 던질 때의 결과는 두 개의 랜덤 값의 튜플을 사용할 수 있다. 이를 코드로 표현하자면 다음과 같다.

from random import randrange

def run_dice(f=6):
  return (randrange(f) + 1, randrange(f) + 1)

다음은 주사위를 던졌을 때, 동작을 코드로 표현해보자.  함수 move()는 현재 위치와 누적된 더블 횟수를 인자로 받는다. 이 함수 내에서 주사위 2개를 던져보고 그 합을 현재 위치 값에 더해서 전진시킨 위치 값과 누적 더블 횟수를 리턴한다. 만약 더블 횟수가 3이 된다면 더 이상 더블 없이 감옥으로 가게 될 것이기에 (10, 0)을 리턴할 것이다.

def move(p:int, dd:int=0) -> (int, int):
  '''현위치와 더블횟수를 받고, 주사위를 굴려 다음위치와 더블횟수를 리턴'''
  a, b = run_dice()
  if a == b:  # 더블
    dd += 1
    if dd == 3:
      return (10, 0)
  else:
    dd = 0
  
 ''' 현재 위치에서 이동할 칸의 수를 더해준다'''
  p = (a + b + p) % 40
  return (p, dd)

이상의 코드가 카드 없이 돌아가는 게임이 된다. 만약 카드를 사용해야 한다면 어떻게 해야할까?  카드에 관한 룰을 먼저 적용해보자.

카드 덱 추가하기

문제에서 정의한 카드는 총 2개의 덱으로 구성되어 있다. 카드의 종류는 기금카드와 찬스카드가 있다. 먼저 기금카드는 총 16장이며 이 중 2개의 카드가 칸의 이동에 관련된다. 한장은 출발점으로 다른 한장은 감옥으로 가는 카드이며, 나머지 14장은 말의 이동에 영향을 주지 못하는 카드이다.

나머지 덱인 찬스 카드는 총 16장인데, 이중 10장이 이동에 관련되는 카드이다. 카드들에 적절한 이름을 붙여서 두 개의 덱을 리스트로 묶으면 다음과 같이 정의할 수 있다.

deck = [
    ['GO', 'JAIL'] + [''] * 14, # GO, JAIL외 다른 카드 14장
    ['GO', 'JAIL', 'C1', 'E3', 'H2', 'R1', 'NR', 'NR', 'NU',
    '-3'] + [''] * 6
]

카드 섞기

문제에서는 각 게임의 앞에 카드덱을 잘 섞는다고 했다. 카드를 섞기 위해서는 각 덱의 0번 카드와 임의의 카드 중 1개를 서로 맞바꾼다. 이를 약 100번씩 시행해주면 적당히 잘 섞였다고 볼 수 있겠다.

'''카드 덱 섞기: 임의의 카드와 첫번째 카드를 서로 바꿈'''
for d in range(2):
    for _ in range(100):
        i = randrange(len(deck[d]) - 1) + 1
        deck[d][0], deck[d][i] = deck[d][i], deck[d][0]

이제 카드를 뽑았을 때, 동작을 살펴보자. 카드를 뽑았을 때의 처리는 다음과 같다.  카드를 뽑는 것은 각 덱에서 0번 카드를 빼는 것이다. 그리고 뺀 카드는 다시 덱의 맨 뒤에 추가한다. (빼낸 카드를 덱 맨 아래에 다시 넣는 것과 같은 이치)

1. 먼저 현재위치와 카드덱의 종류를 인자로 받으며, 리턴 값은 뽑은 카드의 지시를 이행한 결과의 위치값이 될 것이다.
2. 이동과 관련이 없는 카드를 뽑으면 원위치를 그대로 리턴한다.
3. ‘NR’ 카드는 다음번 R위치까지 이동한다.
4. ‘NU’ 카드는 다음번 U위치까지 이동한다.
5. -3 카드는 뒤로 세 칸 이동한다.
6. 그외의 카드는 카드와 같은 이름의 방으로 이동한다.

이상의 로직을 코드로 표현하면 아래와 같다. 계속 돌아가는 게임이지만 한 번에 두 바퀴를 돌수는 없으니 rooms * 2 에서 움직인다고 보면 되겠다.

def run_card(p, i):
    '''카드를 뒤집어주고 새 위치를 리턴한다
    p: 현재위치
    i: 카드덱의 종류 0:기금, 1:찬스
    '''

    c = deck[i].pop(0)
    deck[i].append(c)

    if c == '':
        # 이동과 관련없는 키드
        pass
    elif c == 'NR':
        # 다음 R
        i = (([x[0] for x in rooms] * 2)[p+1:]).index('R') + 1
        p = (p + i) % 40

    elif c == 'NU':
        # 다음 U
        i = (([x[0] for x in rooms] * 2)[p+1:]).index('U') + 1
        p = (p + i) % 40
    elif c == '-3':
        p = (p + 37) % 40
    else:
        p = rooms.index(c)
    return p

칸에 방문했을 때 동작

다음은 칸에 방문했을 때 수행해야 하는 동작이다. 아까는 move() 함수에서 그저 칸을 방문한 것으로 끝났지만 다음의 경우가 있을 수 있다.

1. 아무 일도 일어나지 않는다. 현재 방의 위치가 그대로 유지된다.
2. 방문한 방이 G2J 이면 바로 감옥으로 이동한다. 10이 리턴된다
3. 방문한 방이 찬스카드, 기금카드 칸이면 해당 카드를 뽑아 본다. 방금 작성한 run_card() 함수를 호출한 결과가 새로운 위치가 된다.

이 동작을 다시 새로운 함수로 정의한다.

def visit(p:int) -> int:
    if rooms[p] == 'G2J':
        p = 10
    elif rooms[p][:2] in ('CC', 'CH'):
        p = run_card(p, 0 if rooms[p][1] == 'C' else 1)
    return p

자 그러면 다시 위의 move() 함수에서 p = (a + b + p) % 40 라고 현재 위치에서 앞으로 나아가던 코드는 다음과 같이 바뀌어야 한다.

p = visit((a+b+p) % 40)

그럼 끝이다. 이제 move()를 반복 호출하는 코드를 작성하면 되겠다. 각 게임당 주사위를 300번 굴린다고 하고 매 move()마다 어느 방을 방문하는지를 기록하자. 매 이동 시마다 방문한 칸의 방문수를 올려주기 위해서는 dict 객체를 하나 사용해준다.

result = {}
pos = 0  # 현재 말의 위치
for _ in range(300):
  d = 0
  while True:
    pos, d = move(pos, d)
    result[pos] = result.get(pos, 0) + 1
    if d is 0:
      break

이렇게하면 최종결과에는 (방번호, 방문횟수)의 쌍이 남게 된다. 이제 이상의 모든 코드를 하나의 함수로 묶어준다. 이 때, run_dice() 함수의 인자를 전체 함수의 인자로 옮겨주면 주사위 면의 수에 따른 게임 결과를 알아 볼 수 있게 된다.

이제 게임을 1000번 반복하고 그 결과를 정리하는 코드를 작성해보자.

def main(f=6):
  d = {}
  for _ in range(1000):
    xs = game(

전체 코드는 아래와 같다.