Topcoder: SRM 523

Novembro 27, 2011

No SRM 523 demorei bastante para fazer o problema fácil (50 min!) e por isso sobrou pouco tempo para fazer o médio. Cheguei a bolar uma solução, mas descobri no final que ela estava errada.

Depois de muito tempo voltei acertar um challenge! O erro em questão era um típico caso de Off-by-one error no problema fácil.

Depois de passada a competição, consegui encontrar o erro da minha ideia original e resolvi o problema médio. Neste post vou explicar minha solução.

BricksN

Considere que temos um número infinito de blocos de tamanho 1 a k. Queremos construir uma torre sobre uma base de largura w e altura máxima h usando esses blocos, com a seguinte restrição: só podemos posicionar um bloco em uma dada posição, se todas as posições logo abaixo desse bloco estiverem preenchidas (sem buraco). A pergunta é: quantas torres diferentes podemos formar seguindo essas restrições?

Exemplo de configuração proibida

(Observação: se duas torres têm mesma “forma”, mas existem blocos em posições diferentes, elas também são consideradas diferentes)

Soluções consideradas diferentes

Descrição do problema original.

Solução

Primeiramente, notei que este era um problema de contagem e portanto havia uma grande chance da solução ser por programação dinâmica.

Para encontrar a recorrência em programação dinâmica, é interessante pensar em casos particulares. Vamos por exemplo pensar em uma torre de altura 1 (uma linha) e largura w. Além disso, vamos supor que não há buracos. De quantas maneiras podemos formar tal torre usando blocos de tamanho até k?

Seja C_k(w), o número de maneiras de construir uma linha de comprimento w, permitindo blocos de tamanho até k. Considere todas as soluções com essas características. Podemos particionar essas soluções em grupos nos baseando no tamanho do último bloco utilizado.

Considere um grupo onde o tamanho do último bloco é i. Se removermos esse bloco, teremos linhas de comprimento (w-i). Todas as possíveis soluções diferentes com comprimento (w-i) continuarão diferentes ao adicionarmos o bloco de tamanho i de volta.

Fazendo isso para todos os blocos de tamanho 1 a k, obteremos todas as possíveis soluções contadas em C_k(w). Note que não estamos contando soluções repetidas pois duas soluções com o último bloco diferente, serão diferentes independentemente do que tem anteriormente. Note também que não estamos deixando de contar nenhuma solução, já que qualquer solução deverá conter como último bloco algum entre 1 e k.

Logo, temos a seguinte recorrência:

C_k(w) =  \sum_{i=1}^k C_k(w-i)

Para i \ge  w e com C_k(0) = 1.

Agora vamos generalizar um pouco mais e considerar linhas que podem ter buracos. A receita para encontrar uma recorrência é a mesma: precisamos particionar todas as possíveis soluções e para cada grupo, tentar reduzir para um subproblema.

Seja B_k(w) o número de maneiras de se formar uma linha de comprimento w, permitindo buracos.

Nesse caso, podemos particionar as soluções pela posição onde um buraco primeiro aparece, ou seja, temos um pedaço contíguo de blocos de tamanho i, seguido de pelo menos um buraco. Uma vez que estamos considerando um grupo de soluções para um dado i, qualquer solução diferente formada depois do buraco (posição i+2 em diante), continua sendo diferente ao adicionarmos o pedaço contínuo de comprimento i mais o buraco.

Também temos que contar os casos em que não há buracos. Dessa forma teremos a recorrência

B_k(w) = C_k(w) + \sum_{i=0}^{w-1} C_k(i) \cdot B_k(w-i-1)

Aqui também temos B_k(0) = 1 e podemos argumentar que soluções para i’s diferentes são diferentes (não estamos contando repetições) e também que todas as soluções estão sendo contempladas (inclusive a vazia).

Finalmente, vamos generalizar para torres de altura h. Seja A_k(w,h) o número de soluções respeitando as condições do problema original, sobre uma base w e altura h.

Observamos que devido às restrições do problema, não podemos fazer “pontes” com buracos em baixo. Assim, se tivermos um pedaço contínuo de comprimento w’ no primeiro nível de uma torre com altura máxima h, a construção que pode estar sobre ele são todas as torres sobre uma base w’, com altura máxima h-1.

