Arquivo da tag: c

downloadsubtitle: script para baixar legendas de filmes automaticamente no shell do GNU/Linux

Me acostumei a usar o legendas.tv para baixar legendas de filmes e acabei nunca me perguntando se haveria um jeito mais fácil de baixá-las. Hoje fui assistir um filme e, ao entrar no navegador para baixar sua legenda, me deparei com a mensagem de que o site estava fora do ar:

legendas

A situação me obrigou a procurar outros sites e outras formas de baixar legendas. Minha primeira ideia foi usar o opensubtitles.org, que já havia usado algumas outras vezes. Chegando lá e procurando pelo filme que eu desejava, vi muitas opções e não estava muito claro que legenda baixar para a versão do filme que eu tinha.

Então resolvi dar uma fuçada na pesquisa avançada do site, onde acabei encontrando uma pesquisa por hash. Hash, em computação, é uma função que “resume” uma informação gigante (tipo um arquivo bem grande) numa informação bem pequena (tipo 16 caracteres) que o represente de forma única (ou quase única). A pesquisa por hash, no caso desse site, consiste em procurar uma legenda utilizando esse “ID” do arquivo (ou seja, não importa seu nome).

Achei a possibilidade tão legal que resolvi fazer um programa para nunca mais precisar abrir o navegador quando eu quiser baixar a legenda de um filme. Escrevi um minúsculo programa em C chamado oshash (de OpenSubtitles Hash) para calcular o hash de um filme de acordo com a especificação do site (que não requer nada, a não ser um compilador de C e a biblioteca padrão) e um script (bem tosco, mas funcional) chamado downloadsubtitle que usa o programa oshash (e pequenos programas que todo mundo tem, tipo grep, sed, wget e unzip) para baixar a legenda.

O funcionamento ficou bem fácil: para baixar uma legenda em qualquer língua, basta você digitar downloadsubtitle arquivo.avi para baixar a legenda do “arquivo.avi” (que já vai ser automaticamente nomeada como “arquivo.srt”). Se você quiser especificar uma língua (por exemplo, português do Brasil), é só digitar downloadsubtitle arquivo.avi pob (pob é o código do português do Brasil). Se você quiser baixar uma legenda em inglês ou espanhol, pode usar downloadsubtitle arquivo.avi eng,esp.

Exemplo de funcionamento

$ ls
Amelie [Amélie Poulain].2001.BRRip.x264.AAC[5.1]-VLiS.mkv
$ downloadsubtitle Amelie\ \[Amélie\ Poulain\].2001.BRRip.x264.AAC\[5.1\]-VLiS.mkv pob
Requested language: pob
Movie hash: bcdc90cf4873c09b
Subtitle ID: 4642726
Subtitle: Amelie [Amélie Poulain].2001.BRRip.x264.AAC[5.1]-VLiS.srt
$ ls
Amelie [Amélie Poulain].2001.BRRip.x264.AAC[5.1]-VLiS.mkv  Amelie [Amélie Poulain].2001.BRRip.x264.AAC[5.1]-VLiS.srt
$ 

E aí o filme está pronto para você assistir com o mplayer ou com o seu programa favorito.

Código

Este é o código inicial. Está aqui para fins históricos. Não será atualizado. Use a próxima seção (Download) para baixar a última versão, com bugs corrigidos, tratamento de erros e possivelmente novas funcionalidades.

oshash.c
#include <stdio.h>
#include <stdlib.h>
 
void usage(char *name) {
    printf("Usage: %s <file>\n", name);
    exit(1);
}
 
int main(int argc, char *argv[]) {
    unsigned long long buf[16384], c = 0;
    FILE *in;
    int i;
    if (argc != 2) {
        usage(argv[0]);
    }
    in = fopen(argv[1], "rb");
    if (in == NULL) {
        usage(argv[0]);
    }
    fread(buf, 8192, 8, in);
    fseek(in, -65536, SEEK_END);
    fread(&buf[8192], 8192, 8, in);
    for (i = 0; i < 16384; i++) {
        c+= buf[i];
    }
    c+= ftell(in);
    fclose(in);
    printf("%016llx\n", c);
    return 0;
}
downloadsubtitle
#!/bin/bash
 
usage() {
    echo "Usage: $0 <file> [lang]"
    echo "Examples:"
    echo "$ $0 movie.avi pob         # brazilian portuguese"
    echo "$ $0 movie.avi por,pob     # any portuguese"
    echo "$ $0 movie.avi eng         # english"
    echo "$ $0 movie.avi all         # any language"
    exit
}
 
