quinta-feira, julho 31, 2008

Google Code Jam 2008 - Crop Triangles

Crop Triangles foi o primeiro problema da rodada 1B do Google Code Jam. Embora fosse considerado um problema fácil, pouco mais de um terço dos que enviaram um solução para o large input conseguiram acertar.

O enunciado é bastante enrolado e um exame atento dos exemplos é necessário para entender o que é desejado. Tirando as enrolações, ficamos com o seguinte:

Tem-se uma sequência de N pontos de ccordenada (x,y) gerada pelo seguinte trecho em C:
x = x0;
Y = y0;
for (i = 1; i < n-1; i++)
{
x = (A * x + B) % M;
y = (C * y + D) % M;
}
onde n, x0, y0, A, B, C, D e M são inteiros que variam para cada caso a ser tratado.

O resultado desejado é o número de trios de pontos distintos que tenham a soma dos x e a soma dos y múltiplas de 3.

Pegando o exemplo oficial, com n=4, A=10, B=7, C=1, D=2, x0=0, y0=1 e M=20, temos:
  • os pontos gerados são (0,1), (7,3), (17,5) e (17,7)
  • o único trio que atende à condição estipulada é (0,1) (7,3) (17,5).
Tão importante quanto o enunciado são os limites:
  • número máximo de casos: 10
  • 0 <= A, B, C, D, x0, y0 <= 10^9
  • 1 <= M <= 10^9
  • número máximo de pontos: 100 no small input e 100.000 no large input
