Can you get the loop? #Codewars

No final do ano passado meu namorado me mandou esse site super legal para treinar Algoritmos (sempre bom): Code Wars. Porque eu curti? É mais amigável, a comunidade é mais ativa e você cria um clã com seus amigos. Ainda que você seja iniciante, ele te sugere problemas mais difíceis para você ir treinando, além de mostrar as soluções de outros participantes para você analisar e aprender boas práticas depois de submeter sua solução. E já que falamos de clãs, quem quiser entrar no meu, aí vai o link: entre no meu clã! =D

Semestre passado, vimos algumas Estruturas de Dados e dentre elas, listas encadeadas. Daí resolvi resolver um Kata para revisar nas férias e postar aqui para discutir com vocês.

O problema

Pode ser acessado aqui e a seguir a descrição:

You are given a node that is the beginning of a linked list. This list always contains a tail and a loop.
Your objective is to determine the length of the loop.
For example in the following picture the tail’s size is 3 and the loop size is 11.

Portanto, a solução requer descobrir a posição do tail (que será o nó cujo conteúdo se repete) para retornar o tamanho do loop. O que eu fiz foi criar um dicionário e armazenar os conteúdos dos nós até encontrar um que se repete – o tail. A partir daí, rodei outro while para retornar o tamanho do loop. O código em Python pode ser visto a seguir:


def loop_size(node):
    my_dict = {} 
    p = node // node é o head que foi passado como argumento
    my_dict[node] = p //inicializando dicionário com o conteúdo de node
    
    while p.next not in my_dict: 
        p = p.next
     
    my_dict[p] = p
    tail = p // ao sair do loop eu acho o tail, pois é ele que repete
    
    t = tail
    size = 1 
    while t.next != tail: 
        t = t.next
        size +=1
        
    return size

Sei que é possível resolver esse problema sem utilizar dois whiles, mas por enquanto fica essa solução e depois eu posto novamente o código refatorado, pois ainda preciso estudar mais sobre dicionários. Curtiram? =P

Compreendendo Recursão

Muito bem, semestre começou com tudo e estou aprendendo muita coisa nova! Uma delas que estou vendo agora é Recursão. Se você já ouvi falar de Algoritmos, provavelmente já deve ter ouvido falar de Recursão também. De acordo com o material da nossa aula

um processo recursivo é um processo que implementa uma relação de recorrência. Uma relação de recorrência é uma expressão matemática utilizada para expressar uma equação de recorrência.

Wait, what? Vamos por partes, pois esse é um conceito muito difícil de ser compreendido, mas vale a pena, prometo. O mais legal de se aprender recursão é criar algoritmos menores e mais bonitos (embora nem sempre seja o mais eficiente!). Resumindo, uma função recursiva vai chamar a si mesma e retornando os valores de cada chamada, até chegar no caso base.

Calma, não é mágica! Acredito que uma das maiores dificuldades seja compreender os passos para escrever uma função recursiva para que esta não caia num loop infinito. Por isso é preciso ter atenção às duas partes essenciais de uma chamada deste tipo e verificar com números inteiros o problema até que você entenda o que será o caso base e a chamada recursiva a partir do exemplo a seguir:

Considere um vetor de inteiros de tamanho n. Uma função recursiva que calcule o produto dos elementos estritamente positivos de um vetor de inteiros v [0..n-1].

 int produto (int v[], int n) {
     if(n == 1){
   	 return v[0];
     }
     if(v[n-1] > 0){
   	 return v[n-1] * produto(v, n-1);
    }
	return produto(v,n-1);
 }

O caso base – Essa é a parte que você sabe o resultado e deve se aproximar na próxima etapa. No exemplo abaixo, vemos que o caso base é a condição if (n == 1) return v[0];, pois quando o vetor chegar até o primeiro elemento, não há mais necessidade de se calcular o produto, certo?

A chamada recursiva – Esta deve ser quebrada em pedaços menores até atingir o caso base. No nosso exemplo, fazemos duas chamadas distintas. Caso o elemento da posição v[n-1] a ser testada seja positiva, então retornamos return v[n-1] * produto(v, n-1); , caso contrário, chamamos a função para continuar a descrescer o valor de n até atingir o valor de 1, nosso caso base.

O que a função faz é o seguinte. Vamos supor que o nosso vetor v[4] = {1, 2, 3, 4} e o tamanho do vetor seja n = 4.

produto(v, 4)