if [ $# -lt 1 ]; then
    usage
elif [ $# -gt 2 ]; then
    usage
fi
 
if [ $# = 2 ]; then
    lang=$2
else
    lang="any"
fi
 
echo "Requested language: $lang"
output=$(echo "$1" | sed 's/\.[^.]*$/.srt/')
oshash=$(oshash "$1")
echo "Movie hash: $oshash"
subid=$(wget "http://www.opensubtitles.org/en/search/sublanguageid-$lang/moviehash-$oshash/rss_2_00" -q -O - \
    | grep '<link>.*en/subtitles' | sed 's|.*en/subtitles/||; s|/.*||' | head -n1)
echo "Subtitle ID: $subid"
wget "http://www.opensubtitles.org/en/subtitleserve/sub/$subid" -q -O - | gunzip > "$output" 2> /dev/null
echo "Subtitle: $output"

Download

Criei um repositório no Github para colocar o código: github.com/tmadeira/downloadsubtitle

Para quem tem git, é possível baixar com git clone https://github.com/tmadeira/downloadsubtitle.git

Para quem não tem, dá pra baixar em ZIP daqui: github.com/tmadeira/downloadsubtitle/archive/master.zip

O programa ainda não está empacotado bonitinho (não tem nem Makefile ou instruções de instalação). Se futuramente vier a ter, este post será atualizado. Em resumo, basta compilar o código em C (digitando gcc oshash.c -o oshash) e colocar os arquivos oshash e downloadsubtitle numa pasta do seu $PATH (por exemplo, /usr/local/bin).

Sugestões e correções são bem-vindas.

Triângulo de Pascal mod m

ATENÇÃO: Este conteúdo foi publicado há 6 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Este post possui intencionalmente apenas imagens e códigos.

Uso do programa que gera triângulo de Pascal mod m

mod 2

Pascal's Triangle mod 2

mod 3

Pascal's Triangle mod 3

mod 5

Pascal's Triangle mod 5

mod 7

Pascal's Triangle mod 7

mod 12

Pascal's Triangle mod 12

mod 23

Pascal's Triangle mod 23

Código-fonte (com alguns bugs inofensivos — procure XXX)

/* pascal -- generate colored Pascal's triangles in XPM format
 
   Copyright (C) 2011 Tiago Madeira <madeira@ime.usp.br>
 
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 3, or (at your option)
   any later version.
 
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
 
   You can read a copy of the GNU General Public License at
   http://www.gnu.org/licenses/gpl-3.0.txt */
 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <getopt.h>
#include <math.h>
 
#define DEFMOD 2
#define DEFSIZE 300
#define DEFPADDING 8
 
int mod = DEFMOD;
int size = DEFSIZE;
int padding = DEFPADDING;
 
char makecolors[6][4] = {
	"001", "010", "100", "110", "101", "001"
};
 
struct option longopts[] = {
	{"help", 0, 0, 'h'},
	{"padding", 1, 0, 'p'},
	{"size", 1, 0, 's'},
	{"mod", 1, 0, 'm'},
	{0, 0, 0, 0}
};
 
char *program_name;
 
void try_help() {
	fprintf(stderr, "Try `%s --help' for more information.\n", program_name);
}
 
void help() {
	printf("Usage: %s [OPTION]... [FILE]\n", program_name);
	printf("Generate colored Pascal's triangles (XPM format).\n\n");
	printf("Mandatory arguments to long options are mandatory for short options too.\n\n");
	printf("  -h, --help        print this help\n");
	printf("  -m, --mod=M       paint with different colors numbers mod M\n");
	printf("  -p, --padding=SZ  image padding (margin) in pixels\n\n");
	printf("  -s, --size=SZ     generate SZ lines of Pascal's triangle\n\n");
	printf("With no FILE, or when FILE is -, write to standard output.\n\n");
	printf("Report bugs to <madeira@ime.usp.br>.\n");
}
 
int baselog(int n, int base) {
	return ceil(log(n) / log(base));
}
 
void *xmalloc(size_t size) {
	void *x = malloc(size);
	if (x == NULL) {
		fprintf(stderr, "There is no enough memory to allocate.\n");
		exit(3);
	}
	return x;
}
 
int main(int argc, char **argv) {
	int optc, tofile;
	int i, j;
	int width, height, chars;
	char **color, rgb[7];
	int one, pos;
	int *pascal;
	char *line;
 
	program_name = argv[0];
	while ((optc = getopt_long(argc, argv, "hm:p:s:", longopts, (int *)0)) != -1) {
		switch (optc) {
		case 'h':
			help();
			return 0;
		case 'm':
			mod = atoi(optarg);
			if (mod > 48) { /* XXX */
				fprintf(stderr, "At the moment, this program supports only mod <= 48 (color generation limit).\n");
				return 4;
			}
			if (mod > 26) { /* XXX */
				fprintf(stderr, "At the moment, this program supports only mod <= 26 (bad implementation limit).\n");
				return 5;
			}
			break;
		case 'p':
			padding = atoi(optarg);
			break;
		case 's':
			size = atoi(optarg);
			break;
		default:
			try_help();
			return 1;
		}
	}
	if (optind < argc && strcmp("-", argv[optind])) {
		if (freopen(argv[optind], "w", stdout) == NULL) {
			fprintf(stderr, "Can't open `%s' for writing.\n", argv[optind]);
			return 2;
		}
		tofile = 1;
	} else {
		tofile = 0;
	}
 
	printf("static char *a_xpm[] = {\n");
	width = size * 2 + padding * 2;
	height = size * 2 + padding * 2;
	chars = baselog(mod, 26);
	printf(""%d %d %d %d",\n", width, height, mod + 1, chars);
	color = xmalloc(sizeof(color[0]) * (mod+1));
	rgb[6] = '�';
 
	printf("\"");
	color[mod] = xmalloc(sizeof(color[mod][0]) * (chars + 1));
	for (j = 0; j < chars; j++) {
		color[mod][j] = ' ';
	}
	color[mod][chars] = '�';
	printf("%s c #000000\",\n", color[mod]);
 
	for (i = 0; i < mod; i++) {
		color[i] = xmalloc(sizeof(color[i][0]) * (chars + 1));
		if (i == 0) {
			for (j = 0; j < chars; j++) {
				color[i][j] = 'a';
			}
			color[i][chars] = '�';
		} else {
			strcpy(color[i], color[i-1]);
			for (j = chars-1; j >= 0; j--) {
				if (color[i][j] == 'z') {
					color[i][j] = 'a';
				} else {
					color[i][j]++;
					break;
				}
			}
		}
		one = 255 / pow(2, i / 6);
		sprintf(rgb, "%02x%02x%02x", makecolors[i%6][0] == '1' ? one : 0,
				makecolors[i%6][1] == '1' ? one : 0, makecolors[i%6][2] == '1' ? one : 0);
		printf("\"%s c #%s\",\n", color[i], rgb);
	}
 
	line = xmalloc(sizeof(line[0]) * (width+1));
	pascal = xmalloc(sizeof(pascal[0]) * size);
 
	line[width] = '�';
	for (j = 0; j < width; j++) {
		line[j] = ' ';
	}
	for (i = 0; i < padding; i++) {
		printf("\"%s\",\n", line);
	}
 
	memset(pascal, 0, sizeof(pascal[0]) * size);
	pascal[0] = 1;
 
	for (i = 0; i < size; i++) {
		for (j = i; j >= 0; j--) {
			if (j != 0) {
				pascal[j] = (pascal[j-1] + pascal[j]) % mod;
			}
			pos = padding + 2*j + (size - 1 - i);
			/* XXX a implementacao de line ficou toda errada e so estou pegando
			 * o primeiro caractere de color aqui. precisa ser reescrito. */
			line[pos] = line[pos+1] = *color[pascal[j]];
		}
		printf("\"%s\",\n\"%s\"%s\n", line, line, i == size-1 && !padding ? "" : ",");
	}
 
	line[width] = '�';
	for (j = 0; j < width; j++) {
		line[j] = ' ';
	}
	for (i = 0; i < padding; i++) {
		printf("\"%s\"%s\n", line, i == padding-1 ? "" : ",");
	}
	printf("};\n");
 
	if (tofile) {
		fclose(stdout);
	}
	return 0;
}

(Download — 5kb)

Gerando tabelas de hash MD5

ATENÇÃO: Este conteúdo foi publicado há 10 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

A idéia veio do nada. Na verdade, eu estava fazendo um freelance e procurando uma função pra “ordenar” um vetor aleatoriamente no PHP (no fim usei usort, que recebe uma função de comparação tipo o qsort do C) e me deparei com um comentário lá no PHP.net de um cara que usou geração de números aleatórios para criar um algoritmo de criptografia pra usar no lugar de MD5 e SHA, porque ele não confiava mais no MD5 e no SHA porque segundo ele existem tabelas na internet, o que torna um sistema muito vulnerável (para quem tem acesso ao banco de dados).

Procurei na internet e na verdade eu não encontrei muitos bancos de dados com vários MD5 não, ao menos não visíveis no Google quando se procura por um hash. Só pra strings como “1234”, mas não achei nem pra “060790” (minha data de nascimento). Veja você mesmo: 81811b48cc07432fc550cb42d4ab3e8f

Então pensei: são 31 dias por mês, 12 meses por ano, 100 anos considerando que os anos são representados por dois dígitos. Isso me dá 31 x 12 x 100 = apenas 37200 hashes. O custo pra gerar isso deve ser minúsculo, por que ninguém faz?

A idéia de fazer com essas datas de nascimento veio do fato de vários usuários leigos que conheço utilizarem data de nascimento pra suas senhas (muito também pelo fato de eles usarem essa mesma senha nas senhas de seis dígitos numéricos do banco e esse tipo de coisa). Então lá fui eu pro código. A princípio escrevi em cerca de 30 segundos – 1 minuto o seguinte código em Ruby:

require "md5"
 
100.times do |ano|
        12.times do |j|
                mes = j+1

                31.times do |i|
                        dia = i+1
                        string = sprintf("%02d%02d%02d", dia, mes, ano)

                        md5 = MD5.new(string).to_s
                        puts "#{string}: #{md5}"
                end

        end
end

É funcional e até eficiente…

tiago@flick ~ $ time ruby genmd5.rb > hashes-ruby

real    0m1.662s
user    0m0.620s
sys     0m0.028s

Mas minha geekialidade não permitiu que eu parasse por aqui. Nesse momento eu já nem me lembrava do freelance que estava fazendo e resolvi ver como usar MD5 em C. Meu primeiro chute foi um man md5 no terminal, que já me retornou a resposta da vida, do universo e tudo mais: o cabeçalho openssl/md5.h e sua função MD5:

unsigned char *MD5(const unsigned char *d, unsigned long n,
                 unsigned char *md);

Então lá fui eu pro programa:

#include <stdio.h>
#include <openssl/md5.h>
 
int main() {

        int dia, mes, ano;
        unsigned char string[STRING_LENGTH], md[MD5_DIGEST_LENGTH];
        for (ano = 0; ano < 100; ano++) {

                for (mes = 0; mes < 12; mes++) {
                        for (dia = 0; dia < 31; dia++) {

                                sprintf(string, "%02d%02d%02d", dia+1, mes+1, ano);
                                printf("%sn", MD5(string, sizeof(string), md));
                        }

                }
        }
        return 0;
}

Ao rodar, recebi saídas com caracteres estranhos e nenhum resultado visível. Corri pro Google. Procurei, procurei, e NINGUÉM usa essa maldita função MD5 do C num programa simples e não há exemplos nem howto de como utilizá-la. Depois de uns 30 minutos quebrando a cabeça (pra mais), percebi que alguns códigos que usavam isso na internet usavam %x (é o código pro printf imprimir inteiros hexadecimais) para imprimir caracteres do MD5 na tela. Aí encontrei algo assim:

printf("%x%x...%x%x", md[0], md[1], ..., md[14], md[15]);

(e pior que estou falando sério… tem gente na internet que não conhece for!)

E caiu a ficha. O MD5 tem 16 inteiros hexadecimais de um byte, 32 caracteres. Escrever o código abaixo me tomou bastante tempo, mas uma aprendizagem interessante e um ânimo pra voltar pro meu freelance:

#include <stdio.h>
#include <openssl/md5.h>
 
#define STRING_LENGTH 6
 
int main() {

        int dia, ano, mes;
        int i;
        unsigned char md[MD5_DIGEST_LENGTH], string[STRING_LENGTH];

 
        for (ano = 0; ano < 100; ano++) {
                for (mes = 0; mes < 12; mes++) {

                        for (dia = 0; dia < 31; dia++) {
                                sprintf(string, "%02d%02d%02d", dia+1, mes+1, ano);
                                MD5(string, sizeof(string), md);
                                printf("%s: ", string);
                                for (i = 0; i < 16; i++) {

                                        printf("%02x", md[i]); /* Note isso aqui! */
                                }
                                printf("n");
                        }

                }
        }
        return 0;
}

O “Note isso aqui!” ainda foi uma sacanagem incrível, o código que eu disse do cara que imprimia %x%x%x… não funciona na prática, porque quando um dos dígitos é 0X, ele só imprime X.

Enfim compilei meu código com -lssl (importante para C-zeiros de primeira viagem) e voi lá:

tiago@flick ~ $ time ./md5 > hashes-c

real    0m0.397s
user    0m0.136s
sys     0m0.028s

Confesso que é coisa de nerd mesmo querer otimizar um código que só serve pra gerar um arquivo de hashes e já o fez, mas no momento em que terminei esse teste, pensei: preciso postar isso no blog pra documentar o uso da função MD5 no C, antes que mais alguém perca o tempo que eu perdi.

Pra quem se pergunta se eu realmente fiz tudo certo:

tiago@flick ~ $ diff senhas-c senhas-ruby
tiago@flick ~ $ 

(ie. ou eu errei nos dois ou eu não errei em nenhum)

Útil, não? Não. Na verdade isso não serve pra absolutamente nada, a não ser que você roube o banco de dados de alguém e esse alguém usa como senha a data de nascimento da sua mãe. Mas aí ele merece mesmo que você pegue sua senha, então isso não muda nada.

Dá pra adaptar o código pra gerar outras tabelas, mas por favor não use isso pra nada maligno, e falo sério. Meus fins foram absolutamente educacionais/acadêmicos (eu queria aprender a trabalhar com a função MD5 da biblioteca OpenSSL, não dominar o mundo) e estou postando aqui para ajudar os que também vão querer usar essa função.

Comentários de crackers serão ignorados.

Desenvolvimento livre de drivers de webcam Microdia

ATENÇÃO: Este conteúdo foi publicado há 10 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Como alguns de meus leitores já sabem, meu laptop (Acer Aspire 5050-3205) possui uma Acer Orbicam sem suporte no Linux (tanto com gspcav, quanto com linux-uvc), identificada pelo lsusb como 0c45:6260 (vendor: Microdia).

Além da minha, existem várias webcams desse tipo sem suporte pelo Kernel: 0c45:6027, 0c45:608f, 0c45:60ec, 0c45:60fe, 0c45:60c0, 0c45:613b, 0c45:613c, 0c45:624e, 0c45:624f, 0c45:6242, 0c45:6253, 0c45:6260, 0c45:6270, 0c45:627b, 0c45:8105.

Na lista microdia, surgiu uma iniciativa que pode mudar essa realidade: usando USB sniffs dos drivers de Windows, começamos a desenvolver drivers para webcams Microdia (repositório git).

Gostaria de convidar a comunidade brasileira usuária de Linux que tem webcam Microdia (0c45:XXXX) a também participar, compartilhando as informações de sua câmera para ajudar no desenvolvimento. Quem se interessar, favor entrar na lista ou entrar em contato comigo para mais informações.

Crivo de Eratóstenes

ATENÇÃO: Este conteúdo foi publicado há 10 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Encontrar números primos é um problema comum em olimpíadas e maratonas de programação. Até hoje não existe uma maneira fácil de determinar se um número é ou não primo, mas para resolver estes problemas é indispensável o conhecimento de alguns algoritmos clássicos e simples, como o Crivo de Eratóstenes.

O Crivo de Eratóstenes é um método bastante prático para encontrar os primos de 2 até um valor limite, que pode ser feito a mão e é fácil de implementar.

O algoritmo consiste em:

  1. Determinar (ou receber na entrada do programa) o valor limite, isto é, o maior número que desejamos saber se é primo.
  2. Fazer a raiz quadrada do valor limite. Pode-se arredondar para baixo caso a raiz não seja exata (e quase nunca é).
  3. Criar um vetor (lista) com os números de 2 até o valor limite.
  4. Para i=2 até raiz do valor limite, caso o número (i) não esteja riscado insira-o na lista dos primos (ou imprima-o, ou não faça nada, isso depende da utilidade que você quer dar para o crivo) e risque todos os seus múltiplos na lista.

Há várias maneiras de implementar este algoritmo. Eu pseudocodaria (meu pseudocódigo é bem próximo de uma linguagem normal, porque acho que assim é mais fácil de entender e depois implementar) ele assim:

/* Primeiro passo */
recebe valorLimite

/* Segundo passo */
raiz \leftarrow \sqrt{valorLimite}

/* Terceiro passo */
para i \leftarrow 2 até valorLimite
    vetor[i] \leftarrow i
fim-para

/* Quarto passo */
para i \leftarrow 2 até raiz
    se vetor[i] = i
        imprima "O número " i " é primo."
        para j \leftarrow i+i até valorLimite, de i e i
            vetor[j] \leftarrow 0
        fim-para
    fim-se
fim-para

Vêem como é simples?

Crivo de Eratóstenes implementado em C

#include <stdio.h>
#include <math.h> // necessário para raiz
 
#define NMAX 1000000 // valor máximo para o valor máximo
 
int main() {
    int i, j, vetor[NMAX];
    int valorMaximo, raiz;
 
    // Primeiro passo
    scanf("%d", &valorMaximo);
 
    // Segundo passo
    raiz=sqrt(valorMaximo);
 
    // Terceiro passo
    for (i=2; i<=valorMaximo; i++) {
        vetor[i]=i;
    }
 
    // Quarto passo
    for (i=2; i<=raiz; i++) {
        if (vetor[i]==i) {
            printf("%d é primo!n", i);
            for (j=i+i; j<=valorMaximo; j+=i) {
                vetor[j]=0; // removendo da lista
            }
        }
    }
 
    return 0;
}

No USACO Training Program Gateway (programa de treinamento para olimpíadas dos estado-unidenses) há um problema muito interessante (Prime Palindromes) cujo objetivo é determinar palíndromos primos de X a Y. Uma das melhores situações que já encontrei para usar o Crivo e sem dúvidas é um ótimo treinamento. Além de determinar primos, você terá que determinar palíndromos e é outro ótimo exercício lógico-matemático.

Divirtam-se e qualquer dúvida usem os comentários!

Segunda fase da OBI2007

ATENÇÃO: Este conteúdo foi publicado há 10 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

A prova de segunda fase da Olimpíada Brasileira de Informática aconteceu há duas semanas e eu havia me esquecido de comentar aqui no blog como eu fui. O resultado deve sair amanhã ou depois de amanhã, segundo um dos caras responsáveis pela organização no orkut. Se tudo der certo e Éris quiser eu participarei pela quarta vez do curso de programação e da seletiva para a IOI.

Telemarketing (OBI2007 – Programação Nível 2 – Segunda Fase)

A solução mais eficiente usa heaps. Sem conseguir pensar nesta solução no momento da prova, implementei uma força bruta bem otimizada. Infelizmente, ela tem um pequeno erro que uma alma boa que se apresenta como CEO da Oracle encontrou para mim:

No seu programa, você faz um “for” que vai de “ultimo” até “n”, armazenando o id do vendedor que vai ficar desocupado primeiro na variável “mt”. Então você faz um “for” de 1 até “ultimo” mudando a variável “mt” apenas quando o vendedor ficar livre antes do “mt”, sendo que, como o id dele é menor, deve atender a ligação caso fique disponível antes ou ao mesmo tempo em que o vendedor “mt” ficar livre. Para resolver isso, fiz um “for” que vai de “ultimo” até 1 usando um “if” com “<=”.

Acredito que receberei no máximo 20/100 pontos.

#include <stdio.h>
#include <values.h>
 
#define NMAX 1010
 
int main() {
	int n, l, duracao, c=0, ocupado[NMAX], mt, ligacoes[NMAX], oc;
	int i, j, ultimo;
 
	scanf("%d %d", &n, &l);
 
	for (i=1; i<=n; i++) {
		ocupado[i]=0;
		ligacoes[i]=0;
	}
 
	ocupado[0]=MAXINT;
	ultimo=0;
 
	for (i=1; i<=l; i++) {
		scanf("%d", &duracao);
		c=0;
		mt=0;
		for (j=ultimo+1; j<=n; j++) {
			if (!ocupado[j]) {
				ocupado[j]=duracao;
				ligacoes[j]++;
				c=1;
				ultimo=j;
				break;
			} else {
				if (ocupado[j]<ocupado[mt]) {
					mt=j;
				}
			}
		}
		if (!c) {
			for (j=1; j<=ultimo; j++) {
				if (ocupado[j]<ocupado[mt]) {
					mt=j;
				}
			}
			oc=ocupado[mt];
			ultimo=0;
			for (j=1; j<=n; j++) {
				ocupado[j]-=oc;
			}
			ocupado[mt]=duracao;
			ligacoes[mt]++;
		}
	}
 
	for (i=1; i<=n; i++) {
		printf("%d %dn", i, ligacoes[i]);
	}
 
	return 0;
}

Pizza (OBI2007 – Programação Nível 2 – Segunda Fase)

A solução mais eficiente usa programação dinâmica. A minha solução é uma força bruta, mais simples impossível. O programa está correto, mas não passará em muitos casos de teste por estourar o tempo limite. Espero mais uns 20/100 pontos.

#include <stdio.h>
 
#define MAX 100010
 
int main() {
	int n, soma;
	int i, j;
	int k[MAX];
	int maximo=0;
 
	scanf("%d", &n);
	for (i=1; i<=n; i++) {
		scanf("%d", &k[i]);
		k[i+n]=k[i];
		if (k[i]>maximo) {
			maximo=k[i];
		}
	}
 
	if (maximo==0) {
		printf("0n");
		return 0;
	}
 
	for (i=1; i<=n; i++) {
		soma=0;
		if (k[i]>0) {
			for (j=i; j<i+n; j++) {
				soma+=k[j];
				if (soma>maximo) {
					maximo=soma;
				}
			}
		}
	}
 
	printf("%dn", maximo);
 
	return 0;
}

Labirinto (OBI2007 – Programação Nível 2 – Segunda Fase)

O único problema que resolvi de maneira eficiente. A solução transforma o problema do labirinto em um grafo e depois chega à solução com uma busca em largura. Nesse eu espero a pontuação máxima, 100/100 pontos.

#include <stdio.h>
#include <values.h>
 
#define NMAX 55
#define VERTICES 2510
 
int n, m;
int nivel[VERTICES], vizinhos[VERTICES];
int fila[VERTICES*VERTICES], nvl[VERTICES*VERTICES];
int max[VERTICES];
int grafo[VERTICES][VERTICES];
int saida=MAXINT;
 
int identificador (int a, int b) {
	return (b+(a-1)*m);
}
 
int rn (int nivelerrado) {
	while (nivelerrado>9) {
		nivelerrado-=10;
	}
	return nivelerrado;
}
 
int main() {
	int i, j;
	int idmax, atual, idv;
	int niv, nivv, niva;
	int ini, fim;
 
	scanf("%d %d", &n, &m);
 
	idmax=n*m;
 
	for (i=1; i<=idmax; i++) {
		for (j=1; j<=idmax; j++) {
			grafo[i][j]=0;
		}
		vizinhos[i]=0;
		max[i]=0;
	}
 
	for (i=1; i<=n; i++) {
		for (j=1; j<=m; j++) {
			atual=identificador(i, j);
			scanf("%d", &nivel[atual]);
			if (i-1>0) {
				idv=identificador(i-1, j);
				if (idv>0) {
					grafo[atual][vizinhos[atual]++]=idv;
				}
			}
			if (j-1>0) {
				idv=identificador(i, j-1);
				if (idv>0) {
					grafo[atual][vizinhos[atual]++]=idv;
				}
			}
			if (i+1<=n) {
				idv=identificador(i+1, j);
				if (idv<=idmax) {
					grafo[atual][vizinhos[atual]++]=idv;
				}
			}
			if (j+1<=m) {
				idv=identificador(i, j+1);
				if (idv<=idmax) {
					grafo[atual][vizinhos[atual]++]=idv;
				}
			}
			grafo[atual][vizinhos[atual]++]=atual;
		}
	}
 
	ini=0;
	fim=0;
	nvl[fim]=0;
	fila[fim++]=1;
	while (ini!=fim) {
		niv=nvl[ini];
		if (niv<saida) {
			atual=fila[ini++];
			niva=rn(nivel[atual]+niv);
			if (atual==idmax) {
				if (niv<saida) {
					saida=niv;
				}
			} else {
				for (i=0; i<vizinhos[atual]; i++) {
					idv=grafo[atual][i];
					nivv=rn(nivel[idv]+niv);
					if (nivv<=niva+1&&niv+1>max[idv]) {
						nvl[fim]=niv+1;
						max[idv]=niv+1;
						fila[fim++]=idv;
					}
				}
			}
		} else {
			ini++;
		}
	}
 
	printf("%dn", saida);
	return 0;
}

Conclusão

O resultado da olimpíada deve sair amanhã ou depois de amanhã e a nota de corte deve ser entre 100 e 150 pontos. Pelos meus cálculos, eu devo ter feito 140 (20+20+100), o que talvez me classifique para a próxima fase. Mais notícias a qualquer momento ;)

for (d=hoje; d<=17/03; d++) { Estude – OBI }

ATENÇÃO: Este conteúdo foi publicado há 11 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

IMPORTANTE: Esse post não é recomendado pra quem nunca programou. Escrevi sem pensar neles… :-)

Bom… Existem pessoas que sabem programar e não programam. O difícil na arte de programar é pensar, porque o resto é escrever em inglês e se acostumar com uma sintaxe rigorosa.

Comecei ontem a ensinar um amigo a programar em C para participar da OBI 2007, que foi anunciada nessa semana. Eu poderia ensinar Pascal, que é mais que suficiente para olimpíadas (quem conhece o André Linhares entende o que eu quero dizer…), mas resolvi ensinar C porque eu me embabacaria no Pascal e no C eu vejo os blocos mais “definidos” com as chaves; aqueles begins e ends “sujam” o código. E como diz o lema do sistema desse blog, code is poetry.

O reverendo e meus leitores mais novos devem estar se perguntando: como o Tiago é capaz de fazer essas loucuras? É verdade que fiquei um bom tempo sem escrever sobre programação, mas adoro isso! É lazer pra mim e essa também é a minha profissão, já que eu não consigo viver desse blog (por culpa sua que não clica nos meus anúncios…). Só quando começo a brincar é que lembro como é divertido e acho que é porque eu me sinto “no poder”. :-)

