The fifteenth day of Advent of Code was yesterday 15/12/2024! If you’re here for the first time today, don’t forget to read the posts about Day 1, Day 2, Day 3, Day 4, Day 5, Day 6, Day 7, Day 8, Day 9, Day 10, Day 11, Day 12, Day 13 and Day 14.

I classified the fifteenth problem as medium (part 1) and medium (part 2).

Tips

• The first part of the problem is to read the maze (warehouse) and the robot commands.
• Use the example inputs to test the solution.
• You need to detect in the maze input where the walls, robot, and boxes are.
• The commands are on multiple lines, it’s easier if you concatenate them into a single string.
• You can implement robot directions (commands) using vectors.
• Vectors can also be used to mark box and wall positions.
• The walls surround the entire warehouse, you don’t need to worry about the robot leaving the warehouse.
• To check if the robot can move, verify if the new position is free. In this case, move the robot by updating its position.
• If the next position is occupied by a wall, the robot cannot move and stays in the same place.
• To know if boxes can be moved, you can recursively try all boxes from the movement direction. For each box, check if it can move (blank space in the movement direction). If one of the boxes cannot be moved, the movement is canceled.
• Remember that the robot can push multiple boxes at once. A recursive function can help solve this problem.
• In part 1, boxes are the same size as walls, meaning each box occupies one position. In part 2, each box occupies two positions.
• Part 2 is a bit more complex because you can move more than columns and rows of boxes, but entire parts of the warehouse.
• Horizontal movement is similar to part 1, as each box has a height of only one character, like in part 1.
• Each movement in part 2 can move up to 2 boxes at once. But this movement is done in cascade, so these two boxes can move other 2, 3, or more boxes. Each box movement can move zero, one, or two boxes at each step, but can cause the movement of many others.
• In part 2, you need to verify if the entire movement is valid. For example, when the boxes being pushed form a V or get stuck on a wall, they all have to stop moving. If you implement the movement function as in part 1, you’ll see that the boxes will move in several pieces, which leads to the wrong answer.

How much Python do you need to know?

The chapters refer to my book Introduction to Programming with Python.

O décimo quinto dia do Advent of Code foi ontem 15/12/2024! Se você caiu aqui hoje pela primeira vez, não deixe de ler os posts sobre o Dia 1, Dia 2, Dia 3, Dia 4, Dia 5, Dia 6, Dia 7, Dia 8, Dia 9, Dia 10, Dia 11, Dia 12, Dia 13 e Dia 14.

Classifiquei o décimo quinto problema como médio (parte 1) e médio (parte 2).

Dicas

• A primeira parte do problema é ler o labirinto (armazém) e os comandos do robô.
• Utilize as entradas de exemplo para testar a solução.
• Você precisa detectar na entrada do labirinto, onde estão as paredes, o robô e as caixas.
• Os comandos estão em várias linhas, fica mais fácil se você concatená-las em uma só string.
• Você pode implementar as direções do robô (comandos) usando vetores.
• Vetores também podem ser utilizados para marcar as posições das caixas e paredes.
• As paredes circundam todo o armazém, você não precisa de preocupar com o robô saindo do armazém.
• Para verificar se o robô pode se mexer, verifique se a nova posição está livre. Neste caso, mova o robô, atualizando a posição.
• Se a posição seguinte for ocupada por uma parede, o robô não pode se mexer e fica no mesmo lugar.
• Para saber se pode mover as caixas, você pode tentar recursivamente todas as caixas a partir da direção do movimento. A cada caixa, verifique se ela pode se mover (espaço em branco na direção do movimento). Caso uma das caixas não possa ser movida, o movimento é cancelado.
• Lembre-se que o robô pode empurrar várias caixas ao mesmo tempo. Uma função recursiva pode ajudar a resolver este problema.
• Na parte 1, as caixas são do mesmo tamanho das paredes, ou seja, cada caixa ocupa uma posição. Na parte 2, cada caixa ocupa duas posições.
• A parte 2 é um pouco mais complexa, pois você pode mover mais que colunas e linhas de caixas, mas partes inteiras do armazém.
• O movimento horizontal é semelhante ao da parte 1, pois cada caixa tem altura de apenas um caractere, como na parte 1.
• Cada movimento na parte 2 pode mover até 2 caixas ao mesmo tempo. Mas esse movimento é feito em cascata, logo estas duas caixas podem mover outras 2, 3, ou mais caixas. Cada movimento de caixa pode movimentar a cada passo, zero, uma ou duas caixas, mas pode ocasionar o movimento de muitas outras.
• Na parte 2, você precisa verificar se o movimento inteiro é válido. Por exemplo, quando as caixas sendo empurradas formam um V ou ficam presas em uma parede, todas tem que parar de se mover. Se você implementar a função de movimento como na parte 1, verá que as caixas vão se mexer em vários pedaços, o que leva a resposta errada.

