Snakes and Ladders probability of winning

Question

(This is my first Q here, and I don't know much about code golfing.)

Your aim is to predict the winner of an ongoing Snakes and Ladders game.

INPUT

• A single number (2-1000) indicating the number of spaces on the board, say x.
• Another number (2-4) indicating number of players, say n.
• n numbers, each giving the position of each player on the game board.
• Another number (1-15) indicating number of snakes and ladders (combined), say s.
• s lines of input, each with 2 numbers - the start and end of each snake/ladder.

OUTPUT

n decimal numbers, accurate to 2 decimal places, indicating the probability of each player winning.

WINNER

The person to give the fastest program wins, not necessarily the shortest code. This might help those using a different algorithm to gain a huge advantage.

Notes

Players start on space 1, not 0. They win on reaching space x.

All players use a fair 6 sided dice. There are no re-rolls for 6s.

We assume that there is no 'bad' input given, such as more than 4 players, or a snake starting at the last space.

Players are given the same order of play as your input. The first player is the first to roll now, then the second and so on.

Even if you overshoot the win space, you still win.

Answer 1

C, ~.25 seconds

I have calculated by using dynamic simulations instead of probability of each dice roll. The more accurate the probability, the slower... here a brief code...

Compile using:

gcc -o Snakes snakes.c

Code:

#include <time.h>  
#include <stdlib.h>
#include <stdio.h>

int main()
{
    srand(time(0));

    // initialize principal variables
    int NumberOfSpaces   = 100,        
    NumberOfPlayers  = 4,
    PlayerPosition[] = { 46, 56, 36, 66 };
    //PlayerPosition[] = {0, 0, 0, 0}; 

    // arrays of positions, must be in numerical order,
    // must be in (start, end) format. correct - 1, 2, 5, 6, 8, 9
    //                               incorrect - 1, 2, 8, 9, 5, 6                
    int LadderPositions[10] = { 3, 10, 5, 20, 20, 31, 22, 49, 44, 87 },      // positions of ladders    
    SnakePositions[10] = { 11, 3, 15, 1, 35, 22, 54, 29, 60, 20 }, // positions of snakes
    SnakesLadders    = 10;                                       // # of snakes + ladders

    // static arrays to hold 
    // # of dice rolls to complete game
    int Player1Wins[10000], 
    Player2Wins[10000], 
    Player3Wins[10000],
    Player4Wins[10000]; 

    int NumberOfSimulations = 10001; 

    int OutsideLoop, Counter = 1, i, a, Win, EvenArray; 
    for (OutsideLoop = 0; OutsideLoop < NumberOfPlayers; OutsideLoop++)      // do a simulation for each player
        for (a = 0; a < NumberOfSimulations; a++)                       // play for each simulation  
        {
            for (i = PlayerPosition[OutsideLoop]; i <= NumberOfSpaces + 1; i += (rand() % 6 + 1)) // roll the dice for each turn
            {
                Counter++ ;
                for (EvenArray = 0; EvenArray < SnakesLadders; EvenArray+=2) // check if space is snake or ladder
                {
                    if (i == LadderPositions[EvenArray])
                        i = LadderPositions[EvenArray + 1];
                    if (i == SnakePositions[EvenArray])
                        i = SnakePositions[EvenArray + 1];
                }   
             }
             // put value in array
             if (OutsideLoop == 0)
                 Player1Wins[a] = Counter;  
             else if (OutsideLoop == 1)
                 Player2Wins[a] = Counter;  
             else if (OutsideLoop == 2)
                 Player3Wins[a] = Counter;
             else if (OutsideLoop == 3)
                 Player4Wins[a] = Counter;  
             Counter = 0;
        }

    // count how many time each person won
    int P1Wins = 0, P2Wins = 0, P3Wins = 0, P4Wins, Ties = 0;
    for (Win = 0; Win < NumberOfSimulations; Win++)
    {
        if (Player1Wins[Win] < Player2Wins[Win] && Player1Wins[Win] < Player3Wins[Win] && Player1Wins[Win] < Player4Wins[Win])
            P1Wins++;
        else if (Player2Wins[Win] < Player1Wins[Win] && Player2Wins[Win] < Player3Wins[Win] && Player2Wins[Win] < Player4Wins[Win])
            P2Wins++;   
        else if (Player3Wins[Win] < Player1Wins[Win] && Player3Wins[Win] < Player2Wins[Win] && Player3Wins[Win] < Player4Wins[Win])
            P3Wins++;
        else if (Player4Wins[Win] < Player1Wins[Win] && Player4Wins[Win] < Player2Wins[Win] && Player4Wins[Win] < Player3Wins[Win])
            P4Wins++;
        else if (Player2Wins[Win] == Player1Wins[Win] == Player3Wins[Win])
            Ties++;
    }

    printf("[ + ] Namaste! Welcome to the Snakes & Ladders guess who wins program!\n");
    printf("[ + ] I will run 10K simulations of the game to make a guess on the probability of the winner.\n");
    printf("[ + ] Given %i players, with starting positions of :\n[ + ] P1 - %i\n[ + ] P2 - %i\n[ + ] P3 - %i\n[ + ] P4 - %i\n[ + ] Here's the probability I think each player has of winning...\n", NumberOfPlayers, PlayerPosition[0], PlayerPosition[1], PlayerPosition[2], PlayerPosition[3]);   
    printf("[ + ] P1 = %i / 10000\n[ + ] P2 = %i / 10000\n[ + ] P3 = %i / 10000\n[ + ] P4 = %i / 10000\n[ + ] Ties = %i\n", P1Wins, P2Wins, P3Wins, P4Wins, Ties); 
    return 0;
}

Environment - timed using time (bash command) on linux core i7

10 simulations ~ .003 second

10000 simulation ~ .030 second

Sample outputs :

time ./Snakes
[ + ] Namaste! Welcome to the Snakes & Ladders guess who wins program!
[ + ] I will run 10K simulations of the game to make a guess on the probability of the winner.
[ + ] Given 4 players, with starting positions of :
[ + ] P1 - 10 
[ + ] P2 - 21
[ + ] P3 - 50
[ + ] P4 - 70
[ + ] Here's the probability I think each player has of winning...
[ + ] P1 = 86 / 10000
[ + ] P2 = 254 / 10000
[ + ] P3 = 131 / 10000
[ + ] P4 = 9098 / 10000
[ + ] Ties = 0
real    0m0.036s 
user    0m0.036s
sys 0m0.000s

Alt input position:

[ + ] Given 4 players, with starting positions of :
[ + ] P1 - 15
[ + ] P2 - 5
[ + ] P3 - 60
[ + ] P4 - 50
[ + ] Here's the probability I think each player has of winning...
[ + ] P1 = 955 / 10000
[ + ] P2 = 3041 / 10000
[ + ] P3 = 1833 / 10000
[ + ] P4 = 3572 / 10000
[ + ] Ties = 0
real    0m0.024s
user    0m0.024s
sys     0m0.000s

More input:

[ + ] Given 4 players, with starting positions of :
[ + ] P1 - 46
[ + ] P2 - 56
[ + ] P3 - 36
[ + ] P4 - 66
[ + ] Here's the probability I think each player has of winning...
[ + ] P1 = 94 / 10000
[ + ] P2 = 442 / 10000
[ + ] P3 = 2454 / 10000
[ + ] P4 = 6319 / 10000
[ + ] Ties = 0
real    0m0.018s
user    0m0.018s
sys     0m0.000s