DEV Community: Maurício Antunes

Solving "Minimum Genetic Mutation" leetcode

Maurício Antunes — Thu, 25 Jul 2024 03:07:32 +0000

Hello! Today, we are going to solve Minimum Genetic Mutation on leetcode.

This challenge uses some concepts we've already talked in other posts: BFS (Breadth-First Search), brute force, sets, and finding the minimum using BFS.

The Challenge

Given a gene string that is 8 characters long, containing only the letters A, C, G, and T, find the minimum mutations needed to change the initial gene into a target gene.

For example, changing "AACCGGTT" to "AACCGGTA" is one mutation.

One of the constraints of the exercise is the bank. The bank is a list of valid mutations. To go from the start gene to the end gene and count how many mutations are needed, we must ensure every mutation is valid.

Note that the starting point is assumed to be valid, so it might not be included in the bank.

Our first approach

Seems easy, right? We just need to check the difference in both genes. We don't need this bank.

Let's implement this approach:

def count_mutations(str1, str2):
    mutations = sum(1 for a, b in zip(str1, str2) if a != b)
    return mutations

This code:

Iterates through both strings using zip;
Returns 1 if a char in startGene differs from endGene;
Sum all the ones.

Try this approach and run the tests on leetcode. It passes!

Now, submit the code. It didn't run, right? You will try to cover edge cases until you have no energy and understand that this challenge is not about differences; it is about paths.

Take a look at one of the examples where our simple code breaks:

startGene = "AACCTTGG"
endGene = "AATTCCGG"
bank = ["AATTCCGG","AACCTGGG","AACCCCGG","AACCTACC"]

Output: 4
Expected: -1

It fails because there is no way to change one letter at a time from start gene to end gene while using only valid mutations.

Let's visualize the problem with a simple diagram:

A better approach

Now we know the bank must be used, let's try a correct approach to solve the problem.

Read the challenge description again. Focus on the highlighted parts like minimum, valid, and starting point.

They all suggest that we need a code that:

Ends as soon as we reach the target;
Checks if our moves are valid;
Has a starting point to iterate from to reach the target.

Bread-First Search (BFS) is excelent for finding the shortest or minimum path needed to go from one position to another.

Implementation

Here is the code we are going to explain in detail:

from collections import deque

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        bank = set(bank)

        queue = deque([(startGene, 0)]) # gene, changes

        if endGene not in bank:
            return -1

        while queue:
            gene, changes = queue.popleft()
            if gene == endGene:
                return changes

            for i in range(len(gene)):
                for c in "ACGT":
                    attempt_gene = gene[:i] + c + gene[i+1:]
                    if attempt_gene in bank:
                        queue.append((attempt_gene, changes + 1))
                        bank.remove(attempt_gene)

        return -1

First, we convert our bank in a set to perform O(1) lookups:

bank = set(bank)

Since we need to check if every mutation is valid, turning the bank into a set is the best approach.

Then, we create our queue. In Python, we can initialize the queue with some values. Our starting point is startGene with a total of mutations that starts from zero.

queue = deque([(startGene, 0)])

Remember I said this challenge is about paths? With this in mind, we know we need to keep track of the paths we visited, or the genes we already checked, so we don't end up in an infinite loop.

And now the most complex part:

while queue:
    gene, changes = queue.popleft()
    if gene == endGene:
        return changes

    for i in range(len(gene)):
        for c in "ACGT":
            attempt_gene = gene[:i] + c + gene[i+1:]
            if attempt_gene in bank:
                queue.append((attempt_gene, changes + 1))
                bank.remove(attempt_gene)

while queue ensures we iterate our queue until it has genes.

Everytime we pop one node from the queue, we check if it is equal to our target, endGene.

gene, changes = queue.popleft()
    if gene == endGene:
        return changes

Then we have two nested for loops. They are necessary because we want to replace one letter at a time and check if the mutation is valid. The first loop iterates through the current string, and the second loop tries to replace the current index with A, C, G, or T.

for i in range(len(gene)):
    for c in "ACGT":
        attempt_gene = gene[:i] + c + gene[i+1:]
        if attempt_gene in bank:
            queue.append((attempt_gene, changes + 1))
            bank.remove(attempt_gene)

If the gene is in the bank we add it to the queue as a valid mutation (or a path).

We also remove it from the bank, so we don't need to check it again to avoid adding it back to the queue, which would cause an infinite loop.

Complexity

Time: it is O(b) where b is the bank size.
It is a little tricky, but the reason is that a gene string has a limit of 8 characters. When measuring time complexity we need to drop the constant, no matter how big they are. In our case, the constants are 8 and 4: genes are 8 characters long and we might have ending up replacing each letter by A, C, G or T. 8 * 4 = 32

Space: it is also O(b) where b is the bank size.
We use a queue that can store, in the worst case, all genes from the bank.
There is also the set we use to keep track of visited genes that can contain up to b genes.

Resolvendo o "Rotting Oranges"

Maurício Antunes — Thu, 18 Jul 2024 23:08:00 +0000

Hoje a leitura é sobre como resolver o leetcode Rotting Oranges

Vamos passar por como resolver o problema, como entender algumas palavras-chave da descrição e o código da solução em Python.

O problema

Em uma matriz m x n, cada uma das posição pode ter três valores:

0 - uma posição vazia;
1 - uma laranja fresquinha;
2 - uma laranja podre.

A cada minuto, uma laranja fresca que está perto de uma podre vai apodrecer também.

Precisamos retornar o número de minutos passados até que todas laranjas estejam podres, ou -1 caso não seja possível ter todas elas apodrecidas.

Pensando no problema

Pra ajudar na resolução do problema, é fundamental que a gente consiga visualizar a disposição dessa matriz com algumas laranjas posicionadas:

Com essa disposição, quantos minutos demoraria para todas ficarem podres?

A) 5
B) 3
C) 4

Talvez eu tenha decepcionado você, mas a resposta não é 4 nem 5.
Algumas pessoas pensam que é 4 porque parece ser o maior caminho, se partir da laranja podre que fica embaixo. Outras pessoas pensam que é 5 porque é o número total de laranjas frescas.

Demoram 3 minutos pra que todas as laranjas fiquem podres.

O racional por trás é que a cada minuto mais de uma laranja pode ficar podre. Ou seja, as laranjas vão ficando podre simultaneamente. Guarde bem essa palavra.

Essa matriz é um grafo. Sim, matrizes são grafos. É possível codificar em uma matriz um grafo.

E no que saber isso muda? Primeiramente, isso facilita nossa compreensão sobre o problema. Nosso objetivo é dizer quanto tempo demora até todas laranjas ficarem podres, tentando conectar os pontos (laranjas podres e laranjas frescas). Problemas onde temos conexões entre pontos em uma matriz têm cheiro de grafo.

Há duas maneiras bem famosas de resolver problemas com grafos: DFS (Depth-First Search) e BFS (Breadth-First Search).

Pra esse problema, vamos usar BFS. A motivação tem a ver com a palavra simultaneamente. Quando usamos DFS pra resolver um problema, usamos stack. E uma stack é uma estrutura de dados usada em recursão. Quando usamos recursão, nós esgotamos a possibilidade de um caminho antes de testar outras opções, o que impede que seja simultâneo.

Diferente da stack, uma deque vai nos ajudar a procurar as laranjas simultaneamente.

Nesse problema, por exemplo, usar recursão contaria o caminho partindo de uma única laranja podre, contando de forma errônea.

Passos do algoritmo

Contar quantas laranjas frescas temos. Enquanto elas forem apodrecendo, quando chegar a ZERO, podemos usar isso como condição de parada.
Coletar as posições das laranjas podres. A razão é que, sabendo onde elas estão, podemos usar BFS para iterar em todas as laranjas podres simultaneamente.
Caminhar em todas direções, exceto nas diagonais, tentando achar novas laranjas para apodrecer.

Código da solução

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        minutes = 0

        queue = deque()
        fresh = 0

        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if grid[row][col] == 2:
                    queue.append((row, col))
                elif grid[row][col] == 1:
                    fresh += 1

        deltas = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        while queue and fresh:
            length = len(queue)

            for _ in range(length):
                row, col = queue.popleft()

                for dr, dc in deltas:
                    next_row, next_col = row + dr, col + dc

                    if (
                        next_row in range(len(grid))
                        and next_col in range(len(grid[0]))
                        and grid[next_row][next_col] == 1
                    ):
                        grid[next_row][next_col] = 2
                        queue.append((next_row, next_col))
                        fresh -= 1
            minutes += 1

        return minutes if fresh == 0 else -1

Apesar do código ser um pouco longo (resolução de problemas de grafo costumam ter bastante código), ele não é tão complexo. Pelo menos não dá aquela sensação de ter que tirar um coelho da cachola por linha.

Começamos com algumas variáveis importantes:

Uma deque pra BFS;
minutes pra guardar o resultado final;
E fresh pra contar quantas laranjas frescas temos.

Agora contamos quantas laranjas frescas temos e quais são as laranjas podres:

for row in range(len(grid)):
    for col in range(len(grid[0])):
        if grid[row][col] == 2:
            queue.append((row, col))
        elif grid[row][col] == 1:
            fresh += 1

Agora vem um bloco ligeiramente complexo:

deltas = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while queue and fresh:
    length = len(queue)

    for _ in range(length):
        row, col = queue.popleft()

        for dr, dc in deltas:
            next_row, next_col = row + dr, col + dc

            if (
                next_row in range(len(grid))
                and next_col in range(len(grid[0]))
                and grid[next_row][next_col] == 1
            ):
                grid[next_row][next_col] = 2
                queue.append((next_row, next_col))
                fresh -= 1
    minutes += 1

deltas é uma variável pra guardar todas as direções nas quais podemos caminhar. Em uma matriz m x n podemos caminhar uma coluna a esquerda, uma linha abaixo, etc.

