/Algorithms

Primary LanguagePython

Boas-vindas ao repositório do projeto Algorithms!

👨‍💻 O que deverá ser desenvolvido

Neste projeto você irá resolver problemas e otimizar algoritmos desenvolvendo a sua capacidade de implementar soluções para os mais diversos problemas do dia a dia!

🚵 Habilidades exercitadas:

Lógica;

Capacidade de interpretação de problemas;

Capacidade de interpretação de um código legado;

Capacidade de otimizar a resolução de problemas e;

Resolver problemas/Otimizar algoritmos sob pressão.

Orientações

⚠️ Antes de começar a desenvolver
  1. Clone o repositório
  • Use o comando: git clone git@github.com:tryber/sd-017-project-algorithms.git.
  • Entre na pasta do repositório que você acabou de clonar:
    • cd sd-017-project-algorithms
  1. Crie o ambiente virtual para o projeto
  • python3 -m venv .venv && source .venv/bin/activate
  1. Instale as dependências
  • python3 -m pip install -r dev-requirements.txt
  1. Crie uma branch a partir da branch master
  • Verifique que você está na branch master
    • Exemplo: git branch
  • Se não estiver, mude para a branch master
    • Exemplo: git checkout master
  • Crie uma branch à qual você vai submeter os commits do seu projeto
    • Você deve criar uma branch no seguinte formato: nome-de-usuario-nome-do-projeto
    • Exemplo: git checkout -b joaozinho-sd-017-project-algorithms
  1. Adicione as mudanças ao stage do Git e faça um commit
  • Verifique que as mudanças ainda não estão no stage
    • Exemplo: git status (deve aparecer listada a pasta joaozinho em vermelho)
  • Adicione o novo arquivo ao stage do Git
    • Exemplo:
      • git add . (adicionando todas as mudanças - que estavam em vermelho - ao stage do Git)
      • git status (deve aparecer listado o arquivo joaozinho/README.md em verde)
  • Faça o commit inicial
    • Exemplo:
      • git commit -m 'iniciando o projeto x' (fazendo o primeiro commit)
      • git status (deve aparecer uma mensagem tipo nothing to commit )
  1. Adicione a sua branch com o novo commit ao repositório remoto
  • Usando o exemplo anterior: git push -u origin joaozinho-sd-017-project-algorithms
  1. Crie um novo Pull Request (PR)
  • Vá até a página de Pull Requests do repositório no GitHub
  • Clique no botão verde "New pull request"
  • Clique na caixa de seleção "Compare" e escolha a sua branch com atenção
  • Coloque um título para a sua Pull Request
    • Exemplo: "Cria tela de busca"
  • Clique no botão verde "Create pull request"
  • Adicione uma descrição para o Pull Request e clique no botão verde "Create pull request"
  • Não se preocupe em preencher mais nada por enquanto!
  • Volte até a página de Pull Requests do repositório e confira que o seu Pull Request está criado
⌨️ Durante o desenvolvimento

  • Faça commits das alterações que você fizer no código regularmente

  • Lembre-se de sempre após um (ou alguns) commits atualizar o repositório remoto

  • Os comandos que você utilizará com mais frequência são:

    1. git status (para verificar o que está em vermelho - fora do stage - e o que está em verde - no stage)
    2. git add (para adicionar arquivos ao stage do Git)
    3. git commit (para criar um commit com os arquivos que estão no stage do Git)
    4. git push -u origin nome-da-branch (para enviar o commit para o repositório remoto na primeira vez que fizer o push de uma nova branch)
    5. git push (para enviar o commit para o repositório remoto após o passo anterior)
🧱 Estrutura do Projeto

Este repositório é composto pela pasta challenges que contém todos os arquivos que você utilizará neste projeto.

Cada arquivo .py, dentro da pasta challenges representa um desafio, ou seja, os arquivos não têm ligação uns com os outros. Logo, os problemas devem ser resolvidos de forma separada.

Este repositório já contém um template com a estrutura de diretórios e arquivos, tanto de código quanto de teste criados. Veja abaixo:

.
├── challenges
│   ├──🔹 challenge_anagrams.py
│   ├──🔹 challenge_find_the_duplicate.py
│   ├──🔹 challenge_palindromes_iterative.py
│   ├──🔹 challenge_palindromes_recursive.py
│   └──🔹 challenge_study_schedule.py
├── tests
│   ├── resultados
│   │   └──🔸 .gitignore
│   ├──🔸 __init__.py
│   ├──🔸 complexities.py
│   ├──🔸 geradores.py
│   ├──🔸 test_anagrams.py
│   ├──🔸 test_find_the_duplicate.py
│   ├──🔸 test_palindromes_iterative.py
│   ├──🔸 test_palindromes_recursive.py
│   └──🔸 test_study_schedule.py
├──🔸 dev-requirements.txt
├──🔸 pyproject.toml
├──🔸 README.md
├──🔸 requirements.txt
├──🔸 setup.cfg
├──🔸 setup.py
├──🔸 trybe-filter-repo.sh
└──🔸 trybe.yml

Legenda:
🔸 Arquivos que não podem ser alterados.
🔹 Arquivos a serem alterados para realizar os requisitos.

Na estrutura deste template, você deve implementar as funções necessárias. Novos arquivos e funções podem ser criados conforme a necessidade da sua implementação, porém não remova arquivos já existentes.

🎛 Linter

Para garantir a qualidade do código, vamos utilizar neste projeto o linter Flake8. Assim o código estará alinhado com as boas práticas de desenvolvimento, sendo mais legível e de fácil manutenção! Para rodá-lo localmente no projeto, execute o comando abaixo:

python3 -m flake8

⚠️ PULL REQUESTS COM ISSUES DE LINTER NÃO SERÃO AVALIADAS. ATENTE-SE PARA RESOLVÊ-LAS ANTES DE FINALIZAR O DESENVOLVIMENTO! ⚠️

🐍 Versão do Python A versão do Python utilizada neste projeto é a 3.10.6.

Não se preocupe: você pode continuar desenvolvendo com versões anteriores que tudo deve funcionar corretamente tanto localmente quanto no avaliador remoto.

Se optar por utilizar a versão 3.10.6 ao invés de versões anteriores, poderá utiliza novas funcionalidades da linguagem durante a resolução dos problemas.

Você pode aprender a controlar as versões do Python instaladas em sua máquina por meio do pyenv.
Para utilizar uma versão específica do Python, você pode utilizar o comando pyenv local 3.x.y para especificar uma versão para um diretório e pyenv global 3.x.y para especificar a versão do sistema inteiro.

🏕️ Ambiente Virtual
O Python oferece um recurso chamado de ambiente virtual que permite sua máquina rodar, sem conflitos, diferentes tipos de projetos com diferentes versões de bibliotecas.
  1. criar o ambiente virtual
$ python3 -m venv .venv
  1. ativar o ambiente virtual
$ source .venv/bin/activate
  1. instalar as dependências no ambiente virtual
$ python3 -m pip install -r dev-requirements.txt

Com o seu ambiente virtual ativo, as dependências serão instaladas neste ambiente. :eyes: Caso precise desativar o ambiente virtual, execute o comando "deactivate". :warning: Lembre-se de ativar novamente quando voltar a trabalhar no projeto.

O arquivo dev-requirements.txt contém todas as dependências que serão utilizadas no projeto, ele está agindo como se fosse um package.json de um projeto Node.js.

🛠 Testes

Para executar os testes certifique-se de que você está com o ambiente virtual ativado.

Executar os testes

$ python3 -m pytest

O arquivo pyproject.toml já configura corretamente o pytest. Entretanto, caso você tenha problemas com isso e queira explicitamente uma saída completa, o comando é:

python3 -m pytest -s -vv

Caso precise executar apenas um arquivo de testes basta executar o comando:

python3 -m pytest tests/nome_do_arquivo.py

Caso precise executar apenas uma função de testes basta executar o comando:

python3 -m pytest -k nome_da_func_de_tests

Se desejar rodar os testes de um arquivo específico, execute com -x nome_do_arquivo

python -m pytest -x tests/test_jobs.py

