We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #84: Monopoly odds
  4. Discussions

Project Euler #84: Monopoly odds

Sort by

recency

|

10 Discussions

|

  • Someshraj09
     + 0 comments

    Can anyone please tell me where is my fault only 1 testcase was passed...

    from random import randint
from collections import Counter, deque
from random import shuffle

squares = ["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"]
square_numbers = {square: i for i, square in enumerate(squares)}
num_squares = len(squares)

def build_deck(choices):
    numbers = [square_numbers[square] for square in choices]
    shuffle(numbers)
    return deque(numbers)

transitions = {
    "G2J": build_deck(["JAIL"]),
    "CH1": build_deck(["CH1", "CH1", "CH1", "CH1", "CH1", "CH1", "GO", "JAIL", "C1", "E3", "H2", "R1", "R2", "R2", "U1", "T1"]),
    "CH2": build_deck(["CH2", "CH2", "CH2", "CH2", "CH2", "CH2", "GO", "JAIL", "C1", "E3", "H2", "R1", "R2", "R3", "U2", "D3"]),
    "CH3": build_deck(["CH3", "CH3", "CH3", "CH3", "CH3", "CH3", "GO", "JAIL", "C1", "E3", "H2", "R1", "R1", "R1", "U1", "CC3"]),
    "CC1": build_deck(["CC1", "CC1", "CC1", "CC1", "CC1", "CC1", "CC1", "CC1", "CC1", "CC1", "CC1", "CC1", "CC1", "CC1", "GO", "JAIL"]),
    "CC2": build_deck(["CC2", "CC2", "CC2", "CC2", "CC2", "CC2", "CC2", "CC2", "CC2", "CC2", "CC2", "CC2", "CC2", "CC2", "GO", "JAIL"]),
    "CC3": build_deck(["CC3", "CC3", "CC3", "CC3", "CC3", "CC3", "CC3", "CC3", "CC3", "CC3", "CC3", "CC3", "CC3", "CC3", "GO", "JAIL"])
}
transitions = {square_numbers[square]: deck for square, deck in list(transitions.items())}

def transition(square_number):
    while square_number in transitions:
        deck = transitions[square_number]
        new_square_number = deck.pop()
        deck.appendleft(new_square_number)
        if square_number == new_square_number:
            break
        square_number = new_square_number
    return square_number

def move(square_number, die_size=6):
    roll = randint(1, die_size) + randint(1, die_size)
    square_number += roll
    square_number %= num_squares
    return transition(square_number)

def simulate(iterations=2000000, die_size=6):
    result = Counter()
    square_number = 0
    for i in range(iterations):
        square_number = move(square_number, die_size)
        result[square_number] += 1
    return result

def main():
    simulation = simulate(iterations=2000000, die_size=6)
    print(" ".join(squares[square_number] for square_number, count in simulation.most_common(3)))

if __name__ == "__main__":
    main()

  • david_stek
     + 0 comments

    Just to bump this to the top of the comments section. https://www.hackerrank.com/NiakTheWizard comment below saved me You can get a chance move back 3 spaces that then hits the community chest. I didn't think this was how monopoly worked but anyway. This should be noted in the question i feel.

    Also the fact that the cards go back on the bottom of the deck implies that maybe you have to worry about the order of the cards and can't do markov chains. But that is just false information and should be removed from the question. Assume the decks are shuffled after each draw

  • kitchent
     + 0 comments

    Successively approximation is superb for this problem. I got this idea from thinking about Newton Raphson and chemical equilibrium. Start with an initial arbitrary (in my case, all 0.025) list of probabilities (probability of the player standing on this corresponding square at the end of the last round).

    Use another list to accumulate the probabilities of the player ending up standing in each square which are generated in this round, by iterating each of the squares. Divide them by a common divisor to make sure their sum is . After certain approximating iterations we would end up with a fairly stable list of probabilities.

    I picked approximating iterations for any input, and it passes all test cases within 0.08s. That's Python.

  • franck2
     + 0 comments

    Where can we download what are the input and output for the additional test cases? can't figure out.

  • jack239
     + 1 comment
    When a player lands on CC or CH they take a card from the top of the respective pile and, after following the instructions, it is returned to the bottom of the pile.

    When i was assuming this i got wa. When I has assumed that we take independet random card I got AC. May be it will be helpfull.