womakerscode/challenges-algorithms

Repositório referente à desafios sobre algoritmos da womakerscode

Algorithm Challenges

Este repositório é mantido pela comunidade WoMakersCode, trazendo uma série de desafios e tutoriais sobre Algoritmos.

❓ Não sabe o que é Git ou Github?

Se você não sabe o que é git ou github recomendamos que leia este artigo e qualquer dúvida você pode perguntar no canal #general do nosso slack.

💻 Desafios disponíveis

Desafio	Resolução	Nível
Soma simples	..	level-100
Tabuada	..	level-100
Verificando se um número é primo	..	level-100
Troca vogal por *	..	level-200
Algoritmo Dijkstras	..	level-400
Maior de três	..	level-100
Posição decimal	..	level-200
Inverta a ordem de uma string	..	level-200
Palíndromo	..	level-300
Simulador de caixa eletrônico	..	level-200
Diferença Absoluta	..	level-300
Escadaria	..	level-100
Soma valores mínimos e máximos	..	level-100
Banco de horas	..	level-200
Encontrar caractere em frase digitada pelo usuário	..	level-200
Enigma	..	level-300
Contador de caracter	..	level-100
Adivinhe o número	..	level-100
Classificar por altura	..	level-200
Array de string longas	..	level-100
Contator de palavras repetidas	..	level-200
Imprima o segundo maior número	..	level-300
Imprima o século do ano	..	level-100
Maior produto de um array	..	level-100
Divisíveis por 2 e 3	..	level-100

📕 Tutoriais disponíveis

Desafio	Nível
Birthday Candles Cake	level-200
Tabuada	level-100
Número primo	level-200
Troca vogal por *	level-100

🤔 Como funciona

Estamos adicionando os desafios na aba issues deste repositório. Todos os desafios estão marcados uma label de nível de dificuldade.

Já os tutoriais, workshops e conteúdos extensos ficam em pastas nesse mesmo repositório. (Ainda aguardando contribuição de tutoriais)

Entendendo as labels de nível

• level-100: básico
• level-200: intermediário
• level-300: avançado
• level-400: expert

Dúvidas frequentes

❓Tenho uma sugestão de desafio, posso colaborar?

1. Claro que pode. Crie uma issue com o seu desafio
2. Faça um Fork desse repositório
3. Adicione o link para a sua issue na tabela acima de Desafios disponíveis
4. Envie um Pull Request:tada:

❓ Não entendi um enunciado, o que eu faço?

1. Você pode interagir nos comentários da issue, enviando a sua dúvida.
2. Entre no nosso slack, acesse o canal #challenge-algorithms e lá tiramos todas as dúvidas referente a esse repositório e auxiliamos no que for possível. Entre no nosso slack clicando aqui

❓ Posso enviar um tutorial? Para enviar um tutorial, siga os seguintes passos:

1. 🍴 Faça uma fork deste repositório
2. 🔨 Siga o guia de contribuição
3. 👥 Adicione o seu perfil na área de pessoas colaboradoras do projeto (contributors)
4. 🔧 Envie um Pull Request
5. 🔧 Solicite a revisão do hacktober-team
6. 🎉 Tenha o seu Pull Request aprovado - sucesso!

Contributors

Laís Lima, Kamila Santos, Ana Beatriz , Ieleny Filgueira, Danielle Farias, Letícia Campos, Carlan Calanzas, Kelly Knoblauch e Thalita Neri

challenges-algorithms's Issues

Diferença Absoluta

Calcule a diferença absoluta entre as somas de duas diagonais de matriz quadrada.
Por exemplo,

1 2 3
 4 5 6
 9 8 9

• A primeira diagonal 1 + 5 + 9 = 15.
• A segunda diagonal 3 + 5 + 9 = 17.
• Sua diferença absoluta é | 15–17 | = 2

Nota: | -x | valor absoluto de x = x
| x | valor absoluto de x = x

• Descrição da função:
  A função Dia retorna um número inteiro inteiro. Representa a diferença diagonal absoluta.
  A função Dia usa o seguinte parâmetro:

arr []: matriz de dimensão única inteira.
n: número inteiro único. Representa a coluna da matriz quadrada e a linha n.

• Formato de entrada:

A primeira linha contém um número inteiro único e a segunda linha contém uma matriz de elementos.

• Formato de saída:
  A diferença diagonal absoluta entre a soma de duas diagonais de matriz quadrada em número inteiro único.
  Entrada de amostra:

1 20 4
50 7 1
0 45 2

• Saída de amostra:
  3
• Explicação:
  A primeira diagonal é:

1 1
    7
         2

A soma da primeira diagonal é: 1 + 7 + 2 = 10
A segunda diagonal é:

         4
    7
0 0

A soma da segunda diagonal é: 4 + 7 + 0 = 11
Diferença Diagonal Absoluta: | 10–11 | = 1

Troca vogal por *

[pt-br] Usuário digita uma palavra ou frase, e programa retorna a mesma com as vogais trocadas por *(asterisco).

Exemplo de entrada

a lenda de zelda

Exemplo de saída

* l*nd* d* z*ld*

Tutorial de como fazer um algoritmo de buble sort

Na linguagem de sua preferência implemente e explique o algoritmo de buble sort

Tabuada de multiplicação

[pt-br] Usuário digita uma número inteiro e programa retorna a tabuada de multiplicação deste.

Exemplo de Entrada

5

Exemplo de saída

5 x 0 = 0
5 x 1 = 5
5 x 2 = 10
5 x 3 = 15
5 x 4 = 20
5 x 5 = 25
5 x 6 = 30
5 x 7 = 35
5 x 8 = 40
5 x 9 = 45
5 x 10 = 50

Divisíveis por 2 e 3

Faça um programa que efetue a leitura de dez números inteiros e apresentar os números que são divisíveis por 2 e 3.

Array de string longas

Dada uma matriz de strings, retorna outra matriz contendo todas as suas strings mais longas.

Para inputArray = ["aba", "aa", "ad", "vcd", "aba"], a saída deve ser
allLongestStrings (inputArray) = ["aba", "vcd", "aba"].

Verificando se um número é primo

[pt-br] Usuário digita um número natural inteiro e programa verifica se esse é número primo.

Exemplos de Entrada

13
2020

Exemplos de saída

É primo!
não é primo

Obs.:

Usar o escopo dos números naturais primos, onde se possui dois divisores naturais distintos: o número um e ele mesmo.

Parque de diversões

Hoje é um dia especial, Graziele, professora de história da turma do 2º ano, levará seus alunos em um parque de diversões de história natural, entretanto, alguns brinquedos tem pré-requisito de altura e sua tarefa é ajudar a professora a organizar as coisas. A professora decidiu agrupar os alunos por alturas semelhantes.Logo, sua entrada será um número inteiro n = Número de alunos, seguido de uma sequência com m números reais que representam suas respectivas alturas. A saída de seu programa de ser o agrupamento de todas as alturas dos alunos.

Exemplo: n = 8
Seqüência: 1.30, 1.53, 1.53, 1.35, 1.50, 1.53, 1.30, 1.30
Saída: 1.30 ocorre 3 vezes
1.53 ocorre 3 vezes
1.35 ocorre 1 vez
1.50 ocorre 1 vez
1.30 ocorre 2 vezes

Escadaria

Considere uma escada de tamanho n = 4:

   #
  ##
 ###
####

Observe que sua base e altura são iguais a n, e a imagem é desenhada usando #símbolos e espaços.
*A última linha não é precedida por nenhum espaço.

Escreva um programa que imprima uma escada de tamanho n.

Descrição da função
Complete uma função que deve imprimir uma escada como descrito acima.
a função deve ter o (s) seguinte (s) parâmetro (s):

• n: um inteiro

Exemplo de entrada

6

Exemplo de saída

     #
    ##
   ###
  ####
 #####
######

Explicação:
A escada é alinhada à direita, composta por #símbolos e espaços, e tem uma altura e largura de n = 6.

[pt-br] Algoritmo Dijkstras

