Exercício-Programa 1: A Silhueta de um Conjunto de Edifícios
Considere um conjunto de retângulos cujas bases estão todas sobre uma mesma
reta. O lado esquerdo da figura abaixo mostra um conjunto de retângulos com essa
propriedade. Imagine que esse conjunto é uma vista bidimensional de uma parte de
uma cidade e que cada retângulo representa um edifício. A silhueta do conjunto
de edifícios é o contorno superior da coleção de retângulos. O lado direito da
figura abaixo mostra a silhueta do conjunto de edifícios apresentado no lado
esquerdo.
Neste exercício-programa você usará a linguagem Erlang para escrever um programa
que faz duas coisas:
- determina eficientemente a silhueta de um conjunto de edifícios;
- cria uma imagem com essa silhueta.
Edifícios e silhuetas
Definições.
- Um edifício é uma tripla (e, a, d), onde e e
d denotam as coordenadas horizontais esquerda e direita do edifício,
respectivamente, e a denota a altura do edifício.
- Uma silhueta é uma sequência de inteiros não-negativos
(c0, a1, c1,
a2, c2, ...,
an, cn),
onde os valores de ci representam as coordenadas
horizontais em ordem crescente e cada ai
representa a altura que liga as coordenadas
ci-1
e ci.
Exemplo.
O conjunto de edifícios da figura acima é dado pelas triplas
(1, 11, 5), (2, 6, 7), (3, 13, 9), (12, 7, 16), (14, 3, 25), (19, 18, 22), (23, 13, 29) e (24, 4, 28).
A silhueta desse conjunto é a seguinte sequência:
(1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29).
Obs.: Nesse exemplo as triplas aparecem ordenadas pela coordenada horizontal
esquerda apenas para facilitar a visualização da correspondência entre as
triplas e os retângulos da figura acima. As triplas de um conjunto de
edifícios não precisam aparecer em nenhuma ordem específica. Numa silhueta,
entretanto, as coordenadas horizontais devem estar em ordem crescente.
Considere os dois algoritmos descritos brevemente abaixo. Cada um deles
determina a silhueta de um conjunto de m edifícios.
- Algoritmo 1
- Depois de determinar recursivamente a silhueta de um subconjunto com
m-1 edifícios do conjunto original, determine a união dessa
silhueta com a edifício que ficou fora do subconjunto.
- Algoritmo 2
- Particione o conjunto de edifícios em duas "metades", determine
recursivamente a silhueta para cada uma das "metades", e determine a
união das duas silhuetas obtidas.
Seu programa deve implementar esses dois algoritmos. Note que ambos usam um
algoritmo que determina a união de duas silhuetas dadas. É esse o algoritmo
fundamental do seu programa.
Além de determinar a silhueta de um conjunto de edifícios, seu programa deve
também criar um arquivo de imagem para a visualização dessa silhueta.
A união de duas silhuetas.
Considere, por exemplo, as silhuetas
(3, 6, 7, 2, 8, 9, 12, 4, 16, 17, 19, 14, 22, 9, 27)
e
(5, 4, 9, 13, 14, 6, 18, 16, 20, 11, 23, 5, 25).
A parte esquerda da figura abaixo mostra essas duas silhuetas. A primeira
está desenhada com linhas contínuas e a segunda com linhas tracejadas.
A união dessas silhuetas é a silhueta
(3, 6, 7, 4, 8, 9, 9, 13, 14, 6, 16, 17, 19, 16, 20, 14, 22, 11, 23, 9, 27).
Essa silhueta está na parte direita da figura abaixo.
Sobre a implementação
Módulo. Seu programa deve estar contido num módulo chamado
silhueta
. A função principal do programa (que tem de ser exportada
pelo módulo silhueta
) deve se chamar main
:
main(ArgList) ->
.
. % implementação da função principal
.
init:stop().
Tipos.
Para representar cada edifício, seu programa deve usar uma tripla (tupla com
três campos) {Esq, Alt, Dir}
, cujos campos contém respectvamente
a coordenada horizontal esquerda, a altura e a coordenada horizontal direita
do edifício.
Faça seu programa armazenar o conjunto de edifícios numa lista. Em outras
palavras, use o tipo list
em vez do tipo set
. Dessa
forma seu código poderá aproveitar melhor as facilidades de casamento de
padrões de Erlang, que são muito adequadas para o processamento de listas.
Seu programa deve representar uma silhueta como uma lista cujos elementos são
pares (tuplas com dois campos) {X, H}
, cujos campos contém
respectivamente a coordenada horizontal e a altura do elemento da silhueta.
Na lista de pares que representa uma silhueta, os elementos da silhueta devem
aparecer em ordem crescente da coordenada X
. O último elemento
dessa lista deve ter H
igual a zero.
Funções.
Implemente em seu programa, obrigatoriamente, as seguintes funções:
algoritmo1(ListaDeTriplas) -> ListaDePares
algoritmo2(ListaDeTriplas) -> ListaDePares
Essas duas funções implementam, respectivamente, os dois algoritmos de
determinação de silhueta já descritos. Cada
uma delas recebe um conjunto (lista) de edifícios, determina a silhueta
desse conjunto a devolve como valor da função.
Obs.: A implementação do algoritmo 1 deve usar recursão de cauda.
silhueta_com_foldl(ListaDeTriplas) -> ListaDePares
silhueta_com_foldr(ListaDeTriplas) -> ListaDePares
Essas duas funções são implementações alternativas da idéia básica
do algoritmo 1. Elas empregam, respectivamente, as funções de ordem
superior foldl/3
(fold
left) e foldr/3
(fold
left), ambas do módulo lists
.
O corpo de cada uma delas deve conter apenas uma linha.
uniao(ListaDePares1, ListaDePares2) -> ListaDePares3
Recebe duas silhuetas, determina a união dessas silhuetas e a devolve
como valor da função.
Obs.: Esta função deve ser implementada de modo eficiente,
ou seja, ela deve percorrer apenas uma vez as listas recebidas.
Além disso, ela deve usar recursão de cauda.
silhueta_de_edificio(Tripla) -> ListaDePares
Devolve a silhueta do edifício Tripla
. O número de pares
da lista devolvida é sempre igual a 2.
As funções algoritmo1
, algoritmo2
e
uniao
devem empregar casamento de padrões.
Formato PGM.
Seu programa utilizará o formato PGM (Portable Gray Map) para
armazenar imagens em arquivos. Um arquivo nesse formato deve
conter um cabeçalho e uma matriz com um elemento para cada ponto
(pixel) da imagem. Este é um exemplo de arquivo PGM:
P2
5 4
16
9 4 5 0 8
10 3 2 1 7
9 1 6 3 15
1 16 9 12 7
O texto acima é o conteúdo de um arquivo PGM. As três primeiras linhas formam
o cabeçalho do arquivo. A primeira linha contém a palavra-chave
"P2
", que é obrigatória. A segunda linha contém o número de
colunas e o número de linhas da matriz, nessa ordem. (Note que o número de
colunas aparece primeiro.) A terceira linha do arquivo contém o inteiro
positivo maxval, que representa a cor branca.
O restante do arquivo é uma matriz de inteiros que contém os tons de cinza dos
pontos da imagem. Cada tom de cinza é um número entre 0 e maxval, com
0 indicando "negro" e maxval indicando "branco".
Matrizes.
A biblioteca de Erlang tem uma implementação eficiente de vetores
unidimensionais imutáveis (no módulo array
) mas
não tem matrizes bidimensionais. Para implementar uma matriz, a abordagem
usual é empregar um vetor unidimensional com a "linearização da matriz". Este módulo usa essa abordagem. Ele contém uma
implementação bem simples de matrizes bidimensionais imutáveis. Fique à vontade
para usá-lo e para melhorá-lo. (A implementação de matrizes bidimensionais pode
ficar num módulo separado, não é necessário colocá-la dentro do módulo
silhueta
.)
Funções adicionais.
Seu programa deve implementar, ainda, estas duas funções:
gera_imagem(ListaDePares, String) -> true
Recebe uma silhueta ListaDePares
, converte-a para uma
imagem no formato PGM, e guarda essa imagem no arquivo cujo nome é
String
. As imagens geradas por essa função têm tamanho fixo
de n_lins()
pontos na direção vertical e
n_cols()
pontos na horizontal, com uma distância de
margem_inf()
pontos entre o eixo base da silhueta (o eixo
horizontal) e a borda horizontal inferior da imagem. A função
gera_imagem
supõe que as coordenadas horizontais da
silhueta s
estão no intervalo de 0 a
n_cols()-1
e que as alturas dessa silhueta são menores que
n_lins()-margem_inf()
.
Essa função trabalha com matrizes bidimensionais de n_lins()
linhas e n_cols()
colunas. Ela gera uma imagem fazendo uma
série de chamadas à função
preenche_retangulo/6
para preencher a matriz, e depois grava
essa matriz no arquivo String
, precedida do cabeçalho
adequado. O preenchimento da matriz é feito de modo que os pontos no
eixo base da silhueta tenham cor negra, os pontos da silhueta e os
compreendidos entre a silhueta e o eixo base tenham cor cinza, e todos
os demais pontos tenham cor branca.
Use no seu programa as seguintes definições (note que constantes são
implementadas como funções sem argumentos):
n_lins() -> 600. % número de linhas da imagem
n_cols() -> 800. % número de colunas da imagem
borda_inf() -> n_lins() - 1. % borda inferior (última linha da imagem)
margem_inf() -> 20. % linhas do eixo base à borda inferior da imagem
base() -> borda_inf() - margem_inf(). % linha do eixo base
branco() -> 15. % valor de maxval
cinza() -> 10. % cor da silhueta preenchida
preto() -> 0. % cor do eixo base
preenche_retangulo(Matriz, Lin1, Lin2, Col1, Col2, Valor) -> Matriz1
Recebe uma Matriz
, dois índices de linha
tais que
0 ≤ Lin1
≤ Lin2
,
dois índices de coluna tais que
0 ≤ Col1
≤ Col2
, e
um Valor
. A função devolve uma matriz Matriz1
,
obtida a partir da Matriz
original preenchendo-se
com o Valor
a submatriz retangular de Matriz
delimitada por Lin1
, Lin2
, Col1
e
Col2
.
Sobre os arquivos de entrada e de saída
Formato da entrada.
Os dados devem ser lidos de um arquivo com o seguinte formato:
- A primeira linha do arquivo contém o número de edifícios
m.
- Cada uma das próximas m linhas contém uma tripla que representa
um edifício.
Este é um exemplo de arquivo de entrada correspondente ao conjunto de
edifícios mostrado no lado esquerdo da primeira figura acima:
8
12 7 16
2 6 7
1 11 5
24 4 28
3 13 9
19 18 22
23 13 29
14 3 25
Arquivo de saída com a silhueta.
Seu programa deve gerar um arquivo com a sequência de pares que
representa a silhueta obtida.
- A primeira linha desse arquivo deve conter o número de elementos
da silhueta.
- Cada uma das demais linhas contém um par que representa um elemento
da silhueta.
Este é o arquivo de saída com a silhueta correspondente ao conjunto de
edifícios do arquivo de entrada acima:
9
1 11
3 13
9 0
12 7
16 3
19 18
22 3
23 13
29 0
Exemplos de imagens criadas por uma solução do EP1. Os
exemplos abaixo foram usados na disciplina MAC0122 para BE/BM/BMA.
Cada um deles inclui um arquivo de entrada com um conjunto de edifícios,
um arquivo de saída com a silhueta desse conjunto de edifícios, e um arquivo
com a imagem dessa silhueta. Use esses exemplos para testar seu programa!
Argumentos na linha de comando
Seu programa deve tratar os seguintes argumentos na linha de comando:
erl -noshell -s silhueta main [alg] [arq-entrada] [arq-silhueta] [arq-imagem]
(A linha de comando acima pressupõe que a função principal do programa é
silhueta:main/1
.)
Os argumentos aceitos pelo programa têm estes significados:
- O argumento
alg
especifica o algoritmo que será usado para
determinação da silhueta. Os valores possíveis desse argumento são
1
, 2
, L
, R
. Os
últimos dois valores especificam respectivamente a
determinação da silhueta com fold left e a determinação da
silhueta com fold right.
- O argumento
arq-entrada
é o nome do arquivo de
entrada.
- O argumento
arq-silhueta
é o nome do arquivo de saída
com a silhueta.
- O argumento
arq-imagem
é o nome do arquivo PGM.
Exemplo:
erl -noshell -s silhueta main 1 entrada.txt silhueta.txt silhueta.pgm
O tratamento dado a cada argumento é determinado pela posição do argumento
na linha de comando. O primeiro argumento é o alg
,
o segundo é o arq-entrada
, etc. Podem ser omitidas as
seguintes combinações de argumentos:
- Se o último argumento for omitido, o programa não criará um arquivo
PGM.
- Se os dois últimos argumentos forem omitidos, o programa escreverá a
silhueta na saída padrão e não criará um arquivo PGM.
- Se os três últimos argumentos forem omitidos, o programa lerá da
entrada padrão o conjunto de edifícios, escreverá a silhueta na saída
padrão e não criará um arquivo PGM.
- Se todos os quatro argumentos forem omitidos, o programa usará o
algoritmo 2, lerá da entrada padrão o conjunto de edifícios, escreverá a
silhueta na saída padrão e não criará um arquivo PGM.
Observações
- Além das funções especificadas neste enunciado, fique à vontade para
criar outras. Para usar recursão de cauda, por exemplo, você precisará de
funções auxiliares, com parâmetros adicionais (acumuladores).
- Use a biblioteca de
Erlang! Além das funções
lists:foldl/3
e lists:foldr/3
,
vale a pena olhar as funções lists:split/2
,
lists:splitwith/2
,
lists:foreach/2
,
lists:reverse/1
,
io:get_line/1
,
io:format/2
,
file:open/2
,
file:close/1
e init:stop/0
.
FAQ
Questão 1: Pode fazer em grupo?
Resposta: Este trabalho deve ser feito em grupos de uma ou duas
pessoas.
Questão 2: Pode haver grupo com mais de duas pessoas?
Resposta: Não.
Questão 3: O que exatamente deve ser entregue?
Resposta: Veja abaixo o ítem "Entrega".
Entrega
Este trabalho deve ser entregue até o dia 11/09, por meio do sistema Paca/Moodle.
Entregue um arquivo tar.gz ou zip que satisfaça os seguintes requisitos:
- O nome do arquivo deve ser da forma
ep1-
<nomes-dos-membros-do-grupo>.tar.gz
ou
ep1-
<nomes-dos-membros-do-grupo>.zip
.
Por exemplo:
ep1-joao-maria.zip
. No nome do arquivo devem ser
omitidos os acentos dos nomes dos
membros do grupo. Além disso, a separação entre
palavras não deve ser feita com espaços. Ou seja,
o arquivo não deve se chamar "ep1-joão-maria.tar.gz
"
nem "ep1 joao maria.tar.gz
".
- O desempacotamento do arquivo tar.gz ou zip deve produzir um
diretório com o mesmo nome do arquivo, menos o sufixo .tar.gz ou
zip. (Exemplo:
ep1-joao-maria
.) Todos os arquivos
desempacotados devem estar dentro desse diretório.
- O diretório desempacotado deve conter:
- Os arquivos fonte (
.erl
) do seu programa.
- Um
makefile
que automatiza a geração do programa.
- Um arquivo
README
, com as todas as informações que
você julgar necessárias ou relevantes para a correção do seu
trabalho. O arquivo README
deve ser um arquivo de
texto puro (ASCII) ou um arquivo pdf. (Não quero arquivos doc em
formato MS-Word.)
Last modified: Sun Aug 21 17:05:45 BRT 2011