Escrito por: Preethi Kasireddy

Imperativo x Declarativo, Puro x Impuro, Estático x Dinâmico.

Terminologias como essas são salpicadas por várias publicações em blogs de programação, palestras em conferências, artigos e livros didáticos.

Porém, você não deve se deixar intimidar por esse vocabulário. Vamos examinar e desvendar alguns desses conceitos para que você possa entender sobre o que todos esses desenvolvedores ao seu redor estão falando.

Tipagem estática x dinâmica

Isso se trata de quando a informação de tipo é adquirida — seja no momento da compilação ou em tempo de execução.

Você pode usar essa informação de tipo para detectar erros de tipo. Um erro de tipo ocorre quando um valor não é do tipo esperado.

Verificação de tipo estática

É o processo de verificar a segurança de tipo de um programa com base na análise do código-fonte do programa. Em outras palavras, a verificação de tipo ocorre no momento da compilação, permitindo que erros de tipo sejam detectados mais cedo.

Verificação de tipo dinâmica

O processo de verificar a segurança de tipo de um programa em tempo de execução. Com a verificação de tipo dinâmica, os erros de tipo ocorrem em tempo de execução.

Tipagem forte x fraca

É importante observar que forte x fraca não tem um significado técnico sobre o qual todos universalmente concordam. Por exemplo, mesmo que Java seja tipado estaticamente, toda vez que você usa reflexão ou cast, você está adiando a verificação de tipo para a execução.

Da mesma maneira, a maioria das linguagens fortemente tipadas ainda converterá automaticamente entre inteiros e ponto flutuante. Portanto, você deve evitar usar esses termos porque chamar um sistema de tipagem "forte" ou "fraca", por si só, não diz muito.

Tipagem forte

Em uma linguagem fortemente tipada, o tipo de uma construção não muda — um int é sempre um int e tentar usá-lo como uma string resultará em um erro.

Tipagem fraca

Tipagem fraco significa que o tipo de uma construção pode mudar dependendo do contexto. Por exemplo, em uma linguagem de tipagem fraca, a string "123" pode ser tratada como o número 123 se você adicionar outro número a ela.

Isso geralmente significa que o sistema de tipos pode ser subvertido (invalidando quaisquer garantias) porque você pode converter um valor de um tipo para outro.

Dados mutáveis x imutáveis

Dados imutáveis

Quando um objeto não pode ser modificado após sua criação, você pode dizer que ele é "imutável", que é outro modo de dizer "inalterável". Isso significa que você alocará um novo valor para cada alteração.

Dados mutáveis

Quando você pode modificar um objeto após sua criação, ele é "mutável". Quando você tem uma referência a um objeto mutável, por exemplo, o conteúdo do objeto pode mudar.

Funções puras x impuras

Funções puras

Uma função pura tem duas qualidades:

1. Ela depende apenas da entrada fornecida — e não de nenhum estado externo que possa mudar durante sua avaliação ou entre chamadas.
2. Ela não causa nenhum efeito colateral semanticamente observável, como modificar um objeto global ou um parâmetro passado por referência.

Funções impuras

Qualquer função que não atenda a esses dois requisitos para uma função pura é "impura".

Avaliação lenta x avaliação rápida

Avaliação lenta

A avaliação lenta não avalia os argumentos da função a menos que seus valores sejam necessários para avaliar a própria chamada da função.

Em outras palavras, as expressões são avaliadas apenas quando ocorre a avaliação de outra expressão que depende da expressão atual.

A versão lenta das avaliações permite que os programas calculem estruturas de dados que são potencialmente infinitas sem travar.

Avaliação rápida

A avaliação ávida — também conhecida como avaliação estrita — sempre avalia completamente os argumentos da função antes de invocar a função. Em outras palavras, uma expressão é avaliada assim que é vinculada a uma variável.

Declarativo x imperativo

Programação declarativa

Programas declarativos expressam um conjunto de operações sem revelar como são implementadas ou como os dados fluem através delas. Eles se concentram em "o que" o programa deve realizar (usando expressões para descrever a lógica) em vez de "como" o programa deve alcançar o resultado.

Um exemplo de programação declarativa é o SQL. As consultas SQL são compostas por instruções que descrevem como deve ser o resultado de uma consulta, enquanto abstraem o processo interno de como os dados são recuperados:

SELECT EMP_ID, FIRST_NAME, LAST_NAMEFROM EMPLOYEES WHERE CITY = ‘SAN FRANCISCO’ ORDER BY EMP_ID;

Aqui está um exemplo de código declarativo:

Programação imperativa

A programação imperativa concentra-se em descrever como um programa deve alcançar um resultado usando instruções que especificam o fluxo de controle ou alterações de estado. Ela usa uma sequência de instruções para calcular um resultado.

Aqui está um exemplo de código imperativo:

Com estado x sem estado

Um estado (em inglês, state) é uma sequência de valores calculados progressivamente, que contém os resultados intermediários de um cálculo.

Com estado

Programas com estado (do inglês., stateful) têm algum mecanismo para acompanhar e atualizar o estado. Eles têm alguma memória do passado e lembram transações anteriores que podem afetar a transação atual.

Sem estado

Programas sem estado (do inglês, stateless), por outro lado, não acompanham o estado. Não há memória do passado. Cada transação é realizada como se estivesse sendo feita pela primeira vez. Programas stateless darão a mesma resposta para o mesmo pedido, função ou chamada de método — todas as vezes.

Funcional x orientada a objetos

Funcional

A programação funcional é um paradigma que enfatiza o uso de funções. O objetivo da programação funcional é usar funções para abstrair fluxos de controle e operações em dados, evitando efeitos colaterais.

Então, a programação funcional usa funções puras e evita dados mutáveis, o que, por sua vez, fornece transparência referencial.

Uma função tem transparência referencial quando você pode substituir livremente uma expressão por seu valor e não mudar o comportamento do programa. Dito de um modo um pouco diferente: para uma determinada entrada, ele sempre retorna os mesmos resultados.

Alguns exemplos de linguagens que enfatizam a programação funcional incluem Haskell, Lisp, Clojure e Elm. Você pode, contudo, usar conceitos de programação funcional na maioria das linguagens, incluindo em JavaScript.

Orientada a objetos

O paradigma de programação orientada a objetos enfatiza o uso de objetos. Isso resulta em programas que são feitos de objetos que interagem entre si. Esses objetos podem conter dados (na forma de campos ou atributos) e comportamento (na forma de métodos).

É um estilo de particionamento (ou encapsulamento) do estado de um programa através de objetos para tornar a análise do efeito das mudanças tratável [1].

Além disso, programas orientados a objetos usam herança e/ou composição como seus principais mecanismos para reutilização de código. Herança significa que uma nova classe pode ser definida em termos de classes existentes especificando apenas como a nova classe é diferente. Representa um relacionamento "é um" (por exemplo, uma classe Pássaro que estende uma classe Animal). A composição, por outro lado, é quando as classes contêm instâncias de outras classes que implementam a funcionalidade desejada. Representa um relacionamento "tem um" (por exemplo, uma classe Pássaro tem uma instância de uma classe Asa como membro).

O polimorfismo também é um mecanismo importante para a reutilização de código na programação orientada a objetos. É quando uma linguagem pode processar objetos de maneira diferente dependendo de seu tipo de dados ou classe.

Alguns exemplos de linguagens que enfatizam a programação orientada a objetos incluem Java, C++, Ruby. Novamente, você pode aplicar esses conceitos na maioria das linguagens, incluindo em JavaScript.

Determinístico x não determinístico

Determinístico

Programas determinísticos sempre retornam o mesmo resultado sempre que são chamados com um conjunto específico de valores de entrada e o mesmo estado fornecido.

Não determinístico

Programas não determinísticos podem retornar resultados diferentes cada vez que são chamados, mesmo com o mesmo conjunto específico de valores de entrada e estado inicial.

O não determinismo é uma propriedade de qualquer sistema concorrente — ou seja, qualquer sistema em que várias tarefas podem acontecer ao mesmo tempo, executando em diferentes threads. Um algoritmo concorrente que está alterando o estado pode se comportar de maneira diferente a cada vez, dependendo de qual thread o agendador decidir executar.

Por exemplo:

declare Xthread X=1 endthread X=2 end

A ordem de execução das duas threads não é fixa. Não sabemos se X será vinculado a 1 ou 2. O sistema escolherá durante a execução do programa, sendo livre para escolher qual thread executar primeiro.

Outro exemplo de não determinismo:

Conclusão

Como sempre, seu feedback e sua contribuição são realmente importantes para mim. Você também pode conferir a apresentação do Prezi que criei para este artigo.

[1] Um agradecimento especial a Kent Beck por sua contribuição para este artigo.

Escrito por: Tautvilas Mečinskas

Programas de computador estão por toda parte. Interagimos com eles todos os dias. Parece que os softwares estão se tornando cada vez mais importantes para a nossa sociedade. Por que, no entanto, achamos os programas tão necessários? Por que e quando começamos a programar? Qual é a essência da programação? Essas perguntas podem parecer triviais, mas sinto que hoje ainda não temos uma boa definição do que é programação. Talvez este artigo possa ajudar a mudar isso.

É bastante difícil definir programação porque ela é muito diversa. Pode-se programar jogos, aplicações para dispositivos móveis, sites, compiladores, simulações e muito mais. Nesse caso, pode ser útil começar eliminando algumas ideias preconcebidas e esclarecer o que a programação não é.

Programação não é ciência. A ciência é a arte de examinar o mundo e descobrir padrões repetitivos nele. O método científico consiste em fazer uma hipótese e, em seguida, realizar experimentos para provar ou rejeitá-la. Não usamos esse método na programação – portanto, não é ciência. A programação não se trata de descoberta, mas de criatividade.

Programação não é matemática. Sim, há um aspecto matemático na programação. Algumas partes dos programas podem ser expressas como funções matemáticas. Escrever um gerador de números de Fibonacci é divertido, mas completamente inútil sem uma aplicação no mundo real. A matemática na programação é um meio para um fim, não uma parte central do processo.

Programação não se trata de computadores eletrônicos. Computadores são muito úteis, mas não são necessários. Os programas podem ser entendidos e interpretados por seres humanos também. Portanto, os computadores são apenas ferramentas que usamos na programação.

Então, do que se trata a programação? O que se encontra dentro de todo programa, seja ele ou pequeno?

Abstrações.

O que é abstração? É uma imagem reduzida do mundo. Ao abstrair, estamos convertendo a realidade em símbolos que podem ser transmitidos como informação. A palavra abstração origina-se de duas palavras latinas, que são abs, que significa longe de e trahere, que significa desenhar. A tradução latina sugere que abstrair implica separar algo do todo.

O processo de abstração é único da programação? De fato, não. É algo que os humanos fazem há bastante tempo. Nossas ferramentas de abstração mais básicas são o mapa e o relógio.

Arqueólogos descobriram mapas de pedra que os humanos fizeram há mais de 14 mil anos. Isso mostra que a cartografia é fundamental para os humanos. É um processo de transformar território em símbolos abstratos. Um mapa é um modo de abstrair o espaço. É uma ferramenta que nos ajuda a fazer sentido do território ao nosso redor para que a navegação seja mais fácil.

Um relógio, por outro lado, é um modo de abstrair o tempo. Achamos a natureza contínua do tempo confusa. Por isso, a abstraímos. Os humanos dividem o tempo em intervalos discretos: anos, meses, dias, horas, minutos, segundos. Enquanto um mapa nos ajuda a navegar no espaço, um relógio nos ajuda a navegar no tempo. O predecessor do relógio - o calendário - surgiu há mais de 10 mil anos.

Já aos computadores são ferramentas que também lidam com abstrações. Há 3 partes fundamentais em todo computador:

1. Relógio interno – a maneira de o computador abstrair o tempo
2. Memória – a maneira de o computador abstrair o espaço
3. Unidade de processamento – a maneira de o computador executar operações lógicas

Esses recursos dão aos computadores uma maneira de entender abstrações espaciais e suas interações no tempo abstrato. Isso significa que os programas são abstrações do espaço e do tempo. A programação é a arte de criar abstrações do espaço e do tempo. Essas abstrações nos ajudam a navegar na realidade, sendo, por isso, tão importantes para nós.

Existe um método de abstração que é muito semelhante à programação, mas que é ainda mais antigo que mapas, relógios e calendários: a linguagem.

Se você olhar de perto para nossa linguagem natural, verá que ela possui todas as características necessárias para abstrair o espaço e o tempo.

Vamos analisar um exemplo de frase:

Vá para o jardim e colha algumas flores esta noite.

O jardim e as flores referem-se a espaço abstrato. Esta noite é um modo de abstrair o tempo. E adiciona lógica à frase. Vá para e colha são sub-rotinas.

Podemos facilmente transformar a frase acima em JavaScript:

quandoNoite.then(()=>voce.irPara(jardim)).then(()=>voce.pegar(flor))

Essa frase pode ser entendida por um computador que tenha definições de noite, você, flores e as sub-rotinas necessárias definidas.

O problema da linguagem natural é que ela tem aplicações muito amplas. A linguagem pode ser usada não apenas para comunicar informações, mas também para expressar sentimentos e emoções. Os melhores exemplos de programas de linguagem natural pura são leis, regras de jogos de tabuleiro e manuais de instruções.

As linguagens de programação, por outro lado, são rigorosas e só podem criar abstrações. Os computadores são projetados para interpretar essas abstrações de uma maneira muito específica e determinística.

Para escrever programas de computador, você precisa aprender a programar a linguagem natural em símbolos que o computador possa entender. Isso geralmente requer conhecimento intrincado da arquitetura do computador e da sintaxe da linguagem de computador escolhida. Portanto, se você quiser que um computador entenda suas abstrações de realidade, você precisa aprender a programar.

Os computadores são ferramentas que podem executar regras definidas em programas com velocidade e precisão sobre-humanas. Eles nos capacitam a construir abstrações complexas e multicamadas e a transformar nossos programas em mapas da realidade verdadeiramente dinâmicos e interativos.

De muitas maneiras, programar é algo que todos nós já sabemos fazer. O processo de abstração da realidade é fundamental para os seres humanos. A programação de computadores é apenas a maneira mais eficaz de se fazer isso.

Escrito por: Suz Hinton

Resolvi tentar fazer streaming (transmissão ao vivo) pela primeira vez em julho passado. Em vez de jogos, como a maioria dos streamers na Twitch faz, eu queria transmitir o trabalho com código aberto que faço no meu tempo livre. Eu trabalho um pouco em bibliotecas de hardware do NodeJS (a maioria delas feita por mim). Como que eu já estava em um nicho na Twitch, por que não estar em um nicho ainda menor, como hardware com JavaScript? 😉 Então, fiz meu próprio canal e tenho transmitido regularmente desde então.

Claro que não fui a primeira a fazer isso. Handmade Hero foi um dos primeiros programadores que eu assisti programando on-line, seguido logo depois por Vlambeer, que desenvolveu Nuclear Throne ao vivo na Twitch. Em especial, eu era fascinada por Vlambeer.

O que me fez cruzar a barreira de desejar fazer e passar a fazer de fato tem a ver com Nolan Lawson, um amigo meu. Assisti a um streaming dele mostrando um final de semana de seu trabalho com código aberto e achei aquilo incrível. Ele explicava tudo o que estava fazendo enquanto programava. Tudo. Respondia a problemas no GitHub, fazia a triagem dos bugs, depurava o código das branches, absolutamente tudo o que você pode imaginar. Eu achei fascinante, pois Nolan mantém bibliotecas de código aberto que recebem muita atividade e são muito usadas. Sua vida trabalhando no código aberto é muito diferente da minha.

Você consegue até ver um comentário que eu deixei no vídeo dele:

Eu tentei por conta própria uma semana depois ou algo assim depois de configurar meu canal na Twitch e de me encontrar no OBS Studio. Acho que trabalhei com o Avrgirl-Arduino, no qual eu ainda trabalho com frequência quando faço meus streamings. Foi um primeiro streaming bem complicado. Eu estava muito nervosa. Fiquei até altas horas ensaiando tudo o que eu faria na noite anterior.

O pequeno número de espectadores que recebi naquele sábado foi realmente encorajador. Então, eu continuei fazendo. Hoje em dia, tenho mais de mil seguidores e um lindo subconjunto deles são visitantes regulares que eu chamo de "a família noopkat".

Nos divertimos muito – e eu gosto de chamar as partes de programação ao vivo de "programação com pares on-line em massa para multijogadores". Fico verdadeiramente tocada pela bondade e sagacidade de todos que se juntam a mim a cada fim de semana. Um dos momentos mais engraçados que tive foi quando um membro da família apontou que minha placa Arduino não estava funcionando com meu software porque o microchip não estava na placa.

Diversas vezes, eu costumava encerrar um streaming e, pouco depois, descobria que na minha caixa de entrada do e-mail que alguém havia feito um pull request para algum trabalho que eu havia mencionado e não tinha o tempo para iniciá-lo. Eu posso dizer honestamente que meu trabalho em código aberto mudou para melhor, graças à generosidade e encorajamento da minha comunidade na Twitch.

Tenho muito mais a dizer sobre os benefícios que o streaming na Twitch me trouxe, mas isso é para outro artigo, provavelmente. Em vez disso, quero compartilhar as lições que aprendi com qualquer outra pessoa que gostaria de tentar programar ao vivo dessa maneira para si mesma. Recentemente, fui questionada por alguns desenvolvedores sobre como eles podem começar. Então, estou publicando o mesmo conselho que dei a eles!

Para começar, deixo aqui um link para um guia chamado "Streaming and Finding Success on Twitch" (algo como "fazendo streaming e tendo sucesso na Twitch", texto em inglês), que me ajudou demais. O foco é na Twitch e nos streamings de jogos especificamente, mas ainda há seções relevantes e dicas preciosas ali. Recomendo a leitura antes de considerar outros detalhes sobre como começar seu canal (como o equipamento ou a escolha do software).

Já os meus conselhos, você pode ver a seguir. São dicas que eu compartilho agora e que vêm dos meus próprios erros e da sabedoria infinita de streamers conhecidos meus (que sabem muito bem que estou falando deles).

Software

Há muito software de streaming por aí que você pode usar. Eu uso o Open Broadcaster Software (OBS). Ele está disponível para a maioria das plataformas. Eu descobri que, para mim, ele era bastante intuitivo, que eu conseguiria configurá-lo e colocá-lo a funcionar rapidamente. Sei, porém, que outras pessoas podem passar bastante tempo até aprender como ele funciona. Vai depender de uma pessoa para outra! Aqui está uma tela que mostra como minha configuração de cena do desktop via OBS é ainda hoje:

Essencialmente, você alterna entre 'cenas' enquanto faz seu streaming. Uma cena é uma coleção de 'fontes', em camadas e compostas entre elas. uma fonte pode consistir em coisas como uma câmera, microfone, seu desktop, uma página da web, texto ao vivo, imagens, entre várias outras. O OBS é muito poderoso.

Essa cena do desktop acima é onde eu faço toda a programação ao vivo. Eu praticamente "vivo" aqui durante quase todo o streaming. Eu uso iTerm e o vim. Tenho também uma janela do navegador à mão para onde eu vou para procurar documentação e para fazer uma triagem em coisas no GitHub etc.

O retângulo inferior em preto é a minha webcam, para que os usuários possam me ver trabalhando e ter uma conexão mais pessoal.

Eu tenho alguns 'rótulos' que eu uso para minhas cenas, muitos dos quais tem a ver com as estatísticas e informações no banner superior. O banner simplesmente adiciona um pouco de personalidade. É uma fonte persistente de informações legal durante o streaming. É uma imagem que fiz no GIMP e você pode importá-la como fonte em sua cena. Alguns dos rótulos são estatísticas ao vivo que vêm de arquivos de texto (como, por exemplo, quem é o seguidor mais recente). Outro rótulo é um personalizado que eu fiz e que mostra a temperatura ao vivo e a umidade do ambiente de onde eu faço o streaming.

Eu também tenho 'alertas' configurados em minhas cenas, que mostram banners bonitos na parte superior do streaming sempre que alguém me segue ou doa algum dinheiro. Eu uso o serviço da web chamado Stream Labs para fazer isso, importando-o como uma fonte de página da web do navegador na cena. Stream Labs também cria um arquivo de texto com meus seguidores mais recentes para mostrar no meu banner.

Além disso, eu tenho uma tela de aguardo, que uso quando estou prestes a entrar ao vivo:

Também fiz uma cena para quando eu estou inserindo tokens secretos ou chaves de API. Eu apareço na câmera, mas meu desktop fica oculto com uma página da web divertida, de modo que eu posso trabalhar com privacidade:

Como você pode ver, eu não levo nada muito a sério quando estou fazendo meus streamings, mas eu gosto de ter uma configuração legal para que meus espectadores possam aproveitar ao máximo o streaming.

Agora, vamos a um segredo de verdade: eu uso o OBS para remover a parte inferior e a parte direita da minha tela, ao mesmo tempo em que mantenho o tamanho de vídeo que a Twitch espera. Isso me deixa com espaço para ver meus eventos (seguidores novos e outros) na parte inferior e eu posso olhar e responder na caixa de chat do meu canal à direita. A Twitch permite que você 'extraia' a caixa do chat para uma nova janela, o que é bastante útil.

Essa é a aparência do meu desktop completo de fato:

Comecei a fazer isso há alguns meses e não parei mais. Eu nem tenho certeza se meus espectadores percebem que é assim que minha configuração funciona. Eu acho que eles dão como certo que eu posso ver tudo, mesmo que eu não possa ver o que realmente está sendo transmitido ao vivo quando eu estou ocupada programando!

Você deve estar se perguntando por que eu só uso um monitor. É porque dois monitores era demais para gerenciar além de tudo o que eu já estava fazendo durante o streaming. Eu descobri isso rapidamente e tenho ficado com apenas uma tela desde então.

Hardware

Usei coisas mais baratas para começar e, aos poucos, comprei coisas mais legais quando percebi que o streaming seria algo a que eu me apegaria. Use o que tiver ao começar, mesmo que seja o microfone e a câmara integrados do seu laptop.

Hoje em dia, eu uso uma webcam Logitech Pro C920 e um microfone Blue Yeti em um braço de microfone com um suporte anti-impacto (do tipo aranha shock). Vale totalmente a pena no final, se você tiver o dinheiro para gastar. Fez muita diferença na qualidade dos meus streamings.

Eu uso um monitor grande (27 polegadas), porque, como eu mencionei anteriormente usar dois monitores simplesmente não funcionou para mim. Eu estava perdendo coisas no bate-papo porque eu não estava olhando para a segunda tela do laptop o suficiente, e assim por diante. O nível de experiência das pessoas pode variar aqui, mas ter tudo em uma tela foi fundamental para eu prestar atenção em tudo o que está acontecendo.

Em termos de hardware, acho que é isso. Não tenho uma configuração muito complicada.

Se você estava interessado, minha mesa é bastante normal, exceto pelo microfone assustador que fica grudado do meu lado:

Dicas

Esta última seção tem algumas dicas gerais que eu escolhi, que tornaram meu streaming melhor e mais agradável no geral.

Painéis

Dedique um tempo a criar ótimos painéis. Os painéis são as pequenas caixas de conteúdo na parte inferior da página do canal de todos. Eu os vejo como as novas caixas de perfil do MySpace (verdade). As ideias do painel podem ser coisas como regras de bate-papo, informações sobre quando você transmite, qual computador e equipamento você usa ou sua raça de gato favorita – qualquer coisa que crie um toque pessoal. Examine outros canais (especialmente os populares) para ter ideias!

Um exemplo de um dos meus painéis:

Chat

O chat é muito importante. Você receberá as mesmas perguntas repetidamente à medida que as pessoas entrarem durante o seu streaming depois de perderem o início. É aí que 'macros' de chat podem realmente ajudar. "Em que você está trabalhando?" é a pergunta mais comum feita enquanto estou programando. Eu tenho 'comandos' de atalho no chat para isso, que fiz com o Nightbot. Eles colocam uma explicação de algo que eu inseri anteriormente. Eu só preciso digitar um pequeno comando de uma palavra como !whatamidoing (o que estou fazendo no momento).

Quando as pessoas fizerem perguntas ou deixarem comentários legais, fale com elas! Agradeça, diga seu identificador da Twitch, e eles realmente apreciarão a atenção e o reconhecimento. Isso é MUITO difícil de cuidar quando você começa a transmitir, mas a multitarefa virá mais fácil à medida que você fizer mais e mais. Tente passar alguns segundos a cada dois minutos olhando o chat para encontrar novas mensagens.

Ao programar, explique o que está fazendo. Fale bastante. Faça piadas. Mesmo quando estou bloqueada com algo, eu digo coisas como, "Ah, droga, me esqueci de como usar esse método. Vou olhar no Google hahaha" e as pessoas são sempre legais. Algumas vezes, eles até leem com você e a ajudam. É divertido e uma maneira de engajar, além de manter as pessoas assistindo.

Eu perco o interesse rapidamente ao assistir streamings de programação onde a pessoa se senta em silêncio digitando código, ignorando o chat e seus novos alertas de seguidores.

Com quase toda certeza, 99% das pessoas que encontrarem seu canal serão amigáveis e curiosas. A gente até recebe um troll de vez em quando, mas as ferramentas de moderação oferecidas pela Twitch e pelo Nightbot ajudam muito a desencorajar esse tipo de comportamento.

Tempo de preparação

Automatize sua configuração o máximo possível. Meu terminal é um iTerm, e ele permite que você salve arranjos de janelas e tamanhos de fonte para que você possa restaurá-los mais tarde. Eu tenho um arranjo de janela para streaming e outro para quando não estou no streaming. Isso me poupa muito tempo. Eu uso um comando e tudo está no tamanho perfeito e na posição certa, pronto para funcionar.

Existem outras aplicações por aí que automatizam todos os posicionamentos da janela da aplicação – procure para ver se alguma deles também ajudaria você.

Deixe o tamanho da fonte bem grande no seu terminal e no seu editor de código para que todos possam ver.

Regularidade