Dado um gráfico e um vértice de origem no gráfico, encontre os caminhos mais curtos da origem para todos os vértices no gráfico fornecido.
O algoritmo de Dijkstra é muito semelhante ao algoritmo de Prim para uma árvore de abrangência mínima. Como o MST de Prim, geramos um SPT (árvore de caminho mais curto) com a origem especificada como raiz. Mantemos dois conjuntos, um conjunto contém vértices incluídos na árvore do caminho mais curto, outro conjunto inclui vértices ainda não incluídos na árvore do caminho mais curto. Em cada etapa do algoritmo, encontramos um vértice que está no outro conjunto (conjunto ainda não incluído) e que possui uma distância mínima da fonte.

Abaixo estão as etapas detalhadas usadas no algoritmo de Dijkstra para encontrar o caminho mais curto de um único vértice de origem até todos os outros vértices no gráfico fornecido.

Algoritmo

1. Crie um conjunto sptSet (conjunto da árvore do caminho mais curto) que rastreie os vértices incluídos na árvore do caminho mais curto, ou seja, cuja distância mínima da origem seja calculada e finalizada. Inicialmente, este conjunto está vazio.
2. Atribua um valor de distância a todos os vértices no gráfico de entrada. Inicialize todos os valores de distância como INFINITE. Atribua o valor da distância como 0 ao vértice de origem, para que seja escolhido primeiro.
3. Embora o sptSet não inclua todos os vértices
   … .A) Escolha um vértice u que não esteja no sptSet e tenha um valor mínimo de distância.
   … .B) Inclua u no sptSet.
   … .C) Atualize o valor da distância de todos os vértices adjacentes de u. Para atualizar os valores da distância, itere através de todos os vértices adjacentes. Para cada vértice adjacente v, se a soma do valor da distância de u (da fonte) e o peso da aresta u-v for menor que o valor da distância de v, atualize o valor da distância de v.

Vamos entender com a imagem de exemplo abaixo

O conjunto sptSet está inicialmente vazio e as distâncias atribuídas aos vértices são {0, INF, INF, INF, INF, INF, INF, INF, INF} em que INF indica infinito. Agora escolha o vértice com o valor mínimo de distância. O vértice 0 é escolhido, inclua-o no sptSet. Então sptSet se torna {0}. Depois de incluir 0 no sptSet, atualize os valores de distância de seus vértices adjacentes. Os vértices adjacentes de 0 são 1 e 7. Os valores de distância de 1 e 7 são atualizados como 4 e 8. O subgráfico a seguir mostra vértices e seus valores de distância, apenas os vértices com valores de distância finita são mostrados. Os vértices incluídos no SPT são mostrados na cor verde.

Pick the vertex with minimum distance value and not already included in SPT (not in sptSET). The vertex 1 is picked and added to sptSet. So sptSet now becomes {0, 1}. Update the distance values of adjacent vertices of 1. The distance value of vertex 2 becomes 12.

Escolha o vértice com o valor da distância mínima e ainda não esteja incluído no SPT (não no sptSET). O vértice 7 é escolhido. Então, o sptSet agora se torna {0, 1, 7}. Atualize os valores da distância dos vértices adjacentes de 7. O valor da distância do vértice 6 e 8 torna-se finito (15 e 9, respectivamente).

Escolha o vértice com o valor da distância mínima e ainda não esteja incluído no SPT (não no sptSET). O vértice 6 é escolhido. Então, o sptSet agora se torna {0, 1, 7, 6}. Atualize os valores da distância dos vértices adjacentes de 6. Os valores da distância dos vértices 5 e 8 são atualizados.

Repetimos as etapas acima até que o sptSet inclua todos os vértices do gráfico fornecido. Finalmente, obtemos a seguinte Árvore de caminho mais curto (SPT).

TIP
Você pode uma uma matriz booleana sptSet [] para representar o conjunto de vértices incluídos no SPT. E se um valor sptSet [v] for verdadeiro, o vértice v será incluído no SPT, caso contrário não. A matriz dist [] é usada para armazenar os menores valores de distância de todos os vértices.