Com essa observação, podemos continuar com nossa recorrência de B, mas agora temos que considerar todas as possíveis torres que vão sobre o primeiro bloco contínuo. Note que não precisamos nos preocupar com o restante dos blocos depois do buraco, pois qualquer diferente solução obtida continuará diferente após juntarmos com a nossa primeira torre.

Assim, ficamos com a recorrência:

A_k(w, h) = C_k(w) \cdot A_k(w, h-1) +
\; \sum_{i=0}^{w-1} C_k(i) \cdot A_k(i, h-1) \cdot A_k(w-i-1, h)

A implementação dessa ideia é direta. Coloquei no gitbhub essa solução.

Anúncios

Introdução ao Drools Planner

Novembro 20, 2011

O Drools Planner é um framework Java para resolução de problemas de planejamento através de meta-heurísticas, voltado especialmente para problemas de grande porte e alta complexidade (um número grande de restrições), que inviabilizam uma abordagem exata.

Além de prover um framework que fatora partes comuns a essas meta-heurísticas, o que permite reuso de código, o grande atrativo do Drools Planner é sua integração com o sistema de regras do Drools, o Drools Expert, que permite incluir restrições através de uma linguagem de alto nível.

O Drools Planner também provê uma ferramenta de benchmark, possibilitando a comparação, através de gráficos, entre os diversos algoritmos implementados com parâmetros diferentes, de modo a se escolher aquele que mais se adequa ao problema em questão.

Atualmente o Drools Planner implementa apenas algoritmos de busca local, entre eles: busca tabu, simulated annealing e great deluge.

Nota: A versão do Drools descrita nesse post é a 5.3.0 Final. Vale ainda ressaltar que como o Drools Planner em particular está em um estágio inicial, a API ainda está mudando bastante. Portanto, parte do que está escrito aqui pode não fazer sentido para versões anteriores.

Conceitos Básicos

Vamos discutir agora as principais características do Drools Planner.

Interfaces a serem implementadas

Solução. A solução de um problema é uma classe que representa as possíveis soluções do problema e deve implementar a interface Solution. Nessa classe geralmente incluímos referências a todas as informações que podem ser utilizadas pelo algoritmo.

Vizinhos. Para implementar uma busca local precisamos gerar soluções vizinhas a partir de uma dada solução. Cada tipo de movimento para gerar uma solução vizinha deve implementar a interface Move.

Vizinhança. No Drools Planner existe o conceito de fábrica de movimentos que, dada uma solução S, gera um conjunto de Moves, que estarão disponíveis para o algoritmo utilizar. Uma fábrica de movimentos deve implementar a interface MoveFactory.

Avaliação de uma solução com Drools Expert

A grande sacada do Drools Planner é usar o Drools Expert para associar um valor numérico a uma solução. Basicamente, o Drools Expert é uma linguagem de programação baseada em regras. Existe o conceito de working memory, onde diversos objetos, denominados fatos, estão inseridos. Num arquivo .drl, definimos as regras.

Uma regra utiliza a seguinte sintaxe:

rule "Nome da regra"
when
    // Conjunto de condicionais
then
    // Ação a ser tomada (sintaxe Java)
end

Quando um dado conjunto de fatos passa a satisfazer as condições da regra, a ação definida é executada. A vantagem é que em geral restrições são bem fáceis de serem modeladas com regras.

A ideia é escrever um regra que seja satisfeita quando uma restrição é violada. A ação a ser tomada é basicamente somar uma pontuação proporcional à importância dessa restrição. O algoritmo tratará de minimizar essa pontuação através da busca local.

Entidades de Planejamento

No Drools 5.3.0 foram introduzidos conceitos como Planning facts, entities, variables e value range.

Planning fact. É uma classe de fatos que são usados para calcular a pontuação, mas não são modificados ao longo do algoritmo.

Planning entity. É uma classe de fatos que são usados para calcular a pontuação, mas podem ser modificados pelo algoritmo. Essa classe deve ser anotada com @ PlanningEntity.

Planning Variable. São os membros de uma planning entity que podem ser modificados pelo algoritmo. Os getters desses membros devem ser anotados com @PlanningVariable.