Mantenha-se regular em sua agenda. Eu só transmito uma vez por semana, mas sempre na mesma hora. Avise as pessoas se você não conseguir transmitir durante o tempo em que você normalmente faz isso. Isso me rendeu um público regular. Algumas pessoas adoram a rotina e é exatamente como conversar com um amigo. Você está em um círculo social com sua comunidade. Então, trate-a dessa maneira.

Quero transmitir mais vezes, mas sei que não posso me comprometer com mais de uma vez por semana por causa das minhas viagens. Estou tentando criar uma maneira de transmitir em alta qualidade quando estiver na estrada, ou, talvez, de apenas ter bate-papos casuais e de deixar a programação para o meu streaming normal de domingo. Ainda estou tentando descobrir como fazer isso!

Estranheza

Vai parecer estranho quando você começar. Você vai se sentir nervoso com as pessoas vendo você programar. Isso é normal! Senti isso muito forte no início, apesar de ter experiência em falar em público. Senti que não havia onde me esconder – e isso me assustou. Eu pensava: "todo mundo vai achar que meu código é ruim e que eu sou uma péssima desenvolvedora". Esse é um padrão de pensamento que me atormentou durante toda a minha carreira, no entanto. Não é uma novidade. Eu sabia que, ao vivo, eu não conseguiria refatorar silenciosamente o código antes de enviar para o GitHub, o que, geralmente, é muito mais seguro para minha reputação como desenvolvedora.

Aprendi muito sobre meu estilo de programação fazendo isso ao vivo na Twitch. Aprendi que sou definitivamente do tipo "primeiro, faça funcionar; depois, torne legível; por fim, torne mais rápido". Eu não ensaio mais na noite anterior (desisti disso depois de 3 ou 4 transmissões iniciais). Então, escrevo um código bem tosco na Twitch e tenho que me sentir bem com isso. Eu escrevo meu melhor código quando estou sozinha com meus pensamentos e não olhando para uma caixa de bate-papo e falando em voz alta. Não há problema com isso. Esqueço assinaturas de métodos que usei mil vezes e cometo erros "bobos" em quase todas as sessões de streaming. Não é, com certeza, um ambiente produtivo e, ali, você não estará no seu melhor momento de produção.

Minha comunidade da Twitch nunca me julga por isso. Eles me ajudam muito. Eles entendem que sou multitarefa e são realmente ótimos em dar conselhos e sugestões pragmáticas. Às vezes, eles me socorrem. Em outras, eu tenho que explicar a eles por que a sugestão deles não funciona. É realmente como uma programação em duplas comum!

Acho que a abordagem 'de mostrar tudo, inclusive o problemático' nesse meio é um ponto forte, não uma fraqueza. Isso faz com que as pessoas consigam se relacionar melhor com você. Além disso, é importante mostrar que não existe o programador perfeito ou o código perfeito. Provavelmente, é um grande alívio para os novos programadores que assistem, além de uma lição de humildade para mim como programadora mais experiente.

Conclusão

Se você está querendo começar a fazer programação ao vivo na Twitch, eu encorajo você a experimentá-la! Espero que este artigo tenha ajudado se você tem se perguntado por onde começar.

Se quiser se juntar a mim nos domingos, siga meu canal na Twitch. 🙂

Para encerrar, gostaria de fazer um agradecimento pessoal a Mattias Johansson, por sua sabedoria e encorajamento no início de minha jornada como streamer. Ele foi incrivelmente generoso em seus conselhos, e o canal dele no YouTube, o FunFunFunction é uma fonte contínua de inspiração.

Atualização: algumas pessoas têm me perguntado sobre meu teclado e sobre outras partes da minha estação de trabalho. Aqui vai uma lista completa das coisas que eu uso (em inglês). Agradeço o seu interesse!

Escrito por: Kevin Turney

Como combinar a eficiência de inserção de uma lista vinculada e a busca rápida de um array ordenado.

O que é uma árvore binária de busca?

Vamos começar com a terminologia básica para que possamos falar a mesma língua e investigar conceitos relativos. Primeiramente, quais princípios definem a árvore binária de busca (em inglês, Binary Search Tree ou BST)?

Observação: a partir daqui, usarei somente "BST" para facilitar.

Uma BST é considerada uma estrutura de dados feita a partir de nós (em inglês nodes), assim como as listas encadeadas (em inglês, linked lists – leia mais no artigo em inglês). Esses nós podem ser nulos ou ter referências (encadear) para outros nós. Esses "outros" nós são nós filhos, chamados de nó esquerdo e nó direito. Nós tem valores e esses valores determinam quando eles serão alocados dentro da BST.

Da mesma maneira que ocorre com uma lista vinculada, cada nó é referenciado somente por um outro nó, seu próprio pai, exceto o nó originário ou raiz. Podemos dizer, então, que cada nó em uma BST é uma BST própria, pois ao seguirmos a árvore, logo abaixo, nós alcançamos outro nó que tem outros dois filhos, um esquerdo e um direito. Independentemente de onde formos, esse nó vai ter um nó direito e um esquerdo como filhos e assim por diante.

1. O nó esquerdo é sempre menor que seu pai.

2. O nó direito é sempre maior que seu pai.

3. Uma BST é considerada balanceada se cada nível da árvore está completamente preenchido com exceção do último nível. Nele, a árvore é preenchida da esquerda pra direita.

4. Uma BST perfeita é aquela que é tanto cheia como completa (todos os nós filhos estão no mesmo nível e cada nó tem um nó esquerdo e um direito)

Aplicações úteis da BST

Quais são os exemplos reais das BSTs? Árvores são comumente usadas em buscas, lógicas de jogos, tarefas de preenchimento automático e gráficos.

Velocidade. Como mencionado anteriormente, a BST é uma estrutura ordenada de dados. Após a inserção, os nós são colocados de maneira ordenada. Essa ordem herdada faz as buscas serem mais rápidas. Similarmente a busca binária (com um array que é ordenado), cortamos pela metade o número de dados para ordenar a cada iteração. Por exemplo, suponha que estamos buscando por um nó com um pequeno valor. A cada iteração, continuamos movendo à esquerda em direção ao nó buscado. Isso elimina a metade dos valores maiores automaticamente!

Assim como um array, o dado é guardado por referência. Ao adicionar para a estrutura de dados, criamos um grupo na memória e o conectamos a ele. Fazer isso é mais rápido que criar um array com mais espaços e só então inserir o dado do menor array para o novo e maior.

Para resumir, inserção, exclusão e busca são habilidades de destaque para as BSTs.

Agora que entendemos os princípios, os benefícios e os componentes básicos de uma BST, vamos implementar uma em javascript.

A API para BST contém o seguinte: Insert, Contains, Get Min, Get Max, Remove Node, Check if Full, Is Balanced e os tipos de Busca — Depth First (preOrder, inOrder, postOrder), Breadth First Search e, por fim, Get Height. Essa é uma API bem grande, vamos olhar uma seção de cada vez.

Implementação

O construtor

A BST é feita de nós – e cada nó tem um valor.

function Node(value){  
	this.value = value;
    this.left = null;
    this.right = null;
}

O construtor da BST é criado a partir de um nó raiz.

function BinarySearchTree() {
	this.root = null;
}

let bst = new BST();
let node = new Node();

console.log(node, bst); // Node { value: undefined, left: null, right: null } BST { root: null }

Até agora, tudo vai bem.

Inserção (Insert)

BinarySearchTree.prototype.insert = function(value){
	let node = new Node(value);
	if(!this.root) this.root = node;
	else{    
    	let current = this.root;
        while(!!current){
        	if(node.value < current.value){
           		if(!current.left){
               		current.left = node;
                   	break;
               	}
        	   	current = current.left;
            }
            else if(node.value > current.value){
            	if(!current.right){
                	current.right = node;
                   	break;
               	}
                current = current.right;
            } 
            else {
            	break;
            }
     	}
     }
     return this;
};

let bst = new BST();
bst.insert(25); // BST { root: Node { value: 25, left: null, right: null } }

Vamos adicionar mais valores.

bst.insert(40).insert(20).insert(9).insert(32).insert(15).insert(8).insert(27);

BST { root:  Node { value: 25, left: Node { value: 20, left: [Object], right: null }, right: Node { value: 40, left: [Object], right: null } } }

Para uma visualização melhor, basta só clicar aqui!

Vamos decifrar isso.

1. Primeiramente, passamos um valor e criamos um nó
2. Observar se tem um nó raiz. Senão, configurar esse nó recém-criado para apontar para o nó raiz
3. Se existir um nó raiz, criamos uma variável declarada como "current" e configuramos esse valor para o nó raiz
4. Se o nó for recém-criado, node.value, for menor que o nó raiz, movemos o nó para a esquerda
5. Continuamos comparando esse node.value para os valores da esquerda.
6. Se o valor for bem menor e alcançarmos um ponto onde não existirem mais nós esquerdos, colocaremos esse item aqui.
7. Se o node.value é maior, repetiremos os mesmos passos acima exceto que em direção à direita.
8. Precisamos inserir um break, porque não há um contador de passos para terminar o laço.

Contém (contains)

Essa abordagem é bem direta.

BinarySearchTree.prototype.contains = function(value){
	let current = this.root;
    while(current){
    	if(value === current.value) return true;
        if(value < current.value) current = current.left;
        if(value > current.value) current = current.right;
    }
    return false;
};

Obter o mínimo e o máximo (Get Min e Get Max).

Siga para a esquerda para achar o menor valor e para a direita para o maior valor.

BinarySearchTree.prototype.getMin = function(node){
	if(!node) node = this.root;
    while(node.left) {
    	node = node.left;
    }
    return node.value
};

BinarySearchTree.prototype.getMax = function(node){
	if(!node) node = this.root;
    while(node.right) {
    	node = node.right;
    }
    return node.value;
};

Remoção (removal)

Remover um nó é uma operação mais complicada, pois os nós tem que ser reordenados para que as propriedades da BST sejam mantidas. Existe um caso onde um nó tem apenas um filho e um caso onde o nó tem tanto o filho da direita como da esquerda. Usaremos a uma função para nos ajudar a fazer o trabalho pesado.

BinarySearchTree.prototype.removeNode = function(node, value){
	if(!node){
    	return null;
    }
    if(value === node.value){ // sem filhos
    if(!node.left && !node.right) return null; // um filho e é o da direita
    if(!node.left) node.right;// um filho e é o da esquerda
    if(!node.right) node.left;  // dois filhos
    const temp = this.getMin(node.right);
    node.value = temp;
    node.right = this.removeNode(node.right, temp);
    return node;
    } else if(value < node.value) {
    	node.left = this.removeNode(node.left, value);
        return node;
   } else  {
      	node.right = this.removeNode(node.right, value);
        return node;
   }
};

BinarySearchTree.prototype.remove = function(value){
	this.root = this.removeNode(this.root, value);
};

Funciona assim…

Diferente de deleteMin e deleteMax, onde apenas cruzamos todo o caminho para a direita ou esquerda e pegamos o último valor, aqui, temos que retirar o nó e substituí-lo por algo. Essa solução foi desenvolvida em 1962 por T. Hibbard. Contamos com o caso onde podemos excluir um nó filho ou nenhum, esse é o caso mais fácil. Sem filhos, sem problemas. Se o filho estiver presente é só movê-lo para cima.

Entretanto, quando temos um nó para ser removido que tem dois filhos, qual deles fará a substituição? Certamente, não podemos mover o filho maior para baixo, então o que fazemos é trocá-lo pelo seu sucessor. Temos que buscar o menor filho à direita que é maior que o filho esquerdo.

1. Crie uma variável temporária e guarde o menor nó na sua direita. Isso cumprirá o requisito de que a propriedade que tem o valor da esquerda, ainda assim, é menor e os valores da esquerda que ainda são maiores;
2. Reinicialize o valor do nó essa variável temporária;
3. Exclua o nó direito;
4. Compare os valores na esquerda e na direita e determine qual será o valor atribuído.

Acho que uma imagem ilustrará isso melhor:

Busca (search)

Existem dois tipo de busca: Depth First e Breadth First. Breadth First (busca por largura, em português) é simplesmente quando você para a cada nível ao descer pela árvore. Seria algo parecido com isso: começamos na raiz, então filho esquerdo e depois filho direito. Passamos para o próximo nível, filhos esquerdos e filhos direitos. Pense nisso como se estivesse se movendo horizontalmente. Empregamos, até diria que simulamos, uma fila para ajudar a ordenar o processo. Passamos a função, porque, muitas vezes, queremos operar em um valor.

BinarySearchTree.prototype.traverseBreadthFirst = function(fn) {
	let queue = [];
    queue.push(this.root);
    while(!!queue.length) {
    	let node = queue.shift();
        fn(node);
        node.left && queue.push(node.left);
        node.right && queue.push(node.right);
    }
}

A busca Depth First (busca por profundidade, em português) envolve seguir para baixo da BST de uma maneira específica, ou seja: preOrder, inOrder, ou postOrder (pré-ordem, na ordem ou pós-ordem, respectivamente). Explicarei as diferenças em breve.

Em termos de código, temos uma função básica, traverseDepthFirst, e passamos uma função e um método. Outra vez, a função implica que queremos fazer algo com o valor no percurso, enquanto o método é o tipo de busca que estamos tentando realizar. Na traverseDepthFirst, temos uma alternativa, a busca preOrder, pré-selecionada.

Agora, qual a diferença entre elas? Primeiro, enviamos a função inOrder. Deveria ser autoexplicativo, mas não é. Estamos querendo dizer em ordem de inserção, em ordem do maior para o menor, ou do menor para o maior? Eu quero apenas que você tenha isso em mente de antemão. Nesse caso, sim, quer dizer do menor para o maior.

preOrder pode ser pensado como Pai, Filho Esquerdo, Filho Direito.

postOrder, por outro lado, seria como Filho Esquerdo, Filho Direito, Pai.

BinarySearchTree.prototype.traverseDFS = function(fn, method){
	let current = this.root;
    if(!!method) this[method](current, fn);
    else this._preOrder(current, fn);
};

BinarySearchTree.prototype._inOrder = function(node, fn){
	if(!!node){
    	this._inOrder(node.left, fn);
	    if(!!fn) fn(node);
    	this._inOrder(node.right, fn);
    }
};

BinarySearchTree.prototype._preOrder = function(node, fn){
	if(node){ 
    	if(fn) fn(node);
    	this._preOrder(node.left, fn);
    	this._preOrder(node.right, fn);
    }
};

BinarySearchTree.prototype._postOrder = function(node, fn){
	if(!!node){ 
    		this._postOrder(node.left, fn);
    		this._postOrder(node.right, fn);
        	if(!!fn) fn(node);
    }
};

Checar se a BST está cheia

Lembre-se do que comentamos antes: uma BST está cheia se cada nó existente na árvore tiver ou Zero ou dois filhos.

// uma BST está cheia se cada nó tiver ou zero ou dois filhos (nenhum nó pode ter apenas um filho)

BinarySearchTree.prototype.checkIfFull = function(fn){
	let result = true;
    this.traverseBFS = (node) => {
    	if(!node.left && !node.right) result = false;
        else if(node.left && !node.right) result = false;
    }
    return result;
};

Obter a altura da BST

O que significa obter a altura de uma árvore? Por que é importante? Aqui é onde a Complexidade de Tempo (também conhecida como Big O) aparece. Operações básicas são proporcionais ao tamanho da árvore. Então, se lembrarmos do que foi dito antes, ao buscar por um valor específico, o número de operações que temos a fazer é reduzido a metade a cada etapa.

Isso significa que temos um pão e vamos cortá-lo a metade, depois dividir essa metade em outros dois pedaços e continuamos fazendo isso até termos exatamente o pedaço de pão que queremos.

Em ciência da computação, chamamos isso de O(log n). Começamos com algum tipo de tamanho de entrada e, com o tempo, o tamanho fica melhor (mais achatado). Uma busca linear direta é denotada como O(n). Conforme o tamanho da entrada aumenta, também aumenta o tempo para executar as operações. O(n), conceitualmente, é uma linha de 45° começando da origem zero em um gráfico se movendo para a direita. A escala horizontal representa o tamanho de uma entrada e a escala vertical representa o tempo levado para completá-la.

Tempo constante é O(1). Não importa o tamanho da entrada, seja grande ou pequena, a operação leva exatamente o mesmo tempo. Por exemplo, push() e pop() de um array possuem tempo constante, assim como obter o valor em uma HashTable.

Eu vou explicar mais sobre isso em um artigo futuro, mas já quis adiantar um pouco as coisas agora.

De volta à altura.

Temos uma função recursiva. Nosso caso base é: "se não temos um nó, então começamos em this.root". Isso implica que podemos começar em valores menores na árvore e obter árvores com subalturas.

Então se passamos em this.root para começar, recursivamente movemos para baixo e adicionamos funções que chamarão a pilha de execução (em inglês execution stack). Quando alcançamos o fundo, a pilha é preenchida e, então, a chamada é executada e comparamos as alturas da esquerda e da direita e incrementamos um.

BinarySearchTree.prototype._getHeights = function(node){
	if(!node) return -1;
    let left = this._getHeights(node.left);
    let right = this._getHeights(node.right);
    return Math.max(left, right) + 1;
};

BinarySearchTree.prototype.getHeight = function(node){
	if(!node) node = this.root;
    return this._getHeights(node);
};

Por último, Is Balanced (está balanceada)

O que estamos fazendo aqui é observar se a árvore está preenchida em cada nível, e se  no último nível ela está preenchida da esquerda para a direita.

BinarySearchTree.prototype._isBalanced = function(node){
	if(!node) return true;
    let heightLeft = this._getHeights(node.left);
    let heightRight = this._getHeights(node.right);
    let diff = Math.abs(heightLeft — heightRight);
    if(diff > 1) return false;
    else return this._isBalanced(node.left) &&    this._isBalanced(node.right);
};

BinarySearchTree.prototype.isBalanced = function(node){
	if(!node) node = this.root;
    return this._isBalanced(node);
};

Imprimir a árvore (print)

Use isso para visualizar todos os métodos que você vê, especialmente travessias depth first e breadth first.

BinarySearchTree.prototype.print = function() {
	if(!this.root) {
    	return console.log('Nó raiz não encontrado');
    }
    let newline = new Node('|');
    let queue = [this.root, newline];
    let string = ''; 
    while(queue.length) {
    	let node = queue.shift();
        string += node.value.toString() + ' ';
        if(node === newline && queue.length) queue.push(newline);
        if(node.left) queue.push(node.left);
        if(node.right) queue.push(node.right);
     }
     console.log(string.slice(0, -2).trim());
};

Nosso amigo, o console.log! Sinta-se livre para brincar com ele e experimentar.

const binarySearchTree = new BinarySearchTree();
binarySearchTree.insert(5);
binarySearchTree.insert(3);

binarySearchTree.insert(7);
binarySearchTree.insert(2);
binarySearchTree.insert(4);
binarySearchTree.insert(4);
binarySearchTree.insert(6);
binarySearchTree.insert(8);
binarySearchTree.print(); // => 5 | 3 7 | 2 4 6 8

binarySearchTree.contains(4);

//binarySearchTree.printByLevel(); // => 5 \n 3 7 \n 2 4 6 8
console.log('--- DFS inOrder');

binarySearchTree.traverseDFS(function(node) {
	console.log(node.value);
}, '_inOrder'); // => 2 3 4 5 6 7 8

console.log('--- DFS preOrder');

binarySearchTree.traverseDFS(function(node) {
	console.log(node.value);
}, '_preOrder'); // => 5 3 2 4 7 6 8

console.log('--- DFS postOrder');

binarySearchTree.traverseDFS(function(node) {
	console.log(node.value);
}, '_postOrder'); // => 2 4 3 6 8 7 5

console.log('--- BFS');

binarySearchTree.traverseBFS(function(node) {
	console.log(node.value);
}); // => 5 3 7 2 4 6 8

console.log('min é 2:', binarySearchTree.getMin()); // => 2

console.log('máx é 8:', binarySearchTree.getMax()); // => 8

console.log('árvore contém 3 é true:', binarySearchTree.contains(3)); // => true

console.log('árvore contém 9 é false:', binarySearchTree.contains(9)); // => false

// console.log('altura da árvore é 2:', binarySearchTree.getHeight()); // => 2

console.log('árvore balanceada é true:', binarySearchTree.isBalanced(),'line 220'); // => true

binarySearchTree. remove(11); // remove o nó inexistente

binarySearchTree.print(); // => 5 | 3 7 | 2 4 6 8

binarySearchTree.remove(5); // remove 5 e 6 sobe

binarySearchTree.print(); // => 6 | 3 7 | 2 4 8

console.log(binarySearchTree.checkIfFull(), 'deve ser verdadeiro');

var fullBSTree = new BinarySearchTree(10);

fullBSTree.insert(5).insert(20).insert(15).insert(21).insert(16).insert(13);

console.log(fullBSTree.checkIfFull(), 'should be true');

binarySearchTree.remove(7); // remove 7 e 8 sobe

binarySearchTree.print(); // => 6 | 3 8 | 2 4

binarySearchTree.remove(8); // remove 8 e a árvore fica desbalanceada

binarySearchTree.print(); // => 6 | 3 | 2 4

console.log('árvore balanceada é false:', binarySearchTree.isBalanced()); // => true

console.log(binarySearchTree.getHeight(),'altura é 2')

binarySearchTree.remove(4);

binarySearchTree.remove(2);

binarySearchTree.remove(3);

binarySearchTree.remove(6);

binarySearchTree.print(); // => 'Não foi encontrado o nó raiz'

//binarySearchTree.printByLevel(); // => 'Não foi encontrado o nó raiz'

console.log('altura da árvore é -1:', binarySearchTree.getHeight()); // => -1

console.log('árvore balanceada é true:', binarySearchTree.isBalanced()); // => true

console.log('---');

binarySearchTree.insert(10);

console.log('altura da árvore é 0:', binarySearchTree.getHeight()); // => 0

console.log('ávroe balanceada é true:', binarySearchTree.isBalanced()); // => true

binarySearchTree.insert(6);

binarySearchTree.insert(14);

binarySearchTree.insert(4);

binarySearchTree.insert(8);

binarySearchTree.insert(12);

binarySearchTree.insert(16);

binarySearchTree.insert(3);

binarySearchTree.insert(5);

binarySearchTree.insert(7);

binarySearchTree.insert(9);

binarySearchTree.insert(11);

binarySearchTree.insert(13);

binarySearchTree.insert(15);

binarySearchTree.insert(17);

binarySearchTree.print(); // => 10 | 6 14 | 4 8 12 16 | 3 5 7 9 11 13 15 17

binarySearchTree.remove(10); // remove 10 e 11 sobe

binarySearchTree.print(); // => 11 | 6 14 | 4 8 12 16 | 3 5 7 9 x 13 15 17

binarySearchTree.remove(12); // remove 12 e 13 sobe

binarySearchTree.print(); // => 11 | 6 14 | 4 8 13 16 | 3 5 7 9 x x 15 17

console.log('árvore balanceada é true:', binarySearchTree.isBalanced()); // => true

//console.log('árvore balanceada otimizada é true:', binarySearchTree.isBalancedOptimized()); // => true

binarySearchTree.remove(13); // remove 13 e 13 não tem filhos - nada acontece

binarySearchTree.print(); // => 11 | 6 14 | 4 8 x 16 | 3 5 7 9 x x 15 17

console.log('árvore balanceada é false:', binarySearchTree.isBalanced()); // => false

Complexidade de tempo

1. Inserção O(log n)
2. Remoção O(log n)
3. Busca O(log n)

Uau, isso foi realmente muita informação. Espero que as explicações tenham sido claras e introdutórias o máximo possível. Outra vez, escrever me ajuda a solidificar conceitos e, como dizia Richard Feynman: "Quando uma pessoa ensina, duas pessoas aprendem."

Recursos

Estes são recursos ótimos para visualização (em inglês):

• Data Structure Visualization
• BinaryTreeVisualiser - Binary Search Tree
• VisuAlgo - Binary Search Tree, AVL Tree
• Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!)
• Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne
• Binary search tree - Wikipedia

Versão da Wikipédia em português: Árvore binária de busca

Durante o ano passado, terminei o currículo inteiro do freeCodeCamp enquanto trabalhava em tempo integral como professora. Neste artigo, vou descrever como consegui fazer isso. Particularmente, quero falar sobre como organizei meu tempo e que material complementar usei.

Histórico

Primeiro, vamos falar do que há por trás disso. Eu não era completamente nova na programação. Cresci em uma pequena empresa de tecnologia.

Meu pai fundou sua própria empresa antes de eu nascer, onde eles realizavam diferentes atividades dentro da tecnologia, como consertar computadores, configurar conexões e redes de internet para outras empresas, ministrar cursos de informática e construir aplicações administrativos para empresas. Era uma cidade pequena, então eles eram basicamente os "caras da tecnologia" para toda a cidade.

Os escritórios da empresa eram em nossa casa. Então, eu literalmente cresci entre computadores e pessoas que gostavam deles. Comecei a brincar com o Visual Basic quando criança (um dos caras da empresa me ensinou a usá-lo) e passei todo o meu tempo livre on-line, conversando com colegas nerds.

Quando eu tinha uns 12 anos, um desses nerds me enviou por e-mail um manual de desenvolvimento para web (um arquivo .txt enorme que, basicamente, tratava de HTML) e eu o usei para construir meu próprio site. Ele tinha até um daqueles contadores de visita bacanas.

Eu o hospedei na Geocities, consegui um URL curto gratuito e o listei no Yahoo e no AltaVista (esses eram os maiores na época).

Depois disso, a vida aconteceu e eu desisti completamente da ideia de ser programadora, pois as circunstâncias exigiam uma abordagem mais "realista". Não vou entrar em detalhes agora, mas tive que desistir de estudar e conseguir um emprego.

Continuei vivendo minha vida. Eu construía sites, aqui e ali, para os clientes do meu pai. No fim, decidi começar a ensinar inglês, que era algo que veio fácil para mim e esqueci tudo sobre desenvolvimento para a web. Foi quando chegou o ano de 2016.

Como decidi mudar de carreira

