Entendendo o Algoritmo Hourglass Sum em Arrays 2D

Atualizado pela última vez em 1 de dezembro de 2023

O desafio do “Hourglass Sum” em arrays 2D, extraído do site HackerRank, oferece uma oportunidade excelente para aprimorar habilidades de programação e raciocínio lógico. Este algoritmo não é apenas sobre manipulação de arrays; ele nos ensina a identificar padrões e aplicar lógica em estruturas de dados.

A Estrutura de uma Ampulheta em Arrays 2D

O desafio gira em torno da identificação e soma de valores em um padrão específico de ampulheta em um array 2D. O padrão de uma ampulheta é definido como:

a b c
  d
e f g

Cada “ampulheta” é uma coleção de valores que correspondem a esse formato dentro do array.

Exemplo Prático

Considere o seguinte array 2D:

1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 2 4 4 0
0 0 0 2 0 0
0 0 1 2 4 0

O objetivo é encontrar a maior soma de ampulheta neste array.

Primeira Ampulheta: A primeira ampulheta possível neste array começa no elemento superior esquerdo. Seus elementos são:

1 1 1
  1
1 1 1

A soma desta ampulheta é 1+1+1+1+1+1+1 = 7.

Continuando esse processo para o restante do array, encontramos várias outras ampulhetas. Contudo, a que nos interessa particularmente para este exemplo é a que representa a maior soma.

2 4 4
  2
1 2 4

Calculando a soma desta ampulheta, obtemos 2+4+4+2+1+2+4 = 19, sendo a maior soma de ampulheta possível neste array.

Processo de Implementação do algoritmo

O “Processo de Implementação” do algoritmo Hourglass Sum em um array 2D envolve algumas etapas críticas que garantem a correta identificação e soma das ampulhetas. 

Vamos detalhar o processo de implementação do algoritmo “Hourglass Sum” em Python, passo a passo, com código para cada etapa.

1. Iteração Cuidadosa

A primeira etapa é iterar pelo array 2D. O array tem um tamanho fixo de 6×6, mas cada ampulheta ocupa um espaço de 3×3. Isso significa que não precisamos percorrer todo o array, mas apenas até o índice 4 (exclusivo) tanto para linhas quanto para colunas. A razão para isso é evitar índices fora do limite do array ao calcular as somas das ampulhetas.

# Iteração pelo array 2D
for i in range(4):
    for j in range(4):
        # Código para calcular a soma da ampulheta será inserido aqui

2. Cálculo da Soma Máxima

Em cada posição válida do array (até o índice 4 para linhas e colunas), calculamos a soma dos elementos que formam a ampulheta. Uma ampulheta é composta por três elementos na linha superior, um elemento no meio da linha do meio e três elementos na linha inferior. Para uma posição (i, j) no array, os elementos da ampulheta seriam:

• Linha superior: arr[i][j], arr[i][j+1], arr[i][j+2]
• Linha do meio: arr[i+1][j+1] (elemento central)
• Linha inferior: arr[i+2][j], arr[i+2][j+1], arr[i+2][j+2]

A soma desses sete elementos dá a soma da ampulheta para a posição (i, j).

max_sum = float('-inf')  # Inicialização com o menor valor possível

for i in range(4):
    for j in range(4):
        top = sum(arr[i][j:j+3])
        middle = arr[i+1][j+1]
        bottom = sum(arr[i+2][j:j+3])

        hourglass_sum = top + middle + bottom

        # Atualizando a soma máxima, se necessário
        if hourglass_sum > max_sum:
            max_sum = hourglass_sum

Ao final do processo, max_sum conterá a maior soma de ampulheta possível no array fornecido. Segue o exemplo completo:

def hourglassSum(arr):
    max_sum = float('-inf')

    for i in range(4):
        for j in range(4):
            top = sum(arr[i][j:j+3])
            middle = arr[i+1][j+1]
            bottom = sum(arr[i+2][j:j+3])

            hourglass_sum = top + middle + bottom

            if hourglass_sum > max_sum:
                max_sum = hourglass_sum

    return max_sum