while queue and fresh garante nossa condição de parada. Enquanto a gente tiver laranjas pra adicionar e ainda ter laranjas frescas, precisamos continuar procurando laranjas podres para que elas apodreçam todas as outras que estão ao alcance.

Agora vem a parte mais tricky: o for dentro do while.
Ele é essencial para que a gente conte os minutos das laranjas podres simultaneamente.

Você pode fazer o teste aí. Abra um interpretador do Python, importe o deque, crie uma deque e comece a remover os elementos da esquerda e adicionando à direita.

O for garante que a gente itere, por exemplo, na primeira vez, todas as laranjas podres e continue a seguir a mesma estratégia pras próximas. Se no próximo loop a gente enfileirar mais 3 laranjas podres, vamos iterar nessas 3 laranjas que vão adicionar mais n laranjas, e assim por diante.

Agora mais um for. Esse iterando em todas as direções:

for dr, dc in deltas:
    next_row, next_col = row + dr, col + dc

    if (
        next_row in range(len(grid))
        and next_col in range(len(grid[0]))
        and grid[next_row][next_col] == 1
    ):
        grid[next_row][next_col] = 2
        queue.append((next_row, next_col))
        fresh -= 1

E a condição do meio é extremamente importante:

Confere se ainda estamos caminhando dentro da matriz - colunas e linhas válidas;
Confere se a posição atual é uma laranja e é fresca.

Se positivo, adicionamos ela na queue de laranjas podres e diminuímos a contagem de laranjas frescas.

Sem esquecer de atualizar o valor pra 2, pois garante que não adicionemos a laranja podre de volta na nossa queue.

E, pra finalizar, retornamos o valor de minutos:

return minutes if fresh == 0 else -1

Se ainda tiver laranjas frescas, então não foi possível apodrecer todas, retornando -1. Se não, retornamos o número de minutos passados.

Conclusão

Complexidade de tempo: O(m x n)
Precisamos iterar o board inteiro pra descobrir as laranjas, porém, apenas uma vez cada linha/coluna.

Complexidade de espaço: O(m x n)
Usamos uma queue que, no pior caso, vai ter uma matriz inteira cheia de laranjas podres.

Não é porque tem vários loops aninhados que a complexidade de tempo é quadrática. É preciso analisar, linha por linha, o que o código faz.

Esse desafio não é simples e eu demorei algumas horas pra concluir. E esse não foi o código final. Ao todo eu tentei submeter oito vezes na plataforma leetcode.

Resolvendo o "Five sort"

Maurício Antunes — Thu, 23 May 2024 23:17:45 +0000

O objetivo desse post é demonstrar como eu pensei e solucionei o desafio citado usando uma técnica chamada two pointers.

Desafio

Dado um array de números inteiros, mova os números 5 para o final dele. Exemplo: [1, 5, 2, 5, 3]
Como resultado, espera-se o seguinte retorno da função: [1, 3, 2, 5, 5] ou [2, 1, 3, 5, 5]. O importante é que os 5 estejam no final do array.

Abordagem

Há várias maneiras de resolver esse problema. Muitas pessoas deram ótimas soluções nessa thread no Twitter.

Vou abordar nesse texto uma forma mais profunda de ver o problema além do código.

Uma das maneiras de abordar esse problema é removendo todos os 5 da lista original, adicioná-los em outros lista e concatenar no final (lista1 + lista2). Ou remover da lista e adicionar no final.

Não é uma solução ruim, porém, ela tem uma alta complexidade de tempo. Toda vez que você remove um item de um array e ele não é o último, o array precisa ser rearranjado. Isso significa que toda remoção vai adicionar N passos adicionais na sua solução.

Uma abordagem interessante pro problema é usar a técnica two pointers, assumindo que podemos modificar o array in-place, ou seja, modificar o valor do array que, em Python, por exemplo, é mutável.

A técnica se baseia em ter dois ponteiros para fazer comparações em diferentes partes do array, enquanto se move e aplica todas as operações necessárias para resolver o problema.

Nossa abordagem irá comparar os elementos do início com os do fim do array. Com um exemplo de dois elementos ([5, 1]) fica mais fácil. Começando o algoritmo, comparamos o primeiro valor com o último. O primeiro é 5, então movemos ele pro fim, trocando pelo 1, resultando em [1, 5].

Vamos adicionar dois valores [5, 5, 1, 3].
Primeiro e últimos trocam, pois o primeiro é 5. Movemos os dois ponteiros, trocando 5 e 1 também, resultando em [3, 1, 5, 5].

Abaixo uma demonstração visual (com texto alternativo) do problema sendo resolvido:

Nosso algoritmo se baseia em comparar os elementos do array em direção ao meio do dele. Enquanto o ponteiro i for menor que o ponteiro j, nós continuamos a comparar os elementos e trocando quando for necessário.

Código

A nossa implementação vai usar Python, uma linguagem muito utilizada em resolução de algoritmos, tanto em plataformas quanto leetcode quando em entrevistas de emprego.

def five_sort(nums):
  i, j = 0, len(nums) - 1

  while i < j:
    if nums[j] == 5:
      j -= 1
      continue

    if nums[i] == 5:
      nums[j], nums[i] = 5, nums[j]
      j -= 1

    i += 1

  return nums

Passos do algoritmo:

Começamos os ponteiros nas pontas (começo e fim);
Respeitamos nosso caso base de iterar até que os ponteiros não tenham se encontrado;
Quando o 5 já está no fim do array, apenas decrementamos o j para que continuemos a avaliar os outros números;
Quando o 5 é encontrado no ponteiro i, precisamos fazer a troca com o número do ponteiro j;
Retornamos a lista modificada in-place.

Complexidade

Tempo: O(n)

Independente de quantos elementos tem o array, no pior caso precisamos iterar em todos elementos.

Espaço: O(1)

Nenhum espaço adicional é alocado. Como fazemos a modificação in-place, não há a criação de um array adicional.

Solving "Minimum time to make rope colorful"

Maurício Antunes — Sat, 30 Dec 2023 14:22:38 +0000

Today we're diving into a challenging problem: Minimum time to make rope colorful.

Understanding the problem

In this challenge, we are presented to a rope with some balloons on it. Alice, the owner of the balloons, does not like when the rope has consecutive balloons of the same color.

Each balloon has a different time (in seconds) to remove.

The goal is to remove the minimum number of balloons to ensure no two consecutive balloons are of the same color.

Visualizing the challenge

Look at the image below to better understand our task:

Initial arrangement of balloons: green(1), blue(2), blue(4), red(3).

Which one do you think we need to remove?

In this setup, the best choice is to remove the second balloon (blue, 2 seconds).

For the rope to be colorful in the best time, we need to remove the balloons that takes less time.

After removal, the arrangement looks like this:

Arrangement after optimal removal: green(1), blue(4), red(3).

Approaching the solution

One of the difficulties of this problem is that the optimal solution relies on a technique we don't often use daily: greedy algorithm.

Before explaining how greedy algorithms work, let's write down how we decide which balloons we remove.

Algorithm steps

What are the necessary steps to find the minimum time to make the rope colorful?

One reason this problem is challenging is the difficulty in identifying the underlying pattern. Many problems can be solved by first considering the appropriate data structure — for instance, using Depth-First Search (DFS) for graph problems or recursion for binary tree problems. However, this particular challenge requires a different approach.

Iterate over the balloon sequence (a string is a sequence).
Start from the second balloon to easily compare it with the first.
When encountering balloons of the same color, remove the one taking less time.
Keep track of the maximum time spent on a single balloon removal.
Sum up the time for each removal to get the total time.
If the current balloon is a different color, reset the maximum time to the current balloon's time.

This approach highlights the importance of making local optimal choices at each step, a hallmark of greedy algorithms.

Greedy algorithm explained

Being "greedy" in this context means making the best immediate choice at each step without reconsidering previous choices. This differs from strategies like backtracking, where you might revisit past decisions.

In this problem, a "sequence" of same-colored balloons forms our local problem. By determining the minimum time to remove balloons in each sequence, we find the overall solution.

Solution

Below is the Python code that solves the problem. Pay close attention to the part of the code that checks if the balloons are the same color and how we calculate the minimum time.

class Solution:
    def minCost(self, colors: str, neededTime: List[int]) -> int:
        min_time = 0
        max_time_in_sequence = neededTime[0]

        for idx in range(1, len(colors)):
            if colors[idx] == colors[idx - 1]:
                min_time += min(max_time_in_sequence, neededTime[idx])
                max_time_in_sequence = max(max_time_in_sequence, neededTime[idx])
            else:
                max_time_in_sequence = neededTime[idx]

        return min_time

Efficiency analysis: time and space complexity

Time complexity: O(N) where N is the length of the colors string (or neededTime). This is because our solution involves a single for loop that iterates each color exactly once.

Space complexity: O(1). It is because we don't use any extra additional memory. Our solution uses a fixed amount of space, the variables min_time and max_time_in_sequence, which remain constant regardless of whether the number of colors is 1 or 100.

It's important to note that when calculating space complexity, we do not consider the space used by the input itself.

Conclusion

In this article, we learned how to solve the challenge "Minimum Time to Make Rope Colorful" and apply greedy algorithm using a greedy algorithm. We also explored how to determine when a greedy approach is the most effective strategy.

Keys points of this article include:

Iterating through the balloon sequence starting from the second balloon, allowing for a straightforward comparison between adjacent balloons:

for idx in range(1, len(colors)):

Calculating the minimum time for removal when encountering balloons of the same color:

min_time += min(max_time_in_sequence, neededTime[idx])
max_time_in_sequence = max(max_time_in_sequence, neededTime[idx])

Resolvendo "Grupo de Anagramas"

Maurício Antunes — Wed, 27 Dec 2023 18:01:24 +0000

Hoje vamos resolver mais um leetcode. E, dessa vez, o desafio escolhido é o Grupo de Anagramas

Nesse desafio, precisamos agrupar os diferentes anagramas passados como entrada da função.

