<aside> 🍔 Um relato sincerão de como foi resolver o projeto Push Swap em 42 horas. Spoiler: não levou só 42h, e eu não teria conseguido se tivesse seguido tentando sozinho.
</aside>
palavras-chave: algoritmos, ordenação, pilhas, lista encadeada, coding dojo
Em poucas palavras, o Push_Swap é um projeto em que é preciso escrever um programa que recebe uma lista de números desordenada como argumentos de entrada, e que ordena essa lista de maneira crescente (ou decrescente, depende do ponto de vista 🧐). Para isto, é permitido utilizar somente duas pilhas de números (como as pilhas de prato na imagem do cabeçalho), A e B, e a manipulação destas pilhas deve acontecer seguindo regras específicas (por exemplo, não é permitido tirar um prato do meio da pilha para colocar no seu topo, nem colocar o prato do topo de uma pilha embaixo ou no meio da outra pilha de uma vez só). Essas operações limitadas que se podem fazer com as pilhas deram o nome ao projeto: é permitido fazer um push de uma pilha para outra — ou seja, empurrar o prato do topo da pilha A para o topo da B, e vice-versa; é permitido fazer um swap nos dois primeiros elementos do topo de uma pilha — ou seja, trocar os dois primeiros pratos do topo da pilha, de maneira que o segundo fica em cima do primeiro, e o primeiro embaixo do segundo; e é permitido rotacionar uma pilha por vez, para cima ou para baixo — ou seja, o prato de cima desce e vira o último prato da pilha, ou o contrário, o último prato da pilha vira o primeiro.
Minha experiência com o push_swap foi de altos e baixos, que casaram certinho com o que eu entendo como as 4 principais partes do projeto. Vou narrá-los aqui brevemente, ao mesmo tempo que explico como eu sugiro que o projeto seja feito:
Consegui implementar muito rápido a estrutura de lista duplamente encadeada (me baseando nas funções de bônus que fiz pra Acelera — Libft ), acredito que foi bem tranquilo pra mim fazer isso nesse projeto porque eu já tinha tentado usar listas encadeadas simples antes no Acelera — So_long (apesar de depois desistir da ideia e seguir com array mesmo). Entendo que essa parte é um grande desafio para algumas pessoas (pra mim também foi, só começou um pouco antes do push_swap), então primeiro de tudo sugiro que você avalie a sua situação, e se pergunte se você deseja utilizar uma estrutura de dados um pouco mais sofisticada pra resolver o problema (listas encadeadas) ou se pretende usar arrays (que provavelmente você já tem mais prática usando). Os dois jeitos funcionam, um não é absolutamente melhor que o outro. Neste momento, a avaliação que você tem que fazer é “qual escolha vai ser melhor >>PARA MIM<<”.
Caso queira se desafiar a usar listas encadeadas e esse conceito esteja nebuloso pra você, sugiro que empenhe um tempo de qualidade pesquisando e entendendo o conceito (primeiro a lista simples, depois a duplamente encadeada, depois a circular); daí você abre o seu VSCode e vai brincar de criar listas e de fazer as operações básicas de lista (criar um item de lista novo, adicionar o item novo no início da lista, depois no final, encontrar o último elemento da lista, depois encontrar o primeiro elemento, etc). Dica para facilitar o entendimento de listas encadeadas: se vc estiver com dificuldade de entender o funcionamento da lista encadeada por conta do void *, faça o exercício de reescrever as funções bônus da libft substituindo o void * por um int *. Eu resolvi o push_swap inteiro com essas funções reescritas, e só fui entender mesmo e utilizar a lista encadeada com void * no minishell, então vale a pena facilitar a sua vida num primeiro momento pra entender a manha das listas encadeadas, pra depois abstrair o int * pra um void *. Depois vc parte pra segunda parte do projeto, que é:
Também não tardei pra escrever funções que executam as operações básicas de pilha que o pdf pede: pa, pb, sa, sb, ss, ra, rb, rr, rra, rrb, rrr. Usando as funções de operações básicas de lista encadeada, é muito tranquilo manipular duas pilhas, tirar o elemento do topo de uma e colocar no topo da outra, inverter a ordem do topo com o final e vice-versa. A mesma coisa deve ser feita utilizando arrays caso esta tenha sido sua escolha. Essa parte foi tranquila e é importante fazer testes extensivos — e se uma das pilhas estiver vazia na hora de um push, swap ou rotate? e se tiver só 2 elementos? e se tiver só 1? E claro, sempre testando por vazamentos de memória pra não deixar nada passar. (É muito importante olhar pra isso desde o início!) Até aí, suavão 😎🤙. Mal sabia o que me esperava na terceira parte do projeto que é:
A minha ideia original era usar o jogo da Paula pra bolar uma estratégia infalível de ordenar os bloquinhos, e depois traduzir essa estratégia em linhas de código. Pra mim, essa foi a parte mais DESAFIADORA, porque pensar em uma estratégia que seja consistente e que possa ser infinitamente reproduzida não é tão fácil quanto parece. “Mas tudo bem”, pensei, “pelo menos dei uma adiantada no início, não tem problema ficar mais tempo pensando no algoritmo”. Quando peguei o jogo pra resolver, eu percebi que a minha mente fazia cálculos MUITO rápido baseado no que os meus olhos viam, e que eu não conseguia muito facilmente escrever esse raciocínio numa folha de papel. Além do mais, o computador não tem olhos, então, como traduzir as conclusões que eu tirava a partir do que eu estava VENDO para uma linguagem que o meu código conseguiria reproduzir? Osso demais. De maneira geral percebi que tive bastante dificuldade para focar em uma estratégia — porque a todo momento vinha um novo “e se...?” na minha mente, então foi difícil fechar um raciocínio do início ao fim. Depois de talvez uma semana em busca D’O Algoritmo Para Todos Governar💍, eu tinha uma lista de instruções objetivas que dava pra ser repetida diversas vezes em várias configurações iniciais diferentes dos bloquinhos do jogo, e me pus a transcrever essa lista de instruções em linhas de código. Por fim, eu fiz alguns testes pontuais com 8, depois 50, depois 100 números, e ao que tudo indicava, meu algoritmo estava funcionando! As instruções que ele gerava eram suficientes para ordenar qualquer lista de números de entrada! 🎉 Maravilha! Agora é só partir pro abraço! Ou foi o que pensei.
Lá fui eu com o algoritmo que eu tinha MANUFATURADO com nada mais nada menos que meu cérebro 🧠 e estas mãozinhas que vos escrevem 🖐🏻🖐🏻, pronto para jogá-lo no tester, convencido de que seria uma mera formalidade antes de fechar o projeto na intra e partir para as avaliações. Não podia estar mais enganado. Meu algoritmo para ordenar 100 números estava levando mais de 6000 operações. Para 500, MAIS DE 20 MIL. E de quebra, para ordenar listas pequenas de 5 números, às vezes levava 12, às vezes 19 operações. Quando fui ver meu algoritmo rodando com o visualizer, claro que é muito emocionante ver sua cria dar os primeiros passos 🍼🥲 mas logo em seguida vi que na verdade eu tinha feito algo que parecia mais um Bubble Sort, e que pra ser mais ineficiente que isso, só sendo o Bogo Sort 🤡. Senti muita frustração. Porque tudo o que eu tinha feito com todo o meu poder computacional-cerebral estava extremamente ineficiente, e se eu já tinha gastado esse tempo todo elaborando um algoritmo que ficou ruinzão, eu jamais conseguiria pensar em algo que fosse melhor em tempo hábil. Eu havia falhado a missão, e pra não ter que lidar com isso eu fui catar coisa pra fazer. Faxinei a casa, fui escrever uns README, uns notion de projeto (👀), tudo pra não ter que lidar com o fato de que a minha tentativa inicial, por mais bem pensada, refletida, ponderada, estava ruim, e que eu teria que tentar de novo.
Virou o ciclo, e fui colocado numa squad com uma colega com quem já tinha trocado uma ideia antes fazendo o Acelera — Born2BeRoot, e ela estava falando como tava difícil desemperrar no início do projeto, e eu chorando as pitangas de ter que refazer todo o algoritmo. Logo em seguida teve uma das reuniões semanais no chat de bolsistas, e nessas reuniões a gente costuma fazer um checkin de contar como estamos chegando e quais os desafios da semana (parecido com a hora da vila no basecamp). Foi então que eu falei que tava difícil retomar o push_swap, e vi que outras pessoas também estavam travadas nesse projeto, cada uma em um ponto: uma pessoa tava começandinho, outra tava emperrada na parte das listas, eu e mais outra já tínhamos escrito uma versão inicial do algoritmo, sem grandes sucessos. Eu só sei que alguém em algum momento falou de zoeira “NOSSA IA SER DAHORA se a gente juntasse galera pra resolver esse projeto junto”, alguém brincou “imagina, fazer o push_swap em 24 horas?!”, e mais alguém arrematou: “24 não dá, mas em 48h.........”; “48 não, 42 horas”. Só de zoeira. Até deixar de ser zoeira e virar uma parada séria 😂. E aí decidimos então que uniríamos todas as tribos, habilidades e forças em busca de um único ideal: entregar este fatídico projeto em nada mais nada menos que 42h de fritação, estilo hackathon. Recentemente tinha aprendido sobre Coding Dojos, daí eu sugeri que a gente fizesse esse revezamento de quem pilota (escreve o código) e quem acompanha. A ideia era que cada pessoa ficasse por 15 minutos escrevendo um pouco de código, deu o timer, passa pra próxima, e assim sucessivamente até dar as 42h e termos o projeto pronto 😂 Só que não. E tudo bem. Daí em diante o resto é história, e a real é que essa foi minha primeira experiência na 42 fazendo um projeto a 8 mãos, e foi uma das experiências mais divertidas e incríveis que tive até então! Não concluímos o push swap em 42 horas (levou uma semaninha no todo), mas por mais que tenha sido uma experiência cansativa estilo basecamp, saí do outro lado com mais gás ainda pra continuar fazendo os projetos assim, e com 3 novas amizades que têm me acompanhado na alegria e na tristeza dessa 42sp desde então.
No geral, eu deixo de recomendação tentar seguir mais ou menos esse caminho, senti que foi uma progressão interessante, e na real essa é a natureza e o ingrediente do sucesso pros projetos por aqui: começar pequeno, e ir expandindo. Não vou deixar aqui um caminho passo a passo para resolver o push_swap em si (escrever o algoritmo) além do nosso código que está disponível no Github, porque esses tutoriais já existem por aí, e fica a critério de cada pessoa decidir como chegar na solução. Acredito que o propósito desse projeto é exatamente desafiar cada cadete a inventar sua forma de resolver o problema da maneira mais criativa e eficiente possível, e pra alcançar esse objetivo, claro, é preciso contar com o apoio da comunidade (trocar ideias, pensar juntes, usar visualizadores e testers), e, principalmente, se divertir! Boa sorte 🍀