Mas voltando ao assunto… Esse meu colega é campeão regional de matemática e tem uma facilidade incrível para matérias exatas (e pras humanas mais ainda, eu acho). Eu estava sem nada pra escrever aqui no blog e resolvi escrever sobre o que eu vou ensinar pra ele amanhã: arrays e for.

Meu aluno está resolvendo a prova da Programação Nível 1 da OBI2005. Ele já resolveu a Frota de Táxi e agora precisa resolver o problema Campos de Minhoca.

O problema é que, pela primeira vez, ele se depara com uma situação em que tem que receber como entrada uma tabela completa! Sugeri que ele usasse dois while, um dentro do outro. Ele pensou um pouco e conseguiu fazer o seguinte código:

scanf("%d %d", &n, &m);
 
natual=1;
while (natual<=n) {
	matual=1;
	while (matual<=m) {
		scanf("%d", &valor);
		matual=matual+1;
	}
	natual=natual+1;
}

Perfeito. Era o que eu queria que ele fizesse. Mas agora entenda sua situação: como armazenar todos esses números pra depois trabalhar com eles?

Dessa maneira, cada vez que recebemos um novo elemento da tabela, colocamos numa variável valor e ao final do recebimento da entrada ficaremos apenas com o último elemento da tabela.

E então entram os arrays…

