Aufgabe · Algorithmen schwer Python ·

Domino tilings

The grid is a list of equal-length rows of "." (free cell) and "#" (blocked cell). Count the ways to cover every free cell with 1x2 dominoes placed horizontally or vertically, with no overlaps and no domino on a blocked cell. Return the count modulo 1,000,000,007. If there are no free cells, the answer is 1 (the empty tiling). Up to 400 rows and 1 to 8 columns.

Signatur

def count_tilings(grid: list[str]) -> int:

Beispiele

count_tilings(['..', '..'])  # -> 2
count_tilings(['...', '...'])  # -> 3
count_tilings(['.#', '..'])  # -> 0

Zusätzlich 9 versteckte Tests und 3 Performance-Tests mit großem Input unter Zeitlimit; deren Inputs werden nicht angezeigt. Die Aufgaben werden den Modellen auf Englisch gestellt.

Platz 1Google Gemini 3.8 Flashgelöst · 15 von 15 TestsAntwort in 3.3 s · Laufzeit 144 ms · $0.0021

✓	count_tilings(['..', '..'])erwartet 2	1 ms
✓	count_tilings(['...', '...'])erwartet 3	<1 ms
✓	count_tilings(['.#', '..'])erwartet 0	<1 ms

✓ <1 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 1 ms✓ 2 ms✓ 1 ms⏱ 87 ms⏱ 4 ms⏱ 39 ms

Code

def count_tilings(grid: list[str]) -> int:
    MOD = 1_000_000_007
    if not grid or not grid[0]:
        return 1

    R = len(grid)
    C = len(grid[0])

    dp = {0: 1}

    for r in range(R):
        for c in range(C):
            cell_blocked = (grid[r][c] == '#')
            next_dp = {}

            for mask, count in dp.items():
                is_filled = (mask >> c) & 1

                if is_filled:
                    # Current cell is already covered by a vertical domino from the cell above
                    new_mask = mask ^ (1 << c)
                    next_dp[new_mask] = (next_dp.get(new_mask, 0) + count) % MOD
                else:
                    if cell_blocked:
                        # Cell is blocked, leave it empty
                        next_dp[mask] = (next_dp.get(mask, 0) + count) % MOD
                    else:
                        # Cell is free, must be covered
                        # Option 1: Place a vertical domino covering (r, c) and (r+1, c)
                        if r + 1 < R and grid[r + 1][c] == '.':
                            new_mask = mask | (1 << c)
                            next_dp[new_mask] = (next_dp.get(new_mask, 0) + count) % MOD

                        # Option 2: Place a horizontal domino covering (r, c) and (r, c+1)
                        if c + 1 < C and grid[r][c + 1] == '.' and not ((mask >> (c + 1)) & 1):
                            new_mask = mask | (1 << (c + 1))
                            next_dp[new_mask] = (next_dp.get(new_mask, 0) + count) % MOD

            dp = next_dp
            if not dp:
                return 0

    return dp.get(0, 0)

Platz 2OpenAI GPT-6 Lunagelöst · 15 von 15 TestsAntwort in 3.7 s · Laufzeit 194 ms · $0.0002

✓	count_tilings(['..', '..'])erwartet 2	<1 ms
✓	count_tilings(['...', '...'])erwartet 3	<1 ms
✓	count_tilings(['.#', '..'])erwartet 0	<1 ms

✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 5 ms✓ 3 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 126 ms⏱ 4 ms⏱ 49 ms

Code

def count_tilings(grid: list[str]) -> int:
    MOD = 1_000_000_007
    n = len(grid)
    if n == 0:
        return 1
    m = len(grid[0])
    full = (1 << m) - 1

    # Transpose when beneficial to minimize the profile width.
    if n < m:
        grid = [''.join(grid[r][c] for r in range(n)) for c in range(m)]
        n, m = m, n
        full = (1 << m) - 1

    dp = {0: 1}
    for row in grid:
        blocked = 0
        for c, ch in enumerate(row):
            if ch == '#':
                blocked |= 1 << c

        ndp = {}
        for incoming, ways in dp.items():
            if incoming & blocked:
                continue
            occupied = incoming | blocked

            def fill(mask, outgoing):
                if mask == full:
                    ndp[outgoing] = (ndp.get(outgoing, 0) + ways) % MOD
                    return
                bit = (~mask & full) & -(~mask & full)
                c = bit.bit_length() - 1

                # Place a horizontal domino.
                right = bit << 1
                if c + 1 < m and not (mask & right):
                    fill(mask | bit | right, outgoing)

                # Place a vertical domino into the next row.
                if not (blocked & bit):
                    fill(mask | bit, outgoing | bit)

            fill(occupied, 0)
        dp = ndp

    return dp.get(0, 0)

Platz 3MoonshotAI Kimi K2.7 Codenicht gelöst · 0 von 15 TestsAntwort in 120 s

Kein Code in der Antwort

✗	count_tilings(['..', '..'])erwartet 2Kein Code in der Antwort	—
✗	count_tilings(['...', '...'])erwartet 3Kein Code in der Antwort	—
✗	count_tilings(['.#', '..'])erwartet 0Kein Code in der Antwort	—

✗ Kein Code in der Antwort✗ Kein Code in der Antwort✗ Kein Code in der Antwort✗ Kein Code in der Antwort✗ Kein Code in der Antwort✗ Kein Code in der Antwort✗ Kein Code in der Antwort✗ Kein Code in der Antwort✗ Kein Code in der Antwort⏱ Kein Code in der Antwort⏱ Kein Code in der Antwort⏱ Kein Code in der Antwort