Quanto de Python você precisa saber?

Os capítulos se referem ao meu livro Introdução à Programação com Python.

The fourteenth day of Advent of Code was yesterday 14/12/2024! If you’re here for the first time today, don’t forget to read the posts about Day 1, Day 2, Day 3, Day 4, Day 5, Day 6, Day 7, Day 8, Day 9, Day 10, Day 11, Day 12 and Day 13.

I classified the fourteenth problem as medium (part 1) and medium (part 2).

Tips

• Another maze problem :-D It’s very good to have a Maze class.
• This problem also uses vectors, the Vector2d class will be very useful.
• You can use a regular expression to extract data from the input.
• Organizing code into classes is good practice. In this case, each robot is clearly an object.
• Remember integer division to calculate the middle column and rows.
• Each robot has a position and a velocity vector.
• When the robot moves to a position outside the maze (Zone), it can be corrected using the modulo operator (see chapter 2, properties of division remainder).
• You can see time advancement as a simulation.
• Use test values to verify if your solution answers the problem. Start by testing robot movement and then the teleportation that occurs when they move outside the Zone.
• Part 2 is a bit different from the others. We need to find a Christmas pattern in the robots’ positions.
• After manually running the simulation and examining the output frames, we can determine that the solution appears when the robots form a Christmas figure a bit less than 8000 seconds. This occurs at the first simulation step where no robots overlap (occupy the same position). The problem statement doesn’t make this requirement explicit.

How much Python do you need to know?

The chapters refer to my book Introduction to Programming with Python.

O décimo quarto dia do Advent of Code foi ontem 14/12/2024! Se você caiu aqui hoje pela primeira vez, não deixe de ler os posts sobre o Dia 1, Dia 2, Dia 3, Dia 4, Dia 5, Dia 6, Dia 7, Dia 8, Dia 9, Dia 10, Dia 11, Dia 12 e Dia 13.

Classifiquei o décimo quarto problema como médio (parte 1) e médio (parte 2).

Dicas

• Mais um problema com labirinto :-D É muito bom ter uma classe como a Labirinto.
• Este problema também utiliza vetores, a classe Vector2d será bem útil.
• Você pode utilizar uma expressão regular para extrair os dados da entrada.
• Organizar o código em classes é uma boa prática. Neste caso, cada robô é claramente um objeto.
• Lembre da divisão inteira para calcular a coluna e linhas do meio.
• Cada robô tem uma posição e um vetor velocidade.
• Quando o robô se move para uma posição fora do labirinto (Zona), ela pode ser corrigida usando o operador módulo (ver capítulo 2, propriedades do resto da divisão).
• Você pode ver o avanço do tempo como uma simulação.
• Utilize os valores de teste para verificar se sua solução responde ao problema. Comece por testar a movimentação dos robôs e depois a teleportação que ocorre quando eles se movem fora da Zona.
• A Parte 2 é um pouco diferente das demais. Precisamos encontrar um padrão de natal na posição dos robôs.
• Depois de observar a resposta, avançando a simulação manualmente, pois o enunciado não deixa claro; podemos ver que o segundo da simulação quando os robôs formam a figura de natal é o primeiro em que não há sobreposição de robôs, ou seja, não há dois robôs na mesma posição.

Quanto de Python você precisa saber?

Os capítulos se referem ao meu livro Introdução à Programação com Python.

The thirteenth day of Advent of Code was yesterday 12/13/2024! If you’re here for the first time today, don’t forget to read the posts about Day 1, Day 2, Day 3, Day 4, Day 5, Day 6, Day 7, Day 8, Day 9, Day 10, Day 11 and Day 12.

I classified the thirteenth problem as medium (part 1) and medium (part 2).

Tips

• The program has a multi-line input
• You can use regular expressions to extract values from each line
• Each group of 4 lines brings 4 values, the input for the program
• You can view the problem as a system of linear equations
• The system has no solution when the equation system’s answer is not an integer
• Find the values of a and b that satisfy the equation. In this case, calculate the cost as 3*a + b
• If you use an optimizer like scipy.optimize.linprog or Pulp you might have problems with the large numbers in part 2
• Model in Pulp:

def solve(ax, ay, bx, by, rx, ry):

    model = LpProblem("Minimize Tokens", LpMinimize)
    A = LpVariable("A", lowBound=0, cat=LpInteger)
    B = LpVariable("B", lowBound=0, cat=LpInteger)

    model += 3 * A + B
    model += ax * A + bx * B == rx
    model += ay * A + by * B == ry
    model.solve()    

    return model, value(A), value(B)