Um primeiro fato a lembrar é que um unsigned nos compiladores habituais de 32bits suporta números até 4*1024^3 (ou aproximadamente 4*10^9). Portanto um unsigned é suficiente para os valores, mas não para o cálculo entre eles (A*x ou A*y pode passar de 32bits). Na hora, eu lembrei da primeira parte, mas não da segunda : (.

O segundo fato é que para 100 pontos uma solução força bruta, testando todas as combinações, é viável; para 100.000 pontos vai estourar o tempo.

Solução Força Bruta

A solução força bruta é trivial (exceto para quem esquecer do overflow, como eu):
_int64 n, x0, y0, A, B, C, D, M;

#define MAX_PONTOS 100

struct
{
int x, y;
} Ponto [MAX_PONTOS];

void GeraPontos (void)
{
int i;
int x, y;

x = (int) x0;
y = (int) y0;
for (i = 0; i < n; i++)
{
Ponto[i].x = x;
Ponto[i].y = y;
x = (int) ((A * (_int64) x + B) % M);
y = (int) ((C * (_int64) y + D) % M);
}
}

int ContaTrios (void)
{
int trios = 0;

int i, j, k;

for (i = 0; i < n; i++)
for (j = i+1; j < n; j++)
for (k = j+1; k < n; k++)
{
if ((((Ponto[i].x + Ponto[j].x + Ponto[k].x) % 3) == 0) &&
(((Ponto[i].y + Ponto[j].y + Ponto[k].y) % 3) == 0))
{
trios++;
}
}

return trios;
}
Solução Inteligente

O primeiro ponto a reparar é que não estamos interessados no valor da soma, mas sim no resto da divisão da soma por 3. Portanto tanto faz se o x de um ponto é 1, 4, 7 ou qualquer valor com resto 1, a contribuição para a decisão vai ser a mesma.

O pulo do gato é perceber que uma vez que coordenadas com mesmo resto são iguais, basta contar as ocorrências dos restos, não é preciso guardar as coordenadas:
int cont[3][3];

void GeraPontos (void)
{
int i;
int x, y;

cont[0][0] = cont[0][1] = cont[0][2] = 0;
cont[1][0] = cont[1][1] = cont[1][2] = 0;
cont[2][0] = cont[2][1] = cont[2][2] = 0;

x = (int) x0;
y = (int) y0;
for (i = 0; i < n; i++)
{
cont[x %3][y %3]++;
x = (int) ((A * (_int64) x + B) % M);
y = (int) ((C * (_int64) y + D) % M);
}
}
Montada a tabela de contagem de restos, fica rápido contar os totais. É uma questão de determinar quais combinações produzem soma com resto zero.

Por exemplo, é claro que todas as combinações cont[0][0]*cont[1][1]*cont[2][2] resultam em resto zero. Se pegamos mais de um ponto do mesmo grupo, é preciso fazer o desconto correspondente. Por exemplo, as combinações de três pontos diferentes que tem resto zero nas duas coordenadas é cont[0][0]*(cont[0][0]-1)*(cont[0][0]-2)/6. Adaptando o código java do primeiro colocado (mystic):
__int64 ContaTrios (void)
{
__int64 trios = 0;
int i, j, k;
__int64 ci, cj, ck;

for (i = 0; i < 9; i++)
for (j = i; j < 9; j++)
for (k = j; k < 9; k++)
{
if (((i/3+j/3+k/3) % 3 == 0) &&
((i%3+j%3+k%3) % 3 == 0))
{
ci = cont[i/3][i%3];
cj = cont[j/3][j%3];
ck = cont[k/3][k%3];
if (i < j && j < k)
trios += ci*cj*ck;
else if (i == j && j < k)
trios += (ci * (cj - 1) * ck) / 2;
else if (i [ j && j == k)
trios += (ci * cj * (ck - 1)) / 2;
else
trios += (ci * (cj - 1) * (ck - 2)) / 6;
}
}

return trios;
}
Reparar que novamente o int não é suficiente para armazenar o resultado.

segunda-feira, julho 28, 2008

Google Code Jam 2008 - Online Round 1

Proseguindo no Google Code Jam 2008, tivemos neste fim de semana a primeira rodada para valer. E o meu desempenho foi lastimável, apesar de ter passado para a segunda rodada.

A primeira rodada teve as seguintes diferenças em relação à rodada de qualificação:
  • problemas mais difícies
  • três "baterias", com cada participante podendo participar no máximo de uma
  • problemas mais difícies
  • tempo limitado a duas horas
  • problemas mais difícies
  • pontuação diferente para as questões
  • problemas mais ... acho que já deu para pegar a idéia
Quando digo problemas mais difícies, quero dizer que a forma de resolvê-los estava longe de ser óbvia. Além disso, uma solução "força bruta" não tem velocidade suficiente para resolver o "large input".

A primeira bateria que participei foi a 1A, na sexta a noite. E o meu resultado foi o que os tenistas chamam de "pneu" (zero). Eu perdi uns quinze minutos do começo, devido a um problema bobo de login. Dos três problemas, eu cheguei perto de resolver apenas o primeiro (apesar de estar fazendo um complicação desnecessária). Olhando as soluções dos primeiros colocados para os outros dois problemas, não consegui (ainda) entender.

No sábado à tarde tive a segunda e última oportunidade na bateria 1B. Os problemas me pareceram um pouco mais fáceis (ou eu estava com a cabeça mais no lugar). Resolvi atacar primeiro o terceiro problema (que valia mais pontos) pelo método da força bruta. Em pouco mais de trinta minutos eu consegui resolver o "small input", porém chegou perto do limite do tempo (o que significa que não tinha chance para o "large input"). Fiquei algum tempo tentando achar uma forma mais inteligente de resolver o problema, mas não enxerguei. Após gastar mais 30 minutos pensando nos outros dois problemas, resolvi partir para cima do primeiro novamente na base da força bruta. Entretanto, fiz alguma besteira no nervosismo e não consegui passar nem pelo "small input". Olhando as soluções dos primeiros colocados, vi que tinha uma forma bem simples de resolver o primeiro problema. As soluções para os outros dois ainda não entendi.

Graças às pontuações diferentes e o desempate na base do tempo, a minha solução para o terceiro problema (com 15 pontos) me colocou na frente de muita gente que resolveu o primeiro inteiro (5+10 pontos) ou o "small set" do primeiro e do segundo (também 5+10 pontos). Com isto passei para a segunda rodada. Ficou um gosto ruim de ter deixado para trás pessoas que resolveram mais problemas que eu, ainda mais que apelei para a força bruta.

Não acho que faça muito sentido apresentar as minhas soluções. Se tiver disponibilidade de tempo, vou entender as soluções dos primeiros colocados e descrevê-las aqui.

No próximo sábado à tarde tem a segunda rodada, acho pouco provável que eu passe para a terceira.

sexta-feira, julho 25, 2008

Nova Campanha de Apoio a Projetos

Meio em cima da hora, segue o meu apoio à campanha do Efetividade.net e BR-Linux:

Ajude a sustentar a Wikipédia e outros projetos, sem colocar a mão no bolso, e concorra a um Eee PC!

…e também a pen drives, card drives, camisetas geeks, livros e mais! O BR-Linux e o Efetividade lançaram uma campanha para ajudar a Wikimedia Foundation e outros mantenedores de projetos que usamos no dia-a-dia on-line. Se você puder doar diretamente, ou contribuir de outra forma, são sempre melhores opções. Mas se não puder, veja as regras da promoção e participe - quanto mais divulgação, maior será a doação do BR-Linux e do Efetividade, e você ainda concorre a diversos brindes!

Google Code Jam 2008 - Fly Swatter

Concluindo a minha apresentação dos problemas da rodada de classificação do Google Code Jam 2008, discuto agora o terceiro e mais difícil problema.

Um detalhe interessante é que nas primeiras horas poucos enviaram soluções mas entre os que enviaram a taxa de acerto era bem alta. Foi realmente um problema para separar os homens dos garotos (e eu fiquei na pré-adolescência).

Para preparar este post baixei algumas soluções dos primeiros colocados e dei uma olhada nas poucas descrições disponíveis na internet (como esta). O terceiro colocado parece ter feito um solução muito elegante em Haskell; infelizmente não entendo nada desta linguagem.

Descrição do Problema

A descrição é relativamente simples: o que se deseja é saber a probabilidade de acertar uma mosca com uma raquete de tenis. A figura abaixo mostra a modelagem a ser adotada. A mosca é o circulo laranja de raio f. A raquete é também circular, com raio externo R. A raquete tem um aro de espessura t. As cordas da raquete são simétricas em relação ao centro, tem raio r (devem ser tratadas como faixas de largura 2r) e estão espaçadas de g. A mosca está dentro da raquete e considera-se que ela foi acertada se encostar no aro ou em alguma das cordas.

A resposta é considerada correta se tiver erro inferior ou igual a 10e-6.

Minha Tentativa de Solução

Duas coisas me fizeram entrar em pânico: números em ponto flutuante e as curvas onde as cordas se juntam ao aro. Embora fosse claro que uma solução era calcular a área coberta pelo aro e cordas, eu simplesmente não vi como fazer isto. Nas soluções que examinei, este foi o método mais usado e o que vou implementar adiante.

Tendo ignorado o método mais fácil, imaginei duas possibilidades:
  • usar o Método de Monte Carlo: supondo que eu conseguiria determinar se uma mosca em uma determinada posição seria atingida ou não, gerar aleatoreamente um número muito grande de posições e contar a porcentagem de acertos. Embora correta, não senti firmeza suficiente para ir nesta linha. Pelo menos uma das soluções que eu examinei parece ter usado este método.
  • fazer uma integração manual: já que eu não sabia calcular a área, pensei em somar distâncias: variar o y pouco a pouco e para cada y verificar qual o tamanho da parte livre e da parte ocupada pelo aro+cordas. Foi o que tentei fazer e me enrosquei todo. Algumas soluções corretas fizeram algo parecido, porém usaram retângulos ao invés de retas e calcularam uma aproximação para as áreas.
Um detalhe que eu observei corretamente é que, graças a simetria, basta considerar um dos quadrantes da figura.

Uma Alternativa Geometricamente Correta

A figura abaixo mostra o primeiro quadrante, vamos adotar o centro da circunferência da raquete como o centro das nossas coordenadas. Reparar que na parte central o espaço livre entre as cordas são quadrados de lado g. A área livre para a mosca em cada um destes quadrados é (g - 2*f)^2 (obviamente, se g for menor que 2*f a mosca não tem por onde escapar).


O nosso problema são os quadrados que são cortados pelo aro da raquete (para sermos mais precisos, pelo aro mais a margem necessária para a mosca passar). A figura abaixo mostra as quatro possibilidades:



A figura mostra também como podemos calcular a área de um deles: temos um "gomo" (setor) do qual precisamos descontar a área de dois triângulos. De forma análoga os demais casos podem ser calculados a partir da área de gomo, triângulo e retângulo.

A área do gomo é calculada a partir do ângulo, que por sua vez é calculado pelo arco-tangente. A área dos triângulos pode ser calculada diretamente a partir das coordenadas dos seus vértices. Os pontos de intersecção dos quadrados com o aro podem ser facilmente calculados: conhecemos uma das coordenas e os pontos de uma circunferência com centro em (0,0) seguem a relação x^2 + y^2 = R^2.

O cálculo é feito percorrendo um a um os quadrados gerados pelas cordas. Se o quadrado estiver todo dentro do círculo, é só calcular a área do quadrado. Se estiver todo fora, a área de interesse é zero. Se estiver parcialmente dentro, é preciso verificar em qual dos quatro casos ele se encaixa e calcular a área.

O Código

O código abaixo é uma reformatação do código do participante 'klopyrev'.

A primeira coisa necessária é saber se um ponto está dentro ou fora de uma circunferência:
int Inside (double x, double y, double R)
{
return (x*x + y*y) <= R*R;
}
Outra função útil é a que determina uma coordenada (x ou y) de um ponto na circunferência de centro (0, 0) e raio R a partir da outra:
double CoordCirc (double coord, double R)
{
return sqrt (R*R - coord*coord)
}
Em seguida, temos a função que calcula a área de um triângulo, onde um dos pontos é o centro das coordenadas:
double TriArea (double x1, double y1, double x2, double y2)
{
return fabs (x1*y2 - x2*y1) / 2.0;
}
O cálculo da área de setor fica:
double SectorArea (double x1, double y1, double x2, double y2, double R)
{
double ang = fabs (atan2 (y1, x1) - atan2 (y2, x2));
return ang * R * R / 2.0;
}
Com isso conseguimos calcular a área livre de um quadrado na raquete (a numeração abaixo corresponde aos quadrados na minha figura):
double SqrArea (double R, double x1, double y1, double s)
{
double yint1, yint2, xint1, xint2;

if(!Inside (x1, y1, R))
return 0; // totaly outside
if(Inside (x1+s, y1+s, R))
return s*s; // totaly inside
if(!Inside (x1, y1+s, R))
{
if(Inside(x1+s, y1, R))
{ // case 1
yint1 = CoordCirc (x1, R);
yint2 = CoordCirc (x1+s, R);
return SectorArea (x1, yint1, x1+s, yint2, R) + (yint2-y1)*s
- TriArea (x1, yint1, x1, yint2)
- TriArea (x1,yint2,x1+s,yint2);
}
else
{ // case 2
yint1 = CoordCirc (x1, R);
xint1 = CoordCirc (y1, R);
return SectorArea (x1, yint1, xint1, y1, R)
- TriArea (xint1, y1, x1, y1)
- TriArea (x1, y1, x1, yint1);
}
}
else
{
if(Inside(x1+s, y1, R))
{ // case 3
xint1 = CoordCirc (y1+s, R);
yint1 = CoordCirc (x1+s, R);
return SectorArea (xint1, y1+s, x1+s, yint1, R) + s*(xint1-x1)
+ (x1+s-xint1)*(yint1-y1)
- TriArea (xint1, y1+s, xint1, yint1)
- TriArea (x1+s, yint1, xint1, yint1);
}
else
{ // case 4
xint1 = CoordCirc (y1+s, R);
xint2 = CoordCirc (y1, R);
return SectorArea (xint1, y1+s, xint2, y1, R) + s*(xint1-x1)
- TriArea (xint1, y1+s, xint1, y1)
- TriArea (xint1, y1, xint2, y1);
}
}
}

Agora é só gerar todos os quadrados no nosso programa principal e comparar a área não livre com a área total:
totalarea = PI*R*R;
hitarea = PI*R*R;
if ((g - 2*f) > 0)
{
double removedArea = 0;
for(i = 0; TRUE; i++)
{
int maxj = -1;
for(j = 0; TRUE; j++)
{
double x1 = (g+2*r)*i + r + f;
double y1 = (g+2*r)*j + r + f;
double a = SqrArea(R-t-f, x1, y1, g-2*f);
if (a == 0)
break;
maxj = j;
removedArea += a;
}
if (maxj == -1)
break;
}
removedArea *= 4;
hitarea -= removedArea;
}
printf ("Case #%d: %f\n", iCase, hitarea/totalarea);
E com isto fica resolvido e explicado o problema mais complicado (até agora!).

quarta-feira, julho 23, 2008

Google Code Jam 2008 - Train Timetable

Continuando a minha apresentação dos problemas do Google Code Jam 2008, discuto agora o segundo problema. Este era o problema mais simples e teve a taxa mais alta de acertos.

Descrição do Problema

A descrição do problema é bastante clara:
  • Trens circulam entre duas estações
  • Após chegar uma estação, um trem precisa de T minutos para poder seguir no sentido contrário
  • Fornecidos todos os horários de partida e chegada dos trens, determinar o número inicial de trens de cada lado para não faltem trens para cumprir os horários.
Um detalhe que complica um pouco é o formato da entrada: para cada estação é fornecida uma lista dos trens que partem dela, com o horário de partida e o horário de chegada na outra estação.

Resolvendo o Problema

Minha solução para o problema consistiu em montar para cada estação uma tabela dos trens partindo e dos trens prontos para partir (levando em conta o horário de chegada e o tempo de virada). Esta tabela é ordenada em primeiro lugar pelo tempo, quando mais de um evento ocorrer no mesmo tempo as partidas devem vir depois (para aproveitar os trens que ficaram prontos no mesmo minuto).

Feitas as tabelas, é só percorrer verificando onde falta trem.

Implementando a Solução

Para facilitar a ordenação, converti os horários para minutos, múltipliquei por 10 e coloquei na unidade um dígito para colocar as partidas depois.
#define MAX_TRIPS       100
#define TRAIN_READY 1
#define TRAIN_DEPARTURE 2

int StationA [2*MAX_TRIPS];
int StationB [2*MAX_TRIPS];
int nSA, nSB;
A conversão de HH:MM para os décimos de minuto é trivial:
int EncodeTime (char *s)
{
return (s[0]-'0')*10*600 + (s[1]-'0')*600 +
(s[3]-'0')*100 + (s[4]-'0')*10;
}
Para cada trem na lista de entrada de uma estação é preciso colocar uma entrada na tabela desta estação (com a partida) e uma entrada na tabela da outra estação (com o horário em que o trem poderá ser reutilizado):
scanf ("%d", &t);
t *= 10;
scanf ("%d %d", &nA, &nB);
nSA = nSB = 0;
for (i = 0; i < nA; i++)
{
scanf ("%s %s", depart, arrive);
Register (StationA, nSA, EncodeTime(depart)+TRAIN_DEPARTURE);
nSA++;
Register (StationB, nSB, EncodeTime(arrive)+t+TRAIN_READY);
nSB++;
}
for (i = 0; i < nB; i++)
{
scanf ("%s %s", depart, arrive);
Register (StationB, nSB, EncodeTime(depart)+TRAIN_DEPARTURE);
nSB++;
Register (StationA, nSA, EncodeTime(arrive)+t+TRAIN_READY);
nSA++;
}
O registro de um evento em uma tabela é feito por inserção simples:
void Register (int *tabEvt, int nEvt, int event)
{
int i;

for (i = nEvt; i > 0; i--)
if (tabEvt[i-1] <= event)
break;
if (i < nEvt)
memmove (tabEvt+i+1, tabEvt+i, (nEvt-i)*sizeof(int));
tabEvt[i] = event;
}
Por último temos a contagem dos trens:
int Trains (int *Station, int nEvt)
{
int i, need, cur;

for (i = need = cur = 0; i < nEvt; i++)
{
if ((Station[i] % 10) == TRAIN_READY)
cur++;
else if (cur == 0)
need++;
else
cur--;
}
return need;
}

segunda-feira, julho 21, 2008

Google Code Jam 2008 - Saving the Universe

"Saving the Universe" foi o primeiro problema da etapa de classificação (Qualification Round) do Google Code Jam 2008. Discuto aqui o problema e a minha solução.

O meu post anterior contém um resumo do que é o Google Code Jam. Para ver as regras e o problema completo, veja o site oficial.

Talvez por ser o primeiro da lista, mas principalmente por parecer o mais fácil, este foi o problema que recebeu o maior número de tentativas. Entretanto, ele tem as suas pegadinhas, o que fez com que tivesse a menor taxa de acertos para o "small input".

Descrição do Problema

Este é um daqueles problemas que exigem a interpretação do enunciado e a coragem de assumir algumas premissas. É uma brincadeira em cima de uma lenda urbana que diz que o universo implodirá se alguem pesquisar por 'google' no Google. Limpando o enunciado e olhando com atenção os exemplos fornecidos, ficamos com algo assim:
  • A primeira linha da entrada contém o número de casos de teste (N).
  • Cada caso começa com uma linha contendo o número de máquinas de busca (S). As S linhas seguintes contém os nomes destas máquinas de busca. Em seguida vem uma linha com o número de consultas (Q), as Q linhas seguintes contém as consultas, que são os nomes das máquinas de busca.
  • O objetivo do programa é direcionar as consultas para as máquinas de busca, na ordem de entrada, reduzindo o número de mudanças de máquina e evitando enviar para uma máquina uma consulta com o seu nome. Para isto o programa pode buferizar as consultas antes de enviá-las para a máquina de busca (algo que está implícito nos exemplos mas não explícito no enunciado).
  • A saída do programa para cada caso é o número de mudanças de máquina de busca necessárias.
Resolvendo o Problema

Uma vez entendido o funcionamento desejado, fica claro que é uma questão de buferizar as consultas até que não se consiga mais atendê-las sem mudar de máquina de busca. Em outra palavras, quando o nome de todas as máquinas de busca apareceu nas consultas é hora de mudar.

Usando um exemplo simples. Supondo que as máquinas de busca sejam A B e C e as consultas sejam A A B A B C C A A A B C:
  • o primeiro 'lote' de consultas é A A B A B
  • ao ler o C é preciso fechar o primeiro lote
  • o segundo 'lote' é C C A A A
  • ao ler o B fechamos o segundo lote
  • o último 'lote' seria B C
  • o resultado são 2 mudanças de máquina de busca
Implementado a Solução

Pensei em duas formas de implementar a solução:
  • Ir montando os 'lotes' à medida em que ler as consultas. Quando o tamanho do lote ultrapassa de S-1 é hora de chavear e iniciar um novo lote. Com isto eu poderia ignorar a lista dos nomes das máquinas de busca. Por outro lado, cada consulta lida exige uma busca no lote atual para ver se é um nome novo.
  • Procurar cada consulta lida na lista de máquinas de busca, convertendo-a assim em um índice. Usar este índice para ir 'ticando' as novas e manter um contador de máquinas disponíveis. Quando o contador for baixar de 1 para 0 é hora de chavear.
Acabei adotando a segunda opção por achá-la mais otimizada, além de funcionar corretamente se por acaso uma das consultas não for um nome de máquina de busca. Optei por ordenar a lista de máquinas de busca usando inserção simples para depois fazer buscas binárias. Estes dois algorítmos são bem simples e eu estava confiante em conseguir codificá-los sem erro (o que realmente aconteceu).

Nota: nestes concursos normalmente a melhor opção é sempre usar o algorítmo mais simples que tenha o desempenho desejado. No caso do Code Jam as linguagens e bibliotecas são livres, portanto seria uma vantagem usar uma linguagem que já tivesse pronta estruturas apropriadas para montar a lista e fazer a busca (como C++, Java, C#, etc). Mas não seria tão divertido e gratificante...

O meu Código

O código completo pode ser baixado do scoreboard do Code Jam (lá na posição 1117), reproduzo abaixo apenas as partes interessantes, sem os códigos de depuração e os comentários redundantes. O código foi feito com o Microsoft Visual C++ v6, mas deve rodar em outros ambientes. Os comentários e identificadores estão me inglês (como é tradição na produção científica brasileira*).

O loop básico para tratar os "N" casos (comum para todos os problemas) é óbvio:
scanf ("%d", &nCases);
for (iCase = 1; iCase <= nCases; iCase++)
{
// ... trata um caso
printf ("Case #%d: %d\n", iCase, nSwitches);
}

O tratamente de um caso ficou assim:
for (nS = 0; nS < S; nS++)
{
gets (name);
InsertEngine (name);
}
nSwitches = 0;
unused = nS;
memset (used, ' ', MAX_ENGINES);
scanf ("%d\n", &Q);
for (nQ = 0; nQ < Q; nQ++)
{
gets (name);
se = FindEngine (name);
if (se != -1)
{
if (used[se] == ' ')
{
if (unused == 1)
{
// must switch
nSwitches++;
unused = nS;
memset (used, ' ', MAX_ENGINES);
}
used[se] = '*';
unused--;
}
}
}
Reparar que usei um array de caracteres para marcar as máquinas usadas e não usadas com '*' e ' '. Embora o código acima seja simples, consegui fazer uma besteira e o resultado foi um erro na primeira tentativa de tratar um 'small input'.

A inserção na lista ordenada de máquinas de busca ficou:
void InsertEngine (char *name)
{
int i;

strcpy (Engines[nS], name);
for (i = nS; i > 0; i--)
if (strcmp (Engines[order[i-1]], name) <= 0)
break;
if (i < nS)
memmove (order+i+1, order+i, (nS-i)*sizeof(int));
order[i] = nS;
}
Por último, a minha velha amiga busca binária:
int FindEngine (char *name)
{
int first, last, mid, dif;

first = 0;
last = nS-1;
while (last >= first)
{
mid = (last+first)/2;
dif = strcmp (Engines[order[mid]], name);
if (dif == 0)
return mid;
else if (dif < 0)
first = mid + 1;
else
last = mid - 1;
}
return -1; // not found
}
* Isto vem de um 'causo' contado pelo brilhante físico Richard Feynman. Para uma visita ao Brasil ele preparou uma apresentação em português (Feynman gostava de estudar linguas). Entetanto, todas as apresentações anteriores no evento foram em inglês, o que o levou a se 'desculpar' por desconhecer esta 'tradição' brasileira. Após a apresentação (em português) de Feynman, todos os oradores seguintes apresentaram seu trabalhos também em português.

domingo, julho 20, 2008

Biblioteca Histórica Marvel

A Panini está publicando uma série de albuns com as primeiras histórias de vários heróis da Marvel (nos EUA estes albuns são chamados de Marvel Masterworks). Comento abaixo os volumes que adquiri nos últimos meses.

A qualidade do papel, da impressão e da encadernação são muito boas e compatíveis com o preço na faixa de R$35 a R$60. As históricas são bem antigas (1961 a 1966), do tempo que Stan Lee estava revolucionando as histórias de superheróis. Além das histórias, tem as capas originais e uma introdução do Stan Lee.

(clique nas figuras para ver melhor)



Os Vingadores - devo admitir que muito raramente li histórias deste supergrupo. As histórias são bem razoáveis, com uma inocência incompatível com os dias de hoje.



Quarteto Fantástico - por algum motivo, fiquei um pouco decepcionado com estas histórias. Já teve uma época de gostar muito do Quarteto Fantástico e aí estão as histórias onde surgiram vários dos seus inimigos clássicos (Skrulls, Dr Destino e Mestre dos Bonecos), mas alguma coisa não encaixou direito.



Capitão América - não sou muito fã do Capitão, mas li algumas destas histórias quando comecei a ler gibis (final dos anos 60, para quem estiver curioso). Grande parte das histórias se passam na 2a Guerra Mundial e/ou envolvem o malígno Caveira Vermelha.



Homem de Ferro - no volume do Capitão América, a maioria das capas menciona histórias do Homem de Ferro que li quando criança, o que me levou a comprar o album específico. Entretanto, as histórias aqui são anteriores às mencionadas no album do Capitão América e bastante bobinhas. Enquanto que o patriotismo do Capitão na 2a Guerra seja bem aceitável, a dedicação do Homem de Ferro à indústria de armas americana e sua luta contra os comunistas não me parece resistir tão bem ao tempo.


Resumindo, uma boa pedida para quem é fã destes heróis da Marvel e tem curiosidade de ver como eles começaram.

sábado, julho 19, 2008

Google Code Jam 2008 - Introdução

O Google Code Jam é uma competição de programação. Decidi participar este ano e apresento aqui alguns comentários a respeito.

Competições de Programação

Existem diversas competições de programação por aí. Uma das mais tradicionais é a ICPC, uma competição para estudantes universitários promovida pela ACM, que aqui no Brasil é a Maratona de Programação. No Brasil temos também a Olimpíada Brasileira de Informática, para alunos do segundo grau. Estes sites possuem arquivos de questões passadas e links para competições on-line.

As questões constam de uma descrição e alguns exemplos de entradas e as saídas corretas correspondentes. Para permitir a correção automatizada das provas, são estipulados formatos rígidos para as entradas e saídas e a conferência é feita na base da comparação dos arquivos de saída com um gabarito.

Um guia sobre como participar destas competições pode ser baixado daqui. O inglês do autor às vezes dá uma falhada e tem um tutorial meio longo de C, mas as dicas são relevantes, mesmo as mais óbvias.

Google Code Jam 2008

Esta competição tem algumas características curiosas. Nos exemplos que mencionei acima, a compilação e execução dos programas é feita pela "banca", o que limita as opções de linguagem e compilador. A competição do Google aceita qualquer linguagem e compilador (e até mesmo soluções à mão!).

A avaliação de cada questão consta de duas partes.
  • A primeira ("small input") gera um arquivo de teste pequeno (e mais simples). Após baixar este arquivo o participante tem 4 minutos para enviar o arquivo de saída, que é conferido imediatamente. Em caso de erro (inclusive timeout), o participante pode solicitar vários arquivos (que serão diferentes), mas é penalizado a cada tentativa mal sucedida.
  • Na segunda parte ("large input") o aquivo é maior e envolve casos mais complexos. O arquivo de saída deve ser enviado em até 8 minutos e o resultado só é apresentado no final da etapa. Nesta etapa não tem segunda oportunidade.
Nas duas partes os fontes devem ser enviados junto com os arquivos de saída e ficam à disposição para download por todos ao final da etapa.

Qualification Round

A competição terá várias etapas (detalhes no site). A primeira, que acaba de ser concluída, foi relativamente "leve". Foram três questões, disponíveis por 24h. Para passar para a fase seguinte bastava acertar pelo menos um small input e um large input.

O ranking foi montado considerando 5 pontos por small input correto e 20 pontos por large input correto, o desempate foi feito pelo horário do envio da resposta mais uma penalidade por respostas incorretas na primeira parte.

Meu Desempenho no Qualification Round

Acabei decidindo participar em cima da hora e portanto não fiz nenhuma preparação especial. Optei por usar C pelo fato de ser a linguagem que tenho maior fluência.

Graças ao fuso horário, o horário de competição para mim foi das 20:00 de 16/07 às 20:00 de 17/07. Devido a alguns compromissos pessoais e profissionais, acabei lendo o enunciado da primeira questão às 20:00 mas só trabalhei na resolução dela e da segunda das 21:00 às 24:00. A terceira questão ficou para o dia seguinte, das 18:00 às 20:00 (e não deu tempo, como vou detalhar depois).

Felizmente eu acertei por completo as duas primeiras questões (com uma vacilada na primeira) o que deu pontos suficientes para passar para a próxima fase. Graças ao horário, eu consegui ficar em 1117 dentro dos 6773 que passaram. No total 7154 pessoas fizeram alguma pontuação.

Nos próximos posts vou comentar as três questões e as minhas soluções.

sexta-feira, julho 18, 2008

E ganhamos um Darwin Award!

Já comentei antes a tragédia do Padre Adelir de Carli. Apesar da minha torcida (e de muitos outros) a morte do intrépido 'balonista' foi confirmada com o resgate do seu corpo no começo do mês.

Com isto a sua nominação foi aprovada e ele é o mais novo agraciado com um prêmio Darwin:

http://www.darwinawards.com/darwin/darwin2008-16.html

Código de Barras - Outros

Existem várias simbologias além das que vimos nesta série. De uma forma geral elas são pouco usadas e/ou voltadas para aplicações muito específicas.

De vez enquando aparece alguém que escolheu aleatoreamente uma destas simbologias mais incomuns e encontra dificuldade em achar equipamentos e softwares que as suportem. Minha recomendação: utilize uma simbologia específica para o uso desejado (como o EAN-13) ; se não existir uma use o Code 128.

Esta página (em inglês) contém descrições curtas de várias simbologias. Algumas que merecem comentário:
  • Code 11: alta densidade, à custa da confiabilidade. Usada na identificação de equipamentos de telecomunicações.
  • Code 93: um aperfeiçoamento do Code39.
  • Codabar: uma simbologia usada principalmente em bolsas de sangue.
  • Pharmacode: código usado em bulas e embalagens de remédio.
  • GS1: uma simbologia recente para o varejo, potencialmente pode vir a ser muito usada.
  • Trioptic: uma variante do Code 39, usada principalmente para a marcação de fitas e outras midias magnéticas (normalmente em etiquetas coloridas).
Existem também os códigos ditos bidimensionais, que deixo para uma eventual nova série de posts.

quarta-feira, julho 16, 2008

O Correio nos Dias de Hoje

Lendo o noticiário sobre a greve dos correios, me vieram algumas divagações sobre a importância (ou não) do correio no 'mundo atual'.

Certamente que o correio (e antes dele o telégrafo) já foi um item essencial para a comunicação entre as pessoas. Entretanto, o telégrafo já está à beira da extinção, será que o correio segue os mesmos passos?

E-mail, IM, SMS, são maneiras mais rápidas e mais baratas de enviar mensagens entre pessoas, inclusive (as duas primeiras) acompanhadas de imagens e sons. O telefone é muita vezes mais eficiente. São tecnologias ao alcance de quase todos.

Um fato que alguns ignoram é que a ECT tem monopolio para o transporte e entrega de carta e cartão postal (veja aqui a Lei 6.538). O correio dos EUA também tem um monopolio, que curiosamente impede que qualquer outro coloque correspondecia nas caixas de correio das pessoas e empresas.

Este monopolio tem sido aplicado no Brasil também para a entrega de contas, inclusive nos casos em que um leiturista imprime a conta no momento da leitura. Por outro lado, existe uma imensa pressão para o uso de débito em conta; segundas vias e comprovantes de pagamento podem ser impressos diretamente nos sites. Não faltará, é claro, o argumento dos ambientalistas a favor das soluções "paper-free".

Um outro uso para o correio é o envio de propaganda, mas é claro que existe a concorrência desleal do spam. Catálogos impressos é algo raro, tendo sido substituídos por sites atualizados frequentemente.

Dentro da 'e-realidade', o correio entra com os serviços de entrega expressa, para entregar os bens físicos adquiridos on-line. Porém, este é um segmento onde a ECT não possui monopólio e onde a concorrência é alta. Não deixa de ser irônico que a primeira providência da ECT após a greve foi suspender os serviços Sedex.

Ainda estamos longe de ver o fim da carta, mas não há dúvida que o declínio só deve se acentuar para a frente.

BONUS: música grátis! A cantora country/pop Laura Cantrell disponibiliza no seu site a música 'Letters', os mais versados em inglês perceberão com as cartas já foram algo muito importante. Esta é uma versão acústica, uma versão eletrificada pode ser ouvida em streaming a partir daqui (escolha a faixa 5).

segunda-feira, julho 14, 2008

Código de Barras - UPC-E

Completando a nossa vista rápida sobre os códigos UPC e EAN, veremos agora o código UPC-E. Como o EAN-8, o objetivo do UPC-E é gerar um código mais curto para produtos menores.

O caminho seguido para o UPC-E, entretanto, é diferente do EAN-8. Enquanto o EAN-8 utiliza uma numeração distinta do EAN-13 e requer que a empresa solicite o código à entidade responsável pela numeração, o UPC-E é uma compactação de certos códigos UPC-A. Os doze dígitos de um código UPC-A são reduzidos para os oito dígitos do UPC-E basicamente retirando os zeros no meio do UPC-E. Portanto, a todo código UPC-E corresponde um UPC-A (a recíproca obviamente não é verdadeira).

Lembrando, um código UPC-A é composto por um dígito de sistema de numeração, cinco dígitos de empresa, cinco dígitos de produto e um dígito de controle. Esquecendo por alguns instantes os dígitos de sistema de numeração e de controle, os dez dígitos restantes são codificados em seis dígitos da seguinte forma:

O dígito de controle do UPC-A é codificado no UPC-E através da paridade dos seis dígitos obtidos acima, de forma semelhante ao que vimos no EAN-13. O UPC-E se aplica somente aos sistema de numeração '0' e '1', o sistema de numeração determina os valores de paridade para cada dígito de controle:

A estrutura do UPC-E corresponde ao UPC-A sem o grupo do lado direito e com a marca de fim truncada:
  • A marca de início, 101
  • Os dígitos, codificados conforme indicado abaixo
  • A marca central concatenada com a marca de fim truncada, 010101
A codificação dos dígitos em barras usa a mesma tabela que o lado esquerdo do EAN-13:

(lembrando que '1' corresponde a uma barra e '0' a espaço)

O tamanho de um código UPC-E é, portanto, 3 + 6*7 + 5 = 50 módulos.

sábado, julho 12, 2008

Entrando para o Clube das 07:00

Aproveitei a retomada do blog para fazer algumas alterações no layout e na forma de postar.

O Clube das 07:00

Desconfio que ninguém reparou que os meus posts recentes foram todos exatamente às 7 da manhã.

Até recentemente o meu micro de casa não estava ligado à internet. Por este motivo, normalmente eu preparava o post off-line em casa e publicava na manhã seguinte, do trabalho. A partir do momento em que coloquei acesso à internet no micro de casa, a tendência passou a ser postar de noite ou no fim de semana. Entretando, eu prefiro ver post publicados no começo do dia.

Felizmente o Blogger possui agora um recurso de agendar a publicação, o que me permitiu entrar no que o Raymond Chen chama de Clube das 07:00.

Como vantagem psicológica adicional, eu posso ir acumulando posts antecipados e diminuir a pressão de manter um fluxo constante de publicação.

Feed Truncado

O feed do blog é gerado automaticamente pelo Blogger, que infelizmente tem somente duas opções: completo ou muito curto. Resolvi experimentar um pouco o feed muito curto, ele reduz a carga dos agregadores de feed e obriga os interessados a se exporem à experiência completa do blog.

Widgets

Falando na experiência completa, acrescentei dois widgets ao layout do blog.

O primeiro é a Lista de Blogs, um recurso do próprio Blogger. Por enquanto coloquei somente dois blogs, mais adiante pretendo expandir.

O segundo é a minha estante virtual no Shelfari.

Eu tinha pensado em acrescentar também o widget do Dilbert, mas o site oficial anda muito pesado e fiquei com medo que o meu blog ficasse muito lento para abrir.

sexta-feira, julho 11, 2008

Código de Barras - EAN-8

Nos dois posts anteriores examinamos as simbologias UPC-A e EAN-13 que são normalmente utilizadas para identificar produtos no varejo. Entretanto, existem alguns itens que são pequenos demais para comportarem estes códigos. Por este motivo, existem as versões reduzidas UPC-E e EAN-8. Vamos examinar primeiro o EAN-8 que é o mais simples deles.

Como o nome sugere, o EAN-8 armazena 8 dígitos, assim divididos:
  • sistema de numeração (dois ou três dígitos)
  • código do produto (quatro a cinco dígitos)
  • dígito de controle (um dígito)
No EAN-8 o código do produto é definido pelo grupo responsável pelo sistema de numeração. Por exemplo, no caso do Brasil o sistema de numeração é 789 e o código do produto, com quatro dígitos, é definido pela GS1 Brasil.

O dígito de controle é calculado como no EAN-13, considerando 5 zeros à esquerda:
  • Some os dígitos "pares" (2o, 4o e 6o)
  • Some os dígitos "ímpares" (1o, 3o, 5o e 7o) e multiplique por três
  • Some os dois resultados anteriores
  • O dígito é o valor que somado ao total resulte em um múltiplo de dez
Por exemplo, considerando o código 78918344, o dígito 4 é obtido por
  • (7+9+8+4)*3 + (8+1+3) = 96
  • 10 - (96 % 10) = 4
Um código EAN-13 possui a seguinte estrutura básica:
  • A marca de início, 101
  • O grupo da esquerda, composto pelos primeiros quatro dígitos
  • a marca central, 01010
  • O grupo da direita composto pelos quatro últimos dígitos
  • A marca de fim, 101
A tabela para codificação dos dígitos em barras e a mesma do EAN-13, considerando todos os dígitos do grupo da esquerda com paridade impar.

O tamanho de um código EAN-8 é de 3 + 4*7 + 5 + 4*7 + 3 = 67 módulos.

quinta-feira, julho 10, 2008

Código de Barras - EAN-13

Como vimos no post anterior, a simbologia EAN-13 corresponde a uma expansão da simbologia UPC-A americana para o resto do mundo. Um código EAN-13 é dividido em 4 partes:


  • sistema de numeração (dois ou três dígitos)
  • código da empresa responsável (quatro a seis dígitos)
  • código do produto (três a cinco dígitos)
  • dígito de controle (um dígito)
O sistema de numeração é definido mundialmente e identifica quem é responsável pela atribuição do código da empresa. Por exemplo, o sistema 789 é o prefixo para os códigos controlados pela GS1 Brasil. Um código UPC-A é convertido em um EAN-13 simplesmente colocando um zero à esquerda, desta forma os sistemas 00 a 09 correspondem ao códigos americanos.

A divisão entre o código de empresa e código de produto pode ser variavel dentro de um sistema de numeração. Isto suporta um número pequeno de empresas com muitos produtos em conjunto com um número grande de empresas com poucos produtos.

O dígito de controle é calculado da seguinte forma:
  • Multiplique cada dígito do código por 1 (1o, 3o, 5o, 7o, 9o e 11o dígitos) ou por 3 (2o, 4o, 6o, 8o, 10o e 12o dígitos)
  • Some os produtos
  • Divida a soma por 10
  • Se o resto da divisão for 0, o dígito é zero senão é 10 - resto
Por exemplo, considerando o código 7897833700053:
  • (7*1 + 8*3 + 9*1 + 7*3 + 8*1 + 3*3 + 3*1 + 7*3 + 0*1 + 0*3 + 0*1 + 5*3) = 117
  • Resto da divisão por 10 é 7
  • O dígito é 10 - 7 = 3
Uma outra forma de descrever a mesma operação é:
  • Some os dígitos "pares" (1o, 3o, etc)
  • Some os dígitos "ímpares" (2o, 4o, etc) e multiplique por três
  • Some os dois resultados anteriores
  • O dígito é o valor que somado ao total resulte em um múltiplo de dez
A mesma fórmula vale para o UPC-A, lembrando que o primeiro dígito é zero.

A codificação em barras é ligeiramente confusa devido à necessidade de compatibilidade com o UPC-A. Um código EAN-13 possui a seguinte estrutura básica:
  • A marca de início, 101
  • O grupo da esquerda, composto pelos 2o, 3o, 4o, 5o, 6o e 7o dígitos
  • a marca central, 01010
  • O grupo da direita composto pelos 8o, 90, 10o, 11o, 12o e 13o dígitos
  • A marca de fim, 101
onde 0 corresponde a espaço e 1 corresponde a barra.

Note que na descrição acima não está incluído o primeiro dígito, que é o dígito adicional do EAN-13 em relação ao UPC-A. Este dígito é codificado como um bit de paridade dos dígitos do grupo da esquerda:

(I = Impar, P = Par)

A codificação dos dígitos em barra é diferente conforme o grupo em que ele está e, no caso dos dígitos no grupo esquerdo, da paridade definida pelo primeiro dígito; em todos os casos cada dígito ocupa 7 módulos:


Notar que com esta codificação cada dígito resulta em duas barras e dois espaços, com o tamanho a largura das barras e espaços variando de 1 a 4 módulos.

Exemplificando com o código 7897833700053:

  • O primeiro dígito é 7, o que corresponde à paridades I P I P I P
  • Marca de início é 101
  • O segundo dígito é 8, com paridade I, 0110111
  • O terceiro dígito é 9, com paridade P, 0010111
  • O quarto dígito é 7, com paridade I,0111011
  • O quinto dígito é 8, com paridade P, 0001001
  • O sexto dígito é 3, com paridade I, 0111101
  • O sétimo dígito é 3, com paridade P, 0100001
  • Marca central é 01010
  • O oitavo dígito é 7, 1000100
  • O nono dígito é 0, 1110010
  • O décimo dígito é 0, 1110010
  • O décimo-primeiro dígito é 0, 1110010
  • O décimo-segunto dígito é 5,1001110
  • O décim-terceiro dígito é 3, 1000010
  • Marca de fim é 101
O tamanho de um código EAN-13 ou UPC-A é de 3 + 6*7 + 5 + 6*7 + 3 = 95 módulos.

Um último detalhe é a forma tradicional de apresentação do código de barras, que pode ser visto no início do post. As barras das marcas de início, centro e fim se prolongam um pouco mais para baixo que as demais. Na representação em texto (o chamado humano-legível) o primeiro dígito é colocado à esquerda da marca de início e os demais abaixo das respectivas barras.

quarta-feira, julho 09, 2008

Código de Barras - UPC-A

A aplicação mais visível dos código de barras é a identificação de produtos no varejo. A partir da leitura do código de barras no produto, o PDV determina a descrição e o preço do produto. As simbologias UPC e EAN foram desenvolvidas exatamente para esta aplicação.

Para que esta aplicação seja possível, é necessária uma disciplina na atribuição dos códigos aos produtos. Em primeiro lugar, as simbologias UPC e EAN não devem ser usadas para codificar informações quaisquer, elas devem ser usadas somente para codificar a identificação de produtos. Estas identificações, por sua vez, devem ser criadas conforme regras rígidas. Parte destas identificações são definidas por associações nacionais e internacionais e identificam o país e a empresa responsável pelo produto (normalmente o fabricante). Uma parte é definida pela empresa, existem regras rígidas para o reaproveitamente de códigos.

O código UPC-A é o código original para esta finalidade, tendo sido desenvolvido para o mercado americano. O UPC-A codifica uma identificação com doze dígitos. Para alguns produtos o código resultante é muito longo, porisso foi criada uma versão reduzida com seis dígitos, o UPC-E. Posteriormente o sistema de numeração foi expandido para uso mundial, surgindo o EAN-13 (com treze dígitos) e o EAN-8 (com oito dígitos). Nest post vamos examinar o UPC-A, nos posts seguintes veremos o UPC-E, EAN-13 e EAN-8.

Um código UPC-A é dividido em 4 partes:
  • O sistema de numeração (um dígito)
  • O código da empresa responsável (cinco dígitos)
  • O código do produto (cinco dígitos)
  • O dígito de controle (um dígito)
O sistema de numeração indica o que o código representa:

0 = códigos normais
1 = reservado
2 = produtos de peso variável (marcados na loja)
3 = produto farmacêutico
4 = uso livre dentro da loja
5 = cupons
6 = reservado
7 = códigos normais
8 = reservado
9 = reservado

O código da empresa é definido pela UCC e o código do produto é definido pela empresa. Obs.: mais recentemente a UCC tem criado códigos de empresa com mais de cinco dígitos, com a consequente redução no número de dígitos no código de produto.

Os códigos UPC-A são um subconjuntos dos códigos EAN-13, um código UPC-A pode ser transformado em um código EAN-13 simplesmente acrescentando um zero no início. A forma de codificação dos dois padrões é a mesma, vamos vê-la na próxima parte quando falarmos no EAN-13.

Dica útil: como descobrir qual o produto associado a um código? Procure o código no Google! No caso dos códigos UPC existe uma base de dados não oficial em www.upcdatabase.com.

terça-feira, julho 08, 2008

Usando o Doxygen - Parte 3

Nesta parte final, vamos ver passo a passo como gerar a documentação em formato CHM como o Doxygen.

Para seguir este roteiro, você deve ter instalado o Doxygen e o Microsoft Help Workshop (conforme indicado na parte 1). Você encontra os arquivos que utilizei aqui.

O funcionamento do Doxygen é controlado por arquivos de configuração. Felizmente você não precisa editá-los à mão: junto com o Doxygen vem um utilitário chamado Doxywizard para gerar a configuração e disparar o Doxygen com ela. O Doxywizard não é o programa Windows mais bonito que eu já ví e tem suas esquisitices, mas é mais que suficiente para a tarefa.

A tela inicial do DoxyWizard divide o trabalho em 4 passos: Escolher/criar uma configuração, salvá-la (se foi alterada), definir o diretório de trabalho e executar o Doxygen:



O passo 1 é o mais trabalhoso na primeira vez. Clique no botão Wizard e configure os seguintes parâmetros:

Em Project
  • Project Name: no meu caso, DukeMap
  • Source Code Directory: diretório onde estão os fontes
  • Destination Direcotry: diretório onde será colocada a documentação, no meu caso eu coloco no subdiretório Doc
Em Mode, selecione
  • All entities
  • Include croos-referenced source
  • Optimize for C output
Em Output
  • em HTML, selecione Prepare for compressed html (.chm)
  • desmarque os demais formatos
Em Diagrams
  • No diagrams

Clique em Ok para fechar a configuração no modo Wizard e clique Expert na tela inicial para ter acesso a todos os parâmetros:

Em Project

  • Selecionar OUTPUT_LANGUAGE Brazilian
  • Desmarcar FULL_PATH_NAMES

Em Build

  • marcar INTERNAL_DOCS

Em Input

  • INPUT_ENCODING: trocar UTF-8 por char
  • IMAGE_PATH: colocar o diretório DOC, onde está a figura que eu utilizei

Em HTML

  • CHM_FILE: colocar o nome do arquivo CHM a gerar; no meu caso DukeMap.chm.

Feito tudo isto, clicar no Ok para fechar a configuração e clicar Save na tela inicial. No working directory coloque o diretório embaixo do qual será gerada a documentação (no meu caso, o subdiretório Doc).

Clique em Start. Se der tudo certo, Será criado dentro de Docs um diretório html. Dentro deste diretório está um arquivo .hhp gerado pelo Doxygen. Dê um duplo clique nele para abrir o Help Workshop:


Selecione File Compile (ou clique no ícone de "moedor de carne"). Confirme a criação criando em Compile. No diretório html será criado o arquivo chm. Dê um duplo clique nele e veja o resultado final.

Nestes três posts vimos apenas o básico do Doxygen. A melhor forma de aprender o resto é estudar a documentação, ver os exemplo e, principalmente, experimentar bastante.

segunda-feira, julho 07, 2008

Usando o Doxygen - Parte 2

Na parte 1 vimos o que é o Doxygen e porque usá-lo. Nesta segunda parte vamos ver como colocar no fonte as informações para ajudar o Doxygen a gerar a documentação.

As informações para o Doxygen precisam estar dentro de comentários especiais. As formas mais comuns de comentários para o Doxygen são /** comentário */ e /// comentário. O Doxygen aceita também /*! comentário */ e //! comentário. No caso dos comentários multilinha, um * no início do comentário é ignorado, levando ao popular formato
/**
* comentário
*/
Um comentário como o acima define uma descrição detalhada para o que vier em seguida. O Doxygen reconhece uma série de comandos dentro dos comentários. Estes comandos tem o formato @comando ou \comando. Um exemplo de comando é o \brief que permite definir uma descrição sucinta.

Um primeiro tipo de comentário útil é o \mainpage que define o texto a ser apresentado na página inicial da documentação:
/**
* \mainpage DukeMap
*
* \image html MiniTela.jpg
*
* \section intro_sec Introdução
*
* Este programa é um exemplo de uso das funções GDI
* do Windows, apresentando em uma janela um mapa do
* Duke Nuken 3D
*
* \section hist_sec Histórico
*
* Originalmente desenvolvido em 1996 e 1997 com o
* Borland C como uma aplicação Windows 3.1.
*
* Em 2004 foi transformado em um exemplo de uso da
* GDI para uma série de artigos postados na Sharepedia
* do MSDN Brasil.
*
* Adaptado em 2008 para mostrar o uso do Doxygen na
* documentação de programas.
*
*/
Neste exemplo estamos usando também os comandos \image, que coloca uma figura na documentação e \section que coloca um título em destaque:


Uma outra providência útil é identificar os nossos arquivos fonte:
/**
* \file DukeMap.c
* \brief Mostra um mapa de Duke Nuken 3D
* \author Daniel Quadros
* \version 1.20
* \date Criação: 07/nov/2004
* \date Alteração: 05/jul/2008
* \todo
* \li Pedir nome do arquivo
* \li Opção de zoom
*
* Este modulo contem o ponto de entrada do programa e
* a rotina de janela.
*/
Temos aqui vários comandos do Doxygen. Merece destaque o \todo que indica uma tarefa pendente, o Doxygen irá montar um índice de todos os \todo. Notar que temos dois comandos \date, o Doxygen não entra no mérito do conteúdo da maioria dos comandos se limitando a formatá-los e colocá-los na saída. Por último, temos os \li que indicam itens de uma lista. O resultado está abaixo:


Muitas a organização lógica do nosso programa não coincide com a organização física em arquivos. Por isso, é útil definir grupos:
/**
* \defgroup UI Interface com Operador
*
* Este grupo agrega as rotinas e estruturas de dados usadas
* para interface com o operador.
*
*/
O exemplo acima define um grupo chamado UI, cuja descrição sucinta é "Interface com o Operador".

Embora o Doxygen conheça a sintaxe e parte da semântica da linguagem, é sempre bom dar uma informação adicional nas declarações. Comecemos um define:
/**
* \def ARQ_MAPA
* \brief Nome do arquivo com o mapa a apresentar
*/
#define ARQ_MAPA "Bunker.map"
Vejamos agora um descrição de variável, informando o grupo a qual ela pertence:

/**
* \internal
* \var szAplic
* \ingroup UI
* \brief Nome da Aplicação
*/
char szAplic [] = "DukeMap";
Muitas vezes queremos gerar duas versões da documentação, uma contendo somente as interfaces externas dos módulos e outra contendo os detalhes internos. Podemos fazer isto marcando os itens internos com \internal como acima.

Outros tipos de comando para informar o que estamos comentando são \typedef e \struct:
/**
* \internal
* \typedef STAT
* \ingroup Mapa
* \brief Características de teto e chão
*
* Uso dos bits de ceilingstat e floorstat
*/
typedef enum
{
STAT_PARALLAXING = 0x01, /**< 1 = Parallaxing, 0 = not */
STAT_SLOPED = 0x02, /**< 1 = sloped, 0 = not */
STAT_SWAP_XY = 0x04, /**< 1 = swap, 0 = not */
STAT_DOUB_SMOOSH = 0x08, /**< 1 = double smoshiness */
STAT_X_FLIP = 0x10, /**< 1 = x-flip */
STAT_Y_FLIP = 0x20, /**< 1 = y-flip */
STAT_ALIGN = 0x40 /**< 1 = align texture to first wall */
} STAT;

/**
* \internal
* \struct DSC_WALL
* \ingroup Mapa
* \brief Descritor de parede
*
* Esta estrutura descreve uma parede do mapa, para fins
* de desenho na tela.
*/
typedef struct
{
int x, /**< coordenada do ponto esquerdo */
y; /**< coordenada do ponto esquerdo */
short nextwall; /**< indice da próxima parede */
} DSC_WALL;
Notar no exemplo acima o uso de /**<; descrição */ para colocar uma descrição depois do item sendo descrito. Isto é util para documentar não somente enums e structs, mas também variáveis que não requeiram uma descrição mais sofisticada.

Na descrição de rotinas podemos documentar os parâmetros e o retorno:
/************************************************************************/
/**
* \brief Le o mapa
* \ingroup Mapa
* \param szMapa nome do arquivo com o mapa
* \return TRUE se sucesso, FALSE se falha
*/
/************************************************************************/
BOOL LeMapa (char *szMapa)
{
...
}
Note que na descrição dos parâmetros precisamos usar o mesmo nome que o usado no código.

Com isto cobrimos os comandos básicos. O manual do Doxygen possui a relação completa.

Na terceira e última parte vamos ver passo a passo como gerar um arquivo CHM usando o Doxygen e o Microsoft Help Workshop.

quarta-feira, julho 02, 2008

Usando o Doxygen - parte 1

Venho há alguns anos usando o Doxygen para documentar programas desenvolvidos em C e gostaria de compartilhar a minha experiência.

Embora na maioria dos casos os programas fossem para hardwares embarcados, uso Doxygen sob o Windows, gerando a documentação em formato CHM.

O que é o Doxygen?

Tanto a Wikipedia como meu amigo Caloni descrevem de forma bem completa o que é o Doxygen.

Resumindo bastante, o Doxygen é um programa que gera a documentação de um programa a partir da analise dos fontes de um programa escrito em C (ou linguagens derivadas como C++, Java e C#). Nesta análise são reconhecidas declarações de estruturas de dados e funções e comentários feitos com uma sintaxe especial.

Porque usar o Doxygen?

Muitas vezes é necessário ter uma documentação externa ao fonte. Se esta documentação não for gerada de forma automática, é necessário manter sincronizadas três coisas: o código, os comentários e a documentação. Com o Doxygen basta manter sincronizados os dois primeiros, a documentação será gerada diretamente a partir deles.

Por que gerar CHM? Aliás, o que é um arquivo CHM?

Um arquivo CHM (Compiled HTML Help) é um arquivo de ajuda em formato proprietário da Microsoft, gerado a partir de páginas HTML. Maiores detalhes podem ser vistos na Wikipedia.

A saída nativa do Doxygen é HTML. Entretanto o resultado é um número muito grande de arquivos. Transformando estes arquivos em um arquivo CHM ficamos com um único arquivo e ganhamos recursos de busca e índice. Além disso, o arquivo CHM compacta as páginas de forma bem eficaz.

Nem tudo é perfeito. Como dito, o formato CHM é proprietário e não existe muito suporte a ele fora da plataforma Windows. Outra desvantagem é que o uso de páginas HTML apresentadas através do engine do IE oferece um certo risco de segurança. Por este motivo, o Outlook bloqueia arquivos CHM, não é possível visualizar o conteúdo de um arquivo CHM que está em uma unidade de rede e a Microsoft abandonou os planos de evoluir com o formato.

O que eu preciso para usar o Doxygen e gerar arquivos CHM?

Você precisa instalar o Doxygen, que pode ser baixado do site oficial (aqui).Oo mais simples é baixar e executar o programa de setup para o Windows.

Você precisa baixar e instalar tb o Microsoft Help Workshop do site MSDN (aqui ou aqui)

Por último, você deve utilizar uma formatação especial nos comentários do seu programa. No próximo post vou apresentar a formatação que costumo utilizar. Até lá!

terça-feira, julho 01, 2008

Livro de Junho - A Fire Upon The Deep de Vernor Vinge


Embora eu seja um leitor assíduo de ficção científica, quase todos os livros que eu li são de autores antigos, da "era de ouro". Foi, portanto, uma felicidade descobrir um bom livro e um bom autor autor relativamente recentes (1992).

A Fire Upon The Deep é uma ficção do tipo "duro" (que se atenta aos detalhes científicos) que conta uma história de proporções épicas num futuro distante, envolvendo teorias e alienígenas interessantes.

Um outro ponto interessante é que o autor, Vernor Vinge, é um cientista de computação. O resultado é uma terminologia técnica correta e analogias que realmente fazem sentido. Uma benção para quem está cansado de autores que lem o índice de um "Computação for Dummies" e recheiam seus livros de absurdos. Vários trechos do livro consistem em mensagens enviadas através de uma espécie de internet intergalática.

ATENÇÃO: A trama que descrevo abaixo é apresentada aos poucos nos primeiros capítulos. Se você faz questão de ter o máximo de surpresa na sua leitura, recomendo parar por aqui.

A base para o livro é a idéia da galáxia ser dividida em "zonas de pensamento", com os limites físicos para a velocidade variando de forma não contínua entre elas e com isto a capacidade de pensamento e automação. No centro da galáxia fica o Unthinking Depths, onde as inteligências orgânicas e artificiais não funcionam direito e a viagem espacial é quase impossível. A região em que vivemos hoje é Zona Lenta (Slow Zone) onde a velocidade da luz é o limite e a viagem entre estrelas demora décadas. O Além (Beyond) permite velocidades acima da velocidade da luz, possibilitando automação e tecnologias mais avançadas. Por último temos o Transcend, onde é possível super inteligências artificiais que se comportam como verdadeiros deuses (os Powers ou Poderes).

Muitas raças que habitam o Além almejam atingir o Transcend e criar os seus próprios Poderes ou pelo menos tecnologia mais avançadas. Um grupo de humanos se aventura no Transcend e encontra um repositório com antigas receitas e as seguem para construir um Poder. Entretanto, nem todos os Poderes são bons, alguns deles são Perversões e a que é criada é uma particularmente perigosa. Felizmente, o repositório contém uma espécie de antídoto que escapa em uma nave.

A nave acaba aterrizando em um planeta na parte inferior do Além. Este planeta é habitado pelos Tines. Os Tines são criaturas de aparência próxima a canina que individualmente tem inteligência proxima a um cachorro esperto porém se tornam tão (ou mais) inteligentes quanto seres humanos quando se juntam em grupos e coordenam seus pensamentos através de sons de alta frequência. As consequências pessoais e sociais deste tipo de inteligência distribuída são muito bem exploradas no livro (por exemplo, os grupos precisam manter uma distãncia mínima para não interferirem entre si e uma alma pode se manter por tempos muito grandes através da troca gradativa dos membros). Os Tines possuem uma civilização medieval e a nave acaba sendo objeto de disputa entre duas nações, resultando na morte dos adultos e na separação de dois irmãos.

A nave envia um pedido de socorro que é captado em um importante nó da rede intergalática e uma expedição de socorro acaba sendo lançada, perseguida de perto por agentes da Perversão.
A maior parte do livro trata das aventuras das duas crianças entre os Tines e da viagem da expedição de socorro.

Para saber como a trama termina e, mais importante, curtir todos os detalhes da narrativa, leia o livro!