Arrays são matrizes de matemática ou, numa língua muito mais fácil, tabelas. Vamos supôr que eu receba 1000 valores e queira saber qual é o maior deles. Imaginem como seria para declarar suas variáveis, recebê-los e tratá-los:

int var1, var2, var3, var4, ..., var1000;
 
scanf("%d", &var1);
scanf("%d", &var2);
scanf("%d", &var3);
scanf("%d", &var4);
...
scanf("%d", &var1000);
 
if (var1>maior) {
	maior=var1;
}
 
if (var2>maior) {
	maior=var2;
}
 
if (var3>maior) {
	maior=var3;
}
 
...

Impossível! Totalmente inviável. Então alguém teve a brilhante idéia de criar um elemento que guarda várias variáveis de uma vez. Então surgiram os arrays. Você cria uma só variável e na sua declaração coloca o número de elementos que ele tem dentro de chaves.

int var[1001];

Depois para receber os valores você pode então simplesmente usar o while como usou no exemplo do Campos de Minhoca:

int var[1001], indice;
 
indice=1;
while (indice<=1000) {
	scanf("%d", &var[indice]);
	indice=indice+1;
}

E para ver qual é o maior deles basta usar mais um while:

indice=1;
while (indice<=1000) {
	if (var[indice]>maior) {
		maior=var[indice];
	}
}

