Snakes and Ladders

Introduction

Graph problems pervade computer science, and algorithms to working with them are fundamental to the field. Hundreds of interesting computational problems are couched in terms of graphs. Today let’s discuss graph algorithms.

In fact, I like this problem so much because it reminds me of my childhood. We were playing this game during our school holidays with our friends and it was fun. Let us get into the details next.


Problem Statement

You are given an $n \times n$ integer matrix board where the cells are labeled from $1$ to $n^2$ in a Boustrophedon style starting from the bottom left of the board (i.e. $board[n - 1][0]$) and alternating direction each row.
You start on square $1$ of the board. In each move, starting from square curr, do the following:
Choose a destination square next with a label in the range $[curr + 1, min(curr + 6, n^2)]$
This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the size of the board.
If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next.
The game ends when you reach the square $n^2$.

A board square on row $r$ and column $c$ has a snake or ladder if $board[r][c] \neq -1$. The destination of that snake or ladder is $board[r][c]$. Squares $1$ and $n^2$ are not the starting points of any snake or ladder.

Note that you only take a snake or ladder at most once per dice roll. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent snake or ladder.

For example, suppose the board is 

$\begin{bmatrix}-1 & 4\\-1 & 3\end{bmatrix}$, 

and on the first move, your destination square is 2. You follow the ladder to square 3, but do not follow the subsequent ladder to 4.

Return the least number of dice rolls required to reach the square $n^2$. If it is not possible to reach the square, return $-1$. [1]


Our Approach

This problem is an interesting problem and we solve it using reduction. We reduce the problem into a graph problem and solve it using a graph algorithm which then provides the answer to the original problem. In fact, we can solve this problem using Breadth First Search algorithm. 

From my current position, I roll the dice and it gives me some value $v : v \in \{1, 2, 3, 4, 5, 6\}$ which I can then use to move onto my next position. A dice rolling event would have six possible outcomes and each of them can be thought of as an edge from the current vertex to the next vertex in our graph $G$. Note that $G$ is a directed graph with outdegree $6$.  What follows is our pseudocode to solve this problem.

SNAKE_AND_LADDERS(board)  
    $\phantom{{}++{}}$ let $n \gets board.length$  
    $\phantom{{}++{}}$ let $size \gets n^2$  
    $\phantom{{}++{}}$ let $d$ be a boolean array of size $n^2 + 1$  
    $\phantom{{}++{}}$ let $q$ be a FIFO queue  
    $\phantom{{}++{}}$ $d[1] \gets true$  
    $\phantom{{}++{}}$ enqueue a vertex with label $1$ and distance $0$ to $q$     
    $\phantom{{}++{}}$ `while` $q$ is not empty   
    $\phantom{{}++{}}$ $\phantom{{}++{}}$ let $u \gets q.remove()$  
    $\phantom{{}++{}}$ $\phantom{{}++{}}$ `for` $i = 1$ to $6$      
    $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$  let $next = u.label + i$  
    $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$  `if` $next \le size$    
    $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ let $r, c$ be the corresponding row and column values of the current square with label $next$   
    $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ let $dest \gets next$  
    $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ `if` $board[r][c] \neq -1$  
    $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $dest \gets board[r][c]$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ `if` $dest == size$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ `return` $u.distance + 1$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ `if` $!d[dest]$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $d[dest] \gets true$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ enqueue a vertex with label $dest$ and distance $u.distance + 1$ to $q$  
$\phantom{{}++{}}$ `return` $-1$  

What follows is a sample implementation of the algorithm described above.



Analysis

Let $n \times n$ be the dimensions of the input matrix. Each block is enqueued at most once, hence dequeued at most once. The operations of enqueueing and dequeueing takes O(1) time, and so the total time devoted to queue operations is $\Theta(n^2)$. Calculations of the $d$ values take $\Theta(1)$ time per entry. Thus, the calculation over all the entries in the table $d$ incurs a total cost of $\Theta(n^2)$. The overhead of initialization is $\Theta(n^2)$. Thus, the total running time of our algorithm is $\Theta(n^2)$. Apart from that it consumes $\Theta(n^2)$ asymptotic space complexity for maintaining the table $d$. 


Comments

Post a Comment

Popular posts from this blog

Introducing Java Reactive Extentions in to a SpringBoot Micro Service

Image
Introduction Today we are going to take a look at Reactive Programming using Java8 and RxJava, which is a library for composing asynchronous and event-based programs by using observable sequences. RxJava stands for Reactive Extensions for the JVM. It extends the observer pattern [Gamma95] to support sequences of data/events and adds operators that allow you to compose sequences together declaratively while abstracting away concerns about things like low-level threading, synchronization, thread-safety and concurrent data structures [1]. Pre-Requisites : Having a good knowledge about Java8, Functional Programming and spring boot microservices. What is Reactive programming? In essence, Reactive programming is an asynchronous programming paradigm concerned with data streams. The system time, a list of entries from the DB/API, user clicks, everything can be a stream of data. Data from different streams can easily be combined and transformed, and in the end processed/observed by the ...
Read more

Optimal binary search trees

Image
Suppose that we are designing a program to translate text from English to French. For each occurrence of each English word in the text, we need to look up its French equivalent. We could perform these lookup operations by building a binary search tree with $n$ English words as keys and their French equivalents as satellite data. Because we will search the tree for each individual word in the text, we want the total time spent searching to be as low as possible. We could ensure an $Θ(log_2 \;n)$ search time per occurrence by using a red-black tree or any other balanced binary search tree. Words appear with different frequencies, however, and a frequently used word such as the may appear far from the root while a rarely used word appears near the root. Such an organization would slow down the translation, since the number of nodes visited when searching for a key in a binary search tree equals one plus the depth of the node containing the key. We want words that occur frequently in the t...
Read more

Edit distance

Image
Biological applications often need to compare the DNA of two (or more) different organisms. A strand of DNA consists of a string of molecules called bases, where the possible bases are adenine, guanine, cytosine, and thymine. Representing each of these bases by its initial letter, we can express a strand of DNA as a string over the finite set $\{A, C, G, T\}$. For example, the DNA of one organism may be $S1 = ACCGGTCGAGTGCGCGGAAGCCGGCCGAA$, and the DNA of another organism may be $S2 = GTCGTTCGGAATGCCGTTGCTCTGTAAA$. One reason to compare two strands of DNA is to determine how “similar” the two strands are, as some measure of how closely related the two organisms are. We can, and do, define similarity in many different ways. For example, we can say that two strands are similar if the number of changes needed to turn one into the other is small. [1] We formalize this notion of similarity in our Edit distance problem. 15-5 Edit distance - Problem Statement In order to transform one sour...
Read more