Qualquer dúvida entre no slack da womakerscode e vamos discutir a solução! Eu resolvi com Java!

Vídeo com explicação e resolução, ta em inglês: https://www.youtube.com/watch?v=_lHSawdgXpI

Tutorial de como fazer um algoritmo de binarySearch

Na linguagem de sua preferência implemente e explique o algoritmo de binary search

Banco de horas

A jornada de trabalho semanal de um funcionário é de 40 horas. O funcionário que trabalhar mais
de 40 horas receberá hora extra, cujo cálculo é o valor da hora regular com um acréscimo de 50%.
Escreva um algoritmo que leia o número de horas trabalhadas em um mês, o salário por hora e escreva
o salário total do funcionário, que deverá ser acrescido das horas extras, caso tenham sido trabalhadas
(considere que o mês possua 4 semanas exatas).

Maior de três

[pt-br] Usuário informa 3 números inteiros e programa retorna o maior e o menor deles.

Exemplo de entrada

11, 12, 13
22, 22, 22
32, 33, 33

Exemplo de saída

maior: 13, menor: 11;
números iguais;
maior: 33, menor: 32

Simulador de caixa eletrônico

Usuário informa o valor que deseja sacar.
O programa retorna quantas cédulas de cada valor serão entregues.
O caixa possui cédulas de 50, 20, 10, 5 e 1.

Exemplo de entrada

187

Exemplo de saída

3 cédulas de 50
1 cédulas de 20
1 cédulas de 10
1 cédulas de 5
2 cédulas de 1

Posição decimal

[pt-br] Usuário informa um número inteiro entre 0 e 9999 e programa retorna a posição decimal de cada algarismo; unidade, dezena, centena, etc.

Exemplo de entrada

2158

Exemplo de saída

Unidade: 8
Dezena: 5
Centena: 1
Unidade de Milhar: 2

Enigma

ENIGMA

Durante a Segunda Grande Guerra Mundial, os Aliados conseguiram interceptar grande parte das comunicações dos países do Eixo, porém estas mensagens viam criptografadas utilizando um dispositivo alemão conhecido como ENIGMA. Esta máquina era semelhante a uma máquina de escrever, porém as teclas eram ajustadas por 12 rotores internos. Sendo assim para descobrir o conteúdo das mensagens criptografadas deveria se configurar cada um destes rotores em determinada posição para que quando a mensagem fosse datilografada na ENIGMA, esta fizesse sentido.

Os aliados trabalharam por anos tentando quebrar a criptografia da ENIGMA até que em 1944 uma equipe de matemáticos criou uma máquina capaz de quebrar o código da ENIGMA. Porém esta máquina exigia uma complexa configuração e demorava uma quantidade de tempo para se ajustar e executar a quebra das mensagens em definitivo.

Com o passar do tempo os matemáticos chegaram a três configurações básicas, onde para cada configuração era exigido um tempo de ajuste das configurações. A Configuração A demorava 60 minutos para ser ajustada, a Configuração B demorava 40 minutos e a Configuração C demorava 20 minutos.

Entretanto para cada configuração ajustada, a Máquina tem um tempo para quebrar o código, sendo que para isso cada um dos rotores deveria ser “quebrado” individualmente. Infelizmente cada configuração quebra apenas um número de rotores da ENIGMA de cada vez, sendo que após as quebras dos rotores a Máquina deve ser reajustada (considerar novamente tempo de ajuste) para que volte a continuar a quebrar os códigos até que todos os rotores da ENIGMA tenham sido quebrados. Considere que a Configuração A quebra 6 rotores por ajuste, a Configuração B 2 rotores por ajuste e a Configuração C 6 rotores
Após a quebra de todos os rotores ainda sim é necessário um processo intermediário para a quebra das mensagens propriamente ditas. Este processo é realizado nas mensagens que são interceptadas e ele demora um tempo diferenciado para cada configuração. Na realidade este processo irá definir, após a quebra da ENIGMA, quantas mensagens serão quebradas por minuto pela máquina. Chegamos então aos seguintes valores, a Configuração A, irá conseguir quebrar 1 mensagem a cada 5 minutos, a Configuração B quebrará 1 mensagem por minuto e na Configuração C chega a marca de 1 mensagem a cada 30 minutos.
Como nem tudo é fácil na guerra os países do Eixo têm um protocolo onde a mensagem inicial que gera a chave da ENIGMA é modificada de tempos em tempos. Graças aos serviços de inteligência dos Aliados a informação do tempo de validade das chaves são conhecidas. Sendo assim todos os dias os Aliados interceptam as mensagens e tem em mãos o tempo de validade da chave da ENIGMA.