Mas peraí… Então como faríamos no Campos de Minhoca? Lá não temos só uma lista de N números, mas uma tabela mesmo, com altura e largura. É simples, basta fazer com que cada índice dessa lista seja outra lista.

int tabela[1001][1001];

Assim, podemos acessar todos os elementos e pra saber o elemento da coordenada 5, 23 basta usar a variável tabela[5][23].

Aí aquele primeiro código do Campos de Minhoca torna-se:

scanf("%d %d", &n, &m);
 
natual=1;
while (natual<=n) {
	matual=1;
	while (matual<=m) {
		scanf("%d", &valor[natual][matual]);
		matual=matual+1;
	}
	natual=natual+1;
}

As variáveis [n,m]atual vão crescendo e preenchendo a tabela. :)

Só que acontece que se programássemos dessa maneira gastaríamos uma porção de códigos e ficaríamos confusos pra trabalhar com arrays, tendo que sempre verificar os índices e acabaríamos errando bastante. Então criou-se o for. O for é uma simplificação desse tipo de while. Você diz que:

para todo natual de 1 a n, faça:
	alguma coisa
fim-para

Escrever for em Pascal é super divertido, porque você se sente falando com o computador:

for i:=1 to 100, do begin
	código aqui
end;

No C existe uma sintaxe mais versátil, mas que pode ser um pouquinho mais difícil de entender no início:

for (atribuição; condição; incremento)

A atribuição é onde você coloca o primeiro valor do índice. A condição é a condição para que o enquanto continue funcionando. O incremento é o que ele deve fazer ao final de cada loop (geralmente é aumentar um).

Então, ao invés de fazer esse while:

indice=1;
while (indice<=1000) {
	scanf("%d", &var[indice]);
	indice=indice+1;
}

Você pode escrever:

for (indice=1; indice<=1000; indice=indice+1) {
	scanf("%d", &var[indice]);
}

E como resolver a parte da entrada do Campos de Minhoca sabendo disso?

Simples… Basta colocar um for dentro do outro:

scanf("%d %d", &n, &m);
 
for (i=1; i<=n; i++) {
	for (j=1; j<=m; j++) {
		scanf("%d", &matriz[i][j]);
	}
}

Observação 1: Escrever variavel++ é a mesma coisa que escrever variavel=variavel+1.

Observação 2: Geralmente utiliza-se i para o primeiro for, depois j, k, l e eu nunca tive que passar do l. :)

Observação 3: Se eu queria um vetor de 1000 posições lá em cima, por que eu declarei 1001? Bom… O C conta a partir de 0. Quando eu peço 1000, ele vai me dar um vetor de 0 a 999. Já que eu queria ter o var[1000] eu precisei declarar de 1000+1=1001.