Para executar um teste específico de um arquivo, basta executar o comando:

python -m pytest -x tests/nome_do_arquivo.py::test_nome_do_teste

Se quiser saber mais sobre a instalação de dependências com pip, veja esse artigo.

Requisitos Obrigatórios

1 - Número de estudantes estudando no mesmo horário (Algoritmo de busca)

Você trabalha na maior empresa de educação do Brasil. Certo dia, a pessoa Product Manager (PM) quer saber qual horário tem a maior quantidade de pessoas estudantes acessando o conteúdo da plataforma. Com esse dado em mãos, a pessoa PM saberá qual é o melhor horário para disponibilizar os materiais de estudo para ter o maior engajamento possível.

O horário de entrada e saída do sistema é cadastrado no banco de dados toda vez que uma pessoa estudante entra e sai do sistema. Esses dados estarão contidos em uma lista de tuplas (permanence_period) em que cada tupla representa o período de permanência de uma pessoa estudante no sistema com seu horário de entrada e de saída.

Seu trabalho é descobrir qual o melhor horário para disponibilizar os conteúdos de estudo. Para isso, utilize a estratégia de resolução de problemas chamada força bruta em que a função desenvolvida por você será chamada várias vezes com valores diferentes para a variável target_time e serão analisados os retornos da função.

👀 De olho na Dica: O melhor horário será aquele no qual o contador retornado pela função for o maior

Clique aqui para ver um exemplo. 
# Nos arrays temos 6 estudantes

# estudante             1       2       3       4       5       6
permanence_period = [(2, 2), (1, 2), (2, 3), (1, 5), (4, 5), (4, 5)]

target_time = 5  # saída: 3, pois a quarta, a quinta e a sexta pessoa estudante ainda estavam estudando nesse horário.
target_time = 4  # saída: 3, pois a quinta e a sexta pessoa estudante começaram a estudar nesse horário e a quarta ainda estava estudando.
target_time = 3  # saída: 2, pois a terceira e a quarta pessoa estudante ainda estavam estudando nesse horário.
target_time = 2  # saída: 4, pois a primeira, a segunda, a terceira e a quarta pessoa estudante estavam estudando nesse horário.
target_time = 1  # saída: 2, pois a segunda e a quarta pessoa estudante estavam estudando nesse horário.

Para esse exemplo, depois de rodar a função para todos esses `target_times`, julgamos que o melhor horário é o `2`, pois esse retornou `4`, já que 4 estudantes estavam presentes nesse horário!

  • Este requisito será testado executando milhares de vezes sobre várias entradas com o tamanho variável. Tais execuções no avaliador irão determinar de maneira empírica, através de cálculos, a complexidade assintótica do seu algoritmo.

    • O tempo de execução do código na sua máquina pode variar em relação ao avaliador, mas o cálculo será feito em cima do comportamento, e não do tempo de execução. Ainda assim, o que vale é o resultado do avaliador, e não o local. Na dúvida, busque ajuda do time de instrução.

  • O algoritmo deve utilizar a solução iterativa;

  • Caso o target_time passado seja nulo, o valor retornado pela função deve ser None (considere o horário 0 como um horário válido);

  • O código deve ser feito dentro do arquivo challenges/challenge_study_schedule.py.

🤖 Clique aqui para ver o que será verificado pelo avaliador.

  • 1.1 - Retorne a quantidade de estudantes presentes para uma entrada específica;

  • 1.2 - Retorne None se em permanence_period houver alguma entrada inválida;

  • 1.3 - Retorne None se target_time recebe um valor vazio;

  • 1.4 - A função deverá, por meio de análise empírica, se comportar (no avaliador remoto em sua Pull Request) como no máximo O(n), ou seja, com complexidade assintótica linear.

2 - Palíndromos (Recursividade)

Escreva uma função que irá determinar se uma palavra é um palíndromo ou não. A função irá receber uma string de parâmetro e o retorno será um booleano, True ou False.

Mas o que é um palíndromo?

Um palíndromo é uma palavra, frase ou número que mantém seu sentido mesmo sendo lido de trás para frente. Por exemplo, "ABCBA".