Adoro ensinar. É uma profissão gratificante, interessante e divertida, mas tem seus pontos negativos. No início, tudo parecia um desafio. Porém, depois de tantos anos fazendo isso, comecei a sentir que não tinha propósito, que eu não estava mais crescendo ou aprendendo.

Eu estava me sentindo presa. Era como se meu trabalho fosse exatamente o mesmo ano após ano. Eu estava apenas seguindo em frente. Também não havia muitas oportunidades para realocação, algo que se tornou muito importante para mim mais tarde.

Em 2013, conheci meu marido e, no ano seguinte, fizemos uma viagem de três meses para a Europa mochilando, mas isso vale um outro artigo totalmente diferente. Basicamente, tínhamos um orçamento extremamente baixo e tivemos uma experiência incrível. Amamos a Europa e decidimos que voltaríamos para outra longa viagem.

O tempo passou, fizemos outras coisas e eu encontrei a Codecademy e comecei a brincar com ela e com a ideia de me tornar uma desenvolvedora em tempo integral. Eu já tinha alguma experiência construindo sites apenas com HTML e CSS, mas sem JavaScript. Eu estava lendo muitas histórias de sucesso on-line, mas ainda não considerava uma carreira real, nem de longe.

Enquanto isso, estávamos planejando a próxima viagem longa, economizando dinheiro, planejando e assim por diante. Eu estava trabalhando como tradutora freelancer cada vez mais, muito envolvida com a minha carreira, traduzindo coisas legais como romances e poesias. Chegou 2017 e fomos para a Europa novamente, desta vez por dois meses.

Lá, conhecemos vários desenvolvedores. Foi uma loucura. Cada um dos couch surfers que conhecemos parecia estar em TI de alguma forma, seja como gerente de produto de software, desenvolvedor, testador e assim por diante. Todos eles nos incentivaram a entrar na tecnologia. Nessa altura, já tínhamos decidido que queríamos nos mudar para a Europa. Por isso, muitos deles diziam: "Vocês podem arranjar emprego aqui. Os desenvolvedores são procurados por aqui e precisamos de muitos deles."

Antes de a viagem terminar, tomamos a decisão de nos inscrever para um certificado técnico de 2 anos em uma universidade técnica recém-fundada perto de nossa cidade natal. O programa era principalmente Java. Então, quando voltamos, começamos um curso de Java na Cousera. O primeiro módulo era, na verdade, um curso de JavaScript. Foi como ficamos viciados em JavaScript quase que imediatamente.

Enquanto aprendíamos JavaScript, esperávamos o início do ano letivo, em março de 2018. Foram apenas 50 vagas para a Universidade, então nos dedicamos e aprendemos de antemão. Fomos, fizemos provas, passamos em cursos e depois tivemos que esperar até que eles decidissem. Obtivemos as notas mais altas entre todos os candidatos, mas essas notas não fizeram diferença. As vagas seriam atribuídas por meio de um sistema de sorteio. Meu marido entrou e eu fiquei de fora.

Ele decidiu que preferia aprender sozinho. Não estava mais tão interessado em Java porque estava viciado em JavaScript. Começamos, então, a aprender por conta própria.

Começamos com a Codecademy, mas era muito "manual" para nós (não tínhamos contas Premium). Em algum lugar, lemos sobre o freeCodeCamp. Começamos, daí, muito lentamente no início (o primeiro certificado levou meses para ser obtido – admito que, no meio do currículo, ele foi alterado e eu joguei meu laptop longe e tive que consertá-lo). Depois que as férias de verão terminaram e eu voltei a trabalhar em tempo integral, as coisas ficaram difíceis.

Trabalhando em tempo integral e fazendo os cursos do freeCodeCamp a toda velocidade

Não foi fácil, não vou mentir. Ajudou que a maioria dos meus amigos e conhecidos não mora perto de mim, e eu moro em uma cidade pequena que não oferece muitas oportunidades de entretenimento. Nesse sentido, a programação foi um salva-vidas. Eu tinha algo divertido e viciante para fazer. Assim, eu pudematar horas de tédio com isso.

Isso ajudou muito ao lidar com a quantidade de horas que eu gastava fazendo trabalho mental (ensinando e estudando).

O primeiro certificado demorou meses, em parte porque eu estava esperando para entrar na Universidade e em parte porque eu estava trabalhando 10 horas por dia nos primeiros 3 meses do ano letivo.

Infelizmente, eu não podia simplesmente largar meu emprego e estudar em tempo integral, já que eu precisava pagar as contas. Foi quando precisei ficar muito boa em 3 coisas:

1. Gestão do tempo
2. Disciplina
3. Organização

Gestão do tempo

Eu começava a trabalhar às 7h. Então, comecei a levantar às 4h30 na maioria dos dias. Começava o dia com desafios freeCodeCamp e café. Às vezes, eu também lia um livro ou fazia outros tutoriais, dependendo do que eu estava trabalhando no momento. Também estudava durante o horário de almoço e depois do trabalho, mas aceitei o fato de não ser tão produtiva durante a semana por causa do trabalho. Então, durante a semana, fazia principalmente desafios curtos, leitura e assim por diante. Eu trabalhava em projetos nos finais de semana, feriados e no meu tempo livre.

Se eu tivesse 30 minutos, eu lia 30 minutos. Se eu tivesse 15, eu estudava por 15 minutos. Usei todos os momentos livres do meu dia para estudar.

Aos domingos, eu preparava a maior parte das minhas refeições da semana para não ter que gastar tempo cozinhando e não ter que acabar comendo coisas não saudáveis. Também planejei e reuni tudo o que precisava para trabalhar durante a semana, para não precisar gastar tempo extra além do horário normal de trabalho.

Felizmente, depois de junho, minha jornada de trabalho foi reduzida de 10 a 12 horas para 8. Eu estava trabalhando em um horário normal e foi aí que comecei a pegar o ritmo.

Disciplina

Você vai ter que estudar mesmo nos dias em que não tiver vontade. Aqui é onde a motivação também desempenha um grande papel, mas a disciplina é importante – especialmente se você é como eu e se distrai muito com mídias sociais e vídeos de gatos.

A melhor dica que posso dar para você para combater a tentação de ler artigos on-line é esta: se você vier com uma pergunta em sua cabeça como "como os aviões voam?" (que geralmente é o tipo de pergunta que me deixa levar e me suga por 30 minutos), anote em algum lugar e prometa a si mesmo que você pode ler tudo sobre isso depois de terminar o que está fazendo.

Em 99% das vezes, você não vai se importar mais, porque essas perguntas só aparecem em seu cérebro porque ele quer se distrair. Siga em frente e você vai vencer as distrações.

Outro aspecto da disciplina é ter que escolher o estudo em detrimento de outras coisas. Essa é a parte não tão divertida. Tive que desistir de muitas, muitas coisas que gostava para favorecer os estudos, e mal posso esperar para poder voltar a elas. Eu fiz isso apenas porque eu queria me tornar uma desenvolvedora o mais rápido possível (veja Motivação abaixo), mas mesmo que você não esteja com pressa como eu, você pode achar que gasta muito tempo fazendo coisas que, mesmo que sejam gostosas e agradáveis, ocupam muito do seu tempo.

Você terá de priorizar e fará escolhas difíceis.

Motivação

Eu tinha um motivador muito forte que era me tornar um desenvolvedor e me mudar para a Europa. Esse foi meu objetivo por muito, muito tempo. Cheguei ao ponto de ficar frustrada por não estar conseguindo. Todos os meus amigos saíram da cidade, praticamente não tenho família aqui, me senti isolada e queria ir embora.

Foi isso que me impulsionou. Parecia um fogo debaixo dos meus pés, eu sentia que não tinha escolha. Você precisa de uma forte motivação para fazer mudanças radicais. Eu não sei vocês, mas eu sou uma pessoa do tipo "não conserte o que não está quebrado". Então, é muito difícil me fazer fazer as coisas apenas por fazê-las.

Meus hobbies são todos muito práticos e produtivos: jardinagem, yoga, culinária. Eu preciso ter um motivo para fazê-los (eu quero vegetais grátis, minhas costas doem, estou com fome). Se você é parecido ou parecida comigo, vai precisar encontrar uma motivo para seguir em frente.

Passe algum tempo pensando sobre isso, o que exatamente você quer realizar terminando o freeCodeCamp? O que você quer mudar ou obter em sua vida pessoal através disso?

O currículo e os recursos complementares

A seguir estão alguns dos recursos suplementares que usei na minha jornada com o freeCodeCamp. Tenha em mente que esta não é uma lista exaustiva porque eu consultei demais o Google – e que alguns dos cursos que eu menciono não são gratuitos.

Design responsivo para a Web: essa era a parte com a qual eu já tinha alguma experiência, então foi fácil e divertido. Utilizei alguns recursos complementares, especialmente para o Flexbox. Meu lugar favorito para isso é o Interneting is hard (em inglês).

Algoritmos e estruturas de dados em JavaScript: uma vez que cheguei aos módulos de JavaScript fiquei viciada. Foi tudo muito divertido, aprendi muito e estava ansiosa para colocar tudo isso em prática.

Para essa seção usei livros, principalmente. Eu já tinha feito muitos exercícios com o freeCodeCamp, mas eu precisava de mais no formato de explicações. O livro Beginning JavaScript traz toneladas de exercícios também.

• Beginning JavaScript 5th edition
• You Don’t Know JS
• Programming Foundations with JavaScript, HTML and CSS
• Documentação do JavaScript

Quando cheguei a essa seção, também entrei no programa Summer of Code do 1 Million Women to Tech (1MWTT). Aprendi Python básico e JavaScript do básico ao avançado, o que ajudou muito, principalmente com Promises.

Aprender Python também me ajudou a reforçar alguns conceitos básicos de programação. Eu recomendo seriamente que, quando você se sentir confiante com JavaScript, tente uma nova linguagem, apenas seus conceitos básicos. Você ficará muito mais confortável depois de saber como fazer a mesma coisa com ferramentas diferentes.

Frameworks do JavaScript: esta seção também foi ótima, pois me deu uma base em React e Redux. Eu já estava fazendo um curso de React na Udemy, chamado React 16.6 - The Complete Guide (including React Router & Redux) (curso em inglês).

Recomendo esse curso e outros cursos do mesmo autor. Ele é incrivelmente minucioso e suas explicações são incríveis. Esse foi um dos poucos cursos da Udemy em que eu realmente acompanhei o projeto que ele faz: normalmente assisto os vídeos e aplico os princípios em tudo o que estou trabalhando.

Na 1millionwomentotech, tivemos uma semana do React, que usava principalmente o React Native, então comecei a brincar com isso. Nessa altura também comecei a trabalhar no meu projeto paralelo com o meu marido, que decidimos que seria um PWA com o React.

Não posso enfatizar o quanto é importante construir algo próprio do zero. Aprendi muito mais em algumas semanas construindo nossa aplicação do que aprendi com qualquer curso ou tutorial.

APIs e microsserviços: esta seção foi uma grande revelação para mim e mudou tudo. Até esse módulo, eu tinha certeza de que queria ser uma desenvolvedora de front-end, mas, depois de aprender Node.js, comecei a pensar em ser uma desenvolvedora back-end ou Full Stack. Criar APIs é muito divertido – e você vê os resultados rapidamente. Comecei a construir meus primeiros pequenos projetos Full Stack e fiquei muito animada.

Alguns dos recursos que utilizei (em inglês):

• The Complete Node.js Developer Course (2nd Edition)
• Node Girls Intro to Backend Development with Express
• Documentação do Node
• Documentação do Express
• NodeSchool
• Introduction to Node.js
• REST & GraphQL API Design in Node.js, v2 (using Express & MongoDB)

Durante esse tempo, eu também estava me voluntariando para a "1MWTT" e me pediram para construir uma aplicação de Probot para a integração de voluntários com o Node. Isso também me deu um pouco de prática com o Node, o que foi muito divertido.

QA e segurança da informação: este módulo também ajudou a abrir meus olhos. Até então, eu nunca tinha escrito um único teste na minha vida. Agora, eu adoro escrever testes e até fiquei muito interessada em Test Driven Development.

Eu usei, principalmente, as documentações para essa seção, mas então decidi testar meu front-end também, e encontrei este curso incrível na Udemy que não posso recomendar o suficiente. A instrutora é de longe a melhor instrutora que já vi na Udemy. Mal posso esperar para consumir quaisquer outros cursos que ela lance no futuro.

- Documentação do Chai

- React Testing with Jest and Enzyme

Visualização de dados com o D3: este foi o certificado mais difícil, com certeza. As explicações foram boas, mas uma vez que você chega aos projetos, descobre que os desafios cobrem apenas o primeiro projeto, e você está meio sozinho para o resto. Não há muitos bons recursos on-line. Li principalmente as documentações e usei tutoriais. Aqui estão os recursos que finalmente me fizeram passar por essa certificação:

DTutoriais de D3.js, por d3Vienno

- Documentação do D3

Dicas para terminar o currículo

Resumindo, essas são as coisas que mais me ajudaram a cumprir meu objetivo de terminar o currículo:

• Use o currículo como um roteiro, mas complemente com outros recursos
• Não fique preso por muito tempo: faça perguntas, consulte o Google, programe com seus pares.
• Estabeleça metas realistas para cada dia e semana. Não sofra se em uma semana você estiver mais lenta: a vida acontece. Não deixe que isso tire você do rumo.
• Tenha sua motivação em mente: é o que vai garantir que você siga, mesmo nos dias difíceis.
• Priorize: você terá que reduzir o tempo que gasta fazendo outras coisas.
• Não se esqueça de tirar dias de folga. Eles são vitais para o processo de aprendizagem. Não se esqueça, também, de dormir o suficiente!

Depois do freeCodeCamp, me senti um pouco perdida. Esse foi o roteiro que me guiou através da minha jornada de professora a desenvolvedora.

Depois de alguns dias de reflexão e planejamento, me dediquei ao meu projeto paralelo que estou construindo com meu marido. Estamos aprendendo e nos divertindo e estamos muito animados com isso.

Sim, eu recebi uma oferta de emprego logo após terminar o currículo, mas falarei mais sobre isso em um próximo artigo.

Em resumo, eu não poderia ter aprendido tudo o que aprendi tão rapidamente se não fosse pelo freeCodeCamp e sou extremamente grata a todos que tornam possível um projeto tão maravilhoso.

Se você sente o mesmo e é capaz de retribuir, considere fazer uma doação para o freeCodeCamp aqui.

Escrito por: Sachin Malhotra

Você sabe qual foi o volume global de tráfego aéreo em 2017? Sabe qual foi o aumento do tráfego aéreo nos últimos anos? Bem, vamos dar uma olhada em alguns dados.

De acordo com a Organização da Aviação Civil Internacional (ICAO), um recorde de 4,1 bilhões de passageiros foram transportados pelo setor de aviação em 2017. Além disso, o número de voos no mundo subiu para 37 milhões em 2017.

São muitos passageiros, e muitos voos ocupando o espaço aéreo diariamente no mundo inteiro. Como existem centenas de milhares desses voos, é provável que existam rotas diferentes que tenham mais de uma parada entre um lugar e outro.

Cada voo tem sua própria origem e destino, bem como um preço padrão de assento de classe econômica associado a ele. Vamos deixar de lado as passagens sofisticadas da classe executiva, o espaço adicional para as pernas e tudo mais!

Nesse cenário, é muito confuso escolher qual voo seria o melhor se quiséssemos ir de um lugar para outro.

Vamos ver o número de opções de voos que o StudentUniverse (oferece descontos para estudantes 😜) me proporciona, partindo de Los Angeles a Nova Délhi.

Estão sendo oferecidos 119 voos no total. Em seguida, aparece um pop-up no site informando que há outros sites que podem estar oferecendo voos semelhantes com tarifas ainda mais baratas. 😩

Uma variedade de sites e incontáveis voos – e estamos falando apenas de uma origem e destino.

Como desenvolvedor, se eu quisesse resolver esse problema, criaria um sistema para atender com eficiência às seguintes consultas:

• Número total de destinos acessíveis (com um número máximo de paradas) a partir da minha localização atual, listando também esses destinos.
  É preciso manter as opções em aberto quando se deseja viajar 😃.
• É um fato conhecido (minha opinião 😉) que rotas com escalas tendem a ser mais baratas que voos diretos.
  Assim, dada uma origem e um destino, podemos querer encontrar rotas com pelo menos 2 ou 3 paradas.
• Mais importante: qual é a rota mais barata, dada uma origem e destino?
• E.... bem, vamos deixar isso pro final 🙈.

Como você pode imaginar, existiriam potencialmente milhares de voos como resultado das duas primeiras consultas. Certamente, porém, podemos reduzir isso fornecendo alguns outros critérios para diminuir o tamanho do resultado. Para o escopo deste artigo, vamos nos concentrar nesses tipos de consultas.

Modelando a rede aérea como um grafo

O título deste artigo deixa bem claro que os grafos estariam envolvidos em algum lugar, não é mesmo?

Modelar esse problema como um problema de travessia de grafo simplifica bastante, tornando-o muito mais fácil de ser tratado. Portanto, como primeira etapa, vamos definir nosso grafo.

Modelamos o tráfego aéreo como um grafo:

• direcionado
• possivelmente cíclico
• ponderado
• de floresta. G (V, E)

Direcionado porque cada voo terá uma origem e destino designados. Isso significa muita coisa.

Cíclico porque há grande possibilidade de encontrar vários voos que partam de um determinado local e terminem no mesmo local.

Ponderado porque cada voo tem um custo associado a ele – no caso, poderia ser o custo da passagem aérea da classe econômica citada no início deste artigo.

Por fim, é um grafo de floresta porque podemos ter múltiplos componentes conectados. Não é necessário que todas as cidades do mundo tenham algum tipo de rede aérea entre elas. Assim, o grafo pode ser desconectado e, portanto, uma floresta.

Os vértices, V, seriam os locais em todo o mundo onde há aeroportos em funcionamento.

As arestas, E (do inglês, edges), representariam todos os voos que constituem o tráfego aéreo. Uma aresta u --> v simplesmente significa que você tem um voo direcionado da localização/nó u até v .

Agora que temos uma ideia de como modelar a rede aérea em um grafo, vamos prosseguir e resolver a primeira consulta básica que um usuário pode ter.

Número total de destinos acessíveis

Quem não gosta de viajar?

Como alguém que gosta de explorar lugares diferentes, seria interessante saber quais destinos são acessíveis a partir de seu aeroporto local. Novamente, haveria critérios adicionais aqui para reduzir os resultados dessa consulta. Para fins didáticos, vamos apenas encontrar todos os locais acessíveis a partir de nosso aeroporto local.

Agora que temos um grafo bem definido, podemos aplicar algoritmos de travessia para o computar.

A partir de um determinado ponto, podemos usar a busca em largura (BFS, do inglês, Breadth-First Search) ou a busca em profundidade (DFS, do inglês, Depth-First Search) para examinar o grafo ou os locais acessíveis a partir da localização inicial que tenham um número máximo de paradas. Como este artigo trata exclusivamente do algoritmo de busca em largura, vamos ver como podemos usar o famoso BFS para realizar essa tarefa.

Vamos inicializar a fila do BFS com o local fornecido como o ponto de partida. Em seguida, executamos o primeiro percurso em largura e continuamos até que a fila esteja vazia ou até que o número máximo de paradas tenha se esgotado.

Observação: se você não estiver familiarizado com a busca em largura ou com a em profundidade, recomendo que leia este artigo (texto em inglês) antes de continuar.

Vamos dar uma olhada no código que inicializa a nossa estrutura de dados do grafo. Também precisamos analisar como o algoritmo do BFS acabaria nos fornecendo todos os destinos acessíveis a partir de uma determinada origem.

from collections import defaultdict
from pprint import pprint 
class FlightNetwork:
	def __init__(self):
		self.neighbors = defaultdict(list)
		self.cost = defaultdict(list)
		
	def add_flight(self, source, destination, price):
		self.neighbors[source].append(destination)
		self.cost[source].append(price)
	
	def show_flights(self):
		print("Destinos:");pprint(dict(self.neighbors))
		print("Custo:");pprint(dict(self.cost))
        
f = FlightNetwork()
f.add_flight('Los Angeles', 'New Delhi', 200)
f.add_flight('Los Angeles', 'Japan', 87)
f.add_flight('Germany', 'New Delhi', 125)
f.add_flight('Italy', 'Los Angeles', 150)
f.add_flight('New Delhi', 'France', 100)
f.add_flight('Los Angeles', 'France', 200)
f.add_flight('Italy', 'New Delhi', 300)
f.add_flight('France', 'Norway', 175)
f.add_flight('Ireland', 'Chicago', 100)
f.add_flight('Chicago', 'Italy', 135)
f.add_flight('Los Angeles', 'Ireland', 100)
f.add_flight('Ireland', 'New Delhi', 200)
f.show_flights()
Destinos:
{	
	'Chicago': ['Italy'],
 	'France': ['Norway'],
	'Germany': ['New Delhi'],
 	'Ireland': ['Chicago', 'New Delhi'],
 	'Italy': ['Los Angeles', 'New Delhi'],
 	'Los Angeles': ['New Delhi', 'Japan', 'France', 'Ireland'],
 	'New Delhi': ['France']
 }
Custo:
{
	'Chicago': [135],
 	'France': [175],
 	'Germany': [125],
 	'Ireland': [100, 200],
 	'Italy': [150, 300],
 	'Los Angeles': [200, 87, 200, 100],
 	'New Delhi': [100]
 }

Agora que temos uma boa ideia de como o grafo deve ser inicializado, vamos dar uma olhada no código do algoritmo do BFS.

Executando o bfs na cidade de Los Angeles, o resultado seriam os seguintes destinos acessíveis:

{'Chicago', 'France', 'Ireland', 'Italy', 'Japan', 'New Delhi', 'Norway'}

Isso foi simples, não?

Veremos como podemos limitar o BFS a um número máximo de paradas mais adiante neste artigo.

Se tivéssemos uma rede aérea enorme, que é o que teríamos em um cenário de produção, então não desejaríamos necessariamente saber todos os destinos possíveis de um determinado ponto de partida.

Esse é um caso de uso quando a rede aérea for muito pequena ou pertencer apenas a poucas regiões dos Estados Unidos.

Porém, para uma rede grande, um caso de uso mais realista seria encontrar todas as rotas de voo que possuem várias paradas. Vamos examinar esse problema mais a fundo e ver como podemos resolvê-lo.

Rotas com múltiplas paradas

É um fato bastante conhecido que, normalmente, para uma determinada origem e destino, uma viagem com múltiplas paradas é mais barata que um voo direto, sem escalas.

Muitas vezes, preferimos o voo direto para evitar as escalas, em especial porque os voos com várias paradas tendem a tomar muito tempo – o que não temos.

No entanto, se você não tiver nenhum compromisso urgente e quiser economizar algum dinheiro (e se sentir confortável com o voo que tem escalas – opção oferecida por diversas companhias aéreas) poderá, na verdade, se beneficiar muito ao fazer essa escolha.

Você pode passar por alguns dos lugares mais bonitos do mundo com seus modernos aeroportos. Isso já pode ser motivação o suficiente.

Em termos do modelo de grafo sobre o qual estávamos falando, dada uma origem e um destino, precisamos criar rotas com 2 ou mais paradas para uma origem e destino fornecidos.

Para um usuário final, pode ser que a resposta abaixo não seja a melhor:

[A, C, D, B], 2 paradas, $X
[A, E, D, C, F, W, G, T, B], 8 paradas, $M
[A, R, E, G, B], 3 paradas, $K
[A, Z, X, C, V, B, N, S, D, F, G, H, B, 11 paradas, $P

Eu sei. Ninguém em sã consciência escolheria um voo com 11 paradas, mas o que estou tentando dizer é que um usuário final espera simetria. Ou seja, ele desejaria ver primeiro todos os voos com 2 paradas, depois todos os voos com 3 e assim por diante até um máximo de, digamos, 5 paradas.

Porém, todas as rotas de voo com o mesmo número de paradas entre elas devem ser exibidas juntas. Esse é um requisito necessário.

Então, vamos ver como podemos resolver isso. Dado um grafo de redes aéreas, um ponto de partida S (do inglês, source) e um destino D, precisamos realizar um percurso em nível e guardar as rotas de voo de S --> D com pelo menos 2 e no máximo 5 paradas entre elas. Isso quer dizer que precisamos realizar um percurso em nível até uma profundidade de 7 partindo do nó inicial S.

Aqui está o código para resolver esse problema:

{'A': ['C', 'B', 'F'],
 'B': ['D'],
 'C': ['B', 'M', 'E', 'F'],
 'D': ['C', 'E', 'F'],
 'E': ['F'],
 'M': ['F']}
Custo:
{'A': [10, 20, 14],
 'B': [20],
 'C': [120, 200, 145, 50],
 'D': [75, 45, 60],
 'E': [60],
 'M': [45]}
parent = f.level_order_traversal('A', 'F', (2,5))
for r in range(2, 6):
    print("\nOs voos com {} paradas no meio são os seguintes:".format(r))
    routes = f.get_route(('F', r), 'A', parent)
    for r in routes:
        print(r)
Os voos com 2 paradas no meio são os seguintes:
A-->C-->M-->F
A-->C-->E-->F
A-->B-->D-->F

Os voos com 3 paradas no meio são os seguintes:
A-->C-->B-->D-->F
A-->B-->D-->C-->F
A-->B-->D-->E-->F

Os voos com 4 paradas no meio são os seguintes:
A-->C-->B-->D-->C-->F
A-->C-->B-->D-->E-->F
A-->B-->D-->C-->E-->F
A-->B-->D-->C-->M-->F
A-->C-->B-->D-->E-->F
A-->B-->D-->C-->E-->F

Os voos com 5 paradas no meio são os seguintes:
A-->C-->B-->D-->C-->M-->F
A-->C-->B-->D-->C-->E-->F
A-->B-->D-->C-->B-->D-->F

Essa pode não ser a melhor maneira de resolver esse problema quando ele for muito grande – uma grande restrição de memória aconteceria por conta dos nós presentes na fila no momento.

Como cada nó, ou localização, pode ter milhares de voos para diferentes destinos do mundo, a fila poderia se tornar enorme se fôssemos armazenar dados reais de voos dessa maneira. Esse exemplo é apenas para demonstrar um dos casos de uso do algoritmo de busca em largura.

Por agora, vamos nos concentrar apenas no percurso e ver o que acontece na prática. O algoritmo de percurso é simples, porém, toda a complexidade espacial do percurso em nível se dá graças a elementos presentes na fila e de seu tamanho.

Existem muitas formas de se implementar esse algoritmo. Além disso, cada uma delas varia em termos de consumo máximo memória em determinado momento pelos elementos presentes na fila.

Queremos saber o consumo máximo de memória da fila em um dado momento durante o percurso em nível. Antes disso, vamos construir uma rede aérea aleatória com preços aleatórios.

from collections import defaultdict
import random
from pprint import pprint

def add_edge(s, d, adj_list):
    adj_list[s].append(d)

nodes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']  
adj_list = defaultdict(list)
for i, s in enumerate(nodes[:5]):
    for i in range(10 - i):
        while True:
            d = (nodes[random.randint(0, 8)], "$"+str(random.randint(50, 500)))
            if d[0] != s:
                break
        add_edge(s, d, adj_list)

Agora a implementação do percurso em nível.

import sys
def level_order_naive(source, max_level):
    queue = [(source, 0)]
    max_memory = 0
    levels = []
    while queue:
        max_memory = max(max_memory, sum(list(map(sys.getsizeof, queue))))
        element, level = queue.pop(0)
        levels.append((element, level))
        if level == max_level:
            continue
        if element in adj_list:
            for neighbor in adj_list[element]:
                queue.append((neighbor[0], level + 1))
                
    return max_memory, levels  

Essa, por sinal, é a implementação mais simples e direta do algoritmo de percurso em nível.

Junto a cada nó que adicionamos à fila, armazenamos também as informações de nível e uma tupla de (nó, nível) dentro da fila. Assim, toda a vez que removermos um elemento da fila, teremos as informações do nível em que estava.

As informações de nível, para nosso caso de uso, são o número de paradas desde a origem até esse local específico em nossa rota de voo.

A questão é que podemos fazer otimizações, já que consumo de memória no programa precisa ser levado em consideração. Aqui está uma abordagem um pouco melhorada de como se fazer o percurso em nível.

def level_order_NULL(source, max_level):
    queue = [source, None]
    max_memory = 0
    level = 0
    levels = []
    while queue:
        max_memory = max(max_memory, sum(list(map(sys.getsizeof, queue))))
        element = queue.pop(0)
        if element:
            levels.append((element, level))
        if level == max_level:
            continue
        if not element:
            level += 1
            queue.append(None)
            continue
            
        if element in adj_list:
            for neighbor in adj_list[element]:
                queue.append(neighbor[0])
                
    return max_memory, levels 

A ideia aqui é que não vamos armazenar nenhuma informação extra aos nós que estão sendo adicionados na fila. Usamos um objeto None para marcar o fim do nível. Não sabemos o tamanho de nenhum nível de antemão a não ser o do primeiro nível, que tem apenas o nosso nó source.

Assim, iniciamos a fila com [source, None] e continuamos a remover elementos. Toda vez que encontramos um elemento None, saberemos que o nível terminou e que o seguinte começou. Adicionamos outro None para marcar o final desse novo nível.

Considere o simples grafo abaixo. Vamos ver rapidamente como isso funcionaria na prática.

**************************************************** LEVEL 0 begins
level = 0, queue = [A, None]
level = 0, pop, A, push, B, C, queue = [None, B, C]
pop None ******************************************* LEVEL 1 begins
push None
level = 1, queue = [B, C, None]level = 1, pop, B, push, C, D, F, queue = [C, None, C, D, F]
level = 1, pop, C, push, D, D (lol!), queue = [None, C, D, F, D, D]
pop None ******************************************* LEVEL 2 begins
push None
level = 2, queue = [C, D, F, D, D, None] .... e assim por diante

Espero que a explicação tenha esclarecido o funcionamento do algoritmo. Esse certamente é um método interessante de se fazer o percurso em nível, monitorar níveis e não se preocupar muito com o uso de memória. Sem dúvida, reduz o volume de memória usado pelo código.

Porém, não fique muito entusiasmado pensando que isso foi uma melhoria significativa.

Quero dizer, é significativa, mas você deveria estar se fazendo duas perguntas:

1. De que tamanho foi essa melhoria?
2. Podemos melhorar ainda mais?

Vou responder as duas e começarei pela segunda. A resposta é Sim!

Podemos fazer uma melhoria aqui ao eliminar completamente a necessidade do None dentro da fila. A motivação para essa abordagem vem da própria abordagem anterior.

Se você observar atentamente o algoritmo acima, perceberá que toda vez que retiramos um None, um nível é concluído e outro está pronto para ser processado. O importante é que exista um nível seguinte inteiro dentro da fila no momento em que ocorre a remoção do None. Podemos utilizar essa ideia de considerar o tamanho da fila na lógica do percurso.

Aqui está o pseudocódigo desse algoritmo otimizado:

queue = Queue()
queue.push(S)
level = 0
while queue is not empty {
	size = queue.size()
    // size representa o número de elementos no nível atual
    for i in 1..size {
    	element = queue.pop()
        // Processe o elemento aqui
        // Realize uma série de operações queue.push() aqui
    level += 1

Aqui está o código dele.

def level_order_queue_size(source, max_level):
    queue = [source]
    max_memory = 0
    levels = []
    level = 0
    while queue:
        max_memory = max(max_memory, sum(list(map(sys.getsizeof, queue))))
        size = len(queue)
        for _ in range(size):
            element = queue.pop(0)
            levels.append((element, level))
            if level == max_level:
                continue
            if element in adj_list:
                for neighbor in adj_list[element]:
                    queue.append(neighbor[0])
        level += 1            
                
    return max_memory, levels  

O pseudocódigo é autoexplicativo. Basicamente, eliminamos a necessidade de um elemento None por nível e, ao invés disso, usamos o tamanho da fila para mudar de nível. Isso também leva a uma melhoria em relação ao último método, mas em que proporção?

Dê uma olhada no Jupyter Notebook a seguir para ver a diferença de consumo de memória entre os três métodos.

from collections import defaultdict
import random
from pprint import pprint

def add_edge(s, d, adj_list):
    adj_list[s].append(d)

nodes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']  
adj_list = defaultdict(list)
for i, s in enumerate(nodes[:5]):
    for i in range(10 - i):
        while True:
            d = (nodes[random.randint(0, 8)], "$"+str(random.randint(50, 500)))
            if d[0] != s:
                break
        add_edge(s, d, adj_list)
adj_list['A']
[('G', '$418'), ('F', '$75'), ('H', '$141'), ('D', '$203'), ('D', '$101'), ('I', '$51'), ('G', '$187'), ('H', '$137'), ('F', '$425'), ('F', '$69')]
import sys
def level_order_naive(source, max_level):
    queue = [(source, 0)]
    max_memory = 0
    levels = []
    while queue:
        max_memory = max(max_memory, sum(list(map(sys.getsizeof, queue))))
        element, level = queue.pop(0)
        levels.append((element, level))
        if level == max_level:
            continue
        if element in adj_list:
            for neighbor in adj_list[element]:
                queue.append((neighbor[0], level + 1))
                
    return max_memory, levels                
max_memory, levels = level_order_naive('A', 5)
max_memory, levels[50:60],len(levels)
(20224, [('H', 3), ('I', 3), ('D', 3), ('B', 3), ('B', 3), ('A', 3), ('B', 3), ('F', 3), ('I', 3), ('G', 3)], 523)
def level_order_NULL(source, max_level):
    queue = [source, None]
    max_memory = 0
    level = 0
    levels = []
    while queue:
        max_memory = max(max_memory, sum(list(map(sys.getsizeof, queue))))
        element = queue.pop(0)
        if element:
            levels.append((element, level))
        if level == max_level:
            continue
        if not element:
            level += 1
            queue.append(None)
            continue
            
        if element in adj_list:
            for neighbor in adj_list[element]:
                queue.append(neighbor[0])
                
    return max_memory, levels 
max_memory, levels = level_order_NULL('A', 5)
max_memory, levels[50:60], len(levels)
(15816, [('H', 3), ('I', 3), ('D', 3), ('B', 3), ('B', 3), ('A', 3), ('B', 3), ('F', 3), ('I', 3), ('G', 3)], 523)
def level_order_queue_size(source, max_level):
    queue = [source]
    max_memory = 0
    levels = []
    level = 0
    while queue:
        max_memory = max(max_memory, sum(list(map(sys.getsizeof, queue))))
        size = len(queue)
        for _ in range(size):
            element = queue.pop(0)
            levels.append((element, level))
            if level == max_level:
                continue
            if element in adj_list:
                for neighbor in adj_list[element]:
                    queue.append(neighbor[0])
        level += 1            
                
    return max_memory, levels              
max_memory, levels = level_order_queue_size('A', 5)
max_memory, levels[50:60], len(levels)
(15800, [('H', 3), ('I', 3), ('D', 3), ('B', 3), ('B', 3), ('A', 3), ('B', 3), ('F', 3), ('I', 3), ('G', 3)], 523)
sys.getsizeof(('A', 4))
64
sys.getsizeof(None)
16

• Monitoramos o tamanho máximo da fila a qualquer momento quando consideramos a soma dos tamanhos de cada elemento contido na fila.
• De acordo com a documentação do Python, sys.getsizeof retorna o ponteiro do objeto, ou tamanho, da referência em bytes. Assim, economizamos praticamente 4.4Kb de espaço (20224 — 15800 bytes) quando alteramos o algoritmo original do percurso em nível para usar None. Esta é apenas a economia de memória desse exemplo aleatório que usamos, e descemos apenas até o 5° nível do percurso.
• O último método economiza apenas 16 bytes em relação ao método com None. Isso acontece porque apenas eliminamos os 4 objetos None que estavam sendo usados para marcar os 4 níveis (com exceção do primeiro) que foram processados. Cada ponteiro (ponteiro para um objeto) tem um tamanho de 4 bytes no Python rodando em um ambiente de 32 bits.

Agora que temos todas essas rotas interessantes de múltiplos caminhos, partindo de nossa origem a nosso destino, e algoritmos de percurso em nível altamente eficientes para resolver esse problema, podemos analisar um problema mais lucrativo para resolver usando nosso BFS.

Qual é a rota de voo mais barata, partindo da minha origem até um determinado destino? Eis ai algo capaz de despertar o interesse de todos imediatamente. Quero dizer, quem não quer economizar dinheiro?

Caminho mínimo de uma determinada origem a um destino

Não há muita descrição a ser dada para o enunciado do problema. Precisamos apenas encontrar o caminho mínimo e deixar o usuário final satisfeito.

Algoritmicamente, dado um grafo direcionado ponderado, precisamos encontrar o caminho mínimo da origem ao destino. O mais curto ou o mais barato seriam a mesma coisa do ponto de vista do algoritmo.

Não vamos descrever uma possível solução BFS para esse problema porque por ela o problema é intratável. Vejamos o grafo abaixo para entender por que esse é o caso.

Dizemos que o BFS é o algoritmo a ser usado se quisermos encontrar o caminho mínimo em um grafo não direcionado e não ponderado (texto em inglês). O princípio do BFS é que, na primeira vez que um nó é descoberto durante o percurso, a distância entre ele e o ponto de partida se torna o caminho mínimo.

O mesmo não pode ser dito de um grafo ponderado. Considere o grafo acima. Se, por exemplo, tivéssemos que encontrar o caminho mínimo do nó A ao B numa versão não direcionada desse grafo, então o caminho mínimo seria a aresta que liga A a B. Assim, o caminho mínimo teria tamanho 1 e o BFS funcionaria com precisão.

Entretanto, estamos lidando com um grafo ponderado. Logo, a primeira descoberta de um nó durante o percurso não garante o caminho mínimo para esse nó. Por exemplo, no diagrama acima, o nó B seria descoberto logo no início porque é vizinho de A e o custo associado a esse caminho (uma aresta, nesse caso) seria 25 . Porém, esse não é o caminho mínimo. O caminho mínimo é A --> M --> E --> B , que tem tamanho 10.

A busca em largura não tem como saber se a descoberta de um nó em particular vai nos fornecer o caminho mínimo para esse nó. Portanto, a única maneira possível de o BFS (ou DFS) encontrar o caminho mínimo em um grafo ponderado é varrendo o grafo inteiro e ir registrando a distância mínima da origem até o vértice destino.

Essa solução não é viável para uma rede enorme como a nossa rede aérea, que provavelmente teria milhares de nós.

Não entraremos em detalhes sobre como podemos lidar com isso. Está fora do escopo deste artigo.

O que você faria se eu dissesse que o BFS é o algoritmo certo para encontrar o caminho mínimo em um grafo ponderado sob uma pequena condição?

via GIPHY

Caminhos mínimos com restrições

Como o grafo que teríamos para a rede aérea é enorme, sabemos que explorá-lo completamente não é uma possibilidade plausível.

Considere o problema dos caminhos mínimos a partir da perspectiva de um cliente. Quando ele quer reservar um voo, estas são as opções que ele idealmente considera:

• O voo não deve ser muito longo
• Deve caber no orçamento (muito importante)
• Pode ter algumas paradas, mas não mais do que K, onde K pode variar dependendo do cliente.
• Por fim, temos as preferências pessoais que envolvem coisas como acesso a lounges, qualidade da comida, locais de escala e espaço médio para as pernas.

O ponto principal a ser considerado aqui é o terceiro: pode ter algumas paradas, mas não mais do que K, onde K pode variar dependendo do cliente.

O cliente quer a rota de voo mais barata, mas também não quer, digamos, 20 paradas entre seu ponto de partida e seu destino. O cliente pode concordar com um máximo de 3 paradas ou, em casos extremos, talvez até 4, mas não mais do que isso.

Gostaríamos de ter um programa que descobrisse a rota de voo mais barata com no máximo K paradas para uma determinada origem e destino.

Essa questão do LeetCode foi a principal motivação para que eu escrevesse este artigo. Recomendo fortemente que você analise a questão ao menos uma vez e não confie somente no print que está acima.

"Por que o BFS funcionaria aqui?", alguém poderia perguntar. "Esse também é um grafo ponderado e o motivo pelo qual o BFS não funciona nele. Assim como discutimos na seção anterior, o conceito deveria ser o mesmo." NÃO!

O número de níveis alcançados pela busca é limitado pelo valor de K em questão, descrição fornecida no início da seção. Portanto, essencialmente, estaríamos buscando o caminho mínimo, mas não precisaríamos varrer o grafo inteiro. Vamos apenas até o nível K.

Em um cenário real, o valor de K seria menor que 5 para qualquer passageiro mentalmente são 😝.

Vamos analisar o pseudocódigo do algoritmo:

def bfs(source, destination, K):
      min_cost = dictionary representing min cost under K stops for each node reachable from source. 
      set min_cost of source to be 0
      Q = queue()
      Q.push(source)
      stops = 0
      while Q is not empty {
           size = Q.size
           for i in range 1..size {
                 element = Q.pop() 
                 if element == destination then continue
                 for neighbor in adjacency list of element {
                        if stops == K and neighbor != destination        then continue  
                        if min_cost of neighbor improves, update and add back to the queue.
                }
           }    
           stops ++ 
      }

Novamente, trata-se de um percurso em nível, e a abordagem usada aqui é a que faz uso do tamanho da fila em todos os níveis. Vamos dar uma olhada em uma versão comentada do código para resolver esse problema.

from collections import defaultdict
class Solution:
    def findCheapestPrice(self, n, flights, src, dst, K):
        """
        :type n: int
        :type flights: List[List[int]]
        :type src: int
        :type dst: int
        :type K: int
        :rtype: int
        """
        
        # Construa a estrutura de lista de adjacência para ser usada na travessia de ordem de nível. 
        adj_list = defaultdict(list)
        for s, d, cost in flights:
            adj_list[s].append((d, cost)) 
        
        # Inicie um dicionário com os valores de custo mínimo como +inf e 0 para o nó de origem. 
        min_cost = {k: float("inf") for k in range(n)}
        min_cost[src] = 0
        queue = [src]
        stops = 0
        
        # Execute o while enquanto a fila não estiver vazia, ou seja, enquanto não tivermos examinado todos os nós possíveis de acordo com as restrições. 
        while queue:
            size = len(queue)
            for _ in range(size):
                element = queue.pop(0)
                # Quando um elemento é removido da fila, seu custo atual será o custo mínimo até o momento, da origem até aquele elemento. 
                cost = min_cost[element]
                
                # Não é necessário processar os filhos do nó de destino. 
                if element == dst:
                    continue
                
                # Se esse nó tiver vizinhos
                if element in adj_list:
                    for neighbor, direct_flight_cost in adj_list[element]:
                           
                        # Não é necessário atualizar o custo mínimo se já esgotamos nossas K paradas.
                        if stops == K and neighbor != dst:
                            continue
                        
                        # Se o comprimento do caminho mínimo atual para `neighbor` puder melhorar, melhore e faça a nova fila
                        if  direct_flight_cost + cost <  min_cost[neighbor]:
                            min_cost[neighbor] = direct_flight_cost + cost
                            queue.append(neighbor)
                            
            # Incremente o nível                
            stops += 1                
        return -1 if min_cost[dst] == float("inf") else  min_cost[dst]

Essencialmente, mantemos o controle da distância mínima de cada nó em relação a uma determinada origem. A distância mínima para a origem seria 0 e +inf para todos os outros inicialmente.

Sempre que encontrarmos um nó, checamos se o comprimento mínimo do caminho em questão pode ser melhorado ou não. Se puder ser melhorado, isso significa que encontramos um caminho alternativo da origem até esse vértice que tem um custo menor - uma rota de voo mais barata até esse vértice. Colocamos esse vértice na fila novamente para que os locais e nós acessíveis a partir desse vértice também sejam atualizados (podendo ou não ser).

O ponto chave é esse:

# Não é necessário atualizar o custo mínimo se já esgotamos nossas K paradas. 
if stops == K and neighbor != dst:    continue

Assim, retiramos o nó A representado por element no código e neighbor pode tanto ser um destino como outro nó qualquer. Se já tivermos esgotado nossas K paradas com o element sendo a K-ésima parada, então não devemos processar e atualizar (possivelmente) a distância mínima para o neighbor. Isso violaria nossa condição de K  paradas nesse caso.

Como podem ver, resolvi esse problema originalmente usando programação dinâmica e levou cerca de 165ms para executar no site LeetCode. Executei usando BFS e foi megarrápido, levando apenas 45ms para executar. Essa foi motivação o suficiente para escrever este artigo para vocês.

Espero que tenham aproveitado este artigo sobre a busca em largura e algumas de suas aplicações. O foco principal foi mostrar sua aplicação ao problema do caminho mínimo em um grafo ponderado sob algumas condições😃.

Tradução em português europeu

Demorei algum tempo a compreender o que os termos programar e escrever código realmente significam e o que cada campo implica. Tenho a certeza de que não sou o único que ficou confuso com estes termos quando estava a começar na área da tecnologia.

Durante algum tempo pensei que eram a mesma coisa e demorei algum tempo a perceber que existem diferenças entre os dois "mundos".

Neste artigo, vou explicar as diferenças básicas entre escrever código e programar, como cada um funciona e como trabalham em colaboração para desenvolver aplicações e sites.

Então, vamos explorar estes termos e como os profissionais os utilizam, começando por compreender o que eles significam.

O que é escrever código?

Podes ter visto cursos, bootcamps ou artigos a falar sobre escrever código – então porque enfatizamos este termo?

Isto acontece porque o simples ato de escrever código torna possível fazermos todas as coisas interessantes que fazemos todos os dias. Permite-nos utilizar aplicações mobile, trabalhar com programas diferentes e operar sistemas, e até mesmo brincar com os jogos que amamos, ou visitar o website onde estás a ler este artigo. É tudo possível através da escrita de código.

Então, o que é escrever código em termos simples?

Podemos definir a escrita de código como sendo o ato de traduzir instruções para um computador, de uma linguagem humana para uma linguagem que uma máquina consiga compreender. O código indica ao computador como se comportar e que ações deve realizar.

Se quiseres tornar-te um/a escritor/a de código, vais precisar de ter alguns conhecimentos básicos sobre linguagens de programação. Quando digo linguagens de programação, quero dizer linguagens como: Python, Java, Go, PHP ou JavaScript, só para mencionar algumas.

Abaixo está um bom exemplo de código escrito na linguagem Python, que irá converter qualquer PDF num Audiobook:

import PyPDF2                     # pip install pypdf
import pyttsx3                    # pip install pyttsx3
from tkinter.filedialog import *  # pip install tkinter

book = askopenfilename()
pdfReader = PyPDF2.PdfFileReader(book)

pages = pdfReader.numPages

for num in range(0, pages):
    page = pdfReader.getPage(num)
    text = page.extractText()
    speak = pyttsx3.init()
    speak.say(text)
    speak.runAndWait()

O que é programação?

Provavelmente, também já ouviste alguém a dizer, "Sou programador/a". Algumas pessoas que utilizam este termo têm noção do significado do termo, enquanto outras pessoas não. Se não souberes exatamente o que significa programação, vamos tentar alcançar alguns esclarecimentos ao compreender o que realmente é programar.

Programar é o processo de criar as instruções que vão indicar ao computador como realizar uma tarefa em particular que lhe seja atribuída. Fazes isto ao utilizar linguagens de programação como:

Quando falamos de programação, pensa em algo como um controlo remoto da tua televisão – ele aguardará que tu lhe dês instruções ao pressionar diferentes botões, que por sua vez, indicam à televisão para realizar uma tarefa específica (como mudar de canal, aumentar o volume e assim adiante). Bem, é o mesmo modo com que os programadores podem instruir um computador a fazer várias coisas.

Com programação, podes fazer praticamente tudo – como programar robôs para ajudar nas lides domésticas, ou até mesmo programar carros autónomos como a Tesla.

De maneira a que um programador desenvolva um programa que implemente a sua ideia, é necessário realizar as seguintes tarefas:

• Planear a estrutura da aplicação (com a ajuda de ferramentas como o Trello)
• Criar o design da aplicação (ao utilizar ferramentas como Figma ou AdobeXD)
• Desenvolvê-la (ao utilizar a sua linguagem de programação de eleição)
• Testar as suas funcionalidades
• Implementá-la (quer num serviço de alojamento gratuito quer pago)
• Fazer a manutenção depois de estar terminada.

Por isso, como podes ver, podemos dizer que a programação não lida apenas com a própria escrita do código. Também envolve a utilização de estruturas de dados e algoritmos e, em geral, lidar com o panorama geral da criação e desenvolvimento de sistemas complexos.

A diferença entre escrever código e programar

Vamos dividir as diferenças em quatro categorias principais, o que nos vai ajudar a decompor os conceitos e compreendê-los melhor.

A terminologia

Escrever código lida com colocar o código numa linguagem compreendida tanto por máquinas como por humanos. O foco principal da escrita de código é fornecer comunicação entre os dois (humanos e computadores).

Programação envolve criar perfil e estrutura para o código de um programa, que segue determinados padrões, antes de o código em si ser escrito para realizar a tarefa que necessita realizar.

As ferramentas que utilizas

No que diz respeito a escrita de código, uma das ferramentas mais importantes será o teu editor de texto (como o Bloco de notas, ou algo mais complexo e rico em funcionalidades, como o Visual Studio Code, Sublime, Atom ou Vim).

Quando falamos de programação, por outro lado, precisas adicionar algumas outras ferramentas. Como programador/a, irás realizar revisões de documentos, fazer muito planeamento, pensar em design e assim adiante.

Para te ajudar nestas tarefas, vais utilizar ferramentas como editores de código mais avançados, ferramentas de análise, depuradores, frameworks de modelação, ferramentas de montagem, algoritmos de modelação e muito mais.

Como programador/a, vais precisar de ter muita experiência a utilizar estas ferramentas e mais exposição ao processo que os programadores utilizam para criar aplicações e outros produtos.

O teu nível de conhecimentos

Como escritor/a de código, ter conhecimentos básicos de uma linguagem de programação e a sua sintaxe é um bom começo. Assim que souberes como escrever código numa linguagem, fica mais fácil aprender outras. Novamente, o teu principal objetivo está na escrita no próprio código que indica à máquina o que fazer.

Por outro lado, os/as programadores/as precisam de mais conhecimentos. Vais precisar de saber como criar e trabalhar com algoritmos, como desenhar sites, como depurar e testar o teu código, como gerir projetos, e claro, como trabalhar com outras linguagens de programação.

Resolução de problemas, pensamento crítico e habilidades analíticas também são coisas essenciais quando estás a desenvolver sistemas complexos.

O produto final

Como escritor/a de código, o teu resultado esperado é geralmente uma solução simples que, depois de compilada, irá reproduzir com sucesso o resultado desejado. Um bom exemplo é o que demos anteriormente – converter um PDF num ficheiro de áudio.

Por outro lado, os/as programadores/as vão trabalhar para fornecer uma aplicação completa funcional ou um pedaço de software que as pessoas vão utilizar no mercado. Também serão responsáveis por dar seguimento e fazer a manutenção do que criaram para garantir que está a funcionar suavemente, sem nenhum problema.

Como a escrita de código e a programação trabalham em conjunto

Por esta altura, espero que sejas capaz de dizer a diferença entre escrita de código e programação e com o que estas duas coisas lidam. Agora, vamos ver como as duas podem (e devem) trabalhar em conjunto para alcançar muita coisa.

Para compreender melhor o como, vamos começar por fornecer um cenário real, onde ambas, escrita de código e programação, vão ter de trabalhar em conjunto para produzir uma aplicação funcional completa.

Imagina que te deram a tarefa de criar uma aplicação que irá ajudar a gerir ou acompanhar a tua rotina diária ou estar a par das tuas despesas diárias. Ao utilizar os conceitos dos dois mundos, podemos realizar a tarefa.

Vais precisar de um/a programador/a, que será capaz de:

• Planear a estrutura da aplicação (com a ajuda de ferramentas como o Trello)
• Escrever as principais funcionalidades da aplicação, qual a utilização esperada por parte dos utilizadores, etc.
• Desenhar a aplicação (ao utilizar ferramentas como Figma ou Adobexd)

Após completar estes passos, entra o trabalho do/a escritor/a de código. Eles recebem as ideias que o/a programador/a cria e transformam-nas num formato legível para máquinas ao escrever código para realizar as tarefas especificadas. Depois do passo mágico da escrita do código, o/a programador/a volta novamente ao trabalho.

Então, o/a programador/a, irá analisar o código e verificar se existem erros, executará testes e verificará se está tudo a funcionar corretamente e que o código gera o resultado esperado. Se tudo isto se verificar, a aplicação está agora pronta para lançamento e manutenção – que permanece nas mãos do/a programador/a.

Este simples exemplo explica como as duas habilidades podem ser utilizadas em conjunto para melhor produtividade.

Apenas um apontamento final: um/a "escritor/a de código" e um/a "programador/a" nem sempre são duas pessoas distintas. Pode ser que a mesma pessoa realize todas as tarefas.

Resumindo

Onde nos enquadramos nestes dois mundos? Levei bastante tempo a perceber o que realmente me interessa.

Se tiveres mais interesse na lógica, tenta focar as tuas forças em todo o processo da programação. Se simplesmente gostares de ler e escrever código, então investe o teu tempo nisso.

Como sabemos, a ciência da computação é um campo muito amplo e ainda em desenvolvimento. Trabalha em encontrar o caminho que desejas explorar e foca-te nisso – certifica-te apenas que também desfrutas e te divertes.

Se ainda estiveres com dificuldades, espero que este artigo te tenha dado algumas luzes e ajudado a encontrar o teu caminho.

Obrigado por leres até aqui. Se tiveres gostado deste artigo, por favor compartilha-o para que possas ajudar outro programador (ou escritor de código) a encontrar o seu caminho.

Entra em contacto com o autor nas redes sociais: Twitter | LinkedIn | GitHub

Desfruta da programação ❤

Me interrompa agora se você já ouviu isso antes…

"O código bom é aquele que se autodocumenta."

Em mais de 20 anos escrevendo código como profissão, essa foi uma das expressões que eu mais ouvi.

É um clichê daqueles.

Assim como vários outros clichês, há um fundo de verdade aí. Essa verdade, contudo, já foi muito massacrada por pessoas que disseram a frase sem ter ideia do que ela significava.

É verdade? Com certeza.

Quer dizer que você jamais deve fazer comentários no seu próprio código? Não.

Neste artigo, veremos o que é bom, o que é mau e o que é simplesmente feio quando falamos em comentários no código.

Para começar, há dois tipos diferentes de comentários no código. Eu os chamo de comentários de documentação e comentários de esclarecimento.

Comentários de documentação

Os comentários da documentação destinam-se a qualquer pessoa que provavelmente consumirá seu código-fonte, mas que provavelmente não o lerá. Se você estiver criando uma biblioteca ou framework que outros desenvolvedores usarão, você precisará de alguma forma de documentação de API.

Quanto mais distante do código-fonte a documentação da API estiver, maior a probabilidade de ela se tornar desatualizada ou imprecisa ao longo do tempo. Uma boa estratégia para reduzir esse problema é incorporar a documentação diretamente no código e, em seguida, usar uma ferramenta para extraí-la.

Aqui temos um exemplo de comentário de documentação extraída de uma biblioteca conhecida do JavaScript, chamada Lodash (em inglês).

Se você comparar os comentários com o que está na documentação on-line (em inglês), perceberá uma correspondência exata.

Se você escrever comentários de documentação, deve garantir que eles sigam um padrão consistente e que sejam facilmente distinguíveis de quaisquer comentários de esclarecimento incluídos e que você também queira adicionar. Alguns padrões e ferramentas populares e bem suportados incluem JSDoc para JavaScript, DocFx para dotNet e JavaDoc para Java.

A desvantagem desses tipos de comentários é que eles podem tornar seu código muito "cheio de ruído" e mais difícil de ler para qualquer pessoa que esteja ativamente envolvida na manutenção do código. A boa notícia é que a maioria dos editores de código suporta o "dobramento de código", que nos permite recolher os comentários para que possamos nos concentrar no código.

Comentários de esclarecimento

Os comentários de esclarecimento destinam-se a qualquer pessoa (incluindo o seu futuro eu) que possa precisar de manter, refatorar ou estender o seu código.

Muitas vezes, um comentário de esclarecimento pode mostrar que o código "cheira mal". Ele pode significar que o seu código é muito complexo. Você deve se esforçar para remover comentários de esclarecimento e simplificar o código, porque "o código bom é aquele que se autodocumenta".

Aqui está um exemplo (em inglês) de um comentário de esclarecimento ruim – embora muito divertido.

/*  * Replaces with spaces  * the braces in cases  * where braces in places  * cause stasis.**/ $str = str_replace(array("\{","\}")," ",$str);

Em vez de decorar uma frase levemente confusa com uma rima inteligente — e em anfíbraco, surpreendentemente — o autor se daria muito melhor se tivesse se dedicado a uma função que tornasse o próprio código mais fácil de ler e de entender. Quem sabe se uma função chamada removerChaves chamasse outra função chamada limparOInput?

Não me entenda mal. Há momentos – especialmente quando você está passando por uma carga de trabalho esmagadora – em que colocar um pouco de humor pode ser bom para a alma. Porém, quando você escreve um comentário engraçado para compensar o código ruim, isso realmente torna as pessoas menos propensas a refatorar e corrigir o código mais tarde.

Você realmente quer ser o responsável por roubar de todos os futuros programadores a alegria de ler aquela pequena rima inteligente? A maioria dos programadores riria e seguiria em frente, ignorando o código que "cheira mal".

Há também momentos em que você se depara com um comentário que é redundante. Se o código já é simples e óbvio, não há necessidade de adicionar um comentário.

Por exemplo, evite usar algo como isto:

/*Define o valor do inteiro idade como 32*/int idade = 32;

Ainda assim, há vezes em que, não importando o que você fez com o próprio código, um comentário de esclarecimento ainda é uma boa pedida.

Isso geralmente acontece quando é preciso adicionar um pouco de contexto a uma solução contraintuitiva.

Aqui, temos um bom exemplo do próprio Lodash:

function addSetEntry(set, value) {
/*  Não retorne `set.add`, pois ele não é
	encadeável no IE 11.  */
	set.add(value);
    return set;
}

Também há momentos em que, depois de muita reflexão e experimentação, verifica-se que a solução aparentemente ingênua para um problema é realmente a melhor. Nesses cenários, é quase inevitável que algum outro programador venha achando que é muito mais inteligente do que você e comece a mexer com o código, apenas para descobrir que o seu caminho foi o melhor o tempo todo.

Às vezes, esse outro programador é o seu eu futuro.

Nesses casos, o melhor é poupar tempo e constrangimento de todos e deixar um comentário.

O comentário provocativo abaixo captura esse cenário com perfeição:

/**Caro mantenedor: ao terminar de tentar 'otimizar' este programa e depois de perceber o erro terrível que cometeu, lembre-se de incrementar o seguinte contador como um aviso para a próxima vítima: total_de_horas_perdidas_aqui = 42**/

O comentário acima tem mais a ver com ser engraçado do que ser útil. Você, no entanto, DEVE deixar um comentário alertando os outros para não buscarem alguma "solução melhor" aparentemente óbvia, se você já tentou diversas e viu que não davam certo. Quando você fizer isso, o comentário deve especificar qual solução você tentou e por que você decidiu não usá-la.

Aqui está um exemplo simples em JavaScript:

/* Não use o isFinite() global porque ele retorna true para valores nulos*/
Number.isFinite(value)

O feio

Bem, já vimos o bom e o mau. Vamos, agora, ver o feio.

Infelizmente, há momentos em qualquer trabalho em que você se verá frustrado e quando você escreve código como profissão, pode ser tentador desabafar essa frustração em comentários no código.

Trabalhando com bases de código suficientes, você encontrará comentários que variam de cínicos e deprimentes a sombrios e maldosos.

Há alguns que podem parecer inofensivos… (original em inglês)

/*Este código é uma droga, você e eu sabemos disso. Apenas siga em frente e me xingue mais tarde.*/

…e outros que são simplesmente maléficos (original em inglês)

/* Classe usada para contornar o fato de que o Richard é um idiota sem tamanho*/

Essas coisas podem parecer engraçadas ou podem ajudar a liberar um pouco de frustração no momento, mas quando elas entram no código de produção, acabam fazendo com que o programador que as escreveu e seu empregador pareçam pouco profissionais e amargos.

Não faça isso.

Se gostou deste artigo, compartilhe-o com seus colegas de trabalho. Se quiser ler mais (em inglês) sobre o assunto do artigo, assine a newsletter semanal do autor no site Dev Mastery.

Escrito por: Onur Tuna

Ao contrário de muitas outras linguagens de programação orientada a objetos, o C++ permite várias heranças.

A herança múltipla permite que uma classe filho herde de mais de uma classe pai.

No início, parece um recurso muito útil. Um usuário, porém, precisa estar atento a algumas dificuldades ao implementar esse recurso.

Nos exemplos abaixo, abordaremos alguns cenários sobre os quais é preciso estar atento.

Começaremos com um exemplo simples para explicar esse conceito em C++.

#include <iostream>

class SerVivo {
protected:
    void respirar() {
        std::cout << "Respiro como um ser vivo." << std::endl;
    }
};

class Animal : protected SerVivo {
protected:
    void respirar() {
        std::cout << "Respiro como um animal." << std::endl;
    }
};

class Reptil : protected SerVivo {
protected:
    void rastejar() {
        std::cout << "Rastejo como um réptil." << std::endl;
    }
};

class Cobra : protected Animal, protected Reptil {
public:
    void respirar() {
        std::cout << "Respiro como uma cobra." << std::endl;
    }

    void rastejar() {
        std::cout << "Rastejo como uma cobra." << std::endl;
    }
};

int main() {
    Cobra cobra;

    cobra.respirar();
    cobra.rastejar();

    return 0;
}

A saída desse código é a seguinte:

Respiro como uma cobra.
Rastejo como uma cobra.

No exemplo acima, temos uma classe base chamada SerVivo. As classes Animal e Reptil herdam dela. Somente a classe Animal sobrescreve o método respirar(). A classe Cobra herda das classes Animal e Reptil. Ela sobrescreve seus métodos. Acima, não vemos problemas. O código funciona bem.

Agora, vamos deixar as coisas um pouco mais complexas.

O que ocorreria se a classe Reptil sobrescrevesse o método respirar()?

A classe Cobra não saberia qual método respirar() deve ser chamado. Esse é o "Problema do diamante".

Problema do diamante

Veja o código abaixo. É como o código no exemplo acima, com a diferença que sobrescrevemos o método respirar() na classe Reptil.

#include <iostream>

class SerVivo {
protected:
    void respirar() {
        std::cout << "Respiro como um ser vivo." << std::endl;
    }
};

class Animal : protected SerVivo {
protected:
    void respirar() {
        std::cout << "Respiro como um animal." << std::endl;
    }
};

class Reptil : protected SerVivo {
public:
    void respirar() {
        std::cout << "Respiro como um réptil." << std::endl;
    }

    void rastejar() {
        std::cout << "Rastejo como um réptil." << std::endl;
    }
};

class Cobra : public Animal, public Reptil {

};

int main() {
    Cobra cobra;

    cobra.respirar();
    cobra.rastejar();

    return 0;
}

Se tentar compilar esse programa, ele não funcionará. Você verá uma mensagem de erro como a seguinte.

member ‘respirar’ found in multiple base classes of different types

O erro tem a ver com o "Problema do diamante" da herança múltipla. A classe Cobra não sabe qual método respirar() deve ser chamado.

No primeiro exemplo, apenas a classe Animal sobrescrevia o método respirar(). A classe Reptil class não fazia isso. Assim, não era problema para a classe Cobra saber qual método respirar() deveria ser chamado. A classe Cobra acabaria chamando o método respirar() da classe Animal.

No segundo exemplo, a classe Cobra herda dois métodos respirar(): o método respirar() das classes Animal e Reptil. Como não sobrescrevemos o método respirar() na classe Cobra, acabamos com uma ambiguidade.

O C++ tem muitos recursos poderosos, como a herança múltipla. Porém, não é necessário usarmos todos os recursos que ele oferece.

Prefiro não usar herança múltipla e usar a herança virtual em vez dela.

A herança virtual resolve o clássico "Problema do diamante”. Ela garante que a classe filho receba apenas uma única instância da classe base comum.

Em outras palavras, a classe Cobra teria apenas uma instância da classe SerVivo. As classes Animal e Reptil compartilhariam essa instância.

Isso resolve o erro de tempo de compilação que recebemos anteriormente. As classes derivadas das classes abstratas devem sobrescrever as funções virtuais puras definidas na classe base.

Esperamos que tenha gostado dessa visão geral de heranças múltiplas e do "Problema do diamante".

Você já quis criar algo, mas não tinha ideia do que fazer? Assim como os autores, às vezes, têm "bloqueio de escritor", isso também é verdade para os desenvolvedores.

Juntamente com meu amigo Jim, criamos uma coleção de ideias de aplicações que se destina a resolver esse problema de uma vez por todas!

Essas aplicações são:

• ótimas para aprimorar suas habilidades de programação
• ótimas para dar experiência com novas tecnologias
• ótimas para serem adicionadas ao seu portfólio para impressionar seu próximo empregador/cliente
• ótimas para serem usadas como exemplo em tutoriais (artigos ou vídeos)
• fáceis de completar e também facilmente ampliáveis com novos recursos

Esta não é apenas uma simples lista de projetos, mas uma coleção que descreve cada projeto com detalhes suficientes para que você possa desenvolvê-los do zero!

Cada especificação de projeto contém o seguinte:

1. Um objetivo claro e descritivo
2. Uma lista de histórias de usuários que devem ser implementadas. Essas histórias atuam mais como uma diretriz do que como uma lista forçada de tarefas pendentes – sinta-se à vontade para adicionar seus próprios recursos, se desejar
3. Uma lista de recursos adicionais que aprimoram não apenas o projeto básico, mas também suas habilidades ao mesmo tempo
4. Todos os recursos e links para ajudá-lo a encontrar o que você precisa para concluir o projeto

Projetos

Todos os projetos são divididos em três níveis com base no conhecimento e na experiência necessários para concluí-los. Esses níveis são:

1. Iniciante – Desenvolvedores nos estágios iniciais de sua jornada de aprendizado. Aqueles que normalmente se concentram na criação de aplicações voltadas para o usuário.
2. Intermediário – Desenvolvedores em um estágio intermediário de aprendizado e experiência. Eles se sentem confortáveis em UI/UX, usando ferramentas de desenvolvimento e criando aplicações que usam serviços de API.
3. Avançado – Desenvolvedores que têm todos os conhecimentos acima e estão aprendendo técnicas mais avançadas, como a implementação de aplicações de back-end e serviços de banco de dados.

Abaixo, você encontrará 5 projetos para cada uma das camadas (15 no total), mas há mais de 30 projetos (no momento) neste repositório do GitHub. Não deixe de conferir, pois estamos planejando adicionar mais projetos no futuro. Sua ajuda é bem-vinda! Mais informações sobre isso na seção Contribuição abaixo.

1. Aplicação de notas

Nível: 1 - Iniciante

Descrição: Crie e armazene suas anotações para uso posterior!

Histórias de usuário

• O usuário pode criar uma nota
• O usuário pode editar uma nota
• O usuário pode excluir uma nota
• Ao fechar a janela do navegador, as anotações serão armazenadas e, quando o usuário retornar, os dados serão recuperados

Recursos adicionais

• O usuário pode criar e editar uma nota no formato markdown. Ao salvar, ele converterá markdown em HTML
• O usuário pode ver a data em que criou a nota

Links e recursos úteis

• localStorage
• Guia de Markdown (em inglês)
• Marked – um parser de markdown (instruções do projeto em inglês)

Exemplo de projeto

2. Luzes de Natal

Nível: 1 - Iniciante

Descrição: a aplicação de Luzes de Natal depende de seus talentos de desenvolvimento para criar uma exibição de luzes hipnotizantes. Sua tarefa é desenhar sete círculos coloridos em uma fileira e, com base em um cronômetro, alterar a intensidade de cada círculo. Quando um círculo é iluminado, seu antecessor retorna à intensidade normal.

Isso simula o efeito de uma série de luzes piscantes, semelhante às exibidas durante as festas de Natal.

Histórias de usuário

• O usuário pode pressionar um botão para iniciar e parar a exibição
• O usuário pode alterar o intervalo de tempo que controla a mudança na intensidade

Recursos adicionais

• O usuário pode selecionar a cor usada para preencher cada círculo
• O usuário pode especificar o valor da intensidade
• O usuário pode alterar o tamanho de qualquer círculo na linha
• O usuário pode especificar o número de linhas a serem incluídas na exibição, podendo escolher de uma a sete linhas

Links e recursos úteis

• Imagem de amostra
• Adafruit LED Matrix

Exemplo de projeto

3. FlipImage

Nível: 1 - Iniciante

Descrição: É importante que os desenvolvedores da Web compreendam os fundamentos da manipulação de imagens, pois as aplicações avançadas da Web dependem de imagens para agregar valor à interface e à experiência do usuário (UI/UX).

O FlipImage explora um aspecto da manipulação de imagens: a rotação de imagens. Essa aplicação exibe um painel quadrado contendo uma única imagem apresentada em uma matriz 2x2. Usando um conjunto de setas para cima, para baixo, para a esquerda e para a direita adjacentes a cada uma das imagens, o usuário pode virá-las na vertical ou na horizontal.

Você deve usar somente HTML, CSS e Javascript nativos para implementar essa aplicação. Pacotes de imagens e bibliotecas não são permitidos.

Histórias de usuário

• O usuário pode ver um painel contendo uma única imagem repetida em uma matriz 2x2
• O usuário pode virar qualquer uma das imagens na vertical ou na horizontal usando um conjunto de setas para cima, para baixo, para a esquerda e para a direita ao lado da imagem

Recursos adicionais

• O usuário pode alterar a imagem padrão inserindo o URL de uma imagem diferente em um campo de entrada
• O usuário pode exibir a nova imagem clicando no botão "Display" (Exibir) ao lado do campo de entrada
• O usuário poderá ver uma mensagem de erro se o URL das novas imagens não for encontrado

Links e recursos úteis

• Como virar uma imagem (em inglês)
• Criando uma animação de inversão de CSS (em inglês)

Exemplo de projeto

4. Aplicação de questionário

Nível: 1 - Iniciante

Descrição: Pratique e teste seus conhecimentos respondendo a perguntas em uma aplicação de questionário.

Como desenvolvedor, você pode criar uma aplicação de questionário para testar as habilidades em programação de outros desenvolvedores (em HTML, CSS, JavaScript, Python, PHP etc.)

Histórias de usuário

• O usuário pode iniciar o questionário pressionando um botão
• O usuário pode ver uma pergunta com 4 respostas possíveis
• Depois de selecionar uma resposta, exiba a próxima pergunta para o usuário. Faça isso até que o questionário seja concluído
• No final, o usuário pode ver as seguintes estatísticas:

1. Tempo necessário para concluir o questionário
2. Quantas respostas corretas ele obteve?
3. Uma mensagem mostrando se ele foi aprovado ou reprovado no teste

Recursos adicionais

• O usuário pode compartilhar o resultado de um questionário nas mídias sociais
• Adicione vários testes à aplicação. O usuário pode selecionar quais deles deseja responder
• O usuário pode criar uma conta e ter todas as pontuações salvas em seu painel
• O usuário pode concluir um questionário várias vezes

Links e recursos úteis

• Abrir banco de dados de curiosidades (em inglês)

Exemplos de projetos

Aplicação de questionário criada com React (aguarde o carregamento, pois ela está hospedada no Heroku)

5. Conversor de números romanos para decimais

Nível: 1 - Iniciante

Descrição: O sistema numérico representado pelos algarismos romanos teve origem na Roma antiga e continuou sendo a forma usual de escrever números em toda a Europa até o final da Idade Média. Os números romanos, como usados atualmente, empregam sete símbolos, cada um com um valor inteiro fixo.

Veja na tabela abaixo o Símbolo - pares de Valores:

• I — 1
• V — 5
• X — 10
• L — 50
• C — 100
• D — 500
• M — 1000

Histórias de usuário

• O usuário deve ser capaz de inserir um número romano em um campo de entrada
• O usuário poderá ver os resultados em um único campo de saída contendo o equivalente decimal (base 10) do número romano que foi inserido ao pressionar um botão
• Se um símbolo errado for inserido, o usuário deverá ver um erro

Recursos adicionais

• O usuário pode ver a conversão ser feita automaticamente ao digitar
• O usuário deve ser capaz de converter de decimal para romano (e vice-versa)

Links e recursos úteis

• Uma explicação sobre os números romanos

Exemplo de projeto

Conversor de números romanos (instruções em inglês)

6. Aplicação localizadora de livros

Nível: 2 - Intermediário

Descrição: Criar uma aplicação que permita aos usuários pesquisar livros inserindo uma consulta (título, autor etc.). Exibir os livros resultantes em uma lista na página com todos os dados correspondentes.

Histórias de usuário

• O usuário pode inserir uma consulta de pesquisa em um campo de entrada
• O usuário pode enviar a consulta. Isso chamará uma API que retornará um array de livros com os dados correspondentes (título, autor, data de publicação, imagem etc.)
• O usuário pode ver a lista de livros que aparecem na página

Recursos adicionais

• Para cada item da lista, adicionar um link que enviará o usuário a um site externo que tenha mais informações sobre o livro
• Implementar um design responsivo
• Adicionar animações de carregamento

Links e recursos úteis

Você pode usar a API do Google Livros

Exemplo de projeto

Busca de Livros - React

7. Jogo de memória de cartas

Nível: 2 - Intermediário

Descrição: O jogo de memória de cartas é um jogo em que você precisa clicar em uma carta para ver a imagem que está embaixo dela e tentar encontrar a imagem correspondente embaixo das outras cartas.

Histórias de usuário

• O usuário pode ver uma grade com n x n cartas (n é um número inteiro), sendo que todas as cartas estão inicialmente viradas para baixo (estado oculto)
• O usuário pode clicar em um botão para iniciar o jogo e, quando esse botão for clicado, um cronômetro será iniciado
• O usuário pode clicar em qualquer carta para revelar a imagem que está embaixo dela (alterá-la para o estado visível). A imagem será exibida até que o usuário clique em uma segunda carta

Quando o usuário clica na segunda carta:

• Se houver uma correspondência, as duas cartas serão eliminadas do jogo (seja escondendo-as/removendo-as ou deixando-as visíveis)
• Se não houver uma correspondência, as duas cartas voltarão ao seu estado original (estado oculto)
• Quando todas as correspondências tiverem sido encontradas, o usuário poderá ver uma caixa de diálogo com uma mensagem de parabéns e um contador mostrando o tempo que levou para terminar o jogo

Recursos adicionais

• O usuário pode escolher entre vários níveis de dificuldade (Fácil, Médio, Difícil). Aumentar a dificuldade significa: diminuir o tempo disponível para concluir e/ou aumentar o número de cartas
• O usuário pode ver as estatísticas do jogo (número de vezes que ganhou/perdeu, o melhor tempo para cada nível)

Links e recursos úteis

• Wikipédia (em inglês)

Exemplos de projetos

Flip - jogo de memória de cartas (em inglês)

SMB3 Jogo de memória de cartas (em inglês)

8. Gerador de tabelas em markdown

Nível: 2 - Intermediário

Descrição: Crie uma aplicação que converterá uma tabela normal com dados fornecidos pelo usuário (opcionalmente) em uma tabela formatada em markdown.

Histórias de usuário

• O usuário pode criar uma tabela HTML com um determinado número de linhas e colunas
• O usuário pode inserir texto em cada célula da tabela HTML
• O usuário pode gerar uma tabela formatada em markdown que conterá os dados da tabela HTML
• O usuário pode visualizar a tabela formatada em markdown

Recursos adicionais

• O usuário pode copiar a tabela formatada do markdown para a área de transferência pressionando um botão
• O usuário pode inserir uma nova linha ou coluna em um local especificado
• O usuário pode excluir uma linha ou coluna completamente
• O usuário pode alinhar (à esquerda, à direita ou ao centro) uma célula, uma coluna, uma linha ou a tabela inteira

Links e recursos úteis

• Guia de markdown (em inglês)
• Marked - Um analisador de markdown (em inglês)
• Como copiar para a área de transferência (em inglês)

Exemplo de projeto

Gerador de tabelas/Tabelas Markdown (em inglês)

9. Arte com strings

Nível: 2 - Intermediário

Descrição: O objetivo de Arte com strings é proporcionar ao desenvolvedor a prática de criar um gráfico animado simples, usando geometria no algoritmo de animação e criando algo que seja visualmente agradável de assistir.

A Arte com strings desenha uma única linha multicolorida que se move suavemente até que uma extremidade toque em um lado da janela que a envolve. No ponto em que ela toca, um efeito de "salto" é aplicado para mudar sua direção.

Um efeito de ondulação é criado mantendo apenas 10 a 20 imagens da linha à medida que ela se move. As imagens mais antigas são progressivamente desbotadas até desaparecerem.

As bibliotecas de animação não são permitidas. Use apenas HTML/CSS/JavaScript puro.

Histórias de usuário

• Comece desenhando uma linha multicolorida em uma posição aleatória dentro do limite da janela que a envolve
• A cada 20 ms, desenhe uma cópia da linha em uma nova posição com base em uma trajetória – a distância incremental da linha anterior com base nos pontos finais
• Quando um dos pontos de extremidade da linha tocar o limite da janela circundante, mude sua direção e altere aleatoriamente seu ângulo
• Diminua progressivamente a intensidade das linhas antigas de modo que apenas as 10 a 20 linhas mais recentes fiquem visíveis para criar a sensação de movimento ou "ondulação"

Recursos adicionais

• O usuário pode especificar o comprimento da linha e sua velocidade
• O usuário pode especificar as várias linhas dentro da janela, todas se movendo ao longo de diferentes trajetórias e velocidades

Links e recursos úteis

• Uso de animações e transições de várias etapas (em inglês)
• Noções básicas de animação (em inglês)

Exemplo de projeto

Este projeto é muito próximo do que pretendemos aqui, mas tem uma pequena janela de fechamento e é monocromático. Daniel Cortes

10. Aplicação de tarefas por fazer

Nível: 2 - Intermediário

Descrição: A aplicação de tarefas clássica em que o usuário pode anotar todas as coisas que deseja realizar.

Histórias de usuário

• O usuário pode ver um campo de entrada no qual ele pode digitar um item de tarefa
• Ao pressionar Enter (ou um botão), o usuário pode enviar o item de tarefa e pode ver que ele está sendo adicionado a uma lista de tarefas
• O usuário pode marcar uma tarefa como concluída
• O usuário pode remover um item de tarefa pressionando um botão (ou o próprio item de tarefa)

Recursos adicionais

• O usuário pode editar uma tarefa
• O usuário pode ver uma lista com todas as tarefas concluídas
• O usuário pode ver uma lista com todas as tarefas ativas
• O usuário pode ver a data em que criou a tarefa
• Ao fechar a janela do navegador, as tarefas serão armazenadas e, quando o usuário retornar, os dados serão recuperados

Links e recursos úteis

• localStorage (armazenamento local)

Exemplos de projetos

Aplicação de tarefas desenvolvida com React

11. Mecanismo do jogo de batalha naval

Nível: 3 - Avançado

Descrição: O mecanismo do jogo de batalha naval (em inglês, Battleship Game Engine, ou BGE) implementa o clássico jogo de tabuleiro baseado em turnos como um pacote separado de qualquer camada de apresentação. Esse é um tipo de padrão arquitetônico que é útil em muitas aplicações, pois permite que qualquer número de aplicações utilize o mesmo serviço.

O próprio BGE é invocado por meio de uma série de chamadas de função em vez de ações diretamente acopladas do usuário final. Nesse aspecto, o uso do BGE é semelhante ao uso de uma API ou de uma série de rotas expostas por um servidor da web.

Esse desafio exige que você desenvolva o BGE e uma camada de apresentação baseada em texto muito fina para testes, separada do próprio mecanismo. Devido a isso, as histórias de usuário abaixo estão divididas em dois conjuntos: um para o BGE e outro para a camada de apresentação baseada em texto.

O BGE é responsável por manter o estado do jogo.

Histórias de usuário

BGE

• O chamador pode invocar uma função startGame() para iniciar um jogo para um jogador. Essa função gerará um tabuleiro de jogo 8x8 que consiste em 3 navios com uma largura de um quadrado e um comprimento de:

1. Destroyer: 2 quadrados
2. Cruzador: 3 quadrados
3. Navio de guerra: 4 quadrados

startGame() colocará aleatoriamente esses navios no tabuleiro em qualquer direção e retornará um array que representa o posicionamento dos navios.

• O chamador pode invocar uma função shoot() passando as coordenadas de linha e coluna da célula-alvo no tabuleiro de jogo. shoot() retornará indicadores que representam se o tiro resultou em acerto ou erro, o número de navios restantes (ou seja, ainda não afundados), o array de posicionamento de navios e o array atualizado de acertos e erros.

As células no array de acertos e erros conterão um espaço se ainda não tiverem sido alvos, O se tiverem sido alvos, mas nenhuma parte de um navio estava naquele local, ou X se a célula tiver sido ocupada por parte de um navio.

Camada de apresentação baseada em texto

• O usuário pode ver o array de acertos e erros exibido como uma representação bidimensional de caracteres do tabuleiro de jogo retornado pela função startGame().
• O usuário pode ser solicitado a inserir as coordenadas de um quadrado alvo no tabuleiro de jogo.
• O usuário pode ver uma exibição atualizada do array de acertos e erros depois de dar um tiro.
• O usuário pode ver uma mensagem após cada disparo, indicando se o disparo resultou em acerto ou erro.
• O usuário pode ver uma mensagem de parabéns após o tiro que afunda o último navio restante.
• O usuário pode ser solicitado a jogar novamente no final de cada jogo. A recusa em jogar novamente interrompe o jogo.

Recursos adicionais

BGE

• O chamador pode especificar o número de linhas e colunas no tabuleiro do jogo como um parâmetro para a função startGame().
• O chamador pode invocar uma função gameStats() que retorna um objeto Javascript contendo métricas para o jogo atual. Por exemplo, o número de turnos jogados, o número atual de acertos e erros etc.
• O chamador pode especificar o número de jogadores (1 ou 2) ao chamar startGame(), que gerará um tabuleiro para cada jogador preenchido aleatoriamente com navios.

shoot() aceitará o número do jogador para o qual a jogada está sendo realizada, juntamente com as coordenadas da jogada. Os dados retornados serão para esse jogador.

Camada de apresentação baseada em texto

• O usuário pode ver as estatísticas atuais do jogo em qualquer ponto inserindo as estatísticas da frase no lugar das coordenadas do alvo. Observe que isso requer a função gameStats() no BGE.
• O usuário pode especificar que um jogo para dois jogadores deve ser jogado, com cada jogador alternando turnos na mesma sessão de terminal (observe que isso requer os recursos de bônus correspondentes no BGE).
• O usuário pode ver o número do jogador nos alertas associados às entradas em cada turno.
• O usuário pode ver o tabuleiro de ambos os jogadores no final de cada turno.

Links e recursos úteis

• Jogo de Batalha Naval (Wikipédia)
• Regras do jogo de Batalha Naval (Hasbro) (em inglês)

Exemplo de projetos

Este vídeo do YouTube (em inglês) mostra como é jogado um jogo de batalha naval baseado em texto.

O exemplo a seguir é fornecido como uma demonstração do jogo de batalha naval, caso ele não seja familiar para você. Lembre-se de que você deve implementar uma camada de apresentação baseada em texto para teste. Jogo de Batalha Naval por Chris Brody (em inglês).

12. Aplicação de bate-papo

Nível: 3 - Avançado

Descrição: Interface de bate-papo em tempo real em que vários usuários podem interagir entre si enviando mensagens.

Como MVP (Minimum Viable Product – em português, produto viável mínimo), você pode se concentrar na criação da interface de bate-papo. A funcionalidade em tempo real pode ser adicionada posteriormente (nos recursos adicionais).

Histórias de usuário

• O usuário é solicitado a inserir um nome de usuário quando visita a aplicação de bate-papo. O nome de usuário será armazenado na aplicação
• O usuário pode ver um campo de entrada onde pode digitar uma nova mensagem
• Ao pressionar a tecla Enter ou clicar no botão Enviar, o texto será exibido na caixa de bate-papo ao lado do nome de usuário (por exemplo, Fulano: Olá, mundo!)

Recursos adicionais

• As mensagens ficarão visíveis para todos os usuários que estiverem na aplicação de bate-papo (usando WebSockets)
• Quando um novo usuário entra no bate-papo, uma mensagem é exibida para todos os usuários existentes
• As mensagens são salvas em um banco de dados
• O usuário pode enviar imagens, vídeos e links que serão exibidos corretamente
• O usuário pode selecionar e enviar um emoji
• Os usuários podem conversar em particular
• Os usuários podem participar de canais sobre tópicos específicos

Links e recursos úteis

• Socket.io (em inglês)
• Como criar uma aplicação de bate-papo no React.js em 10 minutos - artigo (em inglês)

Exemplo de projeto

13. Linha do tempo do GitHub

Nível: 3 - Avançado

Descrição: As APIs e a representação gráfica de informações são marcas registradas das aplicações modernas da web. O GitHub Timeline combina os dois para criar um histórico visual da atividade de um usuário no GitHub.

O objetivo do GitHub Timeline é aceitar um nome de usuário do GitHub e produzir uma linha do tempo contendo cada repositório, com as anotações dos nomes dos repositórios, a data em que foram criados e suas descrições. A linha do tempo deve ser compartilhada com um possível empregador. Ela deve ser fácil de ler e fazer uso eficaz de cores e tipografia.

Somente os repositórios públicos do GitHub devem ser exibidos.

Histórias de usuário

• O usuário pode inserir um nome de usuário do GitHub
• O usuário pode clicar em um botão "Generate" (Gerar) para criar e exibir a linha do tempo do repositório do usuário nomeado
• O usuário poderá ver uma mensagem de aviso se o nome de usuário do GitHub não for válido.

Recursos adicionais

• O usuário pode ver um resumo do número de repositórios registrados pelo ano em que foram criados

Links e recursos úteis

O GitHub oferece duas APIs que você pode usar para acessar os dados do repositório. Você também pode optar por usar um pacote do NPM para acessar a API do GitHub.

A documentação da API do GitHub pode ser encontrada em:

• GitHub REST API V3 (em inglês)
• GitHub GraphQL API V4 (em inglês)

O código de exemplo que mostra como usar a API do GitHub é:

Você pode usar esse comando CURL para ver o JSON retornado pela API REST V3 para seus repositórios:

curl -u "user-id" https://api.github.com/users/user-id/repos

Exemplos de projetos

14. Soletrar

Nível: 3 - Avançado

Descrição: Saber soletrar é parte fundamental para ser fluente em qualquer idioma. Seja você é uma criança aprendendo a soletrar ou um indivíduo aprendendo um novo idioma, a prática ajuda a solidificar suas habilidades linguísticas.

A aplicação de Soletrar ajuda os usuários a praticar a ortografia reproduzindo a gravação de áudio de uma palavra que o usuário deve soletrar usando o teclado do computador.

Histórias de usuário

• O usuário pode clicar no botão "Play" (Reproduzir) para ouvir a palavra que deve ser digitada
• O usuário pode ver as letras exibidas na caixa de texto de entrada de palavras à medida que são inseridas no teclado
• O usuário pode clicar no botão "Enter" para enviar a palavra que foi digitada na caixa de texto de entrada de palavras
• O usuário pode ver uma mensagem de confirmação quando a palavra correta é digitada
• O usuário pode ver uma mensagem solicitando que a palavra seja digitada novamente quando ela for escrita incorretamente
• O usuário pode ver um registro do número de grafias corretas, o número total de palavras tentadas e uma porcentagem de entradas bem-sucedidas.

Recursos adicionais

• O usuário pode ouvir um som de confirmação quando a palavra for soletrada corretamente
• O usuário pode ouvir um som de aviso quando a palavra for escrita incorretamente
• O usuário pode clicar no botão "Hint" (Dica) para destacar as letras incorretas na caixa de texto de entrada de palavras
• O usuário pode pressionar a tecla "Enter" no teclado para enviar uma palavra digitada ou clicar no botão "Enter" na janela da aplicação

Links e recursos úteis

• Texas Instruments Speak and Spell (em inglês)
• Web Audio API (em inglês)
• Clique e fale (em inglês)

Exemplos de projetos

Assistente de palavras para iOS (em inglês)

Falar e soletrar no Google Play (em inglês)

15. Aplicação de pesquisa

Nível: 3 - Avançado

Descrição: As pesquisas são uma parte valiosa da caixa de ferramentas de qualquer desenvolvedor. Elas são úteis para obter feedback dos usuários sobre uma variedade de tópicos, incluindo satisfação com a aplicação, requisitos, necessidades futuras, problemas, prioridades e incômodos simples, por exemplo.

A aplicação de pesquisa dá a você a oportunidade de aprender desenvolvendo uma aplicação com todos os recursos que podem ser adicionados à sua caixa de ferramentas. Ela oferece a capacidade de definir uma pesquisa, permitir que os usuários respondam dentro de um período de tempo predefinido e tabular e apresentar resultados.

Os usuários dessa aplicação são divididos em duas funções distintas, cada uma com requisitos diferentes:

• Os coordenadores de pesquisa definem e conduzem pesquisas. Essa é uma função administrativa não disponível para usuários normais.
• Respondentes de pesquisas preenchem pesquisas e visualizam resultados. Eles não têm privilégios administrativos na aplicação.
• As ferramentas de pesquisa comerciais incluem a funcionalidade de distribuição que envia questionários em massa para os Respondentes da pesquisa. Para simplificar, esta aplicação pressupõe que os questionários abertos para respostas serão acessados a partir da página da web da aplicação

Histórias de usuário

Geral

• Os coordenadores e respondentes de pesquisas podem definir, conduzir e visualizar pesquisas e resultados de pesquisas em um site comum
• Os coordenadores de pesquisa podem fazer login na aplicação para acessar funções administrativas, como definir uma pesquisa.

Definição de uma pesquisa

• O coordenador de pesquisa pode definir uma pesquisa que contenha de 1 a 10 perguntas de múltipla escolha.
• O coordenador de pesquisa pode definir de 1 a 5 seleções mutuamente exclusivas para cada pergunta.
• O coordenador de pesquisa pode inserir um título para a pesquisa.
• O coordenador de pesquisa pode clicar em um botão "Cancelar" para retornar à página inicial sem salvar o questionário.
• O coordenador do questionário pode clicar em um botão "Salvar" para salvar um questionário.

Realização de uma pesquisa

• O coordenador de pesquisa pode abrir uma pesquisa selecionando-a em uma lista de pesquisas previamente definidas
• Os coordenadores de pesquisa podem fechar uma pesquisa selecionando-a em uma lista de pesquisas abertas
• O respondente da pesquisa pode concluir um questionário selecionando-o em uma lista de questionários abertos
• O respondente da pesquisa pode selecionar respostas para as perguntas da pesquisa clicando em uma caixa de seleção
• Os respondentes do questionário podem ver que uma resposta selecionada anteriormente será automaticamente desmarcada se uma resposta diferente for clicada.
• Os respondentes do questionário podem clicar em um botão "Cancelar" para retornar à página inicial sem enviar a pesquisa.
• Os respondentes do questionário podem clicar no botão "Enviar" para enviar suas respostas ao questionário.
• Os respondentes do questionário podem ver uma mensagem de erro se "Enviar" for clicado, mas nem todas as perguntas tiverem sido respondidas.

Visualização dos resultados da pesquisa

• Os coordenadores e os respondentes de pesquisa podem selecionar a pesquisa a ser exibido em uma lista de questionários fechados
• Os coordenadores e os respondentes da pesquisa podem visualizar os resultados da pesquisa em formato tabular, mostrando o número de respostas para cada uma das seleções possíveis para as perguntas.

Recursos adicionais

• Os respondentes da pesquisa podem criar uma conta exclusiva na aplicação
• Os respondentes da pesquisa podem fazer login na aplicação
• Os entrevistados não podem responder à mesma pesquisa mais de uma vez
• Os coordenadores e os respondentes da pesquisa podem visualizar representações gráficas dos resultados da pesquisa (por exemplo, gráficos de pizza, de barras, de colunas etc.)

Links e recursos úteis

Bibliotecas para a criação de pesquisas: SurveyJS

Alguns serviços de pesquisa comercial incluem: Survey Monkey e TypeForm

Exemplo de projeto

Contribuição

Fique à vontade para contribuir com o projeto no repositório do GitHub! Qualquer contribuição é muito apreciada.

Você pode contribuir de duas maneiras:

1. criar uma issue e nos contar sua ideia. Não se esqueça de usar o rótulo New Idea (nova ideia) nesse caso;
2. fazer o fork do projeto e enviar um PR. Antes de fazer isso, certifique-se de ler e seguir o Guia de Contribuição (você pode encontrá-lo no repositório);

Adicione seus próprios exemplos

Você também pode adicionar seus próprios exemplos aos projetos depois de concluí-los. Eu o encorajo a fazer isso, pois mostrará aos outros as coisas incríveis que você construiu!

Espalhe a palavra!

Se as informações deste artigo e do repositório foram úteis para você de alguma forma, certifique-se de atribuir uma estrela no GitHub. Assim, outras pessoas poderão encontrar o projeto e se beneficiar também! Juntos, podemos crescer e tornar nossa comunidade melhor!

Você tem alguma sugestão sobre como podemos melhorar este projeto em geral? Entre em contato conosco! Gostaríamos muito de ouvir seus comentários!

Principais colaboradores

Florin Pop: Twitter e site.

Jim Medlock: Twitter e Medium

Desafio semanal de programação

Como bônus, há um desafio de programação semanal em que você pode aprender mais praticando suas habilidades em projetos do mundo real. Leia o Guia completo (em inglês) para saber como você pode participar!

Publicado originalmente em www.florin-pop.com (texto original em inglês).

A web está crescendo em uma velocidade enorme. As aplicações para a web estão cada vez mais dinâmicas, imersivas e não exigem que o usuário recarregue a página para que ocorram atualizações. O suporte para tecnologias de comunicação de baixa latência como websockets também está em constante evolução. Websockets nos permitem realizar comunicações em tempo real entre diferentes clients conectados a um mesmo servidor.

Muitas pessoas não sabem como proteger suas conexões websocket de alguns ataques comuns. Vamos ver quais são eles e o que você pode fazer para deixar seus websockets seguros.

Nº 0: Habilite o CORS

WebSocket não possui CORS nativo. Isso significa que qualquer site pode se conectar com qualquer outro através de uma conexão websocket sem qualquer restrição! Eu não vou entrar em detalhes acerca dos motivos para que isso seja assim, mas uma maneira rápida de corrigir isso é verificar o cabeçalho de requisição Origin no handshake do WebSocket.

Claro, o cabeçalho de requisição Origin pode ser falsificado por um invasor, mas não importa, porque, para explorar isso, o invasor precisa falsificar o cabeçalho Origin no navegador da vítima. Navegadores modernos não permitem que códigos convencionais em JavaScript no navegador alterem o cabeçalho Origin.

Ademais, se você estiver autenticando usuários usando, preferencialmente, cookies, isso não será um problema (mais sobre esse assunto no tópico nº 4).

Nº 1: Implementando taxa de limitação

A taxa de limitação é importante. Sem ela, clients podem – cientes ou não – realizar um ataque do tipo DoS (Denial of Service) no seu servidor. Em outras palavras, DoS significa que um único client está fazendo com que o servidor fique ocupado a ponto de não conseguir lidar com com outros clients.

Na maioria dos casos, é uma tentativa deliberada vinda de um invasor visando derrubar o servidor. Às vezes, uma implementação ruim no front-end também pode gerar um ataque DoS por clients normais.

Faremos uso do algoritmo do balde furado (em inglês, leaky bucket – o qual, aparentemente, é um algoritmo muito usado para implementação de redes) para implementar a taxa de limitação em nossos websockets.

A ideia é que você tenha um balde com um furo de tamanho fixo no fundo. Você começa colocando água nele e a água sai pelo buraco no fundo. Agora, se o balde receber mais água do que está sendo escoado por um longo período de tempo, em algum momento o balde ficará cheio e começará a vazar. É isso.

Agora, vamos entender como isso tem relação com nosso websocket:

A água é o tráfego do websocket enviado pelo usuário.

A água passa pelo buraco no fundo do balde. Isso significa que o servidor processou aquela requisição em particular com sucesso.

A água que está no balde e ainda não vazou é basicamente o tráfego pendente. O servidor processará esse tráfego depois. Isso pode ser também um tráfego em massa, ou seja, muito tráfego de uma vez só, contanto que o balde não vaze).

A água que está vazando é o tráfego descartado pelo servidor (muito tráfego proveniente de um único usuário).

O ponto aqui é que você tem que verificar a atividade do seu websocket e determinar esses números. Você estabelecerá um balde para cada usuário. Decidiremos o tamanho que o balde deve ter (tráfego o qual um único usuário poderá enviar durante o período específico) dependendo do tamanho do buraco ao fundo do balde (quanto tempo em média o seu servidor leva para processar uma única requisição websocket, digamos que salvando uma mensagem enviada pelo usuário em um banco de dados, por exemplo).

Essa é uma implementação simples que eu estou usando no codedamn para implementar o algoritmo de balde furado para websockets. É em NodeJS, mas os conceitos são sempre os mesmos.

if(this.limitCounter >= Socket.limit) {
  if(this.burstCounter >= Socket.burst) {
     return 'O balde está vazando'
  }
  ++this.burstCounter
  return setTimeout(() => {
  this.verify(callingMethod, ...args)
  setTimeout(_ => --this.burstCounter, Socket.burstTime)
  }, Socket.burstDelay)
}
++this.limitCounter

Então, o que está acontecendo aqui? Basicamente, se o limite for alcançado tanto pelo limite de tráfego (que são constantes definidas), a conexão websocket cai. Caso contrário, após um certo tempo, resetaremos o contador de tráfego. Isso deixa espaço livre para outro tráfego em massa.

Nº 2: Restrinja o tamanho da carga

Isso deve ser utilizado como um recurso do seu framework de back-end. Se o seu não tem, é hora de mudar para um melhor! Você deve limitar o tamanho máximo da mensagem que será enviada pelo seu websocket. Teoricamente, não há limite. Claro, é bem provável que receber uma carga muito grande congestionará essa instância de websocket específica e consumirá mais recursos do sistema do que deveria.

Por exemplo, se você está usando a biblioteca WS para Node para criar websockets no servidor, você pode usar a opção maxPayload para especificar o tamanho máximo da carga em bytes. Se o tamanho da carga for maior que o definido, a biblioteca, nativamente, derrubará a conexão.

Não tente implementar isso por conta própria determinando o tamanho da mensagem. Não queremos ler a mensagem inteira na memória RAM do sistema. Se a mensagem for 1 byte acima do limite, descarte-a. Isso pode ser implementado pelo framework (que lidará com as mensagens como fluxo de bytes em vez de strings fixas).

Nº 3: Crie um protocolo de comunicação sólido

Como agora você está em uma conexão duplex, você pode enviar qualquer coisa para o servidor. O servidor também pode enviar qualquer texto de volta para o client. Você pode precisar de um caminho para assegurar a comunicação efetiva entre os dois.

Você não pode enviar mensagens brutas se quiser escalar o aspecto das mensagens do seu site. Eu prefiro usar JSON, mas existem outros meios optimizados de configurar a comunicação. No entanto, considerando o JSON, é assim que um esquema básico de mensagens deve parecer em um site genérico:

Do client para o servidor (ou vice-versa):

{ status: "ok"|"error", event: EVENT_NAME, data: <dados de qualquer tipo> }

Agora, fica mais fácil para você validar eventos e formatos no back-end. Derrube a conexão imediatamente e registre o endereço de IP do usuário, caso o formato da mensagem for diferente. De modo algum o formato pode mudar, a menos que alguém esteja manualmente mexendo na sua conexão websocket. Se você está utilizando o Node, eu recomendo usar a biblioteca Joi para as próximas validações de dados provenientes do usuário.

Nº 4: Autentique os usuários antes de estabilizar a conexão WS

Se você está utilizando websockets para usuários autenticados, é uma ótima ideia permitir que apenas usuários autenticados estabeleçam com sucesso uma conexão websocket. Não permita que ninguém estabeleça uma conexão e espere que eles se autentiquem no próprio websocket. Primeiramente, estabelecer uma conexão websocket é sempre um pouco caro. Logo, você não quer que pessoas sem autorização acessem seu websocket e monopolizem as conexões que poderiam ser utilizadas por outras pessoas.

Para isso, quando estiver estabelecendo uma conexão no front-end, envie algum dado de autenticação para o websocket. Pode ser um header como X-Auth-Token: <token atribuído a este client no login>. Por padrão, cookies serão passados de qualquer jeito.

De novo, realmente depende da biblioteca que você está utilizando para implementar websockets. Se, contudo, você estiver usando Node e a WS, existe uma função chamada verifyClient que te dá acesso às informações do objeto passado pela conexão websocket (assim como você tem acesso ao objeto req para solicitações HTTP).

Nº 5: Use SSL com websockets

Isso não é trivial, mas é necessário ser dito. Use wws:// em vez de ws://. Isso adiciona uma camada de segurança à sua conexão. Use um servidor como o Nginx para realizar proxy reverso nos websockets e habilitar SSL acima deles. Como configurar o Nginx será um tutorial à parte, eu vou deixar algumas diretivas que você precisa utilizar no Nginx para as pessoas que são familiarizadas com ele. Mais informações aqui.

location /local-do-seu-websocket/ {
    proxy_pass ​http://127.0.0.1:1337;
    proxy_http_version 1.1;
    proxy_set_header Upgrade $http_upgrade;
    proxy_set_header Connection "Upgrade";
}

Aqui, assumimos que o seu servidor websocket está ouvindo na porta 1337 e que seus usuários estão conectados ao seu websocket assim:

const ws = new WebSocket('wss://seusite.com/local-do-seu-websocket')

Obrigado pela leitura!

Versão resumida: é o melhor amigo do desenvolvedor!

Escrito por: Wassim Chegham

Nos últimos três anos, eu tenho dedicado meu tempo profissional e uma grande parte do meu tempo pessoal para ajudar outros desenvolvedores a serem bem-sucedidos e produtivos com as ferramentas que eles amam e usam. Essas ferramentas incluem plataformas da web, tais como JavaScript, PWA e Angular, Google Cloud Platform, Actions no Google e chatbots em geral. É isso que eu faço como um Developer Advocate.

Este artigo é baseado na minha experiência pessoal como Developer Advocate. Fala de coisas que aprendi pessoalmente, mas também do que aprendi com outros Developer Advocates e nas empresas com as quais eu trabalhei.

Minha história…

Há treze anos, quando eu estava estudando eletrônica e depois ciência da computação na universidade, nos ensinaram toda a teoria de paradigmas da computação e programação, estruturas de dados, padrões de projetos, compiladores, linguagens e assim por diante. Basicamente, nos ensinaram tudo o que engenheiros de software júnior precisam saber para começar suas carreiras.

Entretanto, eu estava provavelmente muito interessado no curso, porque eu sempre fazia mais do que era pedido nos trabalhos de classe. O que quero dizer é que aprender Java na universidade era interessante, mas eu estava ficando entediado. Eu passava a maior parte do meu tempo livre aprendendo novos paradigmas de programação de linguagens como Python, PHP, Assembly 8086, oCaml e JavaScript. Foi quando eu descobri e me apaixonei por JavaScript e decidi, desde então, sempre apostar em JavaScript. Nunca me arrependi de ter feito isso.

Eu tive que aprender novas linguagens construindo ferramentas, scripts, aplicações, qualquer coisa que me ajudasse a entender o funcionamento interno da linguagem – indo muito além da sintaxe. Claro, eu ainda era um estudante nessa época e estava tentando entender como as coisas funcionavam e como solucionar todos os bugs que eu estava criando.

Então, apareceu a comunidade de desenvolvedores. Graças a web, eu pude pedir e receber ajuda de outros seres humanos – uma comunidade de desenvolvedores professionais e experientes. Eu estava admirado! Eu estava aprendendo muito com os outros desenvolvedores, lendo seus insights nas postagens em blogs, assistindo aos tutoriais no YouTube e discutindo diferentes tópicos em diferentes fóruns de tecnologia e IRC (sim, ele ainda existe!)

Aprendi muito com o que outros desenvolvedores compartilhavam gratuitamente, apenas para ajudar os outros. Por isso, decidi unir-me a comunidade e fazer o meu melhor para compartilhar o que eu estava aprendendo. Para mim, essa era a coisa certa a se fazer: outras pessoas ajudaram a me tornar um bom desenvolvedor. Agora, era minha vez de retribuir e ajudar outros desenvolvedores. Foi então que eu comecei a me preocupar com a produtividade dos outros desenvolvedores e com a minha também, claro. Estamos todos no mesmo barco, certo?

À medida que eu estava crescendo profissionalmente, comecei a pensar em novas maneiras de ajudar meus colegas desenvolvedores. Escrever artigos (no Medium e em revistas impressas) foi um grande começo, mas eu não conseguia medir o impacto que minhas publicações estavam tendo no público-alvo. Decidi, então, sair e conhecer esses desenvolvedores. Eu esperava não só compartilhar com eles, mas também apreender com eles na vida real. Como já era de se esperar, encontros, conferências e eventos para desenvolvedores são onde você pode encontrar todos esses desenvolvedores apaixonados.

Além disso: ser apaixonado por ajudar outros desenvolvedores pode (com sorte) também fazer com que você seja nomeado para o programa Google Developer Experts (ou para outros programas similares). Tive muita sorte em ingressar no programa do GDE há três anos e poder ajudar e influenciar ainda mais colegas desenvolvedores! Obrigado, Google!

Resumindo…

Eu continuo aqui, ainda gostando de ajudar meus colegas desenvolvedores. Acreditem ou não, esse se tornou meu trabalho em tempo integral na SFEIR como Developer Advocate sênior.

Então, o que é um Developer Advocate? O que é necessário para ser um bom Developer Advocate? Por que contratar Developer Advocates dedicados/apaixonados é a decisão certa a ser tomada como empresa? Vou tentar responder a essas perguntas.

O que é um Developer Advocate?

Em primeiro lugar, vamos deixar claro para todos: Developer Advocates também são engenheiros. Eles têm um forte histórico técnico em seus campos, criaram e enviaram aplicações para a produção. Alguns deles, inclusive, causaram crashes na produção ou excluíram acidentalmente banco de dados de clientes (isso aconteceu, de verdade)!

De acordo com esse requisito, Developer Advocates não deveriam ser pessoas da área de marketing ou vendas – há funções mais adequadas para essas pessoas. Porém, Developer Advocates deveriam ser capazes de dar feedback para as áreas de marketing ou vendas. Mais importante — pelo menos, para mim — é dar feedback ao gerenciamento de produto, influenciar no roteiro de criação do produtos com base, é claro, nas necessidades dos desenvolvedores.

Historicamente, muitas empresas em tecnologia contrataram Developer Advocates para defender suas plataformas, ajudando desenvolvedores a usar seus produtos – e eles ainda o fazem. Portanto, a função de um Developer Advocate é ajudar os desenvolvedores a terem sucesso com uma plataforma ou tecnologia. O papel de um Developer Advocate também é atuar como uma ponte entre o time de engenharia e a comunidade de desenvolvedores. A função deles é dar feedback a ambas as partes, igualmente, em ambos os sentidos.

Um Developer Advocate é alguém que realmente defende os desenvolvedores, não somente uma plataforma. Os desenvolvedores deveriam ser a prioridade dos Developer Advocates.

O que é necessário para ser um bom Developer Advocate?

Acredito que engenheiros não se tornam Developer Advocates porque seus gerentes pedem. Também acredito que Developer Advocates são pessoas inerentemente apaixonadas e altruístas. Essas características não podem ser simplesmente ensinadas ou aprendidas.

Pessoalmente, tentei convencer alguns desenvolvedores a começar a compartilhar o conhecimento deles, mas eu estava errado! Descobri que alguns engenheiros se sentem mais confortavéis programando (quem não se sentiria?) e dedicando-se totalmente a resolver problemas ou desenvolver produtos. Compartilhar conhecimento com outros desenvolvedores nã0 é a principal prioridade de todos os engenheiros. Isso é totalmente normal e deve ser respeitado. Se você é um gerente, não obrigue seus engenheiros a fingir ser o que eles não são e não os coloque em situações desconfortáveis. Ninguém quer estar nessa situação.

Então o que é necessário para ser um bom Developer Advocate? Aprendi que muitos, se não todos os Developer Advocates, têm as seguintes características.

Aprender continuamente

Como engenheiros, nunca paramos de aprender, mesmo depois de terminar a universidade. Sem dúvida, o verdadeiro conhecimento está por aí para ser descoberto. Developer Advocates, como qualquer outro engenheiro, são pessoas que gostam de aprender. Eles procuram conhecimento em todos os lugares. Usam todos os meios que conhecem para se manterem atualizados. Os Developer Advocates que eu conheço defendem uma plataforma ou produto, mas também experimentam e usam outros produtos – até mesmo os feitos pelos seus competidores. Por quê? Porque os desenvolvedores geralmente necessitam usar diferentes produtos e ferramentas para construir suas aplicações. Um Developer Advocate sabe disso!

Pensar fora da caixa

Aprender coisas novas não vale a pena se você não as questiona. Eu nunca considero algo que acabei de aprender como certo. Eu sempre me faço as mesmas perguntas: "Por que …?", "E se …?", "Como esse recurso pode ser melhorado?", "Qual é a aparência disso internamente?" Claro que qualquer engenheiro curioso naturalmente faria essas perguntas.

Developer Advocates não são exceções. Eles devem ser capazes de dar uma explicação de alto nível sobre como um recurso funciona internamente ou simplesmente fornecer algumas informações técnicas sobre o produto ou plataforma que eles defendem. Muitos desenvolvedores perguntarão sobre isso mais cedo ou mais tarde e você precisa estar preparado.

Criar aplicações para o mundo real

Aprender novas coisas e saber a teoria por detrás delas não vale a pena se você não criar aplicações que as utilizem. Se você vai defender desenvolvedores, o mínimo que você pode fazer é colocar-se no lugar do desenvolvedor tentando dominar o produto e a plataforma que você está defendendo. Esse é o momento no qual suas habilidades de engenharia serão úteis.

Criar aplicações reais com as ferramentas que você defende ajudará você a entender melhor quais são suas limitações e, com sorte, a sugerir algumas melhorias ao time de engenharia. A função de um Developer Advocate é também garantir que a plataforma e as ferramentas que você defende forneçam a melhor experiência para o desenvolvedor.

Compartilhar e preocupar-se

A habilidade de "compartilhar" informações com a comunidade de desenvolvedores é uma parte essencial na função desempenhada pelo Developer Advocate. Você não pode desenvolver essa função se não gosta de compartilhar ou ajudar a outras pessoas. Tudo bem: nem todos somos altruístas! Porém, fingir que está defendendo desenvolvedores será muito — e não me canso de dizer — muito desafiador!

Além disso, a maioria das empresas exige, nos seus anúncios de emprego, para a função de Developer Advocate, uma boa habilidade de comunicação oral e escrita. Embora eu concorde com esse requisito, também acredito que "habilidades de comunicação" não deveriam substituir nem serem confundidas com as habilidades de "compartilhar e se preocupar". Reformulando, contratar um Developer Advocate que realmente ama compartilhar e ajudar a outras pessoas é mais importante do que contratar alguém com uma boa habilidade de comunicação. Na verdade, o primeiro é mais difícil de desenvolver!

Então, resumindo: você quer contratar um bom Developer Advocate? Contrate um aprendiz curioso e ávido, que tenha a mente aberta, com boas habilidades de engenharia e habilidades genuínas de "compartilhamento e empatia".

Você pode mandar uma mensagem para o autor pelo Twitter caso tenha gostado do artigo e segui-lo caso queira ler mais sobre conteúdos semelhantes. Obrigado pela leitura!

Escrito por: Richard Reis

Tradução em português europeu

Se tens interesse em programação, é possível que já tenhas visto esta citação:

"Toda a gente neste país deve aprender a programar um computador, porque ensina-te a pensar." — Steve Jobs

Também te deves ter questionado sobre o que é, exatamente, pensar como um programador e sobre como podes fazê-lo.

Essencialmente, trata-se de um modo mais eficiente de resolver problemas.

Nesta publicação, o meu objetivo é ensinar-te esse modo.

No final da publicação, ficarás a saber exatamente quais os passos a dar para ser um(a) melhor solucionador(a) de problemas.

Qual é a importância disso?

A resolução de problemas é a habilidade das habilidades.

Todos temos problemas. Grandes e pequenos. O modo como lidamos com eles é, por vezes, bem… bastante aleatório.

A não ser que tenhas um sistema, esta é a forma como provavelmente "resolves" os problemas (que é o que eu fazia quando comecei a programar):

1. Tentar uma solução.
2. Se não funcionar, tentar outra.
3. Se também não funcionar, repetir o passo 2 até teres sorte.

Vejamos: por vezes, podes ter sorte. Esse, porém, é o pior modo de resolver problemas, além de ser um enorme desperdício de tempo.

A melhor forma envolve a) ter uma estrutura e b) praticá-la.