Objetivo do desafio é:

1. Construir um algoritmo que receba o tempo de validade da Chave da ENIGMA (em minutos) e indique qual configuração A, B ou C que quebra a maior quantidade de mensagens até o final da validade da Chave. Informar a configuração que possuir melhor desempenho em um ciclo de chave único (1 período de validade) considerando que são interceptadas pelos Aliados, 1 mensagem por minuto.

2. Indicar qual é a melhor configuração a ser realizada para se receber mensagens decodificadas no menor tempo possível?

3. No caso de os países do Eixo descobrirem sobre a Máquina de decodificação aliada e suas configurações. Qual seria o tempo mínimo de troca de chaves que deveriam utilizar para que os Aliados não conseguissem decodificar nenhuma mensagem?

Contador de caracter

Dada uma string ou texto e um caracter, conte a quantidade de vezes que este caracter aparece nesta string.

Exemplo:

String

“hacktoberfest”

Caracter

“e”

Resultado

2

Inverta a ordem de uma string

Dada uma string ou texto, inverta a sua ordem.

Descrição da Função
A função deve ser capaz de receber uma string e retornar o seu valor invertido.

Exemplos de Entrada
"WoMakersCode"
"Wo Makers Code"
"A mae te ama"

Exemplos de Saída
edoCsrekaMoW
edoC srekaM oW
ama et eam A

Contator de palavras repetidas

Faça um função que retorne a qualidade de palavras repetidas em um frase

Exemplo:

• Frase: "Eu sou muito alto e muito magro"
• Retorno: { "EU": 1, "SOU": 1, "MUITO": 2, "E": 1, "ALT0": 1, "MAGRO": 1 }

Dicas:

• Transforme a string em uma array

Imprima o século do ano

Dado um ano, retorne o século em que ele se encontra. O primeiro século se estende do ano 1 até e incluindo o ano 100, o segundo - do ano 101 até e incluindo o ano 200, etc.

Exemplo:

• Para o year=1995, a produção deve ser
  centuryFromYear (year) = 20;

• Para o year=1700, a produção deve ser
  centuryFromYear (year) = 18;

Desafio de recursividade

Faça uma função recursiva que exiba os 7 primeiros números da sequência Fibonacci:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55

Dicas:

• A sequência começa com os números 1, 1
• O próximo número, ou seja, o terceiro é igual a soma dos dois número anteriores. Cada número novo será a soma dos dois números anteriores

Tutorial de como fazer um algoritmo de Insertion sort

Na linguagem de sua preferência implemente e explique o algoritmo de insertion sort

Maior produto de um array

Dada uma matriz de inteiros, encontre o par de elementos adjacentes que possui o maior produto(multiplicação) e retorne esse produto.

Exemplo:

ParainputArray = [3, 6, -2, -5, 7, 3], a saída deve ser
adjacentElementsProduct(inputArray) = 21

7 e 3 produzem o maior produto.

Validador de CPF

Dado um número de CPF, o algoritmo deve validar se o número dado é um número válido.
Detalhes de como o cálculo funciona pode ser encontrado aqui

Descrição da Função
A função deve ser capaz de receber o CPF como Integer ou String.

Se for String, deve retirar pontos para manter somente os números.

Em seguida, deve fazer os cálculos da validação e retornar true se o número passado for válido ou false se for invalido.

Como opção, a função pode também excluir sequências de números que são conhecidamente inválidos antes de começar os cálculos

Exemplo de Entrada
"108.305.810-06"

Exemplo de Saída
true

Verifique o SEGUNDO maior número utilizando um laço de repetição