Um anagrama é uma palavra que é formada a partir das letras de uma outra palavra. Por exemplo: alegria e alergia e regalia. Todas essas palavras são anagramas.

O desafio é agrupar todos os anagramas. A entrada da função terá uma lista de diferentes palavras que podem ou não ser anagramas. Esse agrupamento deve ser uma lista de listas.

Exemplo do site:

Input: ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Escrevendo o algoritmo

Esse é um problema de nível médio, o que significa que a solução não vem tão fácil. Muitas dessas questões tem diversas soluções, e o que difere elas é uma menor complexidade te tempo/espaço e, também, ciclomática.

Vamos dividir o problema em partes:

Iterar sobre a lista de palavras;
Para cada palavra, vamos calcular a chave desse anagrama (já vamos explicar o que é isso que chamei de chave);
Usaremos essa chave para agrupar os anagramas;
Agruparemos os anagramas em um dicionário, que casa com o conceito de ter uma chave. O valor de cada chave será uma lista de anagramas;
Retornaremos apenas os valores do dicionário, que vai ser uma lista de listas.

Calculando a chave

O cálculo da chave é essencial pra esse algoritmo. Ela vai servir para agruparmos as palavras que são anagramas.

O desafio tem uma limitação de que as palavras são todas minúsculas, o que facilita nosso algoritmo.

A chave é construída calculando quais letras são similares em cada palavra. Vamos usar como exemplo as palavras amor e roma:

A M O R
R O M A

{"A": 1, "M": 1, "O": 1, "R": 1}

Exemplo em imagem:

Ignorando a ordem das letras de ambas as palavras, teremos dicionários com as mesmas chaves e valores, o que nos leva a anagramas.

Existe uma forma mais fácil de calcular essa chave.
As palavras são formadas apenas por letras minúsculas, então temos 26 possibilidades de letras e ocorrências delas, correto?

Come essa informação em mente, podemos criar uma lista de 26 posições e, para cada posição ordinal da letra, incrementar o número de ocorrências dela.

>>> alphabet = [0] * 26
>>> key = ord("m") - ord("a")
>>> alphabet[key] += 1
>>> alphabet
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Ao repetir esse algoritmo, obteremos um array com a quantidade de cada letra. Para as palavras propostas, o array será o mesmo, resultando na nossa chave.

Escrevendo o código

A solução do problema em Python:

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = defaultdict(list)
        for word in strs:
            alphabet = [0] * 26 # 26 letters, a to z
            for letter in word:
                alphabet[ord(letter) - ord("a")] += 1
            anagrams[tuple(alphabet)].append(word)

        return anagrams.values()

Explicando o código em partes:

O defaultdict é essencial para salvar as palavras em grupos. Um agrupamento nesse caso é uma lista de valores associados a uma chave.
Iteramos na lista de palavras;
Para cada palavra, criamos uma lista do alfabeto, que será nossa chave;
Incrementamos a posição ordinal de cada letra;
Usamos esse valor como chave do dicionário anagrams;
A chave é convertida pra tupla porque em Python a chave precisa ser um valor hasheable.

Observe o uso de append no dicionário. Essa instrução só funciona porque estamos usando defaultdict, que nos economiza criar uma lista vazia quando a chave do dicionário ainda não existe.

E, por fim, retornamos os valores do dicionário, a lista de lista com as palavras agrupadas.

Complexidade de tempo e espaço

Tempo: A pior complexidade de tempo desse algoritmo é percorrer a lista de palavras e, para cada palavra, percorrer todas as letras dela. Isso gera uma complexidade O(N X M) onde N é o número de palavras e M é o número de letras de cada uma das palavras.

Espaço: A complexidade de espaço é um pouco mais difícil de definir. É O(N), onde o N pode variar entre ser o tamanho da lista do alfabeto (26 posições) ou o tamanho do anagrama. Quanto mais palavras no input, maior vai ser o tamanho do dicionário de palavras agrupadas.

Conclusão

Eu acredito que esse desafio é considerado de nível médio porque é necessário ter um momento de inspiração pra entender que a chave que falamos anteriormente é um ponto crucial pra solução do problema.

Espero que você tenha aprendido algo novo com esse texto, e eu gostaria muito de ter seu feedback nos comentários.

Solving "Binary Tree Paths"

Maurício Antunes — Sat, 23 Dec 2023 16:35:20 +0000

Today I'm going to explain how to solve "Binary Tree Paths" problem.

Given the root of a binary tree, return all root-to-leaf paths in any order.

A leaf is a node with no children.

A binary tree is a data structure characterized by nodes, each having either none or a maximum of two children: left and right. Each connection between nodes is called an edge, and the paths from the root to the leaves are simple known as path.

Take a look at the image below as an example of a binary tree used in the problem. It illustrates a binary tree and its components:

For this problem, we need to identify and return a list of all the paths in any order.



Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]

In the example, there are two paths, both starting from the root and extending to the leaf nodes.

A leaf node is one that has no children. In this tree, numbers 5 and 3 are leaves as they have no outgoing connections.

How do we traverse this binary tree, discover the paths, and return them as the challenge requires?

Reasoning

First, let's explore how we might approach this without any specific strategy or computational methods. Initially, you start from the root and follow each path to its end, choosing at each step either left or right. You note down each path on paper and proceed to the next until all paths are explored.

With this intuitive approach in mind, let's transition to formulating the algorithm in Python.

Traversing

Understanding how to traverse the binary tree is a crucial part of the algorithm. There are two primary methods: depth-first (DFS) and breadth-first (BFS) search.

DFS is employed when you need to explore one branch of the tree thoroughly before backtraking. On the other hand, BFS is utilized when you need to visit each level of the tree sequentially before backtracking.

Writing the algorithm

This challenge, although considered easy, contains nuances especially for those new to binary trees and traversal methods.

Use depth-first search algorithm to traverse the tree;
In each recursion call, concatenate the current path to the path passed in the initial call;
As you move left and right, continue concatenating this path with an arrow;
The recursion base happens upon encountering a leaf node.

Why recursion?

Recursion is particularly suitable for problems involving binary tree due to its capability to handle a problem one step at a time. In a binary tree, each node often branches into two smaller subtrees (if they exist), which reminds us of step-by-step approach added to the call stack.

No need to maintain a stack to traverse the tree;
No need to implement a branching and backtracking mechanism - recursion handles this for us;
Recursion and branching walk side-by-side.

Coding

Here is the Python code to solve it:



class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        if not root:
            return []

        paths = []

        def dfs(node, path):
            if not node:
                return

            path += str(node.val)

            if not node.left and not node.right:
                paths.append(path)
                return

            if node.left:
                dfs(node.left, path + "->")

            if node.right:
                dfs(node.right, path + "->")

        dfs(root, "")

        return paths

Let's check what this code does in details.

Base case: we handle empty trees as they are valid binary trees. If there is no root (root is None), we return immediately.



if not root:
    return []

DFS

Our main call starts the recursive function from the root with an empty variable for the path.



dfs(root, "")

Base case: this check is similar to our initial base case. For instance, after examining node 5, we see that both left and right are None, signaling the end of this path. Subsequently, each of these recursive calls starts unwinding the stack (backtracking).



if not node: 
    return

Path building: here, we concatenate the current node's value to the path. This step is crucial as it builds the representation (a string) of the path from the root to the current node.



path += str(node.val)

Reaching the path's end: a leaf node is defined as one without children. Upon finding a leaf, we append the path to our list of paths and return, allowing other recursive calls to execute.



if not node.left and not node.right:
    paths.append(path)
    return

Recursive calls: if the current node has a left child, we call dfs recursively on the left child. The right node follows the very same process.



if node.left:

    dfs(node.left, path + "->")

if node.right:

    dfs(node.right, path + "->")

Time and space complexity

When discussing time complexity in our solution, we observe that for each node in the binary tree, a string concatenation operation is performed. In Python, strings are immutable, each concatenation results in the creation of a new string. This leads to an O(N²) operation at each node, where N represents the number of nodes in the tree.

As for space complexity, it is primarily impacted by the creation of multiple string objects resulting from these concatenations (O(N)).

We can do better!

One of the pain points of our solution is string concatenation. In Python, strings are immutable, so everytime you concatenate a string, it creates a new string including the content of both strings.

Understanding the nuances of the programming language in use is vital, as different languages handle string concatenation differently.

Challenge for the reader

Your challenge is to modify the code to avoid string concatenation. After making these changes, evaluate the performance of the revised approach in terms of time and space complexity. Share your findings here in the comments section.

Solving "Word Search" problem

Maurício Antunes — Mon, 18 Dec 2023 00:17:09 +0000

Recently, I attempted to solve "Word Search" leetcode

"Word Search" is a game that the objective is to find a specific word (or even multiple words).

In this post I'll explain in detail how to tackle this problem.

Take a look at this image showing the word "LIFE" in a grid:

How do we solve this problem? How can we write code to search for this word efficiently?

Reasoning

Before delving into complex topics like graphs, depth-first search (DFS), and backtracking, let's consider how we solve word searches in real life.

Initially, we try to locate the first letter of the word, quickly scanning all the letters. Then, we follow the subsequent letters to see if they form the word, checking in all directions but only one at a time.
Then, we follow the next letters in order to check if we find the word. But in which direction? All of them, but one at a time.

In short:

Locate the first letter (L in this case);
Attempt to find the word by following all the letters to the right;
If we don't find, we try all the letters below, and so on.

With this approach in mind, we can move on to the next part.

Writing the algorithm

Let's describe the algorithm in simple terms to clarify our thoughts, almost as if talking about them out loud.

Here are the steps:

Iterate the grid (each row and column);
If grid[row][col] matches the first letter of our word, start searching for the remaining letters from there;
Use depth-first search algorithm;
In each DFS call, check if the current letter is the next one in the word;
If not, return False;
If it matches, continue searching for the other letters;
When the word is found, return True.