"Quase todos os empregadores dão prioridade a competências de resolução de problemas.

A resolução de problemas é, de maneira quase unânime, a qualificação mais importante procurada pelos empregadores… mais do que proficiência em linguagens de programação, depuração e design de sistemas.

Demonstrar pensamento computacional ou a capacidade de decompor problemas grandes e complexos é tão valioso (se não mais) como as competências técnicas necessárias para a vaga." — Hacker Rank (2018 Relatório de Competências do Programador)

Ter uma estrutura

Para encontrar a estrutura certa, segui o conselho no livro de Timothy Ferriss, "The 4-Hour Chef".

Levou-me a entrevistar duas pessoas muito interessantes: C. Jordan Ball (classificado em primeiro ou segundo em mais de 65 mil utilizadores no Coderbyte) e V. Anton Spraul (autor do livro "Think Like a Programmer: An Introduction to Creative Problem Solving").

Fiz-lhes algumas perguntas, e adivinha? As respostas de ambos foram bastante semelhantes!

Brevemente, também vais sabê-las.

Nota: isto não significa que fizeram tudo do mesmo modo. Toda a gente é diferente. Tu serás diferente. Se, no entanto, começares com princípios que todos concordamos que são bons, vais muito mais longe e mais rápido.

"O maior erro que vejo novos programadores a fazer é focarem-se em aprender a sintaxe em vez de aprender como resolver problemas." — V. Anton Spraul