Ficou claro ou muito confuso? Se deu pra entender isso aí, agora é só mandar a ver no resto do problema! :)

Resultado da OBI2006

ATENÇÃO: Este conteúdo foi publicado há 11 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Em breve, estarei divulgando o how-to: Como perder uma viagem, um curso e uma oportunidade de representar o Brasil numa olimpíada internacional por um erro de digitação… :(

Um dia depois do prazo que consta no regulamento, a Comissão Organizadora da OBI2006 divulgou o resultado da modalidade programação. Para minha surpresa, fiz 20 pontos: 10 no Lobo Mau e 10 no Penalidade Mínima.

No último post eu mencionei que estava mal no dia da prova e nem fiz o último problema, mas não esperava tão poucos pontos. Aí baixei os testes do problema Lobo Mau e, com poucos testes, percebi que o erro do meu programa estava na entrada. Os arquivos que a OBI está usando estão no formato DOS (tem um caracter estranho além do n a cada quebra de linha) e por isso o meu programa não pegava corretamente os dados (ele pega todos os caracteres da matriz com scanf(“%c”); e o caracter de quebra de linha da mesma maneira). Já mandei o pedido de correção ontem a noite mesmo e eles já disseram que vão recorrigir.

Maldito erro de digitação!

Agoca… O pcoblema sécio veio depois. Ao lec o ródigo da minha solução*, pecrebi que eccei um racartec no acgumento rondirional de um loop! Tcoquei um “r” (rê) poc um “c” (ecce) (veja a linha 63 do ródigo que está linkado no astecisro), racarteces que signifiravam as linhas e rolunas da matciz, cespertivamente. Maldito ecco de digitação!

Corrija a frase acima, JavaScript! (são as inutilidades que o vício em linguagens client-side pode fazer…)

Se eu não tivesse trocado esses caracteres, tiraria 30 pontos a mais do que eu já devo tirar com a solicitação das quebras de linha: 110 pontos, o suficiente para participar do curso e da prova Seletiva para IOI.

* Minha solução para o problema Lobo Mau: lobo.c

Bom… Já que é a lógica do problema que é o desafio na OBI, vocês não acham que erros de digitação deveriam poder ser corrigidos? Além disso, acho que eles podiam somar essa nota com a nota da primeira fase (mesmo que ela tivesse um peso bem menor).

Eu já esperava ir mal, mas pensei que os 100 pontos do Lobo Mau estavam garantidos, pelo menos. :(

Por enquanto é isso aí… Me ferrei, mas agora pelo menos nunca mais vou errar uma coisa dessas numa prova de programação e nunca mais vou comer no Mc Donalds antes de uma prova… (tô tentando ser otimista, mas tá difícil… hehehe) Parabéns pra quem passou e boa sorte! Embora eu não tenha gostado do resultado, na verdade não tenho motivos lógicos para reclamar. Vacilei na segunda fase mesmo e provas são sempre traiçoeiras (com certeza elas não são a melhor maneira de avaliação).

Como representar um algoritmo?

ATENÇÃO: Este conteúdo foi publicado há 12 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

No primeiro artigo desta série, expliquei o que é um algoritmo e até citei exemplos do cotidiano, como acordar ou falar com outra pessoa. Talvez você nem tenha se dado conta, mas usando listas numeradas eu representei os algoritmos ali presentes, inclusive destacando a entrada e a saída de cada situação-problema. Porém, não é sempre assim que representamos algoritmos.

Não existe uma regra padrão para a representação de algoritmos. Cada pessoa escreve de forma diferente, mas o importante é ser legível e convencionado. Por exemplo, o livro Algoritmos: Teoria e Prática* traz nas páginas 14 e 15 convenções do pseudocódigo que utiliza no livro inteiro. Já eu, quando vou passar o mesmo algoritmo, utilizaria outro tipo de código, você pode utilizar outro, e por aí vai. Mas todos têm que ter o mesmo foco: legibilidade e fácil implementação para qualquer linguagem.

* A partir deste artigo, sempre que eu falar “Cormen”, “CLRS”, “Introduction to Algorithms” ou “Algoritmos: Teoria e Prática” estarei me referindo a um livro que é referência essencial nessa área. A versão que tenho (de onde tiro o número das páginas) é a tradução da segunda edição americana publicada pela Elsevier em 2002.

Os pseudocódigos costumam parecer um código em linguagem Pascal traduzido para a sua língua. :) Usam quase sempre estruturas que estamos acostumados a usar na programação, como se, enquanto, para, arrays, etc. Eles existem para que o algoritmo seja de fácil leitura para qualquer programador, que programe em qualquer linguagem “normal”. Veja o pseudocódigo do Insertion Sort, um algoritmo de ordenação de vetores bastante simples:

para j \leftarrow{} 2 até comprimento do vetor, faça
    elemento \leftarrow{} vetor[j]
    i \leftarrow{} j - 1
    enquanto i > 0 e vetor[i] > elemento, faça
        vetor[i + 1] \leftarrow{} vetor[i]
        i \leftarrow{} i - 1
    fim-enquanto
    vetor[i + 1] \leftarrow{} elemento
fim-para

(Não se preocupe em entender o que ele faz, AINDA, pois veremos isso mais adiante)

Se você programa em qualquer linguagem, você não terá dificuldade em traduzir esse pseudocódigo para ela. O pseudocódigo é sempre uma maneira bem simples de escrever o código. Veja por exemplo, o mesmo código em C:

for (j=2; vetor[j]!=NULL; j++) {
    elemento = vetor[j];
    for (i = j-1; i > 0 && vetor[i] > elemento; i--) {
        vetor[i+1] = vetor[i];
    }
    vetor[i+1] = elemento;
}

Você deve ter percebido que ao invés de usar três linhas com uma declaração, um condicional e um incremento, eu juntei todos num só for. Mas por isso o algoritmo é bem simples e sempre parte do princípio de que a sua linguagem é simples. Veja só a implementação do código em Pascal e compare-a com a do pseudocódigo:

for j:=2 to comprimento, do begin
    elemento := vetor[j];
    i := j-1;
    while i>0 && vetor[i] > elemento, do begin
        vetor[i+1] := vetor[i];
        i := i-1;
    end;
    vetor[i] := elemento;
end;

Linha por linha ela é exatamente igual! A única diferença é que o pseudocódigo é traduzido… Geralmente os pseudocódigos são parecidos sempre com essa base e suas implementações não são muito diferentes. E vai ser sempre dessa maneira que eu vou representar os algoritmos (usando pseudocódigos e alguns traduzindo para C para mostrar implementações). No entanto, qualquer dúvida sobre essa representação, fique a vontade para perguntar através dos comentários.

Agora acabou definitivamente!

ATENÇÃO: Este conteúdo foi publicado há 12 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Acabou a OLIS e agora definitivamente o ano letivo. Comecei a rotina de estudos de leve… Por enquanto só relembrando aonde tinha parado: Brinquei um pouco de C, alocando memória, escovando bits até não aguentar mais; implementei alguns algoritmos em grafos (de problemas já anteriormente resolvidos, do site da OBI) e agora estou exercitando fluxos em rede. O primeiro passo foi me desviciar de usar busca em profundidade resolvendo vários programas anteriormente resolvidos de grafos agora com busca em largura e nessa próxima semana espero ter dominado o algoritmo de coloração, de bipartição e os fluxos em rede.

Pedi na Saraiva (temos que aproveitar o site inteiro em 12x sem juros e frete grátis) o livro Java – Como Programar, dos Deitel. Várias pessoas me recomendaram e acho que vai ser bom pra aprender Java de uma maneira mais “certinha” (não que pesquisando na internet não aprendemos de forma certa, mas com a didática de um livro tudo é bem mais fácil e a gente aprende as coisas numa ordem boa).

Estou acabando de reformular o site do Colégio, porque já que cada vez tem uma coisinha nova o design tava ficando muito cheio e o XHTML pouco acessível. Agora tá ficando mais clean e deve estar lá amanhã de tarde (só falta um pequeno detalhe: fazer funcionar em um troço da Microsoft que não pode ser considerado um navegador)


O que ando vendo por aí…

… além dos meus feeds. Agora eu criei um perfil público no Bloglines (idéia do Zé) e vocês podem ver meus feeds aqui.