# Exemplo de Array
arr = [
    [1, 1, 1, 0, 0, 0],
    [0, 1, 0, 0, 0, 0],
    [1, 1, 1, 0, 0, 0],
    [0, 0, 2, 4, 4, 0],
    [0, 0, 0, 2, 0, 0],
    [0, 0, 1, 2, 4, 0]
]

# Executando a função e exibindo o resultado
result = hourglassSum(arr)
print("A maior soma de ampulheta é:", result)

Após executar o arquivo, você deve ver a seguinte saída no terminal:

A maior soma de ampulheta é: 19

Onde posso aplicar esse conhecimento sobre o Algoritmo Hourglass Sum?

O conhecimento adquirido ao aprender e aplicar o algoritmo Hourglass Sum pode ser utilizado em várias áreas e situações práticas, especialmente aquelas que envolvem processamento de dados, análise de padrões, e manipulação de matrizes. Aqui estão alguns exemplos específicos:

1. Processamento de Imagens e Visão Computacional
2. Análise de Dados e Estatísticas
3. Desenvolvimento de Jogos
4. Inteligência Artificial e Aprendizado de Máquina
5. Cálculos Científicos e Simulações

Vejamos um exemplo prático que se beneficia das habilidades adquiridas ao resolver o problema da ampulheta em arrays 2D é o cálculo de temperaturas médias em uma grade meteorológica. Este exemplo é comum em análises de dados ambientais e climáticos.

Suponhamos que você tenha uma matriz 2D representando temperaturas em uma região e deseja calcular a temperatura média em áreas de 3×3 na matriz.

temperatures = [
    [22, 24, 20, 32, 30],
    [24, 23, 22, 28, 26],
    [26, 30, 28, 26, 24],
    [28, 27, 30, 32, 34],
    [30, 32, 34, 36, 38]
]

Código para Calcular as Médias:

def calculate_average_temperature(temps):
    rows = len(temps)  # Número total de linhas
    cols = len(temps[0])  # Número total de colunas

    # Loop principal sobre as linhas
    for i in range(rows - 2):
        # Loop principal sobre as colunas
        for j in range(cols - 2):
            temp_sum = 0
            # Loop secundário sobre 3 linhas da submatriz
            for di in range(3):
                # Loop secundário sobre 3 colunas da submatriz
                for dj in range(3):
                    temp_sum += temps[i + di][j + dj]
            average_temp = temp_sum / 9
            print(f"A temperatura média em ({i}, {j}) é: {average_temp:.2f}")

Note que estamos utilizando aqui uma abordagem um pouco mais interativa, por conta que precisamos efetuar a média geral. Obseerve que temos 4 loops neste exemplo, porém, ao analisarmos a sua complexidade, podemos ter os seguintes insights:

Complexidade dos Loops Aninhados

Quando temos loops aninhados, cada loop adiciona uma dimensão à complexidade total. Por exemplo, dois loops aninhados, cada um com uma complexidade de O(N), resultam em uma complexidade total de O(N²).

No caso do código fornecido, temos dois conjuntos de loops aninhados:

1. Dois Loops Principais (for i e for j): Estes loops têm uma complexidade combinada de O((N-2)×(M-2)), o que simplifica para O(N×M) para grandes valores de N e M.
2. Dois Loops Secundários (for di e for dj): Eles percorrem uma submatriz de tamanho fixo (3×3), resultando em uma complexidade constante O(1), pois não depende do tamanho da entrada.

A complexidade total do algoritmo é determinada pela parte mais significativa do código. Neste caso, são os dois loops principais que percorrem a matriz inteira. Portanto, a complexidade é O(N×M), onde N e M são as dimensões da matriz. Os loops internos fixos contribuem com uma constante adicional ao tempo de execução, mas não alteram a ordem de complexidade.

Você pode melhorar o exemplo utilizando Slicing e List comprehension:

