#011 Producto en Cuadrícula

1 Entendiendo el Problema

Tenemos una cuadrícula 20×20 con 400 números. Debemos encontrar 4 números consecutivos (en línea) cuyo producto sea máximo. Hay 4 direcciones posibles.

→

Horizontal

↓

Vertical

↘

Diagonal ↘

↙

Diagonal ↙

La cuadrícula 20×20 (click para ver el máximo):

Secuencia ganadora (diagonal ↘):

89

94

97

87

89 × 94 × 97 × 87 = 70,600,674

Respuesta

70,600,674

Posición

Fila 12, Col 6 ↘

2 Fuerza Bruta - 3 Variantes

Recorremos cada celda y probamos las 4 direcciones posibles.

Variante A: while True + break

Bucles con break para cada dirección.

Python

GRID = """
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
""".strip()

# Parsear la cuadrícula
grid = []
for line in GRID.split('\n'):
    row = [int(x) for x in line.split()]
    grid.append(row)

SIZE = 20
LENGTH = 4
max_product = 0

row = 0
while True:
    if row >= SIZE:
        break

    col = 0
    while True:
        if col >= SIZE:
            break

        # Horizontal →
        if col <= SIZE - LENGTH:
            product = 1
            for i in range(LENGTH):
                product *= grid[row][col + i]
            if product > max_product:
                max_product = product

        # Vertical ↓
        if row <= SIZE - LENGTH:
            product = 1
            for i in range(LENGTH):
                product *= grid[row + i][col]
            if product > max_product:
                max_product = product

        # Diagonal ↘
        if row <= SIZE - LENGTH and col <= SIZE - LENGTH:
            product = 1
            for i in range(LENGTH):
                product *= grid[row + i][col + i]
            if product > max_product:
                max_product = product

        # Diagonal ↙
        if row <= SIZE - LENGTH and col >= LENGTH - 1:
            product = 1
            for i in range(LENGTH):
                product *= grid[row + i][col - i]
            if product > max_product:
                max_product = product

        col += 1
    row += 1

print(f"Producto máximo: {max_product}")

// Output aparecerá aquí

Variante B: while condición

Condiciones directas en los while.

Python

GRID = """
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
""".strip()

grid = [[int(x) for x in line.split()] for line in GRID.split('\n')]
SIZE = 20
LENGTH = 4
max_product = 0

# Direcciones: (dr, dc)
directions = [(0, 1), (1, 0), (1, 1), (1, -1)]

r = 0
while r < SIZE:
    c = 0
    while c < SIZE:
        for dr, dc in directions:
            # Verificar si cabe en la cuadrícula
            end_r = r + (LENGTH - 1) * dr
            end_c = c + (LENGTH - 1) * dc

            if 0 <= end_r < SIZE and 0 <= end_c < SIZE:
                product = 1
                i = 0
                while i < LENGTH:
                    product *= grid[r + i * dr][c + i * dc]
                    i += 1

                if product > max_product:
                    max_product = product

        c += 1
    r += 1

print(f"Producto máximo: {max_product}")

// Output aparecerá aquí

Variante C: for range

Usando for con range y vectores de dirección.

Python

GRID = """
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
""".strip()

grid = [[int(x) for x in line.split()] for line in GRID.split('\n')]
SIZE = 20
LENGTH = 4

def get_product(r, c, dr, dc):
    """Calcula el producto de 4 números en la dirección dada."""
    product = 1
    for i in range(LENGTH):
        nr, nc = r + i * dr, c + i * dc
        if not (0 <= nr < SIZE and 0 <= nc < SIZE):
            return 0
        product *= grid[nr][nc]
    return product

# Direcciones: horizontal, vertical, diagonal ↘, diagonal ↙
directions = [(0, 1), (1, 0), (1, 1), (1, -1)]

max_product = 0
best_pos = None

for r in range(SIZE):
    for c in range(SIZE):
        for dr, dc in directions:
            p = get_product(r, c, dr, dc)
            if p > max_product:
                max_product = p
                best_pos = (r, c, dr, dc)

print(f"Producto máximo: {max_product}")
r, c, dr, dc = best_pos
nums = [grid[r + i*dr][c + i*dc] for i in range(LENGTH)]
print(f"Números: {nums}")
print(f"Posición: fila {r}, col {c}, dirección ({dr}, {dc})")

// Output aparecerá aquí

Análisis de complejidad

Tiempo

O(n² × k × d)

n²=400 celdas, k=4 longitud, d=4 direcciones

Espacio

O(n²)

Almacenar la cuadrícula

3 Enfoque Pythónico

Usando math.prod, generadores, y comprensiones elegantes.

Python

from math import prod

GRID = """
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
""".strip()

grid = [[int(x) for x in line.split()] for line in GRID.split('\n')]
N, K = 20, 4