Here is the Python code to solve it:



class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(row, col, index):
            if len(word) == index:
                return True

            # check if we don't surpass the grid
            row_outbounds = row < 0 or row >= len(board)
            col_outbounds = col < 0 or col >= len(board[0])

            if row_outbounds or col_outbounds:
                return False

            wrong_letter = board[row][col] != word[index]

            if wrong_letter:
                return False

            letter = board[row][col]
            # mark visited
            board[row][col] = "#"

            # dfs in all directions
            if (dfs(row - 1, col, index + 1) or 
                dfs(row, col + 1, index + 1) or 
                dfs(row + 1, col, index + 1) or 
                dfs(row, col - 1, index + 1)):
                return True

            # not found, unmark
            board[row][col] = letter
            return False


        # iterate over the grid
        for row in range(len(board)):
            for col in range(len(board[0])):
                if board[row][col] == word[0]:
                    if dfs(row, col, 0):
                        return True

        return False

Let's dive deeper into the code.

This code iterates over the grid, and when it finds the first letter of the word, it starts a search for the subsequent letters. The index parameter plays a crucial role, as explained below.



for row in range(len(board)):
    for col in range(len(board[0])):
        if board[row][col] == word[0]:
            if dfs(row, col, 0):
                return True

return False

dfs is our recursive function used to traverse the grid in search of the next letters of the word. We increment index each time we find a matching letter. For instance, if we find the letter "L," it corresponds to index zero in the array ["L", "I", "F", "E"].



def dfs(row, col, index):
    if len(word) == index:
        return True

    # check if we don't surpass the grid
    row_outbounds = row < 0 or row >= len(board)
    col_outbounds = col < 0 or col >= len(board[0])

    if row_outbounds or col_outbounds:
        return False

    wrong_letter = board[row][col] != word[index]

    if wrong_letter:
        return False

This code also ensures we avoid 'out of range' errors:



row_outbounds = row < 0 or row >= len(board)
col_outbounds = col < 0 or col >= len(board[0])

And here, we check if the current letter is correct:



wrong_letter = board[row][col] != word[index]
if wrong_letter:
    return False

Here is what I find to be the most challenging aspect of this solution: traversing the board recursively.

We save each letter because we need to mark its row and column as visited. Why is this important? It prevents the algorithm from retraversing the same path. In the code, we accomplish this by setting an arbitrary character (in this case, "#") at the position. After exploring all possible paths from this position, we 'unmark' the cell by restoring the saved letter. This step is crucial because it returns the board to its original state, allowing subsequent calls of the dfs function to use this letter for other potential paths.



letter = board[row][col]
# mark visited
board[row][col] = "#"

# dfs in all directions
if (dfs(row - 1, col, index + 1) or 
    dfs(row, col + 1, index + 1) or 
    dfs(row + 1, col, index + 1) or 
    dfs(row, col - 1, index + 1)):
    return True

# not found, unmark
board[row][col] = letter

return False

Additionally, it's important to note that we execute the dfs function four times, each call moving in a different direction (up, right, down, left).

Time and space complexity

Understanding the time and space complexity is essential to evaluate the performance of your solution.

Measuring time complexity of "Word Search" is not an easy task. We can describe it as O(R * C * 4 ^ L) where:

R = number of rows in the grid;
C = number of columns in the grid;
4 = reflects the four directions (up, down, right, left) from each cell;
L = length of the word.

We can simplify it to O(N ^ 2 * 4 ^ L) where N is the larger of the number of rows or columns in the grid (thank you @viglioni )

As you can see, it is not so efficient.

Space complexity of the solution is O(L) because L is the max recursion depth we need to explore all the possibilies before finding the word (or unwinding the stack when it does encounter a wrong letter).

Conclusion

In this article, we explored a detailed solution to the "Word Search" problem, employing a depth-first search (DFS) approach. By breaking down the problem into manageable steps and translating these into Python code, we've demonstrated a practical application of graph traversal algorithms in solving complex problems.

Finding the largest value in each tree row

Maurício Antunes — Tue, 24 Oct 2023 23:13:03 +0000

Recently, a friend sent me an intriguing challenge: finding the largest value in each row of a binary tree. It is a hard but rewarding problem to solve. Understanding how to navigate data structures is crucial.

This tree is a binary tree. In this post we will understand what is a binary tree and how to solve the proposed problem.

What is a binary tree?

A binary tree is a tree formed by nodes. A tree might have zero nodes, or just one. The first node of a tree is called root, and the last one is called leaf. A binary tree, just like a real tree, might have many branches, known as children. Children are nodes with parents, and leaves are nodes without children. Every node might have zero, one or two children.

Let's visualize it:

Every circle in the diagram above represents a node. A node is composed by the following attributes:

Value (a.k.a key)
Left node
Right node

The binary in binary tree means you can go to either left or right. If you could represent a node using Python, you would end up having the following class:

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Can you see how the Node class compares to the visual representation of a node?

Finding the largest value in each tree row

Looking at the tree, we know that the largest values are: 1, 3 and 7.

We could traverse every row of the tree, save every largest value in a list and return it in the end. But finding the largest value in each row is not an easy task.

Notice we just used the word traverse. Traversing is the act of iterating over the nodes of the tree. We can do it using two techniques: depth first search (DFS) and breadth first search (BFS).

Let's explore both techniques in detail:

Depth first search

In depth first search, you find a node in the tree and keep traversing the tree in that direction to the end (leaves). To implement this technique, we will need to use a stack

def dfs(root):
    if not root:
        return []

    stack = [root]
    values = []

    while stack:
        curr_node = stack.pop()
        values.append(curr_node.val)

        if curr_node.right:
            stack.append(curr_node.right)

        if curr_node.left:
            stack.append(curr_node.left)

    return values

Since trees might be empty (or have no nodes), we first check if the root node is present before proceeding. Otherwise we add the root to the stack and traverse the tree until this stack is not empty.

Every round of the while loop we add the value of the current node to the list and add the left and right nodes to the stack if they exist.

First we add root (1) value to list
Then we find a right node (3) and add it to the stack
We also found a left node (2) and add it to the stack

Ok, now it is one of the most important parts: why are we adding the right node first?

It is very common to traverse a binary tree from left to right. Since we are using a stack, we always pop the last element. Our stack looks like this in the first iteration: [right, left]
If we pop from this stack, we always get the left position before right.

Breadth first search

In breadth first search we visit every left and right node of the tree in the same iteration - this is why it has breadth in the name.

We use this technique when we want to traverse the binary tree by row.

The code is very similar to the depth first search, except we use a queue

Since we want to iterate each row, we use a queue and the popleft function - it pops the first element of the structure.
Imagine we have the following queue: [1, 10, 20, 30]. When we perform a popleft operation, the queue becomes [10, 20, 30].

from collections import deque

def bfs(root):
    if not root:
        return []

    queue = deque([root])
    values = []

    while queue:
        curr_node = queue.popleft()
        values.append(curr_node.val)

        if curr_node.left:
            queue.append(curr_node.left)

        if curr_node.right:
            queue.append(curr_node.right)

    return values

First we add root (1) value to list
Then we find a left node (2) and add it to the queue
We also found a right node (3) and add it to the queue
Then we pop left the queue and we get the node with value 2 and add it to the list, it is now [1, 2]
And we, again, add the left and right nodes to the queue
But we still have the 3 in the queue. Next iteration we will append it to the list, and so on

Solving the problem

Which algorithm you think should be used to get the largest value from each row of the tree? Think about the tree below:

If we use depth first search, we will get all the values in a vertical way, right? In a depth first traversal, we move down the tree before considering siblings. But when finding the largest value in a row, we need to consider all nodes at the same depth before moving deeper, which aligns more with a horizontal traversal.

What about breadht first search? It seems the right technique.

Let's implement this, but first we will reason about the steps:

Create a queue and add the root to it
While we have elements in the queue we:
- Determine the current size of the queue, representing the number of nodes in the current row
- And iterate N times to get all the values from the row
- For each node in the current row, compare its value with the current maximum value (initialized as negative infinity).
- Compare and define the new max value
- Every time we end this iteration, we add the max value to the list of largest values

And the code is as follows:

from collections import deque

def largest_values(root):
    if not root:
        return []

    queue = deque([root])
    largest = []

    while queue:
        size = len(queue)
        max_val = float("-inf")

        for i in range(size):
            curr_node = queue.popleft()

            if curr_node.val > max_val:
                max_val = curr_node.val

            if curr_node.left:
                queue.append(curr_node.left)

            if curr_node.right:
                queue.append(curr_node.right)

        largest.append(max_val)

    return largest

For the provided example tree, this code will return the list [1, 3, 9]

Solving these challenges is a matter of reading and practicing. With practice, choosing the right data structures and techniques for a given problem becomes more and more intuitive.

Quem mexeu no meu cache?

Maurício Antunes — Sun, 16 Oct 2022 11:43:30 +0000

O objetivo desse texto é mostrar como um erro de configuração no cache da sua aplicação pode trazer problemas sérios que vão desde uma dor de cabeça até a perda de dinheiro.

O que é caching?

Caching é uma estratégia utilizada para obter dados de forma mais rápida em uma aplicação. Nossa memória recente é uma espécie de cache, pois não precisamos fazer um grande esforço mental pra lembrar.

Se você está pensando em usar alguma forma de cache na sua aplicação, provavelmente você está com alguma parte da sua aplicação executando devagar, por exemplo. Cache pode ajudar sua aplicação de diversas maneiras, até como mecanismo de resiliência.

Errando na configuração do cache

É possível degradar de forma severa uma aplicação ao configurar o cache de maneira errada. Alguns tipos de aplicação são extremamente dependentes de cache, como serviços de storage e multimídia, como transmissão de áudio e vídeo pela internet.

Para o exemplo deste artigo, vamos usar exemplos usando Ruby e um servidor web famoso, o NGINX.