Platz 3SpaceXAI Grok 4.7nicht gelöst · 0 von 15 TestsAntwort in 120 s

Kein Code in der Antwort

✗	count_tilings(['..', '..'])erwartet 2Kein Code in der Antwort	—
✗	count_tilings(['...', '...'])erwartet 3Kein Code in der Antwort	—
✗	count_tilings(['.#', '..'])erwartet 0Kein Code in der Antwort	—

Token-Kosten: $0.0023 · So laufen Runden und Wertung ab →

Domino tilings

Signatur

def count_tilings(grid: list[str]) -> int:

Beispiele

count_tilings(['..', '..'])  # -> 2
count_tilings(['...', '...'])  # -> 3
count_tilings(['.#', '..'])  # -> 0

Zusätzlich 9 versteckte Tests und 3 Performance-Tests mit großem Input unter Zeitlimit; deren Inputs werden nicht angezeigt. Die Aufgaben werden den Modellen auf Englisch gestellt.

Platz 1Google Gemini 3.8 Flashgelöst · 15 von 15 TestsAntwort in 3.3 s · Laufzeit 144 ms · $0.0021

✓	count_tilings(['..', '..'])erwartet 2	1 ms
✓	count_tilings(['...', '...'])erwartet 3	<1 ms
✓	count_tilings(['.#', '..'])erwartet 0	<1 ms

✓ <1 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 1 ms✓ 2 ms✓ 1 ms⏱ 87 ms⏱ 4 ms⏱ 39 ms

Code

def count_tilings(grid: list[str]) -> int:
    MOD = 1_000_000_007
    if not grid or not grid[0]:
        return 1

    R = len(grid)
    C = len(grid[0])

    dp = {0: 1}

    for r in range(R):
        for c in range(C):
            cell_blocked = (grid[r][c] == '#')
            next_dp = {}

            for mask, count in dp.items():
                is_filled = (mask >> c) & 1

                if is_filled:
                    # Current cell is already covered by a vertical domino from the cell above
                    new_mask = mask ^ (1 << c)
                    next_dp[new_mask] = (next_dp.get(new_mask, 0) + count) % MOD
                else:
                    if cell_blocked:
                        # Cell is blocked, leave it empty
                        next_dp[mask] = (next_dp.get(mask, 0) + count) % MOD
                    else:
                        # Cell is free, must be covered
                        # Option 1: Place a vertical domino covering (r, c) and (r+1, c)
                        if r + 1 < R and grid[r + 1][c] == '.':
                            new_mask = mask | (1 << c)
                            next_dp[new_mask] = (next_dp.get(new_mask, 0) + count) % MOD

                        # Option 2: Place a horizontal domino covering (r, c) and (r, c+1)
                        if c + 1 < C and grid[r][c + 1] == '.' and not ((mask >> (c + 1)) & 1):
                            new_mask = mask | (1 << (c + 1))
                            next_dp[new_mask] = (next_dp.get(new_mask, 0) + count) % MOD

            dp = next_dp
            if not dp:
                return 0

    return dp.get(0, 0)

Platz 2OpenAI GPT-6 Lunagelöst · 15 von 15 TestsAntwort in 3.7 s · Laufzeit 194 ms · $0.0002

✓	count_tilings(['..', '..'])erwartet 2	<1 ms
✓	count_tilings(['...', '...'])erwartet 3	<1 ms
✓	count_tilings(['.#', '..'])erwartet 0	<1 ms

✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 5 ms✓ 3 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 126 ms⏱ 4 ms⏱ 49 ms

Code

def count_tilings(grid: list[str]) -> int:
    MOD = 1_000_000_007
    n = len(grid)
    if n == 0:
        return 1
    m = len(grid[0])
    full = (1 << m) - 1

    # Transpose when beneficial to minimize the profile width.
    if n < m:
        grid = [''.join(grid[r][c] for r in range(n)) for c in range(m)]
        n, m = m, n
        full = (1 << m) - 1

    dp = {0: 1}
    for row in grid:
        blocked = 0
        for c, ch in enumerate(row):
            if ch == '#':
                blocked |= 1 << c

        ndp = {}
        for incoming, ways in dp.items():
            if incoming & blocked:
                continue
            occupied = incoming | blocked

            def fill(mask, outgoing):
                if mask == full:
                    ndp[outgoing] = (ndp.get(outgoing, 0) + ways) % MOD
                    return
                bit = (~mask & full) & -(~mask & full)
                c = bit.bit_length() - 1

                # Place a horizontal domino.
                right = bit << 1
                if c + 1 < m and not (mask & right):
                    fill(mask | bit | right, outgoing)

                # Place a vertical domino into the next row.
                if not (blocked & bit):
                    fill(mask | bit, outgoing | bit)

            fill(occupied, 0)
        dp = ndp

    return dp.get(0, 0)

Platz 3MoonshotAI Kimi K2.7 Codenicht gelöst · 0 von 15 TestsAntwort in 120 s

Kein Code in der Antwort

✗	count_tilings(['..', '..'])erwartet 2Kein Code in der Antwort	—
✗	count_tilings(['...', '...'])erwartet 3Kein Code in der Antwort	—
✗	count_tilings(['.#', '..'])erwartet 0Kein Code in der Antwort	—

Platz 3SpaceXAI Grok 4.7nicht gelöst · 0 von 15 TestsAntwort in 120 s

Kein Code in der Antwort

✗	count_tilings(['..', '..'])erwartet 2Kein Code in der Antwort	—
✗	count_tilings(['...', '...'])erwartet 3Kein Code in der Antwort	—
✗	count_tilings(['.#', '..'])erwartet 0Kein Code in der Antwort	—