Linear DPmediumTwo rolling counts, one per row type3 min · 189 of 290

Tints in the stair window

Count the glazings of a three-pane-wide window in three tints with no two touching panes alike, by carrying one count per kind of row.

A stairwell window is three panes wide and as tall as the stair is long. The glazier holds three tints and one rule: no two panes that share an edge may be the same tint.

The problem

The window is rows rows tall and three panes wide. Every pane takes one of three tints — amber, green or grey. Two panes share an edge when they sit side by side in a row, or one directly above the other in a column; panes meeting at a corner only are not neighbours and may match.

Count the complete glazings in which no two edge-sharing panes carry the same tint, modulo 1,000,000,007.

Input. rows — an integer, the number of rows of three panes.

Output. The number of valid glazings, modulo 1,000,000,007.

Example.

rows = 1   ->  12

One row: three tints for the left pane, two for the middle (anything but the left), two for the right (anything but the middle). 3 · 2 · 2 = 12.

A second example, showing that the rows do not multiply out evenly:

rows = 2   ->  54

A row has no fixed number of successors. Six of the twelve legal rows use two tints — amber, green, amber and its like — and admit 5 rows beneath; the other six use all three and admit 4. That is 6 · 5 + 6 · 4 = 54.

A third example, where the split decides it again:

rows = 3   ->  246

Of the 54 two-row windows, 30 end two-tint and 24 three-tint, so the third row gives 3 · 30 + 2 · 24 = 138 and 2 · 30 + 2 · 24 = 108: 246 in all.

Constraints.

  • 1 <= rows <= 5000
  • Exactly three tints are stocked.
  • Return the count modulo 10⁹ + 7.

Hints

Hint 1

Twelve patterns fill one row. Once a row is glazed, does the row below it care about anything higher up the window?

Hint 2

List the rows that may sit under amber, green, amber, then under amber, green, grey. The two lists differ in length.

Hint 3

Any two rows using two tints behave identically, and so do any two using three. Two numbers carry down the window, not twelve.

Approach

Brute force

Tint all 3 · rows panes every way and test the neighbours: 3 to the power 3 · rows candidates, 14 million at five rows. Chaining legal rows is better and still hopeless — 12 per row is 12⁵⁰⁰⁰.

The insight

Rows conflict only with the row above, and the only thing about that row which changes the future is whether it uses two tints or three.

Renaming the tints turns any two-tint row into any other, and the rule never asks which tint is which, so all six two-tint rows admit the same mix of successors — likewise the six three-tint rows. a b a admits 3 two-tint rows and 2 three-tint rows; a b c admits 2 of each.

Algorithm

  1. Start with two = 6 and three = 6, the twelve legal first rows by kind.
  2. For each further row, update both at once: two, three = 3 * two + 2 * three, 2 * two + 2 * three, reduced modulo 1,000,000,007 on every step.
  3. After the last row return (two + three) % 1000000007.

Complexity

Time O(rows) — one fixed-size update per row, 5,000 at the bound. Space O(1): two integers, whatever the height.

Solution

Python 3 · standard library16 lines · 6 test cases, all passing
"""Tints in the stair window — two rolling counts, one per kind of row."""

MOD = 1_000_000_007


def solve(rows):
    # two:   windows glazed so far whose bottom row uses two tints (a b a).
    # three: those whose bottom row uses all three (a b c).
    # Nothing above the bottom row can affect what may go under it, so these
    # two totals are the whole state.
    two = three = 6                      # the twelve legal single rows, six of each kind
    for _ in range(rows - 1):
        # a b a admits 3 two-tint rows and 2 three-tint rows beneath it;
        # a b c admits 2 of each.
        two, three = (3 * two + 2 * three) % MOD, (2 * two + 2 * three) % MOD
    return (two + three) % MOD
The cases that ran
TESTS = [
    ((1,), 12),
    ((2,), 54),
    ((3,), 246),
    ((4,), 1122),
    ((10,), 10107954),
    ((5000,), 30228214),
]

Pitfalls

  • Carrying a single count of 12. One number forces one successor factor, so two rows come out as 12 · 4 = 48 or 12 · 5 = 60, never 54.
  • Treating corner-touching panes as neighbours. Add the six diagonal pairs and three tints cannot fill a second row at all: the answer drops to 0 for every window taller than one row.
  • Reducing only at the end. The exact count at 5,000 rows runs to 3,296 digits; a 64-bit accumulator wraps before the thirtieth row.

Variants

  • Standing the pipe rank — the same neighbours-only rule, but the pieces are a fixed set to order, so the state is a subset rather than a row.
  • Linear DP — the recipe for rolling a fixed number of totals along one axis.