Medium Problemscountingcombinatorics

Arrange Balls with adjacent of different types

Given counts of balls of several distinct types, count the number of distinct arrangements of all the balls in a row such that no two balls standing next to each other share the same type.

Do this lesson first: climbing stairs

Example input

2 balls of type A, 1 of type B, 1 of type C

Expected output

6

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[t][S] is the number of distinct arrangements of exactly the balls in S, any sub-pile of the full one up to all of it, with no two equal neighbours, that END with a ball of type t. S names the columns (every non-empty sub-pile, smallest first, written like AAB) and t names the layers, one per type, with a fourth row adding the three up. A plain count is not enough: a new ball can only go on the end of a row that does not already end in its own type, so the state has to carry the last type. This page draws exactly three types, A, B and C, so the table fits on screen; the recurrence is the same for any number of types (see the first variation).

dp[t][S] = sum over types s ≠ t of dp[s][S minus one t]; all endings[S] = dp[A][S] + dp[B][S] + dp[C][S]

Look at the last ball. If it is a t, the balls before it are S with one t taken out, arranged with no equal neighbours, and their own last ball must be anything but a t. Every such shorter row gives exactly one longer row, so add up the ways the shorter pile ends in each other type. It is the climbing-stairs lesson's count by last step, with the step being which type goes last; that lesson derives the idea and this page assumes it. A sum, not a min or max, because every arrangement counts.

A single ball is one arrangement, ending in its own type, so each one-ball column is 1 in its type's row and 0 in the others. Any cell whose pile has no ball of that row's type is 0 too: nothing can end in a type that is not there, which is why a preset without C still shows a C row of zeros. Every other cell reads a column with one ball fewer, and the all-endings cell reads its own column, so the table fills one pile at a time, smallest piles first, and down each column top to bottom.

Tabulation over every sub-pile. With counts a, b and c there are (a + 1)(b + 1)(c + 1) - 1 non-empty piles, and each cell does a constant amount of work for three types, so the work grows with (a + 1)(b + 1)(c + 1). That is why the presets here stay small: one column per pile, and the page caps the grid at 12 columns. The code below loops the counts in nested order rather than by pile size; both orders reach every smaller pile before the piles built from it, which is all the recurrence needs. Memoized recursion on (counts left, last type) computes the same numbers and only visits the piles it needs, which is often how this problem is written.

Time O(k² × (a + 1)(b + 1)(c + 1)) for k = 3 types with counts a, b, c; each extra type adds one (count + 1) factorSpace O(k × (a + 1)(b + 1)(c + 1)) for k = 3 types; each extra type adds one (count + 1) factor

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

A single ball is one arrangement, ending in its own type, so each one-ball column is 1 in its type's row and 0 in the others. Any cell whose pile has no ball of that row's type is 0 too: nothing can end in a type that is not there, which is why a preset without C still shows a C row of zeros. Every other cell reads a column with one ball fewer, and the all-endings cell reads its own column, so the table fills one pile at a time, smallest piles first, and down each column top to bottom.

Balls

11 non-empty piles, so 11 columns.

The walkthrough uses this input. Finish it to unlock the others.

Rows ↓
Cols →

A

B

C

AA

AB

AC

BC

AAB

AAC

ABC

AABC

end A

1

0

1

0

1

2

4

end B

0

1

0

1

0

1

0

2

1

end C

0

1

0

1

0

2

1

all

1

0

2

1

6

Rows ↓last ball's type

Cols →pile of balls arranged

arrange-balls-adjacent-different-types.ts

1function arrangements(p, q, r) {
2 // dp[a][b][c] = [ends in A, ends in B, ends in C, all endings]
3 const dp = [];
4 for (let a = 0; a <= p; a++) { dp[a] = [];
5 for (let b = 0; b <= q; b++) { dp[a][b] = [];
6 for (let c = 0; c <= r; c++) {
7 const have = [a, b, c], cell = [0, 0, 0, 0];
8 for (let t = 0; t < 4; t++) {
9 if (t < 3 && (have[t] === 0 || a + b + c === 1)) { cell[t] = have[t]; continue; } // bases
10 const rest = [...have]; if (t < 3) rest[t]--;
11 const from = t < 3 ? dp[rest[0]][rest[1]][rest[2]] : cell; // the all row reads its own column
12 cell[t] = [0, 1, 2].reduce((sum, s) => (s === t ? sum : sum + from[s]), 0);
13 }
14 dp[a][b][c] = cell;
15 }
16 }
17 }
18 return dp[p][q][r][3];
19}

Base caseComputedBeing readAnswer

The code, the trap, the variations

arrange-balls-adjacent-different-types.ts

1function arrangements(p, q, r) {
2 // dp[a][b][c] = [ends in A, ends in B, ends in C, all endings]
3 const dp = [];
4 for (let a = 0; a <= p; a++) { dp[a] = [];
5 for (let b = 0; b <= q; b++) { dp[a][b] = [];
6 for (let c = 0; c <= r; c++) {
7 const have = [a, b, c], cell = [0, 0, 0, 0];
8 for (let t = 0; t < 4; t++) {
9 if (t < 3 && (have[t] === 0 || a + b + c === 1)) { cell[t] = have[t]; continue; } // bases
10 const rest = [...have]; if (t < 3) rest[t]--;
11 const from = t < 3 ? dp[rest[0]][rest[1]][rest[2]] : cell; // the all row reads its own column
12 cell[t] = [0, 1, 2].reduce((sum, s) => (s === t ? sum : sum + from[s]), 0);
13 }
14 dp[a][b][c] = cell;
15 }
16 }
17 }
18 return dp[p][q][r][3];
19}

Where people go wrong

Keeping only the all-endings row. Without knowing how a shorter row ended, a step cannot tell whether the new ball lands next to one of its own type, so the rule never gets applied and the count comes out as every arrangement there is: 12 for AABC, against the true 6. The other common slip is treating balls of one type as different from each other. Swap the two A's in ABAC and you get the same row, but a count over labelled balls adds it twice and answers 12 here as well, for a different reason.

Any number k of types (the page draws three).
One more layer per type, and each type cell adds up the other k - 1 types instead of 2. The columns are still every sub-pile, so the number of piles plus one multiplies by (count + 1) for each new type.
The row is a circle, so the first and last balls are neighbours too.
The state must also remember the FIRST ball's type, one table per first type, and the answer adds only the cells whose last type differs from the first. The recurrence inside each table is unchanged; only the one-ball seeds change, since the table for first type f starts from a single f alone. Rows that are rotations of each other still count separately.
Allow two equal neighbours but never three in a row.
The layer becomes (last type, how many of it end the row, 1 or 2). A ball of the same type moves run 1 to run 2 and is not allowed after run 2; a different type resets to run 1. Columns and order stay the same.

Regular Expression Matching Longest Subsequence with 1 adjacent difference