• With scipy:

from scipy.optimize import linprog

def minimize_cost(x, y, r, c, max_tokens=100):    
    A_eq = [x, y]  # Coefficient matrix for equality constraints
    b_eq = r  # Right-hand side of the equations
    
    result = linprog(
        c,
        A_eq=A_eq,
        b_eq=b_eq,
        method="highs",
        bounds=[(0, max_tokens), (0, max_tokens)],
        integrality=[1, 1],
    )

    # Check if the optimization was successful
    if result.success:
        a, b = result.x
        print(
            f"The optimized solution is: a = {a}, b = {b}, with a cost of {3*a + b} {result.fun}"
        )
        return a, b, 3 * a + b

    else:
        print("No valid solution (could not optimize).", result)
        return None

How much Python do you need to know?

The chapters refer to my book Introduction to Programming with Python.

O décimo terceiro dia do Advent of Code foi ontem 13/12/2024! Se você caiu aqui hoje pela primeira vez, não deixe de ler os posts sobre o Dia 1, Dia 2, Dia 3, Dia 4, Dia 5, Dia 6, Dia 7, Dia 8, Dia 9, Dia 10, Dia 11 e Dia 12.

Classifiquei o décimo terceiro problema como médio (parte 1) e médio (parte 2).

Dicas

• O programa tem um entrada em várias linhas
• Você pode usar expressões regulares para extrair os valores de cada linha.
• Cada grupo de 4 linhas, trás 4 valores, a entrada para o programa.
• Você pode observar o problema como uma sistema de equações lineares.
• O sistema não tem solução quando a resposta do sistema de equações não é inteira.
• Ache os valores de a e b que satisfaçam a equação. Neste caso, calcule o custo como sendo 3*a + b.
• Se você utilizar um otimizador como scipy.optimize.linprog ou Pulp você poderá ter problemas com os grandes números da parte 2.
• Modelo no Pulp:

def psolve(ax, ay, bx, by, rx, ry):

    model = LpProblem("Minimize Tokens", LpMinimize)
    A = LpVariable("A", lowBound=0, cat=LpInteger)
    B = LpVariable("B", lowBound=0, cat=LpInteger)

    model += 3 * A + B
    model += ax * A + bx * B == rx
    model += ay * A + by * B == ry
    model.solve()    

    return model, value(A), value(B)

• Com scipy:

from scipy.optimize import linprog

def minimize_cost(x, y, r, c, max_tokens=100):    
    A_eq = [x, y]  # Coefficient matrix for equality constraints
    b_eq = r  # Right-hand side of the equations
    
    result = linprog(
        c,
        A_eq=A_eq,
        b_eq=b_eq,
        method="highs",
        bounds=[(0, max_tokens), (0, max_tokens)],
        integrality=[1, 1],
    )

    # Check if the optimization was successful
    if result.success:
        a, b = result.x
        print(
            f"The optimized solution is: a = {a}, b = {b}, with a cost of {3*a + b} {result.fun}"
        )
        return a, b, 3 * a + b

    else:
        print("No valid solution (could not optimize).", result)
        return None

Quanto de Python você precisa saber?

Os capítulos se referem ao meu livro Introdução à Programação com Python.

The twelfth day of Advent of Code was yesterday 12/12/2024! If you’re here for the first time today, don’t forget to read the posts about Day 1, Day 2, Day 3, Day 4, Day 5, Day 6, Day 7, Day 8, Day 9, Day 10 and Day 11.

I classified the twelfth problem as easy (part 1) and medium (part 2).

Tips

• Another problem with mazes or character maps.
• You can build a zone by looking for identical elements in positions above, below, left, and right of the current node.
• Try to visualize the character map as a matrix. Now imagine each element as a node in a graph, connected to its neighbors.
• Remember to mark nodes already visited
• You can build a fence whenever the element in the direction being explored is different from the current element.
• In part 1, the area equals the number of elements in the same zone. To calculate the perimeter, you need to know how many barriers you placed in each position.
• Part 2 brings a different way to calculate the price, but the problem is very similar to part 1. Now, you need to look at all zone barriers and check how many are contiguous lines and columns.
• You can organize the lines by the y coordinate of their fences. Contiguous lines will have the same y coordinate value. If properly sorted, the next segment will be the next with an x position just 1 element larger than the previous one. This way, you can count contiguous lines.
• Columns follow the same principle, but now you need to sort the fences by x coordinate. Similarly, a column is contiguous if the next segment is in the next line.
• It’s easier to organize the data if horizontal and vertical fences are separated.

How much Python do you need to know?

The chapters refer to my book Introduction to Programming with Python.