Planning Value Range. São os possíveis valores que uma dada planning variable pode assumir. Geralmente esses valores são os elementos de uma lista na classe representando uma solução e nesse caso o getter dessa planning variable também deve conter a anotação @ValueRangeFromSolutionProperty.

Mais informações no manual.

Heurísticas Construtivas

A definição das entidades de planejamento (planning entities) permitem automatizar a geração de uma solução inicial através de heurísticas construtivas padrões como First Fit e Best Fit.

É possível definir sua própria heurística para construir a solução inicial. Para isso, basta o algoritmo implementar a interface CustomSolverPhaseCommand.

Arquivo de Configuração

Um outro item essencial do Drools Planner é o arquivo de configuração. Esse arquivo é no formato XML e define diversas características do algoritmo. Vamos destacar algumas delas.

Estrutura básica do arquivo de configuração

Ambiente de execução

A propriedade environmentMode define o ambiente de execução em que o algoritmo executará. Isso afeta o nível das mensagens de log e a checagem ou não de assertivas. Alguns valores mais comuns dessa propriedade são: DEBUG, REPRODUCIBLE e PRODUCTION.

Para mais informações, consulte o manual.

Classes da solução e da entidade de planejamento

É preciso informar qual classe implementa a solução do problema e qual representa a entidade de planejamento através das propriedades solutionClass e planningEntityClass, respectivamente.

Arquivo de regras

Através da propriedade scoreDrl, informamos o caminho para o arquivo de regras do Drools Expert.

Definição do tipo de pontuação

É possível trabalhar com diferentes tipos de pontuação especificando a propriedade scoreDefinition. As principais são SIMPLE e HARD_AND_SOFT. O primeiro é simplesmente um inteiro e o segundo um par de inteiros, sendo que um representa a parte “hard” e a outra “soft”. Uma pontuação “hard” não nula representa uma solução inviável e portanto tem peso infinitamente maior do que a pontuação “soft”.

A ideia de ter uma pontuação “hard” é permitir que o algoritmo trabalhe com soluções inviáveis e dessa forma conseguir escapar de ótimos locais no espaço de soluções viáveis.

Critério de Parada

A propriedade termination define as condições de parada do algoritmo, como por exemplo tempo de execução, número de iterações sem melhoria da solução, valor de solução alcançado, etc. Para mais detalhes, consulte o manual.

Escolha da heurística construtiva

Através da propriedade constructionHeuristic podemos definir as heurísticas usadas para a construção da solução inicial. Como dito anteriormente, algumas delas são FIRST_FIT e BEST_FIT. Mais informações no manual.

Se você optou por implementar sua própria heurística, a propriedade customSolverPhase deve ser utilizada. Mais detalhes no manual.

Configuração da Busca Local

Há três propriedades principais que precisamos para configurar a busca local: selector, acceptor e forager.

Selector. Define quais fábricas de movimentos serão utilizadas

Acceptor. Define qual algoritmo utilizar, bem como possíveis parâmetros do algoritmo escolhido. Por exemplo, o seguinte trecho de configuração:

<acceptor>
  <completeSolutionTabuSize>
    100
  </completeSolutionTabuSize>
</acceptor>

especifica que usaremos uma busca tabu que possui um conjunto de soluções tabu de tamanho 100 (ou seja, guarda as últimas 100 soluções encontradas e não deixa o algoritmo voltar nelas).

Forager. Especifica a escolha do movimento. As fábricas de movimentos gerarão muitos movimentos a partir da solução corrente. A propriedade minimalAcceptedSelection define que apenas um subconjunto desses movimentos sejam analisados para melhorar a eficiência.

Já a propriedade pickEarlyType permite parar de analisar os vizinhos assim que encontrar um satisfazendo alguma condição (como por exemplo algum que tenha pontuação melhor que a solução corrente).

Para mais detalhes sobre essas três propriedades, consulte no manual.

Conclusão

Pelo que estudei do Drools Planner até agora, consigo ver as seguintes vantagens:

* Parte comum das meta-heurísticas já está implementada
* Sistema de regras é escalável
* Fácil adicionar novas restrições se não precisar mudar as entidades

Já as desvantagens:

* Debugar código Drools é mais difícil do que debugar código Java (principalmente a parte do “when“)
* Paradigma diferente (programação declarativa)


Logging em Java e facade

Novembro 13, 2011

