콘텐츠로 건너뛰기
Home » 오일러 프로젝트 84

오일러 프로젝트 84

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

모노폴리 시뮬레이터를 작성하고 여러 차례 돌리면서 각 칸에 방문한 횟수를 늘려나간다. 정해진 횟수를 돈 다음, 각 칸에 도달했던 횟수를 계산해본다. 먼저 모노폴리 시뮬레이터를 작성해보자.

게임판과 카드덱

게임판은 총 40개의 칸으로 이루어지며 각 칸의 이름은 문제에서 지정해준 이름을 그대로 쓴다.

rooms: list[str] = (
    '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'
)

이 중 우리가 알고 있으면 좋은 몇 가지 위치는 감옥과 출발점이다. 출발점의 위치를 0으로 했을 때, 감옥의 위치는 10이다. 게임판은 총 40개의 칸으로 구성되어 반복해서 돌게 된다. 따라서 진행시에는 주사위를 던져서 나온 눈의 합을 현재 위치에 더하고 그 합을 40으로 나눈 나머지를 사용하면 된다.

카드덱은 다음과 같이 구성하면 된다.

deck_cc: list[str] = [""] * 14 + ["GO", "JAIL"]
deck_ch: list[str] = [""] * 6 + [
    "GO", "JAIL", "C1", "E3", "H2", "R1", "Rn", "Rn", "Un", "-3"
    ]

CC카드는 16장 중에서 GO와 JAIL이 한 장씩 들어있다. 그외 카드는 칸 이동과 상관없는 카드이므로 빈 문자열로 정의했다. 마찬가지로 CH카드는 6개의 빈카드와 10개의 카드가 있다. 대부분 가야할 칸의 이름이 적혀있는데, 예외적으로 Rn은 다음번 R* 위치로, Un은 다음번 U* 위치로 이동하며, -3은 뒤로 세칸을 간다. 참고로 CH3에서 -3이 나온 경우에는 다시 CC3으로 간다는 점을 잘 기억하자.

기본 구성

각 방의 정보와 덱이 준비되어 있고 이제 게임을 돌리는 함수를 작성해보자. 이 함수는 주사위의 눈의 수와 시행 횟수를 인자로 받고, 각 방의 번호에 대해 방문한 횟수를 기록한 사전을 리턴할 것이다.

from random import randrange, shuffle
def run(faces=6, goes=10000) -> dict[int, int]:
    cc_cards, ch_cards = deck_cc[:], deck_ch[:]
    shuffle(cc_cards); shuffle(ch_cards)
    cc_ind, ch_ind = 0, 0
    double, pos = 0, 0
    result = {}
    ...
    

잠시 변수들을 설명하고 넘어가겠다.

  1. cc_cards, ch_cards는 각 카드덱의 사본이다. 게임 시작전에 각 카드는 뒤섞어야 해서 사본을 생성했다.
  2. cc_ind, ch_ind는 각 카드덱에서 뽑을 카드의 번호이다. 이 값은 0, 1, 2, … 15, 0 , 1, 2, .. 와 같이 순환하는 것으로 뽑은 카드를 맨 밑으로 넣는 효과를 줄 수 있다.
  3. double은 더블이 나온 횟수, pos는 현재 위치이다. 초기 위치는 0으로 GO에서 시작한다.
def run(faces=6, goes=10000) -> dict[int, int]:
    cc_cards, ch_cards = deck_cc[:], deck_ch[:]
    shuffle(cc_cards); shuffle(ch_cards)
    cc_ind, ch_ind = 0, 0
    double, pos = 0, 0
    result = {}
    for _ in range(goes):
        x, y = (1+randrange(faces) for _ in range(2))
        # 만약 두 수가 같으면
        if x == y:
            double += 1
            if double == 3:
                double = 0
                # 더블이 3회면 곧장 감옥행이다.
                pos = 10
                result[pos] = result.setdefault(pos, 0) + 1
                continue
        # 두 수가 다르면 더블 횟수 초기화
        else:
            double = 0
        pos = (pos + x + y) % 40
    # 찬스카드, 기금카드 등 처리...

주사위를 던져서 나온 횟수만큼 진행했다. 이제 말을 옮겼을 때 상황을 보자.

  1. G2J 에 도착했으면 감옥으로 간다.
  2. CC*에 도착했으면 기금 카드를 뽑는다.
  3. CH*에 도착했으면 찬스 카드를 뽑니다.

그런데, 찬스카드에서 -3이 나왔을 때 기금카드로 가는 경우가 있기 때문에 찬스 카드를 먼저 뽑아야 한다. 따라서 순서는 3 > 2 > 1 의 순으로 처리하는 것이 좋다.

