Expected number of moves to reach the end of a board | Matrix Exponentiation | Javascript implementation of the approach ; Function to multiply two 7 * 7 matrix ; Function to perform matrix exponentiation ; 7 * 7 identity matrix ; Loop to find the power ; Function to return the required count ; Base cases ; Multiplier matrix ; Finding the required multiplier i . e mul ^ ( X - 6 ) ; Final answer ; Driver code
var maxSize = 50 ; function matrix_product ( a , b ) { var c = Array . from ( Array ( 7 ) , ( ) => Array ( 7 ) . fill ( 0 ) ) ; for ( var i = 0 ; i < 7 ; i ++ ) for ( var j = 0 ; j < 7 ; j ++ ) for ( var k = 0 ; k < 7 ; k ++ ) c [ i ] [ j ] += a [ i ] [ k ] * b [ k ] [ j ] ; return c ; } function mul_expo ( mul , p ) { var s = [ [ 1 , 0 , 0 , 0 , 0 , 0 , 0 ] , [ 0 , 1 , 0 , 0 , 0 , 0 , 0 ] , [ 0 , 0 , 1 , 0 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 1 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 0 , 1 , 0 , 0 ] , [ 0 , 0 , 0 , 0 , 0 , 1 , 0 ] , [ 0 , 0 , 0 , 0 , 0 , 0 , 1 ] ] ; while ( p != 1 ) { if ( p % 2 == 1 ) s = matrix_product ( s , mul ) ; mul = matrix_product ( mul , mul ) ; p = parseInt ( p / 2 ) ; } return matrix_product ( mul , s ) ; } function expectedSteps ( x ) { if ( x == 0 ) return 0 ; if ( x <= 6 ) return 6 ; var mul = [ [ 7 / 6 , 1 , 0 , 0 , 0 , 0 , 0 ] , [ 0 , 0 , 1 , 0 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 1 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 0 , 1 , 0 , 0 ] , [ 0 , 0 , 0 , 0 , 0 , 1 , 0 ] , [ 0 , 0 , 0 , 0 , 0 , 0 , 1 ] , [ - 1 / 6 , 0 , 0 , 0 , 0 , 0 , 0 ] ] ; mul = mul_expo ( mul , x - 6 ) ; return ( mul [ 0 ] [ 0 ] + mul [ 1 ] [ 0 ] + mul [ 2 ] [ 0 ] + mul [ 3 ] [ 0 ] + mul [ 4 ] [ 0 ] + mul [ 5 ] [ 0 ] ) * 6 ; } var n = 10 ; document . write ( expectedSteps ( n - 1 ) ) ;