def sequences():
    """Generador de todas las secuencias de K números."""
    dirs = [(0, 1), (1, 0), (1, 1), (1, -1)]

    for r in range(N):
        for c in range(N):
            for dr, dc in dirs:
                # Verificar que la secuencia cabe
                er, ec = r + (K-1)*dr, c + (K-1)*dc
                if 0 <= er < N and 0 <= ec < N:
                    yield [grid[r + i*dr][c + i*dc] for i in range(K)]

# Una línea para encontrar el máximo
result = max(prod(seq) for seq in sequences())

print(f"Producto máximo: {result}")

# Versión aún más compacta (menos legible)
print("\nAlternativa one-liner:")
print(max(
    prod(grid[r+i*dr][c+i*dc] for i in range(4))
    for r in range(20) for c in range(20)
    for dr, dc in [(0,1), (1,0), (1,1), (1,-1)]
    if 0 <= r+3*dr < 20 and 0 <= c+3*dc < 20
))

// Output aparecerá aquí

Herramientas usadas

yield — Generador perezoso de secuencias
math.prod() — Producto de iterables
max(generator) — Máximo sin lista intermedia
Tuplas de direcciones

Vectores de dirección

# (dr, dc) = delta row, delta col
(0, 1)   # → horizontal
(1, 0)   # ↓ vertical
(1, 1)   # ↘ diagonal
(1, -1)  # ↙ anti-diagonal

4 Enfoque con NumPy

Para cuadrículas grandes, NumPy permite operaciones vectorizadas mucho más rápidas usando convoluciones o slicing avanzado.

grid[:-3] \times grid[1:-2] \times grid[2:-1] \times grid[3:] Productos verticales vectorizados

O(n²) \to O(n²/SIMD) Aceleración por vectorización

Python — NumPy vectorizado

import numpy as np

GRID = """
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
""".strip()

# Crear array NumPy
grid = np.array([[int(x) for x in line.split()] for line in GRID.split('\n')])

K = 4  # Longitud de secuencia

def max_product_numpy(g, k):
    """Encuentra el producto máximo usando operaciones vectorizadas."""
    n = len(g)
    max_prod = 0

    # Horizontal: g[:, i] * g[:, i+1] * g[:, i+2] * g[:, i+3]
    horizontal = g[:, :-k+1] * g[:, 1:-k+2] * g[:, 2:-k+3] * g[:, 3:]
    max_prod = max(max_prod, horizontal.max())

    # Vertical
    vertical = g[:-k+1, :] * g[1:-k+2, :] * g[2:-k+3, :] * g[3:, :]
    max_prod = max(max_prod, vertical.max())

    # Diagonal ↘
    diag1 = g[:-k+1, :-k+1] * g[1:-k+2, 1:-k+2] * g[2:-k+3, 2:-k+3] * g[3:, 3:]
    max_prod = max(max_prod, diag1.max())

    # Diagonal ↙
    diag2 = g[:-k+1, k-1:] * g[1:-k+2, k-2:-1] * g[2:-k+3, 1:-k+2] * g[3:, :-k+1]
    max_prod = max(max_prod, diag2.max())

    return max_prod

result = max_product_numpy(grid, K)
print(f"Producto máximo: {result}")

# Encontrar la posición exacta
def find_max_position(g, k):
    """Encuentra la posición del producto máximo."""
    n = len(g)
    max_prod = 0
    best = None

    for r in range(n):
        for c in range(n):
            for dr, dc in [(0,1), (1,0), (1,1), (1,-1)]:
                er, ec = r + (k-1)*dr, c + (k-1)*dc
                if 0 <= er < n and 0 <= ec < n:
                    p = np.prod([g[r+i*dr, c+i*dc] for i in range(k)])
                    if p > max_prod:
                        max_prod = p
                        best = (r, c, dr, dc)

    return max_prod, best

_, pos = find_max_position(grid, K)
r, c, dr, dc = pos
nums = [grid[r+i*dr, c+i*dc] for i in range(K)]
direction = {(0,1): '→', (1,0): '↓', (1,1): '↘', (1,-1): '↙'}[dr, dc]
print(f"Números: {nums}")
print(f"Posición: ({r}, {c}) dirección {direction}")

// Output aparecerá aquí

Comparación de rendimiento

Método	Cuadrícula 20×20	Cuadrícula 1000×1000
Python puro (loops)	~1 ms	~2 segundos
NumPy vectorizado	~0.1 ms	~10 ms

El poder del slicing NumPy

En vez de iterar celda por celda, NumPy nos permite operar sobre todas las posiciones a la vez. g[:, :-3] * g[:, 1:-2] * g[:, 2:-1] * g[:, 3:] calcula todos los productos horizontales en una sola operación vectorizada, aprovechando instrucciones SIMD del procesador.

Largest Product in a Grid

1 Entendiendo el Problema

La cuadrícula 20×20 (click para ver el máximo):

Secuencia ganadora (diagonal ↘):

2 Fuerza Bruta - 3 Variantes

Variante A: while True + break

Variante B: while condición

Variante C: for range

Análisis de complejidad

3 Enfoque Pythónico

Herramientas usadas

Vectores de dirección

4 Enfoque con NumPy

Comparación de rendimiento

El poder del slicing NumPy