...
for _ in range(goes):
...
    if rooms[pos].startswith("CH"):
        card = ch_cards[ch_ind]
        ch_ind = (ch_ind + 1) % 16
        if card == '-3':
            pos = (pos + 37) % 40
        elif card == 'Rn':
            pos = [room[0] for room in rooms * 2].index('R', pos) % 40
        elif card == 'Un':
            pos = [room[0] for room in rooms * 2].index('U', pos) % 40
        elif card == '':
            pass
        else:
            pos = rooms.index(card)
    if rooms[pos].startswith("CC"):
        card = cc_cards[cc_ind]
        cc_ind = (cc_ind + 1) % 16
        if card != '':
            pos = rooms.index(card)
    if rooms[pos] == 'G2J':
        pos = 10
    result[pos] = result.setdefault(pos, 0) + 1
return res

테스트

시뮬레이터를 만들었으니 일정 횟수만큼 돌려보고 결과를 살펴보자. 일단 짧게 12,000번 정도만 돌려서 비교해보자.

def main():
    res = {}
    s = run(6, 12000)
    for k v in s.items():
        res[k] = res.get(k, 0) + v
    t = sum(res.values())
    ws = {k: v / t * 100 for k, v in res.items()}
    ws = sorted(ws.items(), key=lambda x: x[1], reverse=True)[:6]
    for w, v in ws:
        print(f'{w:02d} - {rooms[w]}\t({v:.2f}%)')

이렇게 해서 10번 시행해보면 문제에서 제시한 순서가 아니라 뒤죽박죽인 순서가 나온다. 아무래도 JAIL을 제외한 다른 칸에 방문하는 횟수가 크게 차이가 나지 않는 것 같다. 시행 횟수를 좀 늘려가면서 테스트했을 때 100만을 넘는 정도의 값이면 비슷하게 나오는 것 같다. (백만 회 정도 시행해도 가끔은 순위가 뒤집히는 경우도 있다.)

10-JAIL (6.29%)
24-E3   (3.16%)
00-GO   (3.12%)
elapsed:3031.00ms

대충 된 것 같으니, 4개짜리 주사위를 돌렸을 때의 결과를 구해보면 되겠다.

from random import choice, randrange, shuffle
from utils import timeit
# fmt:off
rooms: list[str] = (
"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", "CC3", "G3", "R4", "CH3", "H1", "T2",
"H2"
)
deck_cc: list[str] = [""] * 14 + ["GO", "JAIL"]
deck_ch: list[str] = [""] * 6 + [
"GO", "JAIL", "C1", "E3", "H2", "R1", "Rn", "Rn", "Un", "-3"
]
# fmt:on
def run(faces=6, goes=10000):
cc_cards, ch_cards = deck_cc[:], deck_ch[:]
shuffle(cc_cards)
shuffle(ch_cards)
cc_ind, ch_ind = 0, 0
res = {}
d = 0
pos = 0
for _ in range(goes):
x, y = (1 + randrange(faces) for _ in range(2))
if x == y:
d += 1
if d == 3:
d = 0
pos = 10
res[pos] = res.setdefault(pos, 0) + 1
continue
res[pos] = res.setdefault(pos, 0) + 1
continue
else:
d = 0
pos = (pos + x + y) % 40
if rooms[pos].startswith("CH"):
# cdeck
card = ch_cards[cc_ind]
ch_ind = (ch_ind + 1) % 16
if card == "":
pass
elif card == "-3":
pos = (pos + 37) % 40
elif card == "Rn":
pos = ([room[0] for room in rooms] * 2).index("R", pos) % 40
elif card == "Un":
pos = ([room[0] for room in rooms] * 2).index("U", pos) % 40
else:
pos = rooms.index(card)
if rooms[pos].startswith('CC'):
# hdeck
card = cc_cards[ch_ind]
cc_ind = (cc_ind + 1) % 16
if card != "":
pos = rooms.index(card)
if rooms[pos] == "G2J":
pos = 10
res[pos] = res.setdefault(pos, 0) + 1
return res
@timeit
def main():
res = {}
s = run(6, 120_0000)
for k, v in s.items():
res[k] = res.get(k, 0) + v
t = sum(res.values())
ws = {k: v / t * 100 for k, v in res.items()}
ws = sorted(ws.items(), key=lambda x: x[1], reverse=True)[:3]
for w, v in ws:
print(f"{w:02d}-{rooms[w]}\t({v:.2f}%)")
main()
view raw e084_1.py hosted with ❤ by GitHub