Design a Snake Ladder game


  • 0
    B

    Data structure you can use to Design a Snake Ladder game


  • 3
    M

    I understand the problem here is the need of ds to keep board's configuration. An array of Strings may be used as described below.

    String[] board = new String[100];
    board[0] = ..
    board[1] = ..
    board[2] = ..
    .
    .
    .
    board[20] = "d6"; //denotes that if a player lands on # 21, she must go down to # 6 (d6) due to a snake bite
    .
    .
    .
    board[32] = "u47"; //denotes that if a player lands on # 33. she must go up to # 47 (u47) as he climbs up the ladder.
    .
    .
    .


  • 0
    P

    We can reduce it to a sparse weighted graph, which we can then store as an adjacency list.


  • 2
    S

    We can use a hashmap to store snakes and ladders.
    i.e Key -> startingPosition of snake / ladder
    Value -> length of snake / ladder
    length is negative for snake
    If we are able to find current position in HashMap then next is value with this position as key.
    Otherwise next is 1 + currentPosition
    It takes O(snake + ladder) space

    // defualt is 0 in map in c++
    class SnakeAndLadder{
    private:  
      map <int, int> length;
    public:
      int getNext(int current)
      {
        return current +  length[current] + 1;
      }
    };

  • 1
    Z

    @sehgaldam121

    I believe hash map is a good data structure for this design. need one more variable n to define the total game board size. maybe need to define a Player class, which has the current position, and could throw a dice to get a random value from 1 to 6.


  • 1
    public interface Board {
      public void reset();
    }
    // Should be singleton
    public class SnakeBoard implements Board {
      List<Snake> snakes;
      List<Ladder> ladders;
      List<SnakeGamePlayer> players;
      Cell[][] cells;
      SixFaceDice dice = new SixFaceDice();
      SnakeBoard() {
        // initialize snakes, ladder, cells & players
      }
      SnakeBoard(List<SnakeGamePlayer> snakes, List<Ladders> ladders, 
          List<Player> players, int row, int column) {
        // assign member vars
        this.cell = new Cell[row][column]
      }
      boolean winner() {
        // return null until no one won the game
      }
      public void reset() {}
      public void bite() {
        //  if new position of player is same as anyone of the snake head pos, update player position
      }
      public void moveUpTheLadder() {}
    }
    
    class Ladder {
      private int start;
      private end;
    }
    
    class Snake {
      private int[] head;//x,y co-ordinate of player
      private  int[] tail;
    }
    
    public interface Player {
      public int score();
      public int move();
    }
    
    public SnakeGamePlayer implements Player {
      private int pid;
      // implement score and move method
      public int[]  currPositionOnBoard() {
        // return x,y co-ordinate of player in board
      }
    }
    
    public interface Dice {
      public int roll();
    }
    public class SixFaceDice implements Dice {
      private static SixFaceDice s;
      public int roll() {
        // generate random number between 1 to 6
      }
      static private SixFaceDice() {
      }
      public void getSixFaceDice() {
        if (s == null) { return new SixFaceDice()}
        else {
         return this.s;
        }
      }
    }
    public class Cell {
      List<Integer> ids; // players ids who are in the cell
      int num;
      int row;
      int column;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.