Submissões no período de 06 a 12 de julho só serão computadas para alun*s em recuperação de Média dos Laboratórios.
Você certamente já recebeu recomendação de novos amigos em redes sociais. A implementação desta funcionalidade muitas vezes estará baseada na suposição de que se dois usuários têm um ou mais amigos em comum em alguma rede, eles provavelmente também se conhecem pessoalmente ou via outras plataformas.
Nesta tarefa, iremos usar dicionários e os outros conceitos aprendidos na disciplina para, a partir de uma lista de usuários e amizades, calcularmos os amigos em comum para todos os pares de usuários na rede.
A primeira parte da entrada conterá os nomes dos
usuários, com um nome por linha. Esta lista será
encerrada pelos caracteres --.
Gabriel
Beatriz
Guilherme
--A segunda parte da entrada conterá pares de nomes que
indicarão as relações de amizade. Note que um
par <usuarioa> <usuariob>
indica que <usuarioa> é amigo de
<usuariob> e
que <usuariob> é amigo
de <usuarioa>, não sendo
necessário registrar a amizade duas vezes. A lista de pares
também será encerrada pelos
caracteres --.
Gabriel Beatriz
Beatriz Guilherme
--Você pode supor que não haverá repetição nos nomes na primeira parte da entrada e nem nas amizades. Além disso, todos os nomes que aparecem nas amizades foram apresentados na lista de usuários.
Apesar de a saída ter regras bem definidas de ordenação, os nomes dos usuários e as amizades na entrada não se encontram ordenados.
Para cada par de usuários na rede será apresentada a lista de amigos em comum entre eles no seguinte formato:
<usuarioa1> <usuariob1> : <amigo1>, <amigo2>, ..., <amigon>
Os pares serão listados em ordem alfabética
de <usuarioai>. Além
disso, para todo
par <usuarioai> <usuariobi>, <usuarioai>
deve preceder <usuariobi> na
ordem alfabética. Finalmente, a lista de amigos em comum
também deve estar em ordem alfabética.
Para o exemplo da seção anterior, a saída será:
Beatriz Gabriel :
Beatriz Guilherme :
Gabriel Guilherme : Beatriz
Note que quando a lista de amigos em comum for vazia a linha a ser
impressa deve terminar pelo sinal :, sem espaços
em branco extras.
Beatriz Gabriel :
Beatriz Guilherme :
Gabriel Guilherme : BeatrizEsta tarefa terá 8 testes abertos e 2 testes fechados. Veja
na tabela abaixo os testes 02, 03 e 05 e seus respectivos
resultados. Consulte os outros testes e resultados no
link Testes
para a tarefa 11 de mc102 ou no
arquivo aux11.zip
| arq02.in | arq02.res |
|---|---|
|
|
| arq03.in | arq03.res |
|
|
| arq05.in | arq05.res |
|
|
Releia, se necessário, as instruções para fazer os testes em Testes com o SuSy.
Você pode utilizar dicionários para montar a lista de amigos de um usuário enquanto vai lendo os pares de nomes que indicam as amizades.
Utilize o comando sorted ou a
função sort para obter uma lista
ordenada. O comando sorted() irá retornar uma
nova lista com elementos ordenados, sem alterar a lista original. Uma
chamada l.sort() irá ordenar a lista l. Veja os exemplos abaixo:
>>> l = [3, 5, 2]
>>> sorted(l)
[2, 3, 5]
>>> l
[3, 5, 2]
>>> l.sort()
>>> l
[2, 3, 5]
É bastante simples codificar a
intersecção de duas listas para encontrar os amigos em
comum entre dois usuários. No entanto, se tiver interesse em
aprender mais sobre estruturas de dados em Python, você pode
utilizar sets,
que são coleções não ordenadas sem
repetição que permitem operações
matemáticas de união e intersecção,
entre outras. Você pode obter uma lista ordenada a partir de
um set s utilizando sorted(s).
Veja aqui a
página de submissão da tarefa. O arquivo a ser
submetido deve se chamar lab11.py. No
link Arquivos
auxiliares há um
arquivo aux11.zip que
contém todos os arquivos de testes abertos e seus respectivos
resultados compactados.
O limite máximo será de 30 submissões. Serão considerados os resultados da última submissão.
O peso desta tarefa é 4.
O prazo final para submissão é 28/06/2020.
A nota desta tarefa é proporcional ao número de testes que executaram corretamente, desde que o código esteja coerente com o enunciado. A submissão de um código que não implementa o algoritmo requisitado, mas que exibe as saídas esperadas dos testes abertos a partir da comparação de trechos da entrada será considerada fraude e acarretará a atribuição de nota zero à média final da disciplina.
Os nomes utilizados nos exemplos foram selecionados aleatoriamente dentre os nomes não acentuados da lista de alunos matriculados nas turmas de MC102. Qualquer semelhança com amizades reais terá sido mera coincidência.
A imagem que ilustra esta tarefa foi obtida em kindpng.