Então, o que deves fazer quando te deparas com um novo problema?

Aqui estão os passos:

1. Compreender

Saber exatamente o que está a ser perguntado. A maioria dos problemas difíceis são difíceis porque não os compreendes (e por isso é que este é o primeiro passo).

Como saber quando compreendes um problema? Quando o conseguires explicar por palavras tuas.

Lembras-te de estar preso num problema, começas a explicá-lo e reparas, instantaneamente, em problemas na lógica que ainda não tinhas reparado?

A maioria dos programadores conhece essa sensação.

É por isso que devemos escrever o nosso problema, rabiscar um diagrama, ou falar com alguém sobre ele (ou alguma coisa… há quem utilize um pato de borracha).

"Se não conseguires explicar alguma coisa em termos simples, não a compreendes." — Richard Feynman

2. Planificar

Não avances logo para a resolução sem teres um plano (e esperar que por acaso consigas desenrascar-te pelo caminho). Planifica a tua solução!

Nada te pode ajudar se não conseguires escrever os passos exatos.

Em programação, isso quer dizer que não começas logo a resolver. Dá tempo ao teu cérebro para analisar o problema e processar a informação.

Para obter um bom plano, responde a esta questão:

"Dado um valor de entrada X, quais são os passos necessários para obter o resultado Y?"