Nesse post vou falar sobre logging em Java, mais especificamente de SLF4J e comentar sobre o design pattern facade.

SLF4J

O SLF4J (abreviação de simple logging facade for Java) é um bom exemplo do design pattern facade (do francês fachada).

O padrão facade consiste basicamente de uma interface que abstrai a implementação. Isso é interessante para questões de manutenabilidade. Outra vantagem é que podemos utilizar diferentes implementações dessa interface sem ter que modificar o código que a utiliza.

Junto com a api do SLF4J, vem uma implementação padrão chamada slf4j-simple que simplesmente joga o logging para a saída padrão. Há outras implementações para essa api tais como:

  • log4j
  • logback
  • commons-logging
  • java.util.logging

Desses quatro, apenas o logback implementa nativamente as interfaces do SLF4J. Para as outras implementações, é necessária uma camada de adaptação. O diagrama de classes a seguir, retirado do manual do SLF4J, explica bem isso:

Fonte: http://www.slf4j.org/images/concrete-bindings.png

Diagrama (clique para ampliar)

Note que no caso da commons-logging, existe outra camada de adaptação. Isso porque na verdade, essa é uma implementação da api JLC (jakarta commons logging) da Apache. Assim, a primeira camada de abstração é uma conversão da SLF4J para a JLC, ficando a escolha da implementação da JCL a cargo da mesma.

A escolha da implementação do SLF4J é feita com base em qual delas é encontrada primeiro no classpath. Um exemplo básico de uso dessa api é:

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class HelloWorld {
  public static void main(String[] args) {
    Logger logger = 
      LoggerFactory.getLogger(HelloWorld.class);
    logger.info("Hello World");
  }
}

Se nenhuma implementação for encontrada no classpath, a seguinte mensagem de erro é exibida:

SLF4J: Failed to load class "org.slf4j.impl.StaticLoggerBinder".
SLF4J: Defaulting to no-operation (NOP) logger implementation
SLF4J: See http://www.slf4j.org/codes.html#StaticLoggerBinder for further details.

e nesse caso, como podemos ver pelo diagrama, toda a saída é descartada.

Logback

A documentação do SLF4J é bem esparsa e não descreve a maior parte de suas funcionalidades. Como o logback implementa essa api, aproveitei que sua documentação é mais detalhada para entender melhor quais os principais aspectos do SLF4J.

Na verdade, o logback possui três módulos, o logback-core, o logback-classic e o logback-access. A implementação do SLF4J é dada pelo logback-classic que depende do logback-core.

Configuração

Embora a ideia da interface permita abstrair a implementação, pode haver particularidades de cada implementação que não são cobertas pela interface. Para isso, o logback utiliza arquivos de configuração.

O logbak utiliza uma configuração padrão, mas é possível sobrescrevê-la através de um arquivo xml que deve ser chamado logback.xml (ou logback-test.xml).

Para uma referência completa sobre o arquivo de configuração do logback, refira-se ao manual.

Níveis de logging

Há os seguintes níveis de logging: TRACE, DEBUG, INFO, WARN e ERROR. Existe um método na classe Logger para cada um desses níveis.

Quando uma mensagem é enviada através de um desses métodos, ela só é gravada se o modo no qual o logger foi setado for menor ou igual ao modo especificado pelo método. A ordem dos níveis é TRACE < DEBUG < INFO < WARN < ERROR.

Por exemplo, se escolhermos o modo do logger como INFO no arquivo de configurações,

<configuration>
    ...
    <logger name="main.App" level="INFO"/>
</configuration>

só as mensagens enviadas para métodos com nível acima ou igual a INFO serão gravadas, no caso .info(...) e .error(...).

package main;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class App {
    
    public static void main(String[] args) {
        Logger logger = 
            LoggerFactory.getLogger(App.class);
        logger.debug("A"); // não aparece
        logger.info("B"); // aparece
        logger.error("C"); // aparece
    }
}

Appender e Layout

Um appender basicamente diz aonde as mensagens de log deverão ser gravadas. Algumas saídas possíveis são console (stdout ou stderr), arquivo, banco de dados, servidor remoto, etc.