⚠️ Neste projeto iremos focar somente em palavras palíndromas e não em frases ou números.

Clique aqui para ver um exemplo. 
word = "ANA"
# saída: True

word = "SOCOS"
# saída: True

word = "REVIVER"
# saída: True

word = "COXINHA"
# saída: False

word = "AGUA"
# saída: False

  • O algoritmo deve ser feito utilizando a solução recursiva;

  • Não se preocupe com a análise da complexidade desse algoritmo;

  • Se for passado uma string vazia, retorne False;

  • O código deve ser feito dentro do arquivo challenges/challenge_palindromes_recursive.py.

🤖 Clique aqui para ver o que será verificado pelo avaliador.

  • 2.1 - Retorne True se a palavra passada por parâmetro for um palíndromo;

  • 2.2 - Retorne False se a palavra passada por parâmetro não for um palíndromo;

  • 2.3 - Retorne False se nenhuma palavra for passada por parâmetro.

3 - Anagramas (Algoritmo de ordenação)

Faça um algoritmo que consiga comparar duas strings e identificar se uma é um anagrama da outra. Ou seja, sua função irá receber duas strings de parâmetro e o retorno da função será um booleano, True ou False.

O algoritmo deve considerar letras maiúsculas e minúsculas como iguais durante a comparação das entradas, ou seja, ser case insensitive.

Mas o que é um anagrama?

"Um anagrama é uma espécie de jogo de palavras criado com a reorganização das letras de uma palavra ou expressão para produzir outras palavras ou expressões, utilizando todas as letras originais exatamente uma vez."

Clique aqui para ver um exemplo. 
first_string = "amor"
second_string = "roma"
# saída: True
# Explicação: Nesse caso o retorno da função é True, pois a palavra "roma" é um anagrama de "amor".


first_string = "pedra"
second_string = "perda"
# saída: True
# Explicação: Nesse caso o retorno também é True. Na palavra "pedra", trocamos o "d" de lugar com o "r" e formamos "perda", sendo assim um anagrama.  


first_string = "pato"
second_string = "tapo"
# saída: True


first_string = "Amor"
second_string = "Roma"
# saída: True
# Explicação: Nesse caso o retorno da função é True, pois a palavra "Roma" é um anagrama de "Amor" independente da letra "R" e "A" serem maiúsculas.


# Agora vamos pra um exemplo em que não existe um anagrama
first_string = "coxinha"
second_string = "empada"
# saída: False

  • Este requisito será testado executando milhares de vezes sobre várias entradas com o tamanho variável. Tais execuções no avaliador irão determinar de maneira empírica, através de cálculos, a complexidade assintótica do seu algoritmo.

    • O tempo de execução do código na sua máquina pode variar em relação ao avaliador, mas o cálculo será feito em cima do comportamento, e não do tempo de execução. Ainda assim, o que vale é o resultado do avaliador, e não o local. Na dúvida, busque ajuda do time de instrução;

  • Utilize algoritmos de ordenação para realizar este requisito.

    • Utilize qualquer algoritmo que quiser (Selection sort, Insertion sort, Bubble sort, Merge sort, Quick sort ou TimSort), desde que atinja a complexidade O(n log n).
    • ⚠️ Você deverá implementar sua própria função de ordenação, ou seja, o uso de funções prontas não é permitido.
      • Exemplos de funções não permitidas: sort, sorted e Counter;

  • ⚠️ Não será permitido realizar nenhuma importação neste arquivo!

  • A função retorna True caso uma string seja um anagrama da outra independente se as letras são maiúsculas ou minúsculas;

  • A função retorna False caso uma string não seja um anagrama da outra;

  • O código deve ser feito dentro do arquivo challenges/challenge_anagrams.py.