O décimo segundo dia do Advent of Code foi ontem 12/12/2024! Se você caiu aqui hoje pela primeira vez, não deixe de ler os posts sobre o Dia 1, Dia 2, Dia 3, Dia 4, Dia 5, Dia 6, Dia 7, Dia 8, Dia 9, Dia 10 e Dia 11.

Classifiquei o décimo segundo problema como fácil (parte 1) e médio (parte 2).

Dicas

• Outro problema com labirintos ou mapas de caracteres.
• Você pode construir uma zona, procurando por elementos idênticos nas posições acima, abaixo, a esquerda e a direita do nó corrente.
• Tente visualizar o mapa de caracteres como uma matriz. Agora imagine cada elemento como um nó de um grafo, conectado aos seus vizinhos.
• Lembre-se de marcar os nós já visitados
• Você pode construir uma cerca sempre que o elemento na direção sendo explorada for diferente do elemento atual.
• Na parte 1, a área é igual a quantidade de elementos na mesma zona. Para calcular o perímetro, você precisa saber quantas barreiras colocou em cada posição.
• A parte 2 traz uma forma diferente de calcular o preço, mas o problema é bem parecido com a parte 1. Agora, você precisa olhar todas as barreiras da zona e verificar quantas são linhas e colunas contíguas.
• Você pode organizar as linhas pela coordenada y de suas cercas. Linhas contíguas terão o mesmo valor na coordenada y. Se ordenadas adequadamente, o segmento seguinte será o próximo com uma posição em x apenas 1 elemento maior que a anterior. Desta forma, você consegue contar as linhas contíguas.
• As colunas seguem o mesmo princípio, mas agora você precisa ordenar as cercas pela coordenada x. Da mesma forma, uma coluna é contígua se o próximo segmento está na linha seguinte.
• É mais fácil organizar os dados se as cercas horizontais e verticais estiverem separadas.

Quanto de Python você precisa saber?

Os capítulos se referem ao meu livro Introdução à Programação com Python.

The eleventh day of Advent of Code was yesterday 11/12/2024! If you’re here for the first time today, don’t forget to read the posts about Day 1, Day 2, Day 3, Day 4, Day 5, Day 6, Day 7, Day 8, Day 9 and Day 10.

I classified the eleventh problem as easy (part 1) and medium (part 2).

Tips

• Both part 1 and part 2 use the same rules to generate stones.
• A stone 0 becomes a stone 1
• A stone with an even number of digits becomes two stones
• If it doesn’t fall into any of these conditions, the stone value is multiplied by 2024.
• Stone generation in part 1 is quite interesting and easy to implement.
• The problem provides several test values that you should use to validate your functions
• You can use any of the answers for part 1.
• Part 2 is complex because there isn’t enough space to store so many stones. There are hundreds of trillions of stones, storing each one in a list element isn’t practical.
• In part 2, remember that the goal is to calculate the number of stones, not the value of the stones themselves.
• When a stone has an even number of digits, it generates two stones. All other values generate only one stone. If you consider this property, you can increment the stone counter without storing all stones.

How much Python do you need to know?

The chapters refer to my book Introduction to Programming with Python.

O décimo primeiro dia do Advent of Code foi ontem 11/12/2024! Se você caiu aqui hoje pela primeira vez, não deixe de ler os posts sobre o Dia 1, Dia 2, Dia 3, Dia 4, Dia 5, Dia 6, Dia 7, Dia 8, Dia 9 e Dia 10.

Classifiquei o décimo primeiro problema como fácil (parte 1) e médio (parte 2).

Dicas

• Tanto a parte 1 quanto a parte 2 usam as mesmas regras para gerar as pedras.
• Uma pedra 0 vira uma pedra 1
• Uma pedra com número par de dígitos vira duas pedras
• Se não entrar em nenhuma dessas condições, o valor da pedra é multiplicado por 2024.
• A geração das pedras na parte 1 é bem interessante e fácil de implementar.
• O problema traz vários valores de testes que você deve utilizar para validar suas funções
• Você pode usar qualquer uma das respostas para a parte 1.
• A parte 2 é complexa porque não há espaço suficiente para guardar tantas pedras. São centenas de trilhões de pedras, guardar cada uma em um elemento da lista não é interessante.
• Na parte 2, lembre que o objetivo é calcular o número de pedras, não o valor das pedras em si.
• Quando a pedra tem um número par de dígitos, ela gera duas pedras. Todos os outros valores geram apenas uma pedra. Se você considerar esta propriedade, você pode incrementar o contador de pedras sem guardar todas as pedras.

Quanto de Python você precisa saber?

Os capítulos se referem ao meu livro Introdução à Programação com Python.