Já o layout define o formato de cada mensagem gravada. No logback é possível escrever seu próprio layout, mas a implementação padrão, o PatternLayout, é bem flexível. Ela utiliza variáveis (padrões) que são substituídas de acordo com a ocasião. Essas variáveis são precedidas pelo caractere %. Uma lista resumida de padrões dessa classe é a seguinte:

* %class – imprime o nome da classe de onde o método foi chamado
* %date (%d) – data atual (possível formatar)
* %level – o nível de logging
* %logger – imprime o nome do logger
* %line – número da linha de onde o método foi chamado
* %message (%msg) – a mensagem passada como parâmetro
* %thread – nome da thread
* %n – quebra de linha. Equivalente ao \n

Modificadores:

* %<valor> – padding de <valor> espaços à direita (ex. %-5msg)
* %<valor> – padding de <valor> espaços à esquerda (ex. %5msg)

Com isso podemos interpretar o que o trecho a seguir significa:

%d [%thread] %-5level %logger - %msg%n

Uma mensagem formatada com esse padrão consiste da data de quando a mensagem foi enviada, seguida do nível de logging do método, seguido do nome do logger e então a mensagem em si.

Para uma referência completa sobre os padrões e modificadores, consulte o manual.

Agora podemos configurar o logback para imprimir o log na saída de erro por exemplo,

<configuration>

  <appender name="my-apender" class="ch.qos.logback.core.ConsoleAppender">
    <encoder>
      <pattern>%d{HH:mm:ss.SSS} [%thread] %-5level %logger{36} - %msg%n</pattern>
    </encoder>
    <target>
      System.err
    </target>
  </appender>

  <logger name="main.App" level="TRACE">
    <appender-ref ref="my-apender" />
  </logger>

</configuration>

Basicamente a classe ch.qos.logback.core.ConsoleAppender refere-se ao console e a saída de erro é especificada pelo atributo target (padrão é stdout). Depois o appender é associado ao log “main.App”, que é o log que criamos num exemplo anterior. Para mais informações sobre o appender, veja o manual.

Mensagens parametrizadas

Uma funcionalidade provida pela SLF4J é o uso de mensagens parametrizadas para a melhoria de desempenho. Considere o seguinte caso:

logger.debug("Entry number: " + i + " is " + String.valueOf(entry[i]));

Embora a mensagem seja somente logada no modo de debug, o custo de construí-la (conversão do objeto para string e concatenação) será pago em qualquer modo. Uma alternativa é colocar um if, como no exemplo a seguir

if(logger.isDebugEnabled()) {
  logger.debug("Entry number: " + i + " is " + String.valueOf(entry[i]));
}

Além de deixar a sintaxe mais carregada, ainda temos um overhead adicional por conta da condicional. Podemos então usar mensagens parametrizadas da seguinte forma:

logger.debug("The entry is {}.", entry);

Nesse caso a substituição só é feita se o estiver no modo debug.

Leitura adicional

[1] História de logging em Java
[2] Manual do logback
[3] Reasons to prefer logback over log4j


Currying de funções em Haskell

Novembro 6, 2011

Currying de função é uma técnica de avaliação parcial dos argumentos de uma função. O nome da técnica é em homenagem a Haskell Curry, que segundo a Wikipedia re-inventou o método (Moses Schönfinkel já havia desenvolvido o método anteriormente). O curioso é que esse matemático também deu nome à linguagem Haskell.

Nesse post vou falar um pouco sobre currying de funções em Haskell, baseando-me principalmente no capítulo 4 do livro “Real World Haskell“.

Funções com múltiplos argumentos em Haskell

A sintaxe para especificarmos o tipo de uma função em Haskell com múltiplos argumentos parece meio confusa no começo. Por exemplo, se quisermos definir uma função que soma dois inteiros, devemos especificá-la da seguinte forma.

 
soma:: Int -> Int -> Int
soma a b = a + b

A partir do cabeçalho não dá a impressão de que a função recebe dois inteiros como argumento e retorna um inteiro. Isso porque as funções em Haskell recebem na verdade apenas um argumento. Quando há múltiplos argumentos, chamamos a função ‘f’ com o primeiro argumento e retornamos uma função ‘g’ com as ocorrências desse primeiro argumento substituídas pelo valor passado como argumento.