Nota: os programadores têm uma ótima ferramenta para ajudá-los com isto… Comentários!

3. Dividir

Presta atenção. Este é o passo mais importante de todos.

Não tentes resolver um grande problema. Vais arrepender-te.

Em vez disso, divide o problema em problemas mais pequenos. Esses problemas são muito mais fáceis de resolver.

Depois, resolve cada sub-problema, um de cada vez. Começa pelo mais simples. Mais simples significa que sabes a resposta (ou estás perto de saber a resposta).

Depois disso, o mais simples significa que este sub-problema a ser resolvido não depende da resolução de outros.

Assim que resolveres todos os sub-problemas, junta os pontos.

Conectar todas as tuas "sub-soluções" vai dar-te a solução para o problema original. Parabéns!

Esta técnica é o pilar da resolução de problemas. Memoriza-a (relê este passo, caso necessário).

"Se conseguisses ensinar a todos os programadores principiantes uma habilidade de resolução de problemas, esta deveria ser a 'técnica de redução do problema'.
Por exemplo, vamos supor que és um novo programador e pedem-te para escrever um programa que lê dez números e tenta perceber qual deles é o terceiro maior. Para um novo programador, esta pode ser uma tarefa complicada, apesar de ser necessária apenas sintaxe de programação básica.
Se estiveres preso, deves reduzir o problema para algo mais simples. Em vez do terceiro maior número, por que não encontrar o maior de todos? Ainda muito complicado? Que tal encontrar o maior de apenas três números? Ou o maior de dois?
Reduz o problema até ao ponto em que sabes como resolvê-lo e escreve a solução. Depois, expande ligeiramente o problema e escreve de novo uma solução correspondente, continuando assim até chegares ao ponto inicial." — V. Anton Spraul

4. Sem saber o que fazer?

Neste momento, deves estar a pensar "Ei, Richard... isso é muito bonito, mas e se eu não souber o que fazer nem conseguir resolver um sub-problema?"

Em primeiro lugar, respira fundo. Em segundo, é justo.

No entanto, não te preocupes. Isto acontece a todos!

A diferença é que os melhores programadores/solucionadores de problemas ficam mais curiosos com bugs/erros do que irritados.

Na verdade, aqui estão três coisas para tentares fazer quando te deparares com um obstáculo:

• Debug: vai passo a passo pela tua solução e tenta encontrar onde ocorreu o erro. Os programadores chamam a isto de debugging (na verdade, isto é tudo o que um debugger faz).

"A arte do debugging é compreender o que realmente indicaste ao teu programa para fazer e não o que pensas que mandaste fazer." — Andrew Singer

• Reavaliar: Dá um passo atrás. Olha para o problema a partir de uma nova perspetiva. Existe alguma coisa que possa ser substituída por uma abordagem mais genérica?

"Por vezes, ficamos tão perdidos nos detalhes de um problema que ignoramos os princípios gerais que resolveriam o problema num nível mais genérico. […]

Um exemplo clássico disso é, claro, a soma de uma longa lista de números inteiros consecutivos, 1 + 2 + 3 + … + n, onde um Gauss muito jovem rapidamente reconheceu que era simplesmente n(n+1)/2, evitando assim o trabalho de ter de fazer a adição." — C. Jordan Ball

Nota: outro modo de reavaliar é começar de novo. Apaga tudo e começa de novo com a cabeça fresca. Estou a falar a sério. Vais ficar estupefacto com a eficácia disto.

• Pesquisa: ahh, o velho amigo Google. Leste bem. Não interessa qual é o teu problema. Ele, provavelmente, já foi resolvido por alguém. Encontra essa pessoa/solução. Na verdade, faz isto mesmo que tenhas resolvido o problema! Podes aprender muito com as soluções de outras pessoas.

Atenção: não procures pela solução de um grande problema. Procura apenas soluções para os sub-problemas. Por quê? Porque a não ser que tenhas dificuldades (mesmo que poucas), não vais aprender nada. Se não aprenderes nada, desperdiçaste o teu tempo.

Praticar

Não fiques à espera de ser o(a) melhor ao fim de apenas uma semana. Se quiseres ser bom a resolver problemas, resolve muitos problemas!

Pratica. Pratica. Pratica. Será apenas uma questão de tempo até reconheceres que "este problema era facilmente resolvido com <inserir conceito aqui>".

Como praticar? Existem opções até dizer chega!

Puzzles de xadrez, problemas matemáticos, Sudoku, Go, Monopoly, jogos, e assim por diante.

Na realidade, um padrão comum entre pessoas bem sucedidas é o seu hábito de praticar "micro-resolução de problemas". Por exemplo, Peter Thiel joga xadrez e Elon Musk joga jogos.

"Byron Reeves disse que 'Se quiseres ver como se parecerá a liderança das empresas em três a cinco anos, observa o que está a acontecer nos jogos online.'

Avançamos até hoje. Elon [Musk], Reid [Hoffman], Mark Zuckerberg e muitos outros dizem que os jogos foram fundamentais no seu sucesso em criar as suas empresas." — Mary Meeker (2017 – Relatório de tendências na internet)

Isto quer dizer que devo dedicar-me apenas a jogar? Nem por isso.

O que são os jogos, contudo? É isso mesmo: resolução de problemas!

Então, o que deves fazer é encontrar um canal para praticar. Algo que te permita resolver muitos micro-problemas (idealmente, algo que gostes).

Por exemplo, eu gosto de desafios de programação. Todos os dias, tento resolver pelo menos um desafio (geralmente no Coderbyte).

Tal como disse, todos os problemas partilham padrões semelhantes.

Conclusão

É isto!

Agora, compreendes melhor o que significa "pensar como um programador".

Também sabes que a resolução de problemas é uma habilidade incrível para cultivar (a habilidade das habilidades).

Como se isto não fosse suficiente, repara como também sabes o que tens de fazer para praticar as tuas habilidades de resolução de problemas!

Ufa… Muito interessante, certo?

Por fim, desejo que encontres muito problemas.

Leste bem. Pelo menos, agora saberás como resolvê-los! Além disso, vais aprender que, com cada solução, estás a evoluir.

"Assim que achares que navegaste um obstáculo com sucesso, outro emerge. Isso, porém, é o que torna a vida interessante.[…]
A vida é o processo de lidar com todos estes impedimentos — uma série de linhas fortificadas que temos de ultrapassar.
De cada vez, vais aprender alguma coisa.
De cada vez, vais desenvolver força, sabedoria e perspetiva.
De cada vez, um pouco mais de competição fica para trás. Até que tudo o que resta és tu: a melhor versão de ti próprio." — Ryan Holiday (O obstáculo é o caminho)

Agora, é hora de começar a resolver problemas!

Boa sorte!

Agradecimentos especiais a C. Jordan Ball e V. Anton Spraul. Todos os bons conselhos vieram deles.

Obrigado pela leitura! Se gostaste, compartilha este artigo com quem quiseres. Isso vai ajudar outras pessoas a verem a história.

Quando você aprende a programar pela primeira vez, é comum aprender arrays como a "principal estrutura de dados".

Em algum momento, você também aprenderá sobre tabelas hash. Se você estiver buscando o diploma em Ciência da Computação, você terá que fazer uma disciplina de estrutura de dados. Você também aprenderá sobre listas vinculadas, filas e pilhas. Essas estruturas de dados são chamadas de estruturas de dados "lineares", pois todas elas têm um início e um fim lógicos.

Quando começamos a aprender sobre árvores e grafos, pode ficar bastante confuso. Neles, não armazenamos dados de forma linear. As duas estruturas armazenam dados de um modo específico.

Este artigo é para ajudá-lo a entender melhor a estrutura de dados de árvore e para esclarecer qualquer confusão que você possa ter sobre ela.

Nele, vamos aprender:

• O que é uma árvore
• Exemplos de árvore
• Sua terminologia e como ela funciona
• Como implementar estruturas de árvore em código.

Vamos começar esta jornada de aprendizagem :)

Definição

Ao começar a programar, é comum entender melhor as estruturas de dados lineares do que estruturas de dados como árvores e grafos.

As árvores são conhecidas como uma estrutura de dados não linear. Elas não armazenam dados de modo linear. Elas organizam os dados de modo hierárquico.

Vamos examinar exemplos da vida real!

O que quero dizer quando digo de modo hierárquico?

Imagine uma árvore genealógica com relacionamentos de todas as gerações: avós, pais, filhos, irmãos e assim por diante. Geralmente, organizamos as árvores genealógicas de modo hierárquico.

O desenho acima é a minha árvore genealógica. Tossico, Akikazu, Hitomi e Takemi são meus avós.

Toshiaki e Juliana são meus pais.

TK, Yuji, Bruno e Kaio são os filhos dos meus pais (eu e meus irmãos).

A estrutura de uma organização é outro exemplo de uma hierarquia.

Em HTML, o Modelo de Objeto de Documento (em inglês, DOM, ou Document Object Model) funciona como uma árvore.

A tag HTML contém outras tags. Temos uma tag head e uma tag body. Essas tags contêm elementos específicos. A tag head tem tags meta e tags title. A tag body tem elementos que aparecem na interface do usuário, como h1, a, li, entre outros.

Uma definição técnica

Uma árvore é um conjunto de entidades chamadas nós. Os nós são conectados por arestas. Cada nó contém um valor ou dados e pode ou não ter um nó filho.

O primeiro nó da árvore é chamado de raiz. Se este nó raiz é conectado por outro nó, a raiz é então um nó pai e o nó conectado é um nó filho.

Todos os nós das árvores são conectados por links chamados arestas. Essa é uma parte importante das árvores, porque elas gerenciam a relação entre os nós.

As folhas são os últimos nós de uma árvore. Elas são os nós sem filhos. Como árvores reais, temos a raiz, os ramos e, finalmente, as folhas.

Outros conceitos importantes a serem entendidos são altura e profundidade.

A altura de uma árvore é o tamanho do caminho mais longo até uma folha.

A profundidade de um nó é o tamanho do caminho percorrido do nó até a raiz.

Resumo da terminologia

• A raiz é o nó mais alto da árvore
• A aresta é a ligação entre dois nós
• O filho é um nó que tem um nó pai
• O pai é um nó que tem uma aresta apontando para um nó filho
• A folha é um nó que não tem nós filhos na árvore
• A altura é o tamanho do caminho mais longo até uma folha
• A profundidade é o tamanho do caminho percorrido do nó até a raiz

Árvores binárias

Agora, vamos discutir um tipo específico de árvore. Nós a chamamos de árvore binária.

"Na ciência da computação, uma árvore binária é uma estrutura de dados em árvore na qual cada nó tem, no máximo, dois filhos, que são referidos como o filho da esquerda e o filho da direita". - Wikipédia

Então, vejamos um exemplo de árvore binária.

Vamos programar uma árvore binária

A primeira coisa que precisamos ter em mente quando implementamos uma árvore binária é o fato de ela ser uma coleção de nós. Cada nó tem três atributos: value, left_child (o filho da esquerda) e right_child (o filho da direita).

Como implementamos uma árvore binária simples que inicializa com estas três propriedades?

Vamos dar uma olhada.

class BinaryTree:
    def __init__(self, value):
        self.value = value
        self.left_child = None
        self.right_child = None

Aqui está. Esta é a nossa classe de árvore binária.

Quando instanciamos um objeto, passamos value (os dados do nó) como um parâmetro. Olhe para left_child e para right_child. Os dois estão definidos como None (Nenhum).

Por quê?

Porque quando criamos nosso nó, ele não tem filhos. Temos apenas os dados do nó.

Vamos testá-lo:

tree = BinaryTree('a')
print(tree.value) # a
print(tree.left_child) # None
print(tree.right_child) # None

É isso.

Podemos passar a string 'a' como o valor para nosso nó da árvore binária. Se imprimirmos value, left_child e right_child, podemos ver os valores.

Vamos para a parte de inserção. O que precisamos fazer aqui?

Vamos implementar um método para inserir um novo nó à direita e à esquerda.

Aqui estão as regras:

• Se o nó atual não tiver um filho da esquerda, criamos apenas um nó e o configuramos como left_child do nó atual.
• Se ele tiver o filho da esquerda, criamos um nó e o colocamos no lugar da filho da esquerda atual. Alocamos este nó filho da esquerda como o novo nó left_child.

Vamos representar isso com um desenho :)

Aqui está o código:

def insert_left(self, value):
    if self.left_child == None:
        self.left_child = BinaryTree(value)
    else:
        new_node = BinaryTree(value)
        new_node.left_child = self.left_child
        self.left_child = new_node

Novamente, se o nó atual não tiver um filho da esquerda, apenas criamos um nó e o configuramos como left_child do nó atual. Como alternativa, criamos um nó e o colocamos no lugar do left_child atual. Alocamos este nó como o novo nó left_child.

Fazemos a mesma coisa para inserir um nó do filho da direita.

def insert_right(self, value):
    if self.right_child == None:
        self.right_child = BinaryTree(value)
    else:
        new_node = BinaryTree(value)
        new_node.right_child = self.right_child
        self.right_child = new_node

Feito. :)

Porém, temos que testá-lo.

Vamos construir a seguinte árvore:

Para resumir a ilustração desta árvore:

• o nó a será a raiz da nossa árvore binária
• o filho da esquerda de a é o nó b
• o filho da direita de a é o nó c
• o filho da direita de b é o nó d (o nó b não tem um filho da esquerda)
• o filho da esquerda de c é o nó e
• o filho da direita de c é o nó f
• tanto o nó e como o nó f não têm filhos

Portanto, aqui está o código para a árvore:

a_node = BinaryTree('a')
a_node.insert_left('b')
a_node.insert_right('c')

b_node = a_node.left_child
b_node.insert_right('d')

c_node = a_node.right_child
c_node.insert_left('e')
c_node.insert_right('f')

d_node = b_node.right_child
e_node = c_node.left_child
f_node = c_node.right_child