Percorra uma lista em qualquer linguagem, imprimindo na tela o segundo maior número dessa lista.

Exemplo: let lista= [2, 4, 6, 8, 10].

O segundo maior número é 8.

Se você precisar de um start, aqui vai uma ajudinha de como achar o maior.

let comparador = 0

for (let numero of lista){
if (numero>comparador){
comparador = numero
}

console.log(comparador)

Problem: SumOfArray

def simpleArraySum(a):
    return sum(a)

Hopefully this counts as a contribution for Hacktober2022 ✨

Banco de horas

A jornada de trabalho semanal de um funcionário é de 40 horas. O funcionário que trabalhar mais
de 40 horas receberá hora extra, cujo cálculo é o valor da hora regular com um acréscimo de 50%.
Escreva um algoritmo que leia o número de horas trabalhadas em um mês, o salário por hora e escreva
o salário total do funcionário, que deverá ser acrescido das horas extras, caso tenham sido trabalhadas
(considere que o mês possua 4 semanas exatas).

Soma /Sum

[pt-br] Dada uma matriz de números inteiros, encontre a soma de seus elementos.

Por exemplo, se a matriz ar = [1, 2, 3], 1 + 2 + 3 = 6, então retorna 6

Descrição da função

Complete uma função que deve retornar a soma dos elementos da matriz como um número inteiro.
simpleArraySum possui o(s) seguinte(s) parâmetro(s):

• ar: uma matriz de números inteiros

Exemplo de Entrada

6
1 2 3 4 10 11

Exemplo de saída
31

...

[en-us] Given an array of integers, find the sum of its elements.

For example, if the matrix ar = [1, 2, 3], 1 + 2 + 3 = 6, then returns 6

Description of function

Complete a function that should return the sum of the matrix elements as an integer.
simpleArraySum has the following parameter (s):

• ar: an array of integers

Entry example

6
1 2 3 4 10 11

Example output
31

Palíndromo

[pt-br] Usuário informa uma palavra ou frase e programa retorna se é palíndromo.

Exemplo de entrada

luz azul
reviver
buraco negro

Exemplo de saída

É um palíndromo!
É um palíndromo!
não é palíndromo

Soma valores mínimos e máximos

Dados cinco números inteiros positivos, encontre os valores mínimo e máximo que podem ser calculados somando exatamente quatro dos cinco números inteiros. Em seguida, imprima os respectivos valores mínimos e máximos como uma única linha de dois inteiros longos separados por espaço.

Por exemplo, se a matriz arr = [1,3,5,7,9], então a soma mínima é 1 + 3 + 5 + 7 = 16 e nossa soma máxima é 3 + 5 + 7 + 9 = 24, então retorna 16 24

Descrição da função

Complete uma função que deve imprimir dois números inteiros separados por espaço em uma linha: a soma mínima e a soma máxima de 4 dos 5 elementos. A função deve ter o (s) seguinte (s) parâmetro (s):

• arr : uma matriz 5 de inteiros

Exemplo de entrada

1 2 3 4 5

Exemplo de saída

10 14

Encontrar caractere em frase digitada pelo usuário

Escreva uma rotina que faz a leitura de uma frase e um caractere, a rotina deve escrever as posições do caractere digitado na frase informada.

Adivinhe o número

Escreva um programa que escolhe um número aleatório inteiro entre 0 e 100. O usuário deve sugerir um número, se ele acertar, o computador mostra quantas tentativas foram feitas, caso ele não acerte o número, o computador deve dizer se o número aleatório é maior ou menor que o número sugerido e permitir que o usuário faça até 10 sugestões.

Classificar por altura

Algumas pessoas estão em uma fila no parque. Existem árvores entre eles que não podem ser movidas. Sua tarefa é reorganizar as pessoas por suas alturas em uma ordem não decrescente, sem mover as árvores. As pessoas podem ser muito altas!

Para a = [-1, 150, 190, 170, -1, -1, 160, 180], a saída deve ser
sortByHeight (a) = [-1, 150, 160, 170, -1, -1, 180, 190].