Ways to arrange Balls such that adjacent balls are of different types | javascript program to count number of ways to arrange three types of balls such that no two balls of same color are adjacent to each other ; table to store to store results of subproblems ; Returns count of arrangements where last placed ball is ' last ' . ' last ' is 0 for ' p ' , 1 for ' q ' and 2 for ' r ' ; if number of balls of any color becomes less than 0 the number of ways arrangements is 0. ; If last ball required is of type P and the number of balls of P type is 1 while number of balls of other color is 0 the number of ways is 1. ; Same case as above for ' q ' and ' r ' ; If this subproblem is already evaluated ; if last ball required is P and the number of ways is the sum of number of ways to form sequence with ' p - 1' P balls , q Q balss and r R balls ending with Q and R . ; Same as above case for ' q ' and ' r ' ; ( last == 2 ) ; Returns count of required arrangements ; Three cases arise : return countWays ( p , q , r , 0 ) + Last required balls is type P countWays ( p , q , r , 1 ) + Last required balls is type Q countWays ( p , q , r , 2 ) ; Last required balls is type R ; Driver code
var MAX = 100 ; var dp = Array ( MAX ) . fill ( - 1 ) . map ( x => Array ( MAX ) . fill ( - 1 ) . map ( x => Array ( MAX ) . fill ( - 1 ) . map ( x => Array ( 3 ) . fill ( - 1 ) ) ) ) ; function countWays ( p , q , r , last ) { if ( p < 0 q < 0 r < 0 ) return 0 ; if ( p == 1 && q == 0 && r == 0 && last == 0 ) return 1 ; if ( p == 0 && q == 1 && r == 0 && last == 1 ) return 1 ; if ( p == 0 && q == 0 && r == 1 && last == 2 ) return 1 ; if ( dp [ p ] [ q ] [ r ] [ last ] != - 1 ) return dp [ p ] [ q ] [ r ] [ last ] ; if ( last == 0 ) dp [ p ] [ q ] [ r ] [ last ] = countWays ( p - 1 , q , r , 1 ) + countWays ( p - 1 , q , r , 2 ) ; else if ( last == 1 ) dp [ p ] [ q ] [ r ] [ last ] = countWays ( p , q - 1 , r , 0 ) + countWays ( p , q - 1 , r , 2 ) ; else dp [ p ] [ q ] [ r ] [ last ] = countWays ( p , q , r - 1 , 0 ) + countWays ( p , q , r - 1 , 1 ) ; return dp [ p ] [ q ] [ r ] [ last ] ; } function countUtil ( p , q , r ) { } var p = 1 , q = 1 , r = 1 ; document . write ( countUtil ( p , q , r ) ) ;