print(a_node.value) # a
print(b_node.value) # b
print(c_node.value) # c
print(d_node.value) # d
print(e_node.value) # e
print(f_node.value) # f

A inserção está feita.

Agora temos que pensar na travessia da árvore.

Temos aqui duas opções: a Busca em Profundidade (DFS - Depth-First Search) e a Busca em Largura (BFS - Breadth-First Search).

• DFS "é um algoritmo para fazer uma travessia ou pesquisar a estrutura de dados em árvore. Ele começa pela raiz e explora o máximo possível ao longo de cada ramo antes de retroceder". – Wikipedia
• BFS "é um algoritmo para fazer uma travessia ou pesquisar a estrutura de dados em árvore. Ele começa na raiz da árvore e explora os nós vizinhos primeiro antes de passar para os vizinhos do nível seguinte". – Wikipedia

Portanto, vamos analisar os tipos de travessia de árvores.

Busca em Profundidade (DFS - Depth-First Search)

A DFS explora todo um caminho até uma folha antes de retroceder (backtracking) e explorar outro caminho. Vamos dar uma olhada em um exemplo com este tipo de travessia.

O resultado para este algoritmo será 1–2–3–4–5–6–7.

Por quê?

Vamos dividi-lo em partes.

1. Comece na `raiz` (1). Imprima-a.

2. Vá para o filho da esquerda (2). Imprima-o.

3. Então, vá para o filho da esquerda (3). Imprima-o. (Este nó não tem filhos)

4. Retroceda e vá para filho da direita (4). Imprima-o. (Este nó não tem filhos)

5. Retroceda, vá para nó raiz e vá para o filho da direita (5). Imprima-o.

6. Vá para o filho da esquerda (6). Imprima-o. (Este nó não tem filhos)

7. Retroceda e vá para filho da direita (7). Imprima-o. (Este nó não tem filhos)

8. Feito.

Quando vamos a fundo até uma folha e retrocedemos, isso é chamado de algoritmo DFS.

Agora que estamos familiarizados com esse algoritmo de travessia, discutiremos os tipos de DFS: pré-ordem, em ordem e pós-ordem.

Pré-ordem

Isso é exatamente o que fizemos no exemplo acima.

1. Imprimir o valor do nó.
2. Ir para o filho da esquerda e imprimi-lo se, e somente se, tiver um filho da esquerda.
3. Ir para o filho da direita e imprimi-lo se, e somente se, tiver um filho da direita.

def pre_order(self):
    print(self.value)

    if self.left_child:
        self.left_child.pre_order()

    if self.right_child:
        self.right_child.pre_order()

Em ordem

O resultado do algoritmo em ordem para este exemplo da árvore é 3–2–4–1–6–5–7.

Começamos da esquerda primeiro, depois pegamos o do meio e, por fim, o da direita.

Agora, vamos transformar isso em código.

def in_order(self):
    if self.left_child:
        self.left_child.in_order()

    print(self.value)

    if self.right_child:
        self.right_child.in_order()

1. Vá para o filho da esquerda e imprima-o se, e somente se, tiver um filho da esquerda.
2. Imprima o valor do nó
3. Vá para o filho da direita e imprima-o se, e somente se, tiver um filho da direita.

Pós-ordem

O resultado do algoritmo de pós-ordem para este exemplo de árvore é 3–4–2–6–7–5–1.

Começamos com a esquerda, seguindo da direita e depois o meio.

Vamos transformar isso em código.

def post_order(self):
    if self.left_child:
        self.left_child.post_order()

    if self.right_child:
        self.right_child.post_order()

    print(self.value)

1. Vá para o filho da esquerda e imprima-o se, e somente se, tiver um filho da esquerda.
2. Vá até o filho da direita e imprima-o se, e somente se, tiver um filho da direita.
3. Imprima o valor do nó

Busca em largura (BFS - Breadth-First Search)

O algoritmo BFS atravessa a árvore nível por nível e profundidade por profundidade.

Aqui está um exemplo que ajuda a explicar melhor este algoritmo:

Portanto, atravessamos nível por nível. Neste exemplo, o resultado é 1–2–5–3–4–6–7.

• Nível/Profundidade 0: somente o nó com valor 1
• Nível/Profundidade 1: nós com valores 2 e 5
• Nível/Profundidade 2: nós com valores 3, 4, 6, e 7

Agora, vamos transformar isso em código.

def bfs(self):
    queue = Queue()
    queue.put(self)

    while not queue.empty():
        current_node = queue.get()
        print(current_node.value)

        if current_node.left_child:
            queue.put(current_node.left_child)

        if current_node.right_child:
            queue.put(current_node.right_child)

Para implementar um algoritmo de BFS, usamos a estrutura de dados da fila para ajudar.

Como funciona?

Aqui está a explicação.

1. Primeiro adicione o nó raiz na fila (Queue) com o método put.
2. Itere enquanto a fila não estiver vazia.
3. Obtenha o primeiro nó na fila, depois imprima o seu valor.
4. Acrescentar o filho da esquerda e o filho da direita na fila (se o nó atual tiver filhos).
5. Feito. Imprimiremos o valor de cada nó, nível por nível, com nosso ajudante de fila.

Árvore binária de busca

"Uma árvore binária de busca é às vezes chamada de árvore binária ordenada ou classificada, e mantém seus valores em ordem, para que a busca e as outras operações possam usar o princípio da busca binária" - Wikipedia

Uma propriedade importante de uma árvore binária de busca é que o valor de um nó da árvore binária de busca é maior que o valor dos descendentes do seu filho da esquerda, mas menor que o valor dos descendentes de seu filho da direita".

Aqui está uma descrição da ilustração acima:

• A está invertido. A subárvore 7-5-8-6 precisa estar do lado direito e a subárvore 2-1-3 precisa estar do lado esquerdo.
• B é a única opção correta. Ela satisfaz a propriedade da árvore binária de busca.
• C tem um problema: o nó com o valor 4. Ele precisa estar do lado esquerdo da raiz porque é menor do que 5.

Vamos programar uma árvore de busca binária!

Agora é hora de programar!

O que veremos aqui? Vamos inserir novos nós, procurar um valor, deletar nós e o equilíbrio da árvore.

Vamos começar.

Inserção: adicionar novos nós à nossa árvore

Imagine que temos uma árvore vazia e que queremos adicionar novos nós com os seguintes valores nesta ordem: 50, 76, 21, 4, 32, 100, 64, 52.

A primeira coisa que precisamos saber é se 50 é a raiz de nossa árvore.

Podemos agora começar a inserir nó por nó.

• 76 é maior que 50, portanto insira 76 no lado direito.
• 21 é menor do que 50, portanto insira 21 no lado esquerdo.
• 4 é menor do que 50. O nó com valor 50 tem um filho da esquerda 21. Como 4 é menor do que 21, insira-o no lado esquerdo deste nó.
• 32 é menor do que 50. O nó com valor 50 tem um filho da esquerda 21. Como 32 é maior que 21, insira 32 no lado direito deste nó.
• 100 é maior que 50. O nó com valor 50 tem um filho da direita 76. Como 100 é maior que 76, insira 100 no lado direito deste nó.
• 64 é maior que 50. O nó com valor 50 tem um filho da direita 76. Como 64 é menor que 76, insira 64 no lado esquerdo deste nó.
• 52 é maior que 50. O nó com valor 50 tem um filho da direita 76. Como 52 é menor do que 76, o nó com valor 76 tem um filho da esquerda 64. 52 é menor do que 64, portanto insira 54 no lado esquerdo deste nó.

Você percebe um padrão aqui?

Vamos analisar.

1. O valor do novo nó é maior ou menor que o do nó atual?
2. Se o valor do novo nó for maior que o nó atual, vá para a subárvore à direita. Se o nó atual não tiver um filho da direita, insira-o lá ou retroceda para o passo nº 1.
3. Se o valor do novo nó for menor do que o nó atual, vá para a subárvore à esquerda. Se o nó atual não tiver um filho da esquerda, insira-o lá ou retroceda para o passo nº 1.
4. Não tratamos de casos especiais aqui. Quando o valor de um novo nó for igual ao valor atual do nó, use a regra número 3. Considere a inserção de valores iguais no lado esquerdo da subárvore.

Agora vamos transformar isso em código.

class BinarySearchTree:
    def __init__(self, value):
        self.value = value
        self.left_child = None
        self.right_child = None

    def insert_node(self, value):
        if value <= self.value and self.left_child:
            self.left_child.insert_node(value)
        elif value <= self.value:
            self.left_child = BinarySearchTree(value)
        elif value > self.value and self.right_child:
            self.right_child.insert_node(value)
        else:
            self.right_child = BinarySearchTree(value)

Parece muito simples.

A parte poderosa desse algoritmo é a parte de recursão, que está nas linhas 9 e 13. As duas linhas de código chamam o método insert_node e o utilizam para seus filhos à esquerda e filhos à direita, respectivamente. As linhas 11 e 15 são as que fazem a inserção para cada filho.

Vamos procurar o valor do nó... ou não...

O algoritmo que construiremos agora é o de buscas. Para um determinado valor (número inteiro), diremos se nossa árvore de busca binária tem ou não esse valor.

Um item importante a ser observado é como definimos o algoritmo de inserção de árvores. Primeiro, temos nosso nó raiz. Todos os nós da subárvore da esquerda terão valores menores que o nó raiz. Todos os nós da subárvore da direita terão valores maiores que o nó raiz.

Vamos dar uma olhada em um exemplo.

Imagine que temos esta árvore.

Agora, queremos saber se temos um nó baseado no valor 52.

Vamos analisar.

1. Começamos com o nó raiz como nosso nó atual. O valor dado é menor do que o valor do nó atual? Se sim, buscaremos esse valor na subárvore da esquerda.
2. O valor dado é maior do que o valor do nó atual? Se sim, buscaremos esse valor na subárvoreda direita.
3. Se as regras nº 1 e 2 forem falsas, podemos comparar o valor do nó atual e o valor dado se forem iguais. Se a comparação retornar True, podemos dizer: "Sim! Nossa árvore tem o valor dado", caso contrário, dizemos: "Não, não tem".

Agora, vamos transformar isso em código.

class BinarySearchTree:
    def __init__(self, value):
        self.value = value
        self.left_child = None
        self.right_child = None

    def find_node(self, value):
        if value < self.value and self.left_child:
            return self.left_child.find_node(value)
        if value > self.value and self.right_child:
            return self.right_child.find_node(value)

        return value == self.value

Vamos detalhar o código:

• As linhas 8 e 9 estão sob a regra nº 1.
• As linhas 10 e 11 estão sob a regra nº 2.
• A linha 13 está sob a regra nº 3.

Como testamos isso?

Vamos criar a nossa árvore binária de busca, inicializando o nó raiz com o valor 15.

bst = BinarySearchTree(15)

Agora, vamos inserir muitos nós novos.

bst.insert_node(10)
bst.insert_node(8)
bst.insert_node(12)
bst.insert_node(20)
bst.insert_node(17)
bst.insert_node(25)
bst.insert_node(19)

Para cada nó inserido, testaremos se o nosso método find_node realmente funciona.

print(bst.find_node(15)) # True
print(bst.find_node(10)) # True
print(bst.find_node(8)) # True
print(bst.find_node(12)) # True
print(bst.find_node(20)) # True
print(bst.find_node(17)) # True
print(bst.find_node(25)) # True
print(bst.find_node(19)) # True

Sim, ele funciona para esses valores dados! Vamos testar para um valor que não existe em nossa árvore de busca binária.

print(bst.find_node(0)) # False

Sim. Nossa busca está feita.

Eliminação: remoção e organização

A eliminação é um algoritmo mais complexo porque precisamos tratar de casos diferentes. Para um determinado valor, precisamos remover o nó com este valor. Imagine os seguintes cenários para este nó: ele não tem filhos, tem um único filho ou tem dois filhos.

• Cenário nº 1: um nó sem filhos (nó folha).

#        |50|                              |50|
#      /      \                           /    \
#    |30|     |70|   (DELETE 20) --->   |30|   |70|
#   /    \                                \
# |20|   |40|                             |40|

Se o nó que queremos excluir não tem filhos, simplesmente o excluímos. O algoritmo não precisa reorganizar a árvore.

• Cenário nº 2: um nó com apenas um filho (filho da esquerda ou filho da direita).

#        |50|                              |50|
#      /      \                           /    \
#    |30|     |70|   (DELETE 30) --->   |20|   |70|
#   /            
# |20|

Neste caso, nosso algoritmo precisa fazer com que o pai do nó aponte para o nó filho. Se o nó for o filho da esquerda, fazemos com que o pai do filho da esquerda aponte para o filho. Se o nó for o filho da direita do seu pai, fazemos com que o pai do filho da direita aponte para o filho.

• Cenário nº 3: uim nó com dois filhos.

#        |50|                              |50|
#      /      \                           /    \
#    |30|     |70|   (DELETE 30) --->   |40|   |70|
#   /    \                             /
# |20|   |40|                        |20|

Quando o nó tem dois filhos, precisamos encontrar o nó com o valor mínimo, a começar pelo filho da direita do nó. Colocaremos este nó com o valor mínimo no lugar do nó que queremos remover.

É hora de transformar isso em código.

def remove_node(self, value, parent):
    if value < self.value and self.left_child:
        return self.left_child.remove_node(value, self)
    elif value < self.value:
        return False
    elif value > self.value and self.right_child:
        return self.right_child.remove_node(value, self)
    elif value > self.value:
        return False
    else:
        if self.left_child is None and self.right_child is None and self == parent.left_child:
            parent.left_child = None
            self.clear_node()
        elif self.left_child is None and self.right_child is None and self == parent.right_child:
            parent.right_child = None
            self.clear_node()
        elif self.left_child and self.right_child is None and self == parent.left_child:
            parent.left_child = self.left_child
            self.clear_node()
        elif self.left_child and self.right_child is None and self == parent.right_child:
            parent.right_child = self.left_child
            self.clear_node()
        elif self.right_child and self.left_child is None and self == parent.left_child:
            parent.left_child = self.right_child
            self.clear_node()
        elif self.right_child and self.left_child is None and self == parent.right_child:
            parent.right_child = self.right_child
            self.clear_node()
        else:
            self.value = self.right_child.find_minimum_value()
            self.right_child.remove_node(self.value, self)

        return True

1. Primeiro: observe o valor dos parâmetros e o pai. Queremos encontrar o nó que tem este valor. O nó pai é importante para a remoção do nó.
2. Segundo: observe o valor de retorno. Nosso algoritmo retornará um valor booleano. Ele retorna True se encontrar o nó e o remove. Caso contrário, ele retornará False
3. Da linha 2 à linha 9: começamos a procurar o nó que tem o valor que estamos procurando. Se o valor for menor que o valor atual, vamos para a subárvore da esquerda, recursivamente (se, e somente se, o nó atual tiver um filho da esquerda). Se o valor for maior, vamos para a subárvore da direita, recursivamente.
4. Linha 10: começamos a pensar sobre o algoritmo de remoção.
5. Da linha 11 à linha 13: cobrimos o nó sem filhos. É o filho da esquerda do seu pai. Removemos o nó definindo o filho da esquerda do pai como None.
6. Linhas 14 e 15: cobrimos o nó sem filhos. É o filho da direita do seu pai. Removeremos o nó definindo o filho da direita do pai como None.
7. Método de limpeza do nó: mostrarei o código de clear_node abaixo. Ele define os nós do filho da esquerda, do filho da direita e o valor do nó para None.
8. Da linha 16 à linha 18: cobrimos o nó com apenas um filho (filho da esquerda). É o filho da esquerda do seu pai. Ajustamos o filho da esquerda do pai para o filho da esquerda do nó (o único filho que ele tem).
9. Da linha 19 à linha 21: cobrimos o nó com apenas um filho (filho da esquerda), e ele é o filho da direita do seu pai. Configuramos o filho da direita do pai para o filho da esquerda do nó (o único filho que ele tem).
10. Da linha 22 à linha 24: cobrimos o nó com apenas um filho (filho da direita), e ele é o filho da esquerda do seu pai. Configuramos o filho da esquerda do pai para o filho da direita do nó (o único filho que ele tem).
11. Da linha 25 à linha 27: cobrimos o nó com apenas um filho (filho da direita), e ele é o filho da direita do seu pai. Colocamos o filho da direita do pai no filho da direita do nó (o único filho que ele tem).
12. Da linha 28 à linha 30: cobrimos o nó com o filho da esquerda e o filho da direita. Obtemos o nó com o menor valor (o código é mostrado abaixo) e o configuramos com o valor do nó atual. Termine removendo o menor nó.
13. Linha 32: se encontrarmos o nó que estamos procurando, ele precisa retornar True. Da linha 11 à linha 31, tratamos desse caso. Então, basta retornar True e pronto.

• Para usar o método clear_node: configure o valor None para todos os três atributos — (value, left_child e right_child)

def clear_node(self):
    self.value = None
    self.left_child = None
    self.right_child = None

• Para usar o método find_minimum_value: desça para a esquerda. Se não conseguirmos encontrar mais nós, encontramos o menor.

def find_minimum_value(self):
    if self.left_child:
        return self.left_child.find_minimum_value()
    else:
        return self.value

Agora vamos testá-lo.

Usaremos esta árvore para testar nosso algoritmo remove_node.

#        |15|
#      /      \
#    |10|     |20|
#   /    \    /    \
# |8|   |12| |17| |25|
#              \
#              |19|

Vamos remover o nó com o valor 8. É um nó sem filho.

print(bst.remove_node(8, None)) # True
bst.pre_order_traversal()

#     |15|
#   /      \
# |10|     |20|
#    \    /    \
#   |12| |17| |25|
#          \
#          |19|

Agora, vamos remover o nó com o valor 17. É um nó com apenas um filho.

print(bst.remove_node(17, None)) # True
bst.pre_order_traversal()

#        |15|
#      /      \
#    |10|     |20|
#       \    /    \
#      |12| |19| |25|

Finalmente, removeremos um nó com dois filhos. Esta é a raiz da nossa árvore.

print(bst.remove_node(15, None)) # True
bst.pre_order_traversal()

#        |19|
#      /      \
#    |10|     |20|
#        \        \
#        |12|     |25|

Os testes agora estão prontos. :)

Isso é tudo por enquanto!

Parabéns por terminar este conteúdo denso. É realmente difícil entender um conceito que não conhecemos, mas você conseguiu. :)

Este é mais um passo adiante na minha jornada de aprendizagem e domínio de algoritmos e estruturas de dados. Você pode ver a documentação de minha jornada completa aqui na minha publicação Renaissance Developer (em inglês).

Divirta-se, continue aprendendo e programando.

Twitter e Github do autor. ☺

Recursos adicionais (em inglês)

• Introdução à estrutura de dados em árvore, da mycodeschool
• Como não ser atropelado pelas árvores, do talentoso Vaidehi Joshi
• Introdução às árvores, palestra do professor Jonathan Cohen
• Introdução às árvores, palestra do professor David Schmidt
• Introdução às árvores, palestra do professor Victor Adamchik
• Árvores com Gayle Laakmann McDowell
• Implementação de árvores binárias e testes, por TK
• Curso do Coursera: Estruturas de dados, da Universidade da Califórnia, San Diego
• Curso do Coursera: Estruturas de Dados e desempenho, da Universidade da Califórnia, San Diego
• Conceitos e implementação da árvore binária de busca, de Paul Programming
• Implementação da árvore binária de busca e testes, por TK
• Algoritmo de remoção de nó da árvore binária de busca, de GeeksforGeeks
• Algoritmo de remoção de nó da árvore binária de busca, de Algolist
• Aprendendo Python do zero ao herói
• Travessia de árvores, da Wikipédia

Recursos adicionais (em português)

• Árvore, da Wikipedia

Escrito por: Radu Raicea

Recentemente, tivemos algumas notícias empolgantes para os desenvolvedores em todo o mundo. O Facebook mudou a licença de várias bibliotecas que eles desenvolvem. Eles mudaram de patentes BSD-3+ para MIT (Massachusetts Institute of Technology).

Certo, mas o que significa? Quais são as implicações de diferentes licenças de código aberto?

Este artigo dará a você uma rápida compreensão das licenças populares. Ele também ensinará como aplicá-las aos seus projetos de código aberto no GitHub.

A autoridade

As licenças de código aberto mais populares têm um aspecto importante em comum. A Iniciativa de Código Aberto (OSI - Open Source Initiative) as aprovou.

A OSI foi formada em 1998 com o objetivo de promover o software de código aberto. Ela criou a Definição de Código Aberto (OSD - Open Source Definition) para definir o que significa um software de código aberto.

É assim que eles se descrevem:

A Iniciativa de Código Aberto (OSI - Open Source Initiative) é uma organização sem fins lucrativos com escopo global formada para educar e defender os benefícios do código aberto e construir pontes entre os diferentes círculos da comunidade de código aberto.

As licenças

A maioria das licenças de código aberto inclui as seguintes declarações:

1. O software pode ser modificado, utilizado comercialmente e distribuído.
2. O software pode ser modificado e utilizado em particular.
3. Uma licença e um aviso de direitos autorais devem ser incluídos no software.
4. Os autores do software não fornecem nenhuma garantia com o software e não são responsáveis por nada.

Passaremos pelas licenças mais populares, de modo a mostrar as mais restritivas e as mais permissivas (da perspectiva do usuário).

GNU (General Public License ) – Licença Pública Geral, versão 3 (GPLv3)

A GPLv3 é uma das licenças mais restritivas. Ela oferece alta proteção para o autor do software.

• O código-fonte deve ser tornado público sempre que uma distribuição do software for feita.
• As modificações do software devem ser liberadas sob a mesma licença.
• As alterações feitas no código-fonte devem ser documentadas.
• Se o material patenteado for usado na criação do software, ela concede aos usuários o direito de usá-lo. Se o usuário processar alguém pelo uso do material patenteado, ele perde o direito de usar o software.

A GPLv2 é também muito popular. A principal diferença em relação à GPLv3 é a cláusula sobre concessão de patentes.

Essa cláusula foi acrescentada na versão 3 para evitar que as empresas cobrassem dos usuários pelo uso de suas patentes (texto em inglês).

Projetos populares que usam GPLv3 são o Bash e o GIMP. O Linux utiliza a GPLv2.

Ezequiel Foncubierta apontou algo importante para as licenças GPL:

A licença do seu código-fonte deve ser compatível com a licença do código-fonte aberto ao qual você está vinculado. Por exemplo, se seu código for proprietário, você não terá permissão para usar uma biblioteca sob a licença GPL. É aqui que as pessoas tendem a cometer mais erros.

Licença Apache 2.0

A licença Apache 2.0 oferece mais flexibilidade para os usuários.

• O código-fonte não precisa ser público quando uma distribuição do software é feita.
• As modificações no software podem ser liberadas sob qualquer licença.
• As alterações feitas no código fonte devem ser documentadas.
• Ela oferece a mesma proteção de uso de patente que a GPLv3.
• Ela proíbe explicitamente o uso de nomes de marcas registradas encontradas no projeto.

Projetos populares usando a licença Apache 2.0 são o Android, o Apache e o Swift.

Distribuição de Software da Berkeley (BSD - Berkeley Software Distribution)

A BSD tem duas versões principais: a de 2 cláusulas e a de 3 cláusulas (textos em inglês). Ambas oferecem mais flexibilidade para os usuários do que a Licença Apache 2.0.

• O código-fonte não precisa ser público quando uma distribuição do software é feita.
• As modificações no software podem ser liberadas sob qualquer licença.
• As alterações feitas no código-fonte podem não ser documentadas.
• Ela não oferece nenhuma posição explícita sobre o uso da patente.
• A licença e o aviso de direitos autorais devem ser incluídos na documentação da versão compilada do código-fonte (em oposição a apenas no código-fonte).
• A BSD de 3 cláusulas afirma que os nomes do autor e dos colaboradores não podem ser usados para promover produtos derivados do software sem permissão.

Os projetos populares que usam a licença BSD são o Go (3 cláusulas), o Pure.css (3 cláusulas) e o Sentry (3 cláusulas).

Licença MIT (Massachusetts Institute of Technology)

A MIT é uma das licenças mais permissivas. É também a mais popular. Ela oferece uma proteção muito baixa para o autor do software.

• O código-fonte não precisa ser público quando uma distribuição do software é feita.
• As modificações no software podem ser liberadas sob qualquer licença.
• As alterações feitas no código-fonte podem não ser documentadas.
• Ele não oferece nenhuma posição explícita sobre o uso da patente.

Os projetos populares que utilizam a MIT são o Angular.js, o jQuery, o Rails, o Bootstrap e muitos outros.

O React.js do Facebook tinha uma licença de patente BSD-3+ até 25 de setembro de 2017. Ela combinava a licença do BSD-3 com uma cláusula adicional sobre o uso de patentes.

Em resumo, se você processar o Facebook ou qualquer uma de suas subsidiárias, perderá o direito de usar o React (ou qualquer outro software sob a mesma licença).

O React agora é licenciado pela MIT. Agora, você pode processar o Facebook e ainda usar o React. Que alívio!

Aplicando uma licença para os seus projetos de código aberto

Licenciar os seus projetos é fácil. Você precisa apenas adicionar um LICENSE, LICENSE.txt ou LICENSE.md no diretório raiz do seu repositório.

O GitHub torna tudo ainda mais fácil:

1. Abra o seu repositório GitHub em um navegador.
2. No diretório raiz, clique em Create new file.
3. Nomeie o arquivo "LICENSE".
4. Clique em Choose a license template.
5. Escolha uma das licenças (todas as mencionadas neste artigo estão lá).
6. Uma vez escolhido, clique em Review and submit.
7. Faça o commit do arquivo.

Em resumo...

• Uma das licenças mais restritivas é a GPL
• Uma das licenças mais permissivas é a MIT.
• Outras licenças populares são  a licença Apache 2.0 e a BSD.
• Para aplicar uma licença em seu projeto do GitHub, você precisa apenas criar um arquivo LICENSE usando os templates de licença do GitHub.

Confira também o artigo do autor sobre como ele usou o Python para encontrar pessoas interessantes para seguir no Medium (texto em inglês)!