Vamos falar de dois tipos de ataque que podem acontecer nos seus servidores.

Minha aplicação caiu porque o cache não funcionou!

Cache que não funciona é muito comum, principalmente quando sites usam CDNs externas e as pessoas envolvidas não têm conhecimento de como um erro de configuração pode derrubar a aplicação.

Vamos supor que você seja dev de um site que contenha várias imagens de produtos, com boa resolução e você adicione caching para que o seu serviço de imagens não seja acionado toda requisição. Essa é uma ótima ideia e há expectativas de que ela vai melhorar a performance da aplicação. Porém, a configuração que você fez coloca os parâmetros da query string como parte da chave de cache.

Chave de cache (cache key) é um hash formado a partir de variáveis especificadas pela configuração das diretivas do servidor. Essa chave é uma maneira de mapear um valor para um hash md5 que vai ser alocado em um grande mapa, de rápido acesso, no seu servidor

O que pode dar errado? Essa imagem abaixo exemplifica requests que furam o cache ao usar parâmetros quaisquer na query string.

Podemos representar isso com código Ruby, criando funções que definem as chaves de cache, similares às configurações que podemos fazer no NGINX:

require 'digest'

# Esse é o nosso cache
cache = {}

# Uma lista de requests a serem feitos
reqs = [
  '/airfy.jpg',
  '/airfy.jpg',
  '/airfy.jpg',
]

# Nossa função que define a cache key de acordo com 
# o valor passado
def good_cache_key_hash(value)
    # Divide a string por "?" e remove o "/"
    key = value.split('?')[0].slice(1, value.size)
    Digest::MD5.hexdigest key
end

# Valida que todos os paths vão usar a mesma chave de cache
puts(reqs.map { |req| good_cache_key_hash(req) })

# Agora vamos ter uma nova lista de requests maliciosos (ou não)
reqs = [
  '/airfy.jpg?foo=1',
  '/airfy.jpg?foo=2',
  '/airfy.jpg?foo=3',
]

# Nossa função que define a cache key de acordo com 
# o valor passado mas dessa vez ela não foi pensada corretamente
def bad_cache_key_hash(value)
    key = value
    Digest::MD5.hexdigest key
end

# Valida que todos os paths vão usar chaves diferentes, 
# mesmo que as imagens sejam exatamente as mesmas
puts(reqs.map { |req| bad_cache_key_hash(req) })

O resultado fica como a seguir:

43eb6cb76f885b82fbfef92cbee4acd1
43eb6cb76f885b82fbfef92cbee4acd1
43eb6cb76f885b82fbfef92cbee4acd1
9a03b0f4730f70964c01f97355823f20
b0affdcb74f872918bb795937f98feaa
0082e52c9b5e1613888e1a26bbc96f37

Observe que os 3 primeiros valores são iguais, provando que a chave será a mesma. Entretanto, os próximos três requests estão com os valores diferentes, mesmo que a imagem seja a mesma.

O que podemos concluir? Que nosso cache vai ficar furado por uma má definição do hash computado que é usado para mapear requests aos nossos valores.

Às vezes vejo uma air fry, às vezes um liquidificador

Você já entrou em um site que a imagem ficava trocando, sem ter um motivo muito óbvio? Provavelmente muitos objetos estão apontando pra mesma cache key.

Esse caso acima está relacionado a um erro de configuração que vai fazer todas as URLs de imagem do seu site apontarem pro mesmo arquivo. Como?

Lembra que a cache key é o hash md5 que aponta qual lugar do mapa de objetos vai ser consultado? Então, nesse caso a cache key apontou qualquer URL para o mesmo lugar. A primeira requisição trouxe airfry.jpg e fez cache. As requisições subsequentes vão sempre trazer a imagem da airfry, até que o tempo de cache termine e faça a imagem expirar.

O exemplo abaixo um Ruby mostra que uma chave de cache mal definida pode fazer todos os objetos apontarem pro mesmo hash:

# Esse é o nosso cache
cache = {}

# Agora vamos supor que nós deixamos passar que nossa cache key
# foi definida usando a extensão da imagem. Isso é totalmente
# possível quando você usa variáveis erradas ou define
# uma função de cache e não testa ela corretamente
def wrong_cache_key(value)
  # pega a extensão do caminho passado
  key = value.split(".").last
  Digest::MD5.hexdigest key
end

# Uma lista de requests a serem feitos
reqs = [
  '/airfy.jpg',
  '/liquidificador.jpg',
  '/airfy.jpg',
]

# Valida que todos as chaves são a mesma
puts(reqs.map { |req| wrong_cache_key(req) })

O resultado fica como a seguir:

c36bbd258b7ee694eb987221b2b197b0
c36bbd258b7ee694eb987221b2b197b0
c36bbd258b7ee694eb987221b2b197b0

Testando as requisições em um servidor web

Foi criado o projeto https://github.com/mauricioabreu/my-cache-haz-a-problem que contém o código do web server e os exemplos didáticos criados para o texto.

Cache key com query string

Aqui demonstramos o caso em que usar a query string como cache pode degradar sua aplicação:

curl -v "http://localhost:8080/items/airfry.jpg?foo=1"

< HTTP/1.1 200 OK
< Content-Length: 101321
< X-Cache-Status: MISS

Uma boa estratégia de cache ignoraria esses parâmetros na chave de cache. Um segundo request com os parâmetros foo=2 deveria retornar HIT

HIT - objeto encontrado no cache
MISS - objeto não encontrado no cache. Uma requisição ao upstream será realizada, o objeto será baixado e cacheado.

curl -v "http://localhost:8080/items/airfry.jpg?foo=2"

< HTTP/1.1 200 OK
< Content-Length: 101321
< X-Cache-Status: MISS

Imagine essa informação nas mãos erradas?

Não é um erro formar a cache key com parâmetros da query string. Um exemplo bom é se o seu site renderiza imagens com tamanhos predefinidos, como /products/airfry.jpg?width=300&height=250. Esses parâmetros podem ser usados e vão aumentar a performance do seu cache.

Cache key errada

Usar a cache key errada pode deixar as pessoas usuárias do seu site infelizes ao receber sempre a mesma imagem:

curl -v http://localhost:8080/products/airfry.jpg

< HTTP/1.1 200 OK
< Content-Length: 101321
< X-Cache-Status: MISS

O primeiro request está OK. O estado do cache é MISS, ainda não existia no cache e foi resgatado do nosso storage.

Vamos requisitar a imagem de um liquidificador.

curl -v http://localhost:8080/products/liquidificador.jpg

< HTTP/1.1 200 OK
< Content-Length: 101321
< X-Cache-Status: HIT

Aqui observamos duas coisas estranhas: o tamanho e o X-Cache-Status. Muita coincidência o tamanho da imagem liquidificador ter o exato mesmo tamanho da imagem da air fry, não é? Além disso, como uma imagem que nunca requisitamos trouxe um estado de HIT? Isso aconteceu porque a chave de cache foi baseada, erroneamente, na extensão da requisição, jpg

Solucionando os problemas

Uma das maneiras mais simples de resolver os problemas apresentados é usar a cache key padrão do NGINX, que é $scheme$proxy_host$request_uri. Em detalhe:

Scheme - HTTP/HTTPS
Proxy host - host e porta do endereço do storage (ou do upstream usado)
Request URI - URI original com os parâmetros da query string

Algumas dicas:

Use a cache key default quando puder;
Verifique suas cache keys antes de colocar seu site em produção;
Colete métricas de uso do cache. Quanto mais requests com HIT, melhor vai ser seu cache hit ratio.

Evil icons created by Smashicons - Flaticon

Um pouco sobre streaming de vídeo ao vivo

Maurício Antunes — Fri, 19 Aug 2022 16:16:09 +0000

Motivado pela dica do @leandronsp sobre assuntos técnicos, trago nesse artigo uma introdução a vídeo ao vivo. Atualmente trabalho no time de vídeo ao vivo da Globo, uma das maiores empresas de mídia da América Latina.

Vídeo ao vivo tem temperado a web há mais de década. Nossas conexões ficaram mais rápidas e nossa vontade de ver vídeo com mais qualidade aumentou com o passar do tempo. A experiência ao assistir vídeo foi ficando cada vez melhor à medida que as pessoas ficaram mais exigentes: buscamos o melhor áudio, melhor imagem e sem falhas nem buffering.

Pra entender um pouco da complexidade que envolve uma transmissão de vídeo ao vivo, vamos voltar um pouco e entender como chegamos até aqui.

Um pouco do passado

Em 1996, a Macromedia inventou o protocolo RTMP (Real-Time Messaging Protocol) destinado a envio de vídeo, áudio e dados. O intuito do protocolo era garantir uma rápida performance e um padrão pra envio de dados em tempo real, e que esses dados pudessem ser decodificados por um player, o Flash.

Embora exista muita piada em cima do término do Flash, o Flash foi por mais de duas décadas um ótimo player de vídeo, tendo sido base para algoritmos de encoding/decoding futuramente

O fato de muitos sites de streaming do passado exigirem a instalação de Flash não era à toa. RTMP era o protocolo usado pelas empresas. O player conectava em uma URL diretamente no servidor que estava recebendo o vídeo e as pessoas assistiam diretamente do servidor, usando RTMP diretamente. Mesmo sem Flash atualmente, você pode usar um player como VLC para tocar uma transmissão ao vivo RTMP.

Como funciona?

Protocolos, players, encoding e decoding. Ok, mas pra que tudo isso?

Uma transmissão ao vivo passa por muitas etapas antes de chegar no seu dispositivo tocador de vídeo.

A partir de agora alguns termos em inglês vão ser utilizados pela falta uso das mesmas em português.

Ingest

A fonte do vídeo é a primeira etapa. É nela que definimos qual o modo de captura do vídeo e pra onde vamos publicar a transmissão. O software OBS ficou muito famoso por ser usado por gamers que fazem streaming na Twitch/Facebook/Youtube. O que essas pessoas estão fazendo é o ingest do vídeo.