v[3] * produto(v, 3)
v[3] * v[2] * produto(v, 2)
v[3] * v[2] * v[1] * produto(v, 1)
v[3] * v[2] * v[1] * v[0]
>> 4 * 3 * 2 * 1 = 24

Esse exemplo foi retirado desse material e está disponívelneste link. Veja também outras formas de usar a recursividade para resolver o mesmo problema (:

Vá fazendo com calma cada passo para não se perder (o que é muito fácil) e compreender como o computador entende essas chamadas (vale printar todas as entradas para ver o valor de retorno a cada chamada). Dá um trabalho e sua cabeça buga por um momento (ou dias xD), mas seu código fica mais bonito e te deixa com uma sensação maravilhosa de finalmente aprender Recursão 🙂

O que é preciso para aprender a programar?

Quando começamos a estudar programação, percebemos o quanto o método tradicional na verdade nos ensina a não pensar. É por isso que para muitos é tão difícil programar, porque você tem que aprender a pensar direito e nosso cérebro meio que atrofia depois de tantos anos repetindo fórmulas e datas descontextualizadas (alguns países já incluem programação como disciplinas curriculares, mas vai levar muito tempo para isso se tornar algo global, infelizmente). Mas, calma, nem tudo está perdido!

Se você tiver acesso à internet e se interessar por programação, com certeza vai achar centenas de tutoriais e de sites voltados a isso. No entanto, pela minha experiência própria, acredito que aprender a Lógica de Programação deva ser o primeiro passo. Aprender a construir algoritmos deve ser a sua principal preocupação nesse momento. Na verdade, essa palavrinha Algoritmos é algo bem comum no nosso dia a dia, a diferença é que não estamos acostumados a abstrair as nossas ações e colocá-las em uma sequência clara de instruções. Resumindo, a Lógica de Programação será sua melhor amiga que vai dizer pro computador fazer exatamente o que você quer.

large

Quando eu comecei a fazer o curso de JavaScript no CodeCademy tive muitas dificuldades e hoje entendo porquê. Estudando Lógica de Programação na faculdade, percebo o quanto foi difícil para mim encarar assim logo com uma linguagem. Por mais que o curso seja didático, alguns termos e funcionalidades eu não entendia e além disso, ainda tinha que aprender a sintaxe de JavaScript! Portanto, se isso é algo que aconteceu com você ou está acontecendo, isso é normal.

517af58f32d50c62c36c04f7d9cca982

Aprendendo os fundamentos da programação, você só precisa depois aplicá-los à linguagem que você quer, olha que genial! A Lógica será sempre a mesma, por isso, você não precisa se preocupar em aprender Ruby, Python, Java, etc. (ok, maldade querer comparar Ruby e Python com qualquer outra linguagem xD), mas sim em aprender pensar como um computador (que, convenhamos, finge muito bem ser super inteligente).

O Visulg foi criado pelo programador e professor universitário no RJ, Claudio Morgado de Souza. É um programa que edita, interpreta e executa algoritmos com uma linguagem próxima do português estruturado como um programa normal de computador. Você pode baixar de graça e se divertir. Existem vários PDF’s também disponíveis e, o mais importante, com vários exercícios. A minha dica de ouro nesse contexto é: não procure a resolução dos exercícios na internet! Pense, pense que você chega lá. Pode não ser no mesmo dia, mas você consegue 🙂

Porém, mesmo com todas essas ferramentas que a internet oferece, existirão vários momentos em que você se sentirá empacado. Nessas horas, alguém que já tenha experiência com programação fará toda a diferença na sua vida . O mais legal dessa parte é quando você percebe que já sabia a resposta, só não sabia como implementar ou então, que faltava só um detalhe e voilà! Com o tempo você mesmo será um mentor para outros. Interessante, não?

Resumindo, se você acha que programar deve ser legal, tente partir de um jeito que seja menos traumático para você. Juntando tudo isso com sua vontade de aprender e curiosidade, é muito legal quando depois de um tempo, revendo seus algoritmos você pensa “Nossa, que ruim, posso fazer melhor”. Isso é sinal de que você realmente está aprendendo. Isso não significa que você deva se envergonhar do que fez, mas sim ficar feliz por estar melhorando, claro! Na real, se você não é nenhum gênio, às vezes você faz um algoritmo que funciona, mas que poderia ser melhorado.

Aproveitando o contexto, essa semana saiu até o curso temático do Minecraft no Code.org Corra lá e divirta-se, essa é a melhor parte de programar! =)