Algorithm Playground

Entendendo o Algoritmo Hourglass Sum em Arrays 2D

Atualizado em

Capa do artigo Entendendo o Algoritmo Hourglass Sum em Arrays 2D
Leitura com foco

Entenda o contexto.
Leve para a prática.

Neste artigo
  1. A Estrutura de uma Ampulheta em Arrays 2D
  2. Exemplo Prático
  3. Processo de Implementação do algoritmo
  4. 1. Iteração Cuidadosa
  5. 2. Cálculo da Soma Máxima
  6. Onde posso aplicar esse conhecimento sobre o Algoritmo Hourglass Sum?
  7. Complexidade dos Loops Aninhados
  8. Conclusão

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.

Para medir o custo de loops aninhados como estes, veja como calcular a complexidade de um algoritmo na prática.

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!

Veja também: O que é Algoritmo?, Análise de Complexidade de Algoritmos e Estruturas de Dados: listas, filas, pilhas e árvores.

Confiança Sempre!!!

Compartilhe este artigo

Sobre quem escreve

Walmir Silva

Olá! Sou Walmir, engenheiro de software com MBA em Engenharia de Software e o cérebro por trás do GrowthCode e autor do livro "Além do Código".

Se você acha que programação é apenas sobre escrever código, prepare-se para expandir seus horizontes. Aqui, nós vamos além do código e exploramos as interseções fascinantes entre tecnologia, negócios, artes e filosofia.

Você está em busca de crescimento na carreira? Quer se destacar em um mercado competitivo? Almeja uma vida mais rica em conhecimento e realização? Então você chegou ao lugar certo. No GrowthCode, oferecemos insights profundos, estratégias comprovadas e um toque de sabedoria filosófica para catalisar seu crescimento pessoal e profissional.

Ver todos os artigos →

Continue a conversa

Compartilhe sua perspectiva

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

Guardamos o IP e o navegador de quem comenta por 6 meses, para barrar spam e porque o Marco Civil da Internet pede a guarda dos registros de acesso por esse prazo. Veja como tratamos seus dados.

Encontre sua próxima resposta

O que você quer aprender?

Preferências de cookies

Os cookies opcionais começam desligados. Você pode mudar a escolha a qualquer momento por esta tela.

NecessáriosSempre ativos

Guardam a sua escolha de cookies e o código do registro dela, e mantêm o site funcionando. Não são usados para publicidade.

Contam visitas e mostram como o site é usado: Google Analytics e Microsoft Clarity, carregados pelo Google Tag Manager.

Exibem anúncios do Google AdSense sem personalização. Os cookies desta categoria limitam a repetição dos anúncios e medem o resultado deles.

Usa a sua navegação para escolher anúncios e formar públicos de anúncio: anúncios do Google escolhidos pelos seus interesses e os indicadores do Google no Analytics. Desligado, os anúncios aparecem sem personalização. Depende de Publicidade.

Também é possível bloquear cookies nas configurações do navegador. Detalhes na Política de privacidade.