Há outras formas de publicar um vídeo. É possível usar o ffmpeg como fonte e publicar em um endereço RTMP ou HTTP.

Encoding

Essa etapa vai depender muito de como o produto de vídeo aborda o ingest. Quando a fonte é um OBS, apenas um input é enviado para um servidor e, lá nesse serviço, o vídeo passa por um processo de encoding que acaba criando várias qualidades do seu vídeo, para que ele possa ser assistido por diferentes dispositivos e, também, para que sua rede de internet se adapte melhor às qualidades oferecidas. Redes de computadores sofrem degradações diárias que fazem com que seu vídeo não toque na melhor qualidade, pois isso o produto deve pensar nesses casos de uso.
O processo de oferecer mais de uma qualidade de vídeo é essencial para o bom funcionamento da tecnica ABR (Adaptive Bitrate Streaming), usada para escolher a melhor experiência para o player de vídeo e, consequentemente, pra você.

A etapa de encoding pode ser diferente quando a entrada de vídeo é um SDI (Serial Digital Interface). SDI é uma interface (cabo) usado para trafegar os dados de uma câmera para o encoder. É usando um SDI que eventos ao vivo de grande porte são transmitidos. A fonte do vídeo passa pelo cabo, sem nenhum tipo de codificação, e vai pro encoder processar. No encoder a pessoa técnica terá como escolher como o vídeo vai ser processado (codec de vídeo, codec de áudio, resolução, de metadata e outras dezenas de opções).

Packaging

Essa etapa é onde o vídeo é empacotado em diferentes formatos. Todo player de vídeo precisa saber como ler uma URL de um vídeo e tocar o conteúdo descrito nela. É aqui que entram protocolos como HLS e DASH e também os segmentos de vídeo. O processo de empacotar um vídeo é sobre como os segmentos (chunks, que são pedacinhos do vídeo) são criados e como eles são organizados, que são os manifestos de vídeo (também chamados de playlists).

Uma playlist é uma forma de descrever as qualidades de vídeo oferecidas pela plataforma e, também, os chunks oferecidos por essas playlists.

Delivery

Nos primórdios de streaming de vídeo, apenas uma qualidade era ofertada e a escalabilidade da plataforma era complexa e custosa.

Atualmente, a entrega de vídeo precisa ser rápida e melhor localizada. Quanto mais perto o servidor estiver de você, melhor vai ser sua experiência. Diferente de acessar um site, os dados trafegados em um vídeo são muito maiores do que páginas web que acessamos no dia a dia, e não temos como tomar vantagem do cache local pois o vídeo muda, enquanto as folhas de estilo ou scripts de uma página não.

Para ter uma entrega mais adequada, a plataforma de vídeo precisa saber como entregar o servidor mais perto da pessoa assistindo. Estamos falando de CDNs (Content Delivery Network), que são redes de entrega de conteúdo que contém inteligência de roteamento e cache para entregar uma experiência personalizada e com menos latência.

Outro ponto importantíssimo sobre CDNs é caching. Servidores que entregam o conteúdo são protegidos com camadas de cache que reduzem o impacto nos servidores de conteúdo, fazendo com que o mesmo arquivo possa ser requisitado com muito menos latência e resiliência.

Play

A parte inicial de um vídeo é o play. Plataformas de streaming têm e evoluem seus próprios players à medida que features vão sendo adicionadas e codecs de vídeo novos precisam ser suportados. A melhora da experiência só é possível se todas as etapas estiverem alinhadas.

Para o player isso não é diferente. Players precisam estar aptos para tocar o conteúdo entregue pela CDN, caso contrário, seu vídeo nem começará a tocar. E, para estar apto, o player deve possuir suporte ao decoding dos segmentos de vídeo.

Essa é uma breve introdução sobre vídeo. No próximo, vamos nos aprofundar melhor em alguns termos como codec, CDN, player, buffering, etc.

Uma das camisetas aqui da Globo é essa, descrevendo as etapas pra entregar vídeo ao vivo

Uma introdução ao NGINX

Maurício Antunes — Sat, 21 May 2022 12:25:27 +0000

Volta e meia leio de algumas pessoas que NGINX (engine X) é complicado. Eu não vou mentir: não é algo simples de se entender e usar de primeira. Primeiramente, não é fácil entender qual a finalidade dele. É um servidor, mas o que ele faz? Como é usado?

NGINX é um servidor que pode ser usado de diversas maneiras, tais como: load balancer (balancear requests para os servidores de aplicação), proxy reverso (receber um request da internet e repassar para outro servidor ou serviço) e uma das capacidades mais fantásticas do NGINX, na minha opinião, é sua finalidade como cache.

Uma generosa parte da internet roda sobre NGINX e alguns segmentos bem importantes usam ele como principal servidor, como plataformas de streaming, aplicações de larga escala tais como lojas, redes sociais e, também, é usado como base de muitas CDNs.

Porque usar NGINX?

Talvez você já tenha se perguntado: porque eu deveria usar NGINX? Não é mais fácil só apontar o DNS para vários IPs?
Isso é possível, mas você não vai ter a robustez de apontar seu DNS para um load balancer que pode balancear seus requests de uma forma mais inteligente, com o apoio de healthcheck caso seus servidores de aplicação não estejam respondendo e de algoritmos de balanceamento, implementando o modelo correto de distribuição de requests.

Se você já compreende o básico e apenas quer olhar uma configuração escrita com containers rodando uma solução, o repositório de exemplo. Ele está dividido em tags mostrando a evolução das partes do texto.

Vamos criar nossa primeira configuração, bem básica, com apenas uma rota que sempre retorna 200:



worker_processes auto;

events {
  worker_connections 1024;
}

http {
  server {
    listen 80;

    location / {
      return 200;
    }
  }
}

Vamos usar Docker com a ajuda do Docker Compose:



services:
  nginx:
    image: nginx:alpine
    volumes:
      - ./nginx.conf:/etc/nginx/nginx.conf
    ports:
      - "8080:80"

Testando nossa rota:



curl -v http://localhost:8080

< HTTP/1.1 200 OK
< Server: nginx/1.21.6
< Content-Type: text/plain
< Content-Length: 0
< Connection: keep-alive

Nossa rota funcionou. Ela retorna 200 como esperado.

Vamos entender o que essa configuração faz, focando apenas no bloco http. O bloco http é chamado de contexto, assim como o events, e ambos está em um contexto chamado main

server - é um bloco designado a escrever as configurações de um servidor dentro da sua configuração. Você pode ter vários deles, cada um atendendo em uma porta diferente. Você pode expor um servidor para o mundo e ter outro interno, sem cache, por exemplo, ou até driblando a autenticação, por exemplo.
listen - aqui você define em qual porta seu servidor vai aceitar as conexões. Note que o docker-compose.yml exporta a 80 como 8080 para o host, por isso o request é feito na 8080 (porta 80 do container).
location - é a diretiva usada para definir as rotas. Elas são bem poderosas. Aceitam expressões regulares, é possível capturar as variáveis e usá-las na configuração. O sistema de location, também, conta com diferentes tipos de match.
- Sem modificador, o match é feito pelo começo da URI
- = é um match exato
- ~ é um match com expressão regular

Esses são os modificadores que mais usei até hoje.

Nossa location faz match com qualquer URI que comece com /, ou seja, qualquer uma como /compras, /produtos/lista, etc.

Podemos adicionar uma nova location com match exato.



location = /teste {
  return 200 "teste route";
}

location / {
  return 200;
}

Agora podemos notar que a rota /teste tem um body sendo respondido.



curl -v http://localhost:8080/teste

< HTTP/1.1 200 OK
< Server: nginx/1.21.6
< Content-Type: text/plain
< Content-Length: 11
< Connection: keep-alive
teste route

Vimos um pouco do básico da configuração, agora é hora de fazermos algo mais avançado.

Usando como proxy reverso

Uma definição simplista de proxy reverso é um request que você faz em algum endereço interno, como por exemplo http://meusite.com.br/minhaloja/produtos/1 e não sabendo pra onde exatamente esse request vai ser processado. E, após processado, o servidor de proxy reverso te manda o conteúdo da resposta do servidor de aplicação.

Vamos criar uma aplicação de teste que responde na porta 8081, mas que vamos acessar através do nosso NGINX.

A aplicação vai ser em Python usando Flask.



from flask import Flask

app = Flask(__name__)

@app.route("/")
def index():
    return "<p>Index page!</p>"

Modificamos nossa configuração do servidor para conter apenas a rota da aplicação. Agora com a adição da diretiva proxy_pass, que é usada para fazer do NGINX um servidor de proxy reverso.



server {
  listen 80;

  location / {
    proxy_pass http://app:8081;
  }
}

Observe que usamos o nome do serviço descrito (app) no docker-compose para referenciar o nome que a aplicação atende.



curl -v http://localhost:8080
< HTTP/1.1 200 OK
< Server: nginx/1.21.6
< Content-Type: text/html; charset=utf-8
< Content-Length: 18
< Connection: keep-alive
<p>Index page!</p>

Podemos ver que a resposta possui um header adicional (Content-Type), agora, além da resposta que veio da aplicação.

Como fazer proxy reverso pra múltiplos servidores?

A realidade de uma aplicação em produção, na grande maioria das vezes, é ter mais de um servidor pra servir ela. E isso se deve a inúmeros motivos. Servidores têm recursos finitos (placa de rede, disco, CPU) para atender muitas requisições. E não é apenas sobre isso. E se o servidor sofrer uma falha de hardware? Ou até alguma falha de rede? Inúmeros motivos podem fazer sua aplicação ficar sem um fallback pra esses casos.

É aí que entramos com a diretiva upstream do NGINX, usada para definir um conjunto de servidores usados para balancear sua aplicação.

