7
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ 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 \$\endgroup\$ – Nathan Merrill Jun 27 '15 at 15:38
  • 1
    \$\begingroup\$ Is an exact roll required to reach the last square or is overshooting OK? \$\endgroup\$ – feersum Jun 27 '15 at 16:27
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Sebastian Höffner Jun 28 '15 at 11:41
  • \$\begingroup\$ @SebastianHöffner that does make it clear - thanks for that \$\endgroup\$ – trichoplax Jun 28 '15 at 11:56
  • \$\begingroup\$ @feersum Overshooting is allowed; you still win. \$\endgroup\$ – ghosts_in_the_code Jun 28 '15 at 15:54
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – ghosts_in_the_code Jun 29 '15 at 15:19
  • \$\begingroup\$ Maybe you could upload it to Google Drive and share it, otherwise I don't know how to share an exe.... \$\endgroup\$ – ghosts_in_the_code Jun 29 '15 at 15:20
  • \$\begingroup\$ Also I may need to enter values greater than 100 to compare, so please allow for input upto 1000. Sorry and thanks! \$\endgroup\$ – ghosts_in_the_code Jun 29 '15 at 15:25
  • 1
    \$\begingroup\$ @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? \$\endgroup\$ – Alex A. Jun 29 '15 at 16:40
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ – Pulga Jun 29 '15 at 18:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.