[Richard R Richard]

Primero introduces los datos en una matriz de n por m (5x10).
Fabricas un bucle doble para recorre la matriz
Le sumas o restas 1 a la posición o bien en horizontal  solamente o bien vertical (4 casos)
Chequeas que la posición pertenece a la matriz si es correcto , cuentas 1 en la  variable a y chequeas que el valor almacenado en esa ubicación sea mayor que el de la ubicación original. Si es correcto cuentas uno en la variable b.
Si luego a y b coinciden el punto es un pozo.
Y cuentas uno en c , almacenas en un array el valor del punto en la posición c.
Terminado de analizar los 50 puntos , sumas los valores en el array y sumales c.


---------------------
Moderación. Se han movido aquí los mensajes relativos al problema 8 del advent of code 2021. Aquí el hilo original.

[geómetracat]

Muy bien Richard, pero yo preferiría ver código, porque a veces el algoritmo está muy claro pero a la hora de programar aparecen dificultades (aunque no creo que sea el caso del ejercicio de hoy).

Por si queréis pensar la segunda parte pero no tenéis ganas de registraros o de programar la primera, la copio aquí. Básicamente se trata de encontrar componentes conexas de la matriz, donde la componente conexa correspondiente a un punto son todos los puntos a los que se puede llegar por caminos que no contengan ningún 9 (con movimientos solo en horizontal o vertical).

--- Part Two ---

Next, you need to find the largest basins so you know what areas are most important to avoid.

A basin is all locations that eventually flow downward to a single low point. Therefore, every low point has a basin, although some basins are very small. Locations of height 9 do not count as being in any basin, and all other locations will always be part of exactly one basin.

The size of a basin is the number of locations within the basin, including the low point. The example above has four basins.

The top-left basin, size 3:

2199943210
3987894921
9856789892
8767896789
9899965678

The top-right basin, size 9:

2199943210
3987894921
9856789892
8767896789
9899965678

The middle basin, size 14:

2199943210
3987894921
9856789892
8767896789
9899965678

The bottom-right basin, size 9:

2199943210
3987894921
9856789892
8767896789
9899965678

Find the three largest basins and multiply their sizes together. In the above example, this is 9 * 14 * 9 = 1134.

What do you get if you multiply together the sizes of the three largest basins?


Pongo mi código para las dos partes:

Spoiler

Aquí quizás lo único interesante es el truquillo del padding de la matriz con 9 (es decir, añadir filas y columnas de 9's al principio y al final) para evitar tener que imponer condiciones adicionales para los bordes.

Código: [Seleccionar]

with open("input9.txt") as f:
    inp = [x[:-1] for x in f.readlines()]

# Part 1

import numpy as np

matrix = np.array([[int(x) for x in y] for y in inp])

def local_minima(matrix):
    """Returns list with locations of all local minima"""
    ncol, nrow = len(matrix), len(matrix[0])
    matrix = np.pad(matrix, ((1,),(1,)), constant_values=(9,9))
    minima=[]
    for i in range(1, nrow+1):
        for j in range(1, ncol+1):
            if matrix[i][j] < min(matrix[i-1][j], matrix[i][j-1], matrix[i+1][j], matrix[i][j+1]):
                minima.append((i-1,j-1))
    return minima

minima = local_minima(matrix)
print(sum([matrix[i][j]+1 for i,j in minima]))

# Part 2

def basin(minima, matrix):
    """Returns a list with the points of the basin corresponding to the given minima"""
    matrix = np.pad(matrix, ((1,),(1,)), constant_values=(9,9))
    points = [minima]
    iteration = points
    end = False
    while not end:
        new_iter = []
        for x in iteration:
            list_pos = [(x[0]-1, x[1]), (x[0]+1, x[1]), (x[0], x[1]-1), (x[0], x[1]+1)]
            new_iter = new_iter + [(i,j) for (i,j) in list_pos if matrix[i+1][j+1] != 9]
        new_iter = [x for x in list(set(new_iter)) if x not in points]
        if not new_iter:
            end = True
        iteration = new_iter
        points = points + new_iter
    return points

basin_sizes = [len(basin(x, matrix)) for x in minima]
print(np.prod(sorted(basin_sizes)[-3:]))


[cerrar]

[Richard R Richard]

Muy bien Richard, pero yo preferiría ver código,

Es que el arcaico Visual Basic  no debe ser muy util por estos tiempos

Spoiler

Código: [Seleccionar]

Public x As Integer
Public y As Integer

Public D(1 To 100, 1 To 100) As Integer
Public res(1 To 10000) As Integer

Private Sub Command1_Click()
n = fila.Text * columna.Text
x = 1
y = 1
Do Until x = fila.Text + 1
Do Until y = columna.Text + 1
leyenda.Caption = " intoduzca dato de fila " & x & " y columna " & y
y = y + 1
Loop
x = x + 1
Loop
x = 1
y = 1
c = 0
Do Until x = fila.Text + 1
Do Until y = columna.Text + 1
xu = x - 1
xd = x + 1
yl = y - 1
yr = y + 1
If xu > 0 Then
a = a + 1
If D(x, y) < D(xu, y) Then
b = b + 1
End If
End If
If xd < fila.Text + 1 Then
a = a + 1
If D(x, y) < D(xd, y) Then
b = b + 1
End If
End If
If yl > 0 Then
a = a + 1
If D(x, y) < D(x, yl) Then
b = b + 1
End If
End If
If yr < columna.Text + 1 Then
a = a + 1
If D(x, y) < D(x, yr) Then
b = b + 1
End If
End If
If a = b Then
c = c + 1
res(c) = D(x, y)
x = x + 1
Loop
y = y + 1
Loop
e = 1
Sum = 0
Do Until e = c + 1
Sum = Sum + res(e) + 1
e = e + 1
Loop
resultado.Caption = "El resultado es " & Sum

End Sub

Private Sub Command2_Click()
D(x, y) = Dato.Text
Dato.Text = ""
End Sub
 adjunto imagen del formulario



Por supuesto no hice  nada  por el manejo de los posibles errores de tipeo en las entradas.

Saludos

[cerrar]

Pd  la segunda parte  tiene un problema en la definición de pozo todos los que lo rodean deben ser mayores al valor de la posición del pozo, pero

999999
987789
999999 

no tiene pozos,  pero si es una cuenca

y bajo la definición

Una cuenca son todas las ubicaciones que eventualmente fluyen hacia abajo a un solo punto bajo. Por tanto, cada punto bajo tiene una cuenca, aunque algunas cuencas son muy pequeñas. Las ubicaciones de altura 9 no cuentan como si estuvieran en ninguna cuenca, y todas las demás ubicaciones siempre serán parte de exactamente una cuenca.

cada punto bajo tiene una cuenca correcto ...pero si
 Una cuenca son todas las ubicaciones que eventualmente fluyen hacia abajo a un solo punto bajo y todas las demás ubicaciones siempre serán parte de exactamente una cuenca.
he encontrado el contra ejemplo. donde hay una cuenca sin punto bajo , es decir la definición de punto bajo debe cambiar de menor estricto a menor e igual, y todo solucionado, cada cuenca tiene sus puntos bajos.
La definición de punto bajo es "las ubicaciones que están más bajas que cualquiera de sus ubicaciones adyacentes" implicaría NO igualdad exclusiva.

Que no es lo mismo que ". Todas las demás ubicaciones en el mapa de altura tienen una ubicación adyacente inferior, por lo que no son puntos bajos."  que tampoco indica que sucedería en caso de igualdad.

PD  vere si puedo hacer un código, por ahora me lia la definición.
Saludos