There are p, q and r balls. arrange balls in a straight line such that no two balls of the same type are adjacent.

Hint

This algorithm uses memoization to improve performance. It's same as the recursive version of Arrange balls, but with a special 'cache' to store results. The 'cache key' is crucial. It's how we identify and store past results. Sometimes we need one key, sometimes multiple keys. We add code to:

# Python implementation

cache = None

def arrange(p, q, r, pick):
  if (p < 0 or q < 0 or r < 0):
    return 0

  if (
    (pick=='p' and p==1 and q==0 and r==0) or
    (pick=='q' and p==0 and q==1 and r==0) or
    (pick=='r' and p==0 and q==0 and r==1)):
    return 1

  global cache
  if not cache:
    cache = [[[{} for _ in range(r + 1)] for _ in range(q + 1)] for _ in range(p + 1)]

  if pick not in cache[p][q][r]:
    if pick == 'p':
      cache[p][q][r][pick] = arrange(p-1, q, r, 'q') + arrange(p-1, q, r, 'r')
    elif pick == 'q':
      cache[p][q][r][pick] = arrange(p, q-1, r, 'p') + arrange(p, q-1, r, 'r')
    elif pick == 'r':
      cache[p][q][r][pick] = arrange(p, q, r-1, 'p') + arrange(p, q, r-1, 'q')

  return cache[p][q][r][pick]

p = 1
q = 1
r = 0

print(arrange(p, q, r, 'p') + arrange(p, q, r, 'q') + arrange(p, q, r, 'r'))

// Javascript implementation

let cache = null;

function arrange(p, q, r, from) {
  if (p < 0 || q < 0 || r < 0) {
    return 0;
  }

  if (
    (from=='p' && p==1 && q==0 && r==0) ||
    (from=='q' && p==0 && q==1 && r==0) || 
    (from=='r' && p==0 && q==0 && r==1)) {
    return 1;
  }

  if (cache == null) {
    cache = [];

    for (let i = 0; i <= p; i++) {
      cache[i] = [];

      for (let j = 0; j <= q; j++) {
        cache[i][j] = []

        for (let k = 0; k <= r; k++) {
          cache[i][j][k] = {}
        }
      }
    }
  }

  if (cache[p][q][r][from] == undefined) {
    switch(from) {
      case 'p':
        cache[p][q][r][from] = arrange(p-1, q, r, 'q') + arrange(p-1, q, r, 'r');
        break;
      case 'q':
        cache[p][q][r][from] = arrange(p, q-1, r, 'p') + arrange(p, q-1, r, 'r');
        break;
      case 'r':
        cache[p][q][r][from] = arrange(p, q, r-1, 'p') + arrange(p, q, r-1, 'q');
        break;
    }
  }

  return cache[p][q][r][from];
}

const p = 1;
const q = 1;
const r = 0;

console.log(arrange(p, q, r, 'p') + arrange(p, q, r, 'q') + arrange(p, q, r, 'r'));

Arrange balls (Memoization)

Hint