Snakes and Ladders probability of winning

(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.

• Could you provide some sample inputs/outputs? Also, fastest algorithm is for the the theoretical fastest algorithm (Aka, O(n) beats O(n^2) ). If you want actual fastest code, then use the tag fastest-code Jun 27, 2015 at 15:38
• Is an exact roll required to reach the last square or is overshooting OK? Jun 27, 2015 at 16:27
• @trichoplax I assume the specification makes it clear: "s lines of input, each with 2 numbers - the start and end of each snake/ladder.": If the first number is higher than the second it's a snake, otherwise a ladder. Jun 28, 2015 at 11:41
• @SebastianHöffner that does make it clear - thanks for that Jun 28, 2015 at 11:56
• @feersum Overshooting is allowed; you still win. Jun 28, 2015 at 15:54

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

// 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 == 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

• I just realised that, for me to compare response time, I will have to test it myself (each person's machine and language may vary). Please give the exe file so I can check the time required. Jun 29, 2015 at 15:19
• Maybe you could upload it to Google Drive and share it, otherwise I don't know how to share an exe.... Jun 29, 2015 at 15:20
• Also I may need to enter values greater than 100 to compare, so please allow for input upto 1000. Sorry and thanks! Jun 29, 2015 at 15:25
• @ghosts_in_the_code: Couldn't you just copy and paste the code into a .c file on your computer and compile it using the gcc line provided in the answer? Jun 29, 2015 at 16:40
• I don't think it's a good habit to start sharing binaries when we have the source. I've tried to keep the variable names as descriptive as possible so it's easy to edit. There are no limits, so you can change # of spaces, players, etc. Jun 29, 2015 at 18:58