Por exemplo, considere uma função f(a, b, c) sobre três inteiros a, b e c. A primeira chamada da função f(1,2,3) retorna uma nova função g(b, c) = f(1, b, c), que por sua vez retorna uma outra função h(c) = g(2, c), que recebe apenas um argumento.

Para testar isso na prática, podemos fazer no terminal (ghci):

> :type soma
soma :: Int -> Int -> Int
> let somaTres = soma 3
> :type somaTres
soma3 :: Int -> Int
> somaTres 7
10 

No exemplo acima, o parâmetro a de soma, foi substituído por 3 e a função resultante atribuída a somaTres, que agora só recebe um argumento.

Em uma função com vários parâmetros, podemos trabalhar com versões intermediárias do processo de currying provendo apenas alguns dos parâmetros. Por exemplo,

-- Função que retorna uma tripla a partir de 3 argumentos
foo a b c = (a, b, c)
foo1 = foo 3
foo2 = foo 4 5
foo3 = foo 6 7 8

Nesse caso, foo1 recebe dois argumentos, foo2 apenas um e foo3 já é o resultado da função foo.

Omissão de parâmetros usando currying

Suponha que queiramos selecionar os números primos de uma lista de entrada. Uma versão bem simples, onde tentamos encontrar um divisor de p indo de 2 até \sqrt{p}, pode ser dada por:

ehPrimo p | p < 2 = False
          | otherwise = ehPrimoAux p 2 
                      
ehPrimoAux p q | q*q > p        = True
               | p `mod` q == 0 = False 
               | otherwise      = ehPrimoAux p (q+1)

Na biblioteca padrão do Haskell, existe a função filter, que recebe um array e uma função que recebe um elemento desse array e retorna verdadeiro ou falso. Podemos passar nossa função ehPrimo para gerar uma lista com os elementos primos de 1 a 50 por exemplo.

> :type filter
filter :: (a -> Bool) -> [a] -> [a]
> filter ehPrimo [1..50]
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]

Para facilitar, podemos criar uma função que recebe um array e retorna a lista de primos:

listaPrimos xs = filter ehPrimo xs

Utilizando currying, é possível definir a função acima sem o parâmetro

listaPrimos = filter ehPrimo

No primeiro caso, estamos definindo uma função que chama filter ehPrimo xs. No segundo, estamos apenas associando o resultado da avaliação parcial da função filter com seu primeiro argumento, no caso o ehPrimo.

Currying sobre o segundo parâmetro

Por padrão, a substituição dos argumentos é feita a partir do primeiro argumento, ou seja, da esquerda para a direita. Entretanto, para funções com dois parâmetros (binárias), podemos usar a notação infixa para fazer a substituição do segundo argumento.

A notação infixa consiste em chamar a função entre acentos graves (backtick). Por exemplo, a função soma poderia ser chamada assim:

> 1 `soma` 2
3

Essa sintaxe é interessante para fins de legibilidade de código. Ao chamar a função na forma infixa passando somente o segundo argumento, a substituição é feita somente para ele. Como um exemplo, vamos definir a função potência que recebe dois inteiros a e b e eleva a a b (a função soma não tem graça porque ela é comutativa).

> let potencia a b = a ^ b

Agora, podemos fazer currying e aplicar a função a um argumento apenas

-- Faz a substituição do parâmetro b
> let quadrado = (`potencia` 2)
> quadrado 9
81

Currying em C++

A STL do C++ provê algumas ferramentas para trabalhar com o paradigma funcional, através da biblioteca functional. Através dela podemos reproduzir o nosso primeiro exemplo em Haskell:

#include <functional>
#include <iostream>
using namespace std;

struct adder : public binary_function<int, int, int> {
    int operator() (int a, int b) const {
        return a + b;
    }
};
// currying sobre o primeiro argumento da funcao 
int main (){

    adder soma;
    binder1st<adder> somaTres = bind1st(soma, 3);  
    cout << somaTres(7) << endl; // 10
    cout << somaTres(-1) << endl; // 2
}

Nesse caso trabalhamos com um functor, que é um objeto representando uma função. A classe adder deve derivar da classe binary_function. A função bind1st faz um bind do primeiro argumento da função, e retorna um objeto do tipo binder1st, que deriva da classe unary_function e que recebe um argumento.

É possível fazer o bind do segundo argumento através da função bind2nd.