def calculate_average_temperature(temps):
    rows = len(temps)
    cols = len(temps[0])
    
    for i in range(rows - 2):
        for j in range(cols - 2):
            # Utilizando slicing para capturar uma submatriz 3x3
            submatrix = [row[j:j+3] for row in temps[i:i+3]]

            # Calculando a soma usando comprehension list e sum()
            temp_sum = sum(sum(row) for row in submatrix)

            # Calculando a média
            average_temp = temp_sum / 9
            print(f"A temperatura média em ({i}, {j}) é: {average_temp:.2f}")

Este código utiliza slicing e list comprehensions para simplificar o acesso e o cálculo das submatrizes 3×3. Embora a complexidade também seja O(N×M) para os loops externos, a abordagem com slicing e list comprehensions é mais eficiente em termos de execução.

Veja no exemplo a seguir como analisar o desempenho dos 2 algoritmos implementados aqui neste exemplo:

import time

# Função com quatro loops aninhados
def calculate_average_temperature_v1(temps):
    rows = len(temps)
    cols = len(temps[0])
    for i in range(rows - 2):
        for j in range(cols - 2):
            temp_sum = 0
            for di in range(3):
                for dj in range(3):
                    temp_sum += temps[i + di][j + dj]
            average_temp = temp_sum / 9

# Função com slicing e list comprehensions
def calculate_average_temperature_v2(temps):
    rows = len(temps)
    cols = len(temps[0])
    for i in range(rows - 2):
        for j in range(cols - 2):
            submatrix = [row[j:j+3] for row in temps[i:i+3]]
            temp_sum = sum(sum(row) for row in submatrix)
            average_temp = temp_sum / 9

# Gerando uma matriz grande de temperaturas para teste
import random
temperatures = [[random.randint(20, 35) for _ in range(1000)] for _ in range(1000)]

# Medindo o tempo de execução da primeira função
start_time = time.time()
calculate_average_temperature_v1(temperatures)
time_v1 = time.time() - start_time

# Medindo o tempo de execução da segunda função
start_time = time.time()
calculate_average_temperature_v2(temperatures)
time_v2 = time.time() - start_time

time_v1, time_v2

Neste teste, utilizando uma matriz grande de 1000×1000 elementos. Os resultados da simulação de desempenho para os dois algoritmos são os seguintes:

• Tempo de execução da função com quatro loops aninhados (calculate_average_temperature_v1): 7.68 segundos
• Tempo de execução da função com slicing e list comprehensions (calculate_average_temperature_v2): 4.38 segundos

Estes resultados demonstram que a versão com slicing e list comprehensions é significativamente mais rápida do que a versão com quatro loops aninhados. Isso confirma que a otimização realizada através do slicing e das list comprehensions não apenas simplifica o código, mas também melhora sua eficiência em termos de tempo de execução, especialmente em matrizes de grande escala.

Conclusão

🌟 Espero que tenha gostado do artigo! Abordamos detalhadamente o algoritmo Hourglass Sum e suas aplicações, além de comparar diferentes métodos para calcular temperaturas médias em grades meteorológicas. Demonstramos que a eficiência e a clareza do código são fundamentais, especialmente ao trabalhar com grandes conjuntos de dados.

📣 Compartilhe seu conhecimento! Se achou este artigo útil, considere compartilhá-lo com seus colegas e amigos interessados em programação e ciência de dados. A troca de conhecimento é uma ferramenta poderosa para o crescimento coletivo.

📹 Descubra Mais no Nosso Canal! Para explorar esses tópicos com mais detalhes visuais e práticos, assista ao vídeo relacionado no canal GrowthCode no YouTube. Lá, você encontrará uma abordagem interativa e aprofundada desses conceitos, juntamente com outras dicas valiosas. Inscreva-se no canal para se manter atualizado com as últimas tendências e aprimorar ainda mais suas habilidades.

🔗 Acesse os Códigos e Exemplos! Todos os códigos e exemplos mencionados neste artigo estão disponíveis para download no nosso repositório no GitHub: Algorithm-Playground. Sinta-se à vontade para explorar, baixar e contribuir com o projeto!

Até o próximo artigo!

Confiança Sempre!!!