package org.pilgrim.base.game;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class LadderChutesProblem
{
    static class Node
    {
        public Node(int v,
                    int d)
        {
            this.v = v;
            this.d = d;
        }

        int v;
        int d;

        @Override
        public String toString()
        {
            StringBuilder builder = new StringBuilder();
            builder.append("v=");
            builder.append(v);
            builder.append(", d=");
            builder.append(d);
            return builder.toString();
        }
    }

    public static int findMinMove(int[] board,
                                  int n)
    {
        int m = -1;
        boolean[] visitted = new boolean[n];
        visitted[0] = true;
        Queue<Node> q = new LinkedList<>();
        Node qn = new Node(0, 0);
        q.add(qn);

        int d = 0;
        while (!q.isEmpty())
        {
            qn = q.peek();
            int v = qn.v;

            if (v == n - 1)
            {
                break;
            }

            q.poll();

            for (int j = v + 1; j <= (v + 6) && j < n; j++)
            {
                if (!visitted[j])
                {
                    Node s = new Node(0, qn.d + 1);
                    visitted[j] = true;
                    if (board[j] == -1)
                    {
                        s.v = j;
                    }
                    else
                    {
                        s.v = board[j];
                    }
                    q.add(s);
                }
            }
        }

        if (qn.v == n - 1)
        {
            m = qn.d;
        }
        return m;
    }

    public static void main(String[] args)
    {
        int n = 100;
        int a[] = new int[n];
        Arrays.fill(a, -1);
        a[2] = 70;//ladder from 2 to 70
        a[71] = 60;//chute from 71 to 60
        a[61] = 99;//ladder from 61 to 99

        int min = findMinMove(a, n);
        System.out.println(min);
    }
}

@@ -1,8 +1,1585 @@
+/**%0A * Snake and Ladder Problem%0AGiven a snake and ladder board, find the minimum number of dice throws required to reach%0Athe destination or last cell from source or 1st cell. Basically, the player has total control%0Aover outcome of dice throw and wants to find out minimum number of throws required to reach last cell.%0A%0AIf the player reaches a cell which is base of a ladder, the player has to climb up that%0Aladder and if reaches a cell is mouth of the snake, has to go down to the tail of snake without a dice throw.%0A%0Asnakesladders%0A%0AFor example consider the board shown on right side (taken from here),%0Athe minimum number of dice throws required to reach cell 30 from cell 1 is 3. Following are steps.%0A%0Aa) First throw two on dice to reach cell number 3 and then ladder to reach 22%0Ab) Then throw 6 to reach 28.%0Ac) Finally through 2 to reach 30.%0A%0AThere can be other solutions as well like (2, 2, 6), (2, 4, 4), (2, 3, 5).. etc.%0A%0AWe strongly recommend to minimize the browser and try this yourself first.%0AThe idea is to consider the given snake and ladder board as a directed graph with number%0Aof vertices equal to the number of cells in the board. The problem reduces to finding the shortest%0Apath in a graph. Every vertex of the graph has an edge to next six vertices%0Aif next 6 vertices do not have a snake or ladder. If any of the next six vertices has a snake or ladder,%0Athen the edge from current vertex goes to the top of the ladder or tail of the snake.%0ASince all edges are of equal weight, we can efficiently find shortest path using Breadth First Search of the graph.%0A */%0A
 package 

add description