Exercício-Programa 2: A Silhueta de um Conjunto de Edifícios
Programação Funcional Contemporânea - Segundo Semestre de 2009
[Este EP é uma adaptação do EP2 da disciplina MAC0122 (para BE/BM/BMA) ministrada neste semestre.]
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 Scala 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 três algoritmos descritos brevemente abaixo. Cada um deles
determina a silhueta de um conjunto de m edifícios.
- Algoritmo 1 (iterativo)
- Para cada valor de k, 2 ≤ k ≤ m,
determine a silhueta dos k primeiros edifícios. Faça isso
determinando a união de duas silhuetas: a silhueta dos k-1
primeiros edifícios e a silhueta do k-ésimo edifício.
- Algoritmo 2 (recursivo)
- Versão recursiva do algoritmo anterior.
- Algoritmo 3
- 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 três algoritmos. Note que todos eles
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
ter também um algoritmo que cria 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
Tipos.
Para representar cada edifício, seu programa deve usar o seguinte tipo:
case class Edificio(
esq: Int, // coordenada horizontal esquerda do edifício
alt: Int, // altura do edifício
dir: Int // coordenada horizontal esquerda do edifício
)
Os três parâmetros da classe Edificio
(esq
,
alt
e dir
) são na verdade campos paramétricos, pois
todo parâmetro de uma case class é implicitamente precedido por um
val
. Em aula veremos outras características das case
classes.
Faça seu programa armazenar o conjunto de edifícios numa lista. Em outras
palavras, use List[Edificio]
em vez de Set[Edificio]
.
Dessa forma seu código poderá aproveitar melhor as facilidades de casamento de
padrões da linguagem Scala, que são muito adequadas para o processamento de
listas.
Seu programa deve representar uma silhueta como uma lista cujos elementos são
do seguinte tipo:
case class ElemSilhueta(
x: Int, // coordenada horizontal
h: Int // altura
)
No objeto List[ElemSilhueta]
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:
def algoritmo1(edifs: List[Edificio]): List[ElemSilhueta] = ...
def algoritmo2(edifs: List[Edificio]): List[ElemSilhueta] = ...
def algoritmo3(edifs: List[Edificio]): List[ElemSilhueta] = ...
Essas três funções implementam, respectivamente, os 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 2 deve usar recursão de cauda.
def silhuetaComFoldLeft(edifs: List[Edificio]): List[ElemSilhueta] = ...
def silhuetaComFoldRight(edifs: List[Edificio]): List[ElemSilhueta] = ...
Essas duas funções são implementações alternativas do algoritmo comum
às funções algoritmo1
e algoritmo2
. Elas
empregam, respectivamente, os métodos de ordem superior fold
left (operador /:
) e fold left (operador
:\
), ambos da classe List
. O corpo de cada uma
delas deve conter apenas uma linha.
def uniao(s1: List[ElemSilhueta],
s2: List[ElemSilhueta]): List[ElemSilhueta] = ...
Recebe duas silhuetas s1
e s2
, 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
s1
e s2
.
def silhuetaDeEdificio(edif: Edificio): List[ElemSilhueta] = ...
Devolve a silhueta do edifício edif
. Note que o número de
elementos da silhueta devolvida é sempre igual a 2.
As funções algoritmo2
, algoritmo3
e
uniao
devem ser escritas em estilo funcional e devem
empregar casamento de padrões. O suporte a casamento de padrões em
Scala é semelhante ao oferecido por Erlang. Pense em como você escreveria
essas funções em Erlang e faça algo parecido em Scala.
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".
Classe Matriz.
Seu programa deverá ter uma classe parametrizada Matriz[T]
,
que implementa uma matriz bidimensional mutável, cujos elementos são do tipo
T
. Uma Matriz
tem dimensões (número de linhas e
número de colunas) fixas, especificadas em tempo de construção da matriz.
A classe Matriz
deverá dar suporte à notação a(i, j)
para acesso ao elemento armazenado na linha i
e coluna
j
de uma matriz a
. O acesso ao elemento poderá ser
tanto para leitura (v = a(i, j)
) como para atualização
(a(i, j) = v
).
Funções adicionais.
Seu programa deve implementar, ainda, estas duas funções:
def geraImagem(s: List[ElemSilhueta], nomeArq: String): Unit = ...
Recebe uma silhueta s
e a converte para uma imagem no
formato PGM. As imagens geradas por essa função têm tamanho fixo de
NLins
pontos na direção vertical e NCols
pontos na horizontal, com uma distância de MargemInf
pontos
entre o eixo base da silhueta (o eixo horizontal) e a borda horizontal
inferior da imagem. A função geraImagem
supõe que as
coordenadas horizontais da silhueta s
estão no intervalo de
0 a NCols-1
e que as alturas dessa silhueta são menores que
N_Lins-MargemInf
.
Essa função tem uma variável local do tipo Matriz[Int]
, que
contém uma matriz com dimensões NLins
e NCols
.
Ela gerar uma imagem fazendo uma série de chamadas à função
preencheRetangulo
para preencher a matriz, e depois grava
essa matriz no arquivo nomeArq
, 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 de constantes:
val NLins = 600 // número de linhas da imagem
val NCols = 800 // número de colunas da imagem
val BordaInf = NLins - 1 // borda inferior (última linha da imagem)
val MargemInf = 20 // linhas do eixo base à borda inferior da imagem
val Base = BordaInf - MargemInf // linha do eixo base
val Branco = 15 // valor de maxval
val Cinza = 10 // cor da silhueta preenchida
val Preto = 0 // cor do eixo base
def preencheRetangulo(a: Matriz[Int],
lin1: Int, lin2: Int,
col1: Int, col2: Int, k: Int): Unit = ...
Recebe uma matriz a
, dois índices de linha
lin1
e lin2
tais que
0 ≤ lin1
≤ lin2
,
dois índices de coluna col1
e col2
tais que
0 ≤ col1
≤ col2
, e
um valor k
. A função preencheRetangulo
preenche
com o valor k
a submatriz retangular de a
delimitada por lin1
, lin2
, col1
e
col2
.
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 EP2. 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:
scala Silhueta [alg] [arq-entrada] [arq-silhueta] [arq-imagem]
A linha de comando acima pressupõe que o nome da aplicação Scala é
Silhueta
.
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
, 3
, 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:
scala Silhueta 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 3, 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.
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 27/11, 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 (
.scala
) do seu 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: Thu Nov 12 15:28:17 BRST 2009