🤖 Clique aqui para ver o que será verificado pelo avaliador.

  • 3.1 - Retorne True se as palavras passadas por parâmetro forem anagramas;

  • 3.2 - Retorne False se as palavras passadas por parâmetro não forem anagramas;

  • 3.3 - Retorne False se alguma das palavras passadas por parâmetro for uma string vazia;

  • 3.4 - A função deverá, por meio de análise empírica, se comportar (no avaliador remoto em sua Pull Request) como no máximo O(n log n), ou seja, com complexidade assintótica linearítmica.

  • 3.5 - Retorne True se as palavras passadas forem anagramas sem diferenciar maiúsculas e minúsculas.

Requisitos Bônus

4 - Encontrando números repetidos (Algoritmo de busca)

Dada um array de números inteiros contendo n + 1 inteiros, chamado de nums, em que cada inteiro está no intervalo [1, n].

Retorne apenas um número duplicado em nums.

Clique aqui para ver um exemplo. 
nums = [1, 3, 4, 2, 2]
# saída: 2

nums = [3, 1, 3, 4, 2]
# saída: 3

nums = [1, 1]
# saída: 1

nums = [1, 1, 2]
# saída: 1

nums = [3, 1, 2, 4, 6, 5, 7, 7, 7, 8]
# saída: 7

  • Caso não passe nenhum valor ou uma string ou não houver números repetidos retorne False;

  • Este requisito será testado executando milhares de vezes sobre várias entradas com o tamanho variável. Tais execuções no avaliador irão determinar de maneira empírica, através de cálculos, a complexidade assintótica do seu algoritmo.

    • O tempo de execução do código na sua máquina pode variar em relação ao avaliador, mas o cálculo será feito em cima do comportamento, e não do tempo de execução. Ainda assim, o que vale é o resultado do avaliador, e não o local. Na dúvida, busque ajuda do time de instrução;

  • O array montado deve:

    • Ter apenas números inteiros positivos maiores do que 1;

    • Ter apenas um único número repetindo duas ou mais vezes, todos os outros números devem aparecer apenas uma vez;

    • Ter, no mínimo, dois números.

  • O código deve ser feito dentro do arquivo challenge_find_the_duplicate.py.

👀 De olho na Dica: ordene o array.

🤖 Clique aqui para ver o que será verificado pelo avaliador.

  • 4.1 - Retorne o número repetivo se a função receber como parâmetro uma lista com números repetidos;

  • 4.2 - Retorne False se a função não receber nenhum parâmetro;

  • 4.3 - Retorne False se a função receber como parâmetro uma string;

  • 4.4 - Retorne False se a função receber como parâmetro uma lista sem números repetidos;

  • 4.5 - Retorne False se a função receber como parâmetro apenas um valor;

  • 4.6 - Retorne False se a função receber como parâmetro um número negativo;

  • 4.7 - A função deverá, por meio de análise empírica, se comportar (no avaliador remoto em sua Pull Request) como no máximo O(n log n), ou seja, com complexidade assintótica linearítmica.

5 - Palíndromos (Iteratividade)

Resolva o mesmo problema apresentado no requisito 2 - Palíndromos, porém dessa vez utilizando a solução iterativa.

  • Este requisito será testado executando milhares de vezes sobre várias entradas com o tamanho variável. Tais execuções no avaliador irão determinar de maneira empírica, através de cálculos, a complexidade assintótica do seu algoritmo.

    • O tempo de execução do código na sua máquina pode variar em relação ao avaliador, mas o cálculo será feito em cima do comportamento, e não do tempo de execução. Ainda assim, o que vale é o resultado do avaliador, e não o local. Na dúvida, busque ajuda do time de instrução;

  • O algoritmo deve utilizar a solução iterativa;

  • O código deve ser feito dentro do arquivo challenge_palindromes_iterative.py.

🤖 Clique aqui para ver o que será verificado pelo avaliador.

  • 5.1 - Retorne True se a palavra passada como parâmetro for um palíndromo, executando uma função iterativa;

  • 5.2 - Retorne True se a palavra passada como parâmetro for um palíndromo, executando uma função iterativa;

  • 5.3 - Retorne False se nenhuma palavra for passada como parâmetro, executando uma função iterativa ;

  • 5.4 - A função deverá, por meio de análise empírica, se comportar (no avaliador remoto em sua Pull Request) como no máximo O(n), ou seja, com complexidade assintótica linear.