EP1: A Silhueta de um Conjunto de Edifícios

Exercício-Programa 1: A Silhueta de um Conjunto de Edifícios

Programação Funcional Contemporânea - Segundo Semestre de 2011

[Este EP é uma adaptação do EP1 da disciplina MAC0122 (para BE/BM/BMA) ministrada no segundo semestre de 2009.]

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.


[Ampliar]		[Ampliar]

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 (c₀, a₁, c₁, a₂, c₂, ..., a_n, c_n), onde os valores de c_i representam as coordenadas horizontais em ordem crescente e cada a_i representa a altura que liga as coordenadas c_i_-1 e c_i.

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.

Determinação da silhueta

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.


[Ampliar]		[Ampliar]

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:

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:

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!

Exemplo de arquivo de imagem criado por uma solução do EP1.
Outro exemplo, este para um arquivo de entrada muito maior.

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