Primeiramente, modificaremos nosso docker-compose para criar duas instâncias da aplicação. Para fins de exemplo, não usaremos a diretiva scale porque ela possui um balanceamento round robin, e queremos mostrar como usar a diretiva de upstream com múltiplos servidores de aplicação.



app_1:
  build: app
  ports:
    - "8081:8081"
  environment:
    - FLASK_RUN_PORT=8081
    - FLASK_RUN_HOST=0.0.0.0
app_2:
  build: app
  ports:
    - "8082:8081"
  environment:
    - FLASK_RUN_PORT=8081
    - FLASK_RUN_HOST=0.0.0.0

Vamos modificar nossa configuração para criar um upstream e colocar os dois hostnames da nossa aplicação:



upstream app {
  server app_1:8081;
  server app_2:8081;
  keepalive 100;
}

server {
  listen 80;

  location / {
    proxy_pass http://app;
  }
}

Definimos um upstream chamado app, e é esse nome que usamos na diretiva proxy_pass. Usar proxy_pass tem algumas vantagens em vez de usar o proxy_pass diretamente com um IP ou hostname:

Definir diferentes estratégias de balanceamento dos servidores de aplicação (algoritmos de balanceamento diferente com pesos diferentes para cada servidor);
Usar keepalive, um número inteiro do total de conexões TCP mantidas do NGINX com o servidor, evitando criar conexões TCP a todo request;
Resolução de DNS é feita quando o servidor sobe. Sem definir um upstream, um nome como google.com no proxy_pass vai gerar uma consulta de DNS por request. Em larga escala isso pode ser um gargalo (até para o DNS interno da sua empresa, caso exista).

A configuração que fizemos vai balancear os request de forma igual, 50% pra cada servidor. Olhando nos logs, podemos ver isso acontecendo na prática:



nginx-intro-nginx-1  | 192.168.144.1 - - [20/May/2022:16:33:48 +0000] "GET / HTTP/1.1" 200 18 "-" "curl/7.79.1"
nginx-intro-app_1-1  | 192.168.144.4 - - [20/May/2022 16:33:48] "GET / HTTP/1.0" 200 -
nginx-intro-nginx-1  | 192.168.144.1 - - [20/May/2022:16:33:50 +0000] "GET / HTTP/1.1" 200 18 "-" "curl/7.79.1"
nginx-intro-app_2-1  | 192.168.144.4 - - [20/May/2022 16:33:50] "GET / HTTP/1.0" 200 -
nginx-intro-nginx-1  | 192.168.144.1 - - [20/May/2022:16:33:53 +0000] "GET / HTTP/1.1" 200 18 "-" "curl/7.79.1"
nginx-intro-app_1-1  | 192.168.144.4 - - [20/May/2022 16:33:53] "GET / HTTP/1.0" 200 -
nginx-intro-nginx-1  | 192.168.144.1 - - [20/May/2022:16:33:55 +0000] "GET / HTTP/1.1" 200 18 "-" "curl/7.79.1"
nginx-intro-app_2-1  | 192.168.144.4 - - [20/May/2022 16:33:55] "GET / HTTP/1.0" 200 -

Agora, vamos dar uma olhada em como funciona o sistema de cache do NGINX.

Utilizando o NGINX como um servidor de cache

Muita da informação que consumimos não precisa, necessariamente, estar 100% atualizada a todo o instante. Se temos um arquivo estático como um script, uma foto ou um vídeo em nosso site, não precisamos ir buscar ou gerar esse conteúdo a todo momento. Podemos nos utilizar do NGINX como um servidor de cache em alguns passos, fazendo cache de diversos requests da sua aplicação.

Primeiro, vamos adicionar uma rota que trabalha com um parâmetro de query:



@app.route("/hello")
def hello():
    name = request.args.get("name", "nobody")
    return f"<p>Hello, {name}</p>"

Agora, vamos modificar o NGINX para ele fazer cache das respostas.



worker_processes auto;

events {
  worker_connections 1024;
}

http {
  proxy_cache_path /tmp/cache levels=1:2 keys_zone=app_cache:5m max_size=10m inactive=20m use_temp_path=off;

  upstream app {
    server app_1:8081;
    server app_2:8081;
    keepalive 100;
  }

  server {
    listen 80;

    location / {
      add_header X-Cache-Status $upstream_cache_status;
      proxy_cache app_cache;
      proxy_cache_valid 200 30s;
      proxy_cache_valid 404 1m;
      proxy_cache_key $host$uri$is_args$args;
      proxy_cache_lock on;
      proxy_pass http://app;
    }
  }
}

O que significa cada diretiva de proxy adicionada?

proxy_cache_path - descreve onde vamos guardar o cache. Os arquivos de cache são guardados em arquivos.
add_header - adiciona um header X-Cache-Status na resposta para que possamos depurar quando aconteceu MISS, HIT, etc.
- HIT - conteúdo veio diretamente do cache por estar válido, ainda.
- MISS - conteúdo não foi achado no cache e precisou ser buscado na origem.
proxy_cache - zona do cache. A mesma zona pode ser usada em outros lugares da configuração.
proxy_cache_valid - define um tempo de validade do cache para um código HTTP específico. Nossa aplicação não define um header Cache-Control, então, configuramos ele direto no NGINX.
proxy_cache_key - parâmetros usados para montar a chave de cache. Essa montagem de valores é extremamente importante para construir um cache seguro e eficiente.
proxy_cache_lock - impede que mais de um request vá na origem para buscar o mesmo conteúdo. Uma diretiva importante para proteger a origem do conteúdo. As conexões esperam até que o cache seja populado.

Conferindo o resultado, podemos fazer uma requisição pra rota nova:



curl -v "http://localhost:8080/hello?name=bento"



nginx-intro-nginx-1  | 192.168.176.1 - - [20/May/2022:22:04:51 +0000] "GET /hello?name=bento HTTP/1.1" 200 19 "-" "curl/7.79.1"
nginx-intro-app_1-1  | 192.168.176.4 - - [20/May/2022 22:04:51] "GET /hello?name=bento HTTP/1.0" 200 -
nginx-intro-nginx-1  | 192.168.176.1 - - [20/May/2022:22:04:55 +0000] "GET /hello?name=bento HTTP/1.1" 200 19 "-" "curl/7.79.1"
nginx-intro-nginx-1  | 192.168.176.1 - - [20/May/2022:22:04:57 +0000] "GET /hello?name=bento HTTP/1.1" 200 19 "-" "curl/7.79.1"
nginx-intro-nginx-1  | 192.168.176.1 - - [20/May/2022:22:04:58 +0000] "GET /hello?name=bento HTTP/1.1" 200 19 "-" "curl/7.79.1"
nginx-intro-nginx-1  | 192.168.176.1 - - [20/May/2022:22:04:59 +0000] "GET /hello?name=bento HTTP/1.1" 200 19 "-" "curl/7.79.1"
nginx-intro-nginx-1  | 192.168.176.1 - - [20/May/2022:22:06:05 +0000] "GET /hello?name=bento HTTP/1.1" 200 19 "-" "curl/7.79.1"
nginx-intro-app_2-1  | 192.168.176.4 - - [20/May/2022 22:06:05] "GET /hello?name=bento HTTP/1.0" 200 -

Observe como o primeiro request bate no NGINX e na app. Os requests em sequência não vão até a app porque eles estão usando o cache que orientamos o servidor a fazer.

Nos últimos dois requests é possível ver que o request foi pra outra instância da app porque passou os 30 segundos de validade que configuramos, garantindo que o cache precisa ser revalidado e que o balanceamento continua funcionando.

Próximos passos

Ao mesmo tempo que isso é o básico de NGINX é, também, o suficiente para você desbravar mais utilidades pra ele. É possível adicionar muita lógica de aplicação no NGINX que pode ajudar você a construir aplicações mais focadas na regra de negócio em vez de focar em balanceamento, cache, autorização, etc.

NGINX possui suporte a embutir código dinâmicamente, sendo as principais Lua e Javascript.

Construindo o seu próprio emulador, parte 1

Maurício Antunes — Sun, 24 Oct 2021 12:03:56 +0000

O que é um emulador?

Um emulador emula hardware em software. É uma técnica que habilita um computador imitar as características de outro hardware, como por exemplo, um video game. Existem emuladores famosos como o Project64 e o ZSNES, usados para emular os video games Nintendo 64 e Super Nintendo respectivamente.

Além de emular, um emulador pode ir adiante, providenciando uma maior performance, maior qualidade de vídeo e melhor gerenciamento de recursos como CPU e memória.

Por que aprender sobre emuladores?

Boa pergunta! Entender o básico de emuladores vai te proporcionar uma boa ideia de como computadores funcionam.

Emuladores são compostos de vários componentes de um computador, como uma memória, uma CPU, um teclado e um display. Cada um desses componentes tem suas características. O desenvolvimento de um emulador vai te ajudar a entender como um programa é carregado na memória (ROM, read-only memory), ou como as instruções do programa são interpretadas e executadas e como as informações são mostradas na tela.

Alguns requisitos são necessários para entender e construir um, como:

Conhecer alguma linguagem de programação;
Operações lógicas;
Deslocamento de bits (bit shifting).

Se você conhece uma linguagem de programação mas não entende sobre operações lógicas e operações de bit, não se preocupe, eu vou colocar referências de estudo e explicar as partes do código que falam sobre isso em detalhes.

O hello world! dos emuladores é o chip-8, e é ele que vamos construir.

Um pouco de base

Antes de começarmos a falar sobre o emulador que vamos construir, vamos relembrar ou aprender um pouco sobre dois assuntos que precisamos compreender para seguir este guia.

Binário e hexadecimal

Nosso sistema número mais comum é o sistema decimal. Isso quer dizer que temos do 0 ao 9 para formarmos outros números, como o 2, o 321, o 9825, etc. Depois do 9, para adicionarmos um número passamos o 9 para 0 e colocamos 1 à esquerda e teremos o 10. Computadores usam outros sistemas de números: binário e hexadecimal.

O sistema binário é constituído de 2 números, o 0 e o 1. Zero é 0, um é 1 e o 2 troca o 1 pra 0 e adiciona um 1 à esquerda. Contando em binário: 0, 1, 10, 11, 100, 101, 110, 111, 1000 (0, 1, 2, 3, 4, 5, 6, 7, 8).

O sistema hexadecimal conta com 16 símbolos. Isso provê uma maior compactação na representação de números maiores. Por exemplo o 15 é representado pela letra F. Quanto maior o número, mais isso fica perceptível.

Todas as instruções do chip-8 são analisadas de forma hexadecimal. A instrução de limpar a tela começa com 0x0 e a operação de desenhar é 0xD.

Lógica binária

Lógica binária opera em bits. Usamos para manipular valores e fazer comparações.

Algumas dessas operações você já pode conhecer, mas uma em especial é importante conhecer, o XOR. O XOR devolve 1 bit sempre que a quantidade de números 1 for ímpar:



 |  V1 |  V2 |  R  |
 +-----+-----+-----+
 |  0  |  0  |  0  |
 +-----+-----+-----+
 |  1  |  0  |  1  |
 +-----+-----+-----+
 |  0  |  1  |  1  |
 +-----+-----+-----+
 |  1  |  1  |  0  |
 +-----+-----+-----+

Você pode testar isso com alguma linguagem com REPL ou usando bash:



echo $((0 ^ 0))
0
echo $((0 ^ 1))
1
echo $((1 ^ 1))
0

Deslocamento de bits

Uma das razões do deslocamento de bits existir é a possibilidade de codificar informações importantes usando menos dados. O receptor da mensagem pode decodificar a mensagem, extraindo valores com significado.

As instruções do chip-8, por exemplo, são codificadas de 2 em 2 bytes, e cada byte pode ser dividido em 2 nibbles usando deslocamento de bits. Veremos isso em mais detalhes no próximo post, quando vamos aprender a decodificar as instruções da ROM.

Geralmente a primeira instrução de uma ROM é limpar a tela, a 00E0. Em binário isso seria 00000000 (00) e 11100000 (E0).

A tela é limpa quando o OpCode é 0 e o quarto nibble é 0. Vamos testar usando o REPL do Python:



>>> (0b00000000 >> 4) & 0xF // OpCode
0
>>> 0b11100000 & 0xF // quarto nibble chamado de N
0

A instrução de jump (0x1NNN) faz o código pular até a instrução de memória NNN.



0b11010 | 0b100101
1A      | 25

JUMP | 0xA25
0x1  | A25

0x1 é a operação de pular e A25 forma o NNN, o quarto, terceiro e segundo nibble dos dois bytes da instrução.

Veremos esse assunto em detalhes na parte 2.

O que é o chip-8?

O chip-8 é uma linguagem interpretada e, também, uma máquina virtual criada por Joe Weisbecker em 1977 para rodar no COSMAC VIP

A ideia do Joe era rodar pequenos programas e jogos com a ajuda de um teclado de hexadecimal. Em vez de usar linguagem de máquina, o teclado hexadecimal era usado para digitar instruções que seriam interpretadas.

Interpretadas? O correto não seria emuladas? Não. Nesse guia não vamos construir um emulador exatamente, mas sim um interpretador de instruções chip-8. Nosso interpretador vai ler instruções de uma ROM e executá-las uma a uma, em um loop de ler, decodificar e executar as instruções carregadas.

Mas qual a diferença entre interpretador e emulador nesse caso? O chip-8 é um programa que rodava em um computador. Um emulador imita hardware. Simular o chip-8 significa que vamos escrever uma máquina virtual que interpreta comandos via uma linguagem hexadecimal, porém, trazendo vários conceitos vistos em emulação e arquitetura de computadores como PC (program counter), stack, timers, RAM, ROM, etc.

O chip-8 é formado por diversos componentes. Abaixo vamos falar de cada um dos componentes de maneira breve.

Memória

O espaço de memória deve ser de 4kB (4096 bytes). Toda essa memória é volátil (RAM) e pode ser modificável.

Uma ROM deve começar começar a ser carregada a partir do endereço 0x200 (512 em decimal). Os endereços 0x000 até o 0x1FF são reservados para o chip-8, porém vamos construir ele usando nosso computador, então não precisamos nos preocupar com isso.

Registradores

Existem dois registradores: dados e de endereço.
Eles são usados para gerenciar dados no chip-8. Há várias operações como adição, subtração, leitura de valores, etc. Essas operações se tornam possíveis quando você tem registradores.

O registrador de dados é um array com 16 posições de valor inteiro de 8 bits sem sinal (u8). O endereço 0xF é normalmente usado para configurar uma flag (0 ou 1), que pode ser usado para indicar se houve colisão ao desenhar no display.

O registrador de endereço não é um array, mas sim uma espécie de ponteiro. Ele é chamado de index e é usado para ler e escrever na memória. O registrador de endereços, chamado de I, também é usado para desenhar as fontes no display, que serão configuradas através de uma das instruções contidas na ROM.

Display

Com as dimensões de 64 pixels de largura e 32 pixels (64x32) de altura, o display é usado para renderizar na tela toda atualização identificada pela instrução de draw (DXYN) que veremos adiante.

No chip-8, os pixels são valores booleanos, 0 ou 1, on ou off, 0x0 ou 0x1. Os displays eram monocromáticos (preto e branco), porém, quando chegar a hora você vai poder usar diferentes cores para os pixels. O display começa com todos os pixels off.

Em desenvolvimento você pode, em vez de escrever na tela usando alguma engine de gráficos, escrever no STDOUT para conferir se o programa está desenhado da maneira correta.

Teclado

O teclado do COSMAC VIP tem 16 teclas, por isso é chamado de hex keypad. Não vamos construir o teclado, mas precisamos saber que ele existe e que algumas instruções do chip-8 esperam por uma tecla a ser pressionada.

Ao construir seu chip-8 você não precisa seguir esse layout. O layout que usei é como mostrado abaixo:



╔═══╦═══╦═══╦═══╗
║ 1 ║ 2 ║ 3 ║ 4 ║
╠═══╬═══╬═══╬═══╣
║ Q ║ W ║ E ║ R ║
╠═══╬═══╬═══╬═══╣
║ A ║ S ║ D ║ F ║
╠═══╬═══╬═══╬═══╣
║ Z ║ X ║ C ║ V ║
╚═══╩═══╩═══╩═══╝

Se o seu teclado não é no layout QWERTY, tudo bem, você pode mapear outras teclas ou até deixar isso configurável.

Stack

A stack é uma área de memória relacionada a sub-rotinas que podem ser chamadas durante a execução da ROM.
Como o próprio nome já diz, isso é uma stack. Se a sua linguagem de programação suporta o uso de stacks, use-a para maior legibilidade.

Os valores guardados nessa stack são de 16 bits.

Em Rust, os vectors possuem as funções push e pop:



let mut stack: Vec<u16> = Vec::new();
stack.push(0xF);
stack.pop();

Existe uma limitação no chip-8 de 12 a 16 endereços de memória, porém, não precisamos nos preocupar com isso, deixando o tamanho da stack ilimitada.

Fontes

O chip-8 vem com fontes pré-determinadas. Isso significa que existe na memória do chip-8 sprites que são basicamente números e letras no intervalo hexadecimal: 0 a F. Cada uma dessas representações tem 4 pixels de largura e 5 pixels de altura.

Guarde essas fontes em uma área de memória antes do 0x200 que falamos acima. Por algum motivo ficou popular gravar a partir do 0x50. É possível definir e carregar as fontes usando um código similar ao debaixo:



static FONTS: [u8; 80] = [
    0xF0, 0x90, 0x90, 0x90, 0xF0, // 0
    0x20, 0x60, 0x20, 0x20, 0x70, // 1
    0xF0, 0x10, 0xF0, 0x80, 0xF0, // 2
    0xF0, 0x10, 0xF0, 0x10, 0xF0, // 3
    0x90, 0x90, 0xF0, 0x10, 0x10, // 4
    0xF0, 0x80, 0xF0, 0x10, 0xF0, // 5
    0xF0, 0x80, 0xF0, 0x90, 0xF0, // 6
    0xF0, 0x10, 0x20, 0x40, 0x40, // 7
    0xF0, 0x90, 0xF0, 0x90, 0xF0, // 8
    0xF0, 0x90, 0xF0, 0x10, 0xF0, // 9
    0xF0, 0x90, 0xF0, 0x90, 0x90, // A
    0xE0, 0x90, 0xE0, 0x90, 0xE0, // B
    0xF0, 0x80, 0x80, 0x80, 0xF0, // C
    0xE0, 0x90, 0x90, 0x90, 0xE0, // D
    0xF0, 0x80, 0xF0, 0x80, 0xF0, // E
    0xF0, 0x80, 0xF0, 0x80, 0x80, // F
];

for (n, font) in FONTS.iter().enumerate() {
    machine.memory[0x50 + n] = *font;
}

Existe uma instrução (FX29) que guarda o endereço da fonte a ser desenhada. Então, a instrução de desenhar vai usar esse valor de memória para escrever a fonte na tela.

Timers

O chip-8 conta com 2 timers (temporizadores): delay timer e sound timer.

Ambos timers são decrementados numa taxa de 60khz até chegar a zero. Ao chegar em zero, cada um terá seu evento interrompido e a contagem recomeça.

O delay timer é usado para sincronizar eventos.
O sound timer vai tocar um som (beep) enquanto o valor for maior que zero.

Os dois timers podem ser inicializados como um inteiro de 8 bits sem sinal (u8).



if self.delay_timer > 0 {
    self.delay_timer -= 1;
}

if self.sound_timer > 0 {
    self.sound_timer -= 1;
}

No próximo post vamos abordar, em detalhes, a codificação do chip-8 usando a linguagem Rust, entendendo como decodificar as instruções e executar as operações.