terça-feira, 23 de maio de 2017

Ontem o alphago ganhou mais uma, vitória por meio ponto em cima do Ke Jie, campeão chinês. Antes que alguém ache que ele ganhou raspando, lembro que o algoritmo do alphago é tunado para maximizar a probabilidade de vitória, não para maximizar a diferença de pontos. Então é comum que a diferença seja pequena mesmo.
Na partida contra o Lee Sedol o alphago fez um monte de jogadas loucas e fora do comum. Eu estava esperando ver isso de novo, e aconteceu mesmo. Só que as jogadas doidas vieram do Ke Jie!
Isso faz sentido, e eu cantei essa bola na minha análise dos jogos contra o Sedol ano passado. O alphago tem dois estágios de processamento, uma rede neutral treinada com partidas profissionais, e um monte Carlo tree search. Se você fizer jogadas loucas, você neutraliza a rede neural, e briga só com o mcts. O Ke Jie estava tentando fazer isso (mas não foi o suficiente).
A impressão que eu tive na partida é que eu não sei mais jogar Go. Os dois estavam fazendo jogadas que até ano passado eram consideradas ruins (tipo invadir o sansan no começo do jogo, como assim?). Mas ouvindo os comentaristas parece que é assim que os outros estão jogando hoje em dia, eles aprenderam essas jogadas com o alphago e agora elas são mainstream.
Os comentaristas foram curiosos também, era claro que o ocidental comentando era mais forte que a chinesinha, mas eu entendia melhor os comentários dela (porque está mais próximo do meu nível, o ocidental é avançado demais pra mim). E a chinesinha falando era engraçado porque ela falava em inglês, mas com sotaque chinês, e usando termos técnicos em japonês (sente, dame, etc).
Também achei engraçada a contagem de pontos, a chinesa contou os pontos das brancas de um jeito muito louco, eu não entendi a conta dela haha. Mas o Ke Jie parecia estar entendendo.
A próxima é na quarta, vou assistir mas já não tenho muita esperança de ver o humano ganhando.


sábado, 13 de maio de 2017

Essa semana eu achei um bug em três compiladores diferentes!

Eu estava de boa otimizando o rgzip quando notei ele gerando um assembly bizarro. A função era equivalente a essa:

fn vecsum(v : &[u32]) -> u32 {
return v[0] + v[1] + v[2] + v[3] + v[4] + v[5];
}

O Rust tem como princípio sempre fazer bounds checking para evitar buffer overflow, isso é cool. Mas olha só o assembly que ele gera:

movq %rsi, %rax
testq %rax, %rax
je .LBB0_7
cmpq $1, %rax
je .LBB0_8
cmpq $3, %rax
jb .LBB0_9
je .LBB0_10
cmpq $5, %rax
jb .LBB0_11
je .LBB0_12

Um bound check para cada acesso! Claramente não precisava. Se você fizer só o bound check no v[5], então todos os outros garantidamente passam, porque o vetor é contínuo.

Reportei isso na comunidade de Rust e aí ficou mais bizarro ainda. Primeiro, o bug não aparece se você inverter a função:

return v[5] + v[4] + v[3] + v[2] + v[1] + v[0];

Segundo, não é um bug do Rust, é na camada mais embaixo do LLVM. A gente sabe disso porque um código equivalente em C++ no clang gera o mesmo bug:

struct Vec {
int len;
int* data;
};

inline int get(struct Vec* vec, int i) {
if (i < vec->len) {
return vec->data[i];
} else {
abort();
}
}

int sum5(struct Vec* vec) {
return get(vec, 0) + get(vec, 1) + get(vec, 2) + get(vec, 3) + get(vec, 4) + get(vec, 5);
}

Por fim, o bug não é só no LLVM, ele aparece também no gcc e o no icc! Confiram:


Já foi tudo reportado, agora é só esperar alguém consertar. Idealmente eu mesmo consertaria, mas infelizmente a vida é curta :(



sábado, 29 de abril de 2017

Eu estava com vontade de escrever um descompressor de gzip do zero, também estava com vontade de aprender Rust, aí pensei: por que não os dois ao mesmo tempo? O resultado é o rgzip:
A parte gzip foi relativamente simples, eu só segui os RFCs. Por dentro ele é um LZ codificado com Huffma, não tem muito segredo. Mas tem duas coisas curiosas sobre o formato.
A primeira é que ficou claro para mim que o Phil Katz escreveu a primeira versão em assembly. Tem partes do formato que são difíceis de escrever em linguagens de alto nível, mas são triviais para quem tem rot e shl.
A segunda é que o formato permite emular RLE, usando janelas para o futuro. Por exemplo, se o arquivo começa com AB, você pode colocar uma janela "volta 2 e copia 6", aí o output é ABABABAB.
Sobre a linguagem Rust, achei bem bacana. A idéia foi tentar construir uma linguagem focada em segurança, onde é impossível programar um bug. Ele faz isso colocando restrições bem severas no tipo de código que você consegue escrever, e usando compile-time checks para garantir isso.
Por exemplo, em C++ você pode fazer isso:
int *func () {
int x = 1;
return &x;
}
Esse código vai dar segfault porque x estava no stack, quando a função retorna o x já morreu. Em Rust isso nem compila, ele saca que o lifetime do &x está restrito ao escopo da função e não deixa você retornar o ponteiro.
Outro problema do C++ é assim:
class X {
X(int *p) : p_(p) {}
int *p_;
};
int *p = new int;
X x(p);
E aí, quem vai dar o delete *p, o X() ou quem chamou o X()? O Rust resolve isso com sintaxe própria para dizer quem é o dono do ponteiro. (E como ele sabe quem é o dono, você nem precisa dar o delete. Ele deleta sozinho quando o dono sai do escopo).
Tem mais um monte de manhas, achei bem legal. Outras características são:
- Ele usa o sistema de type inference do Haskell, e tem muitas ferramentas de programação funcional disponíveis.
- O const é invertido em relação ao C++. Por default, todas as variáveis são const, se você quiser alterar o valor de uma variável precisa declarar como mut (inspirado em linguagens funcionais provavelmente).
- A sintaxe lembra bastante o Go, mas ele possui generics, o que é uma grande vantagem! Generics + type inference permite pegar um monte de erros em tempo de compilação.
- Além de generics, ele tem também macros! Mas não são as macros podres do C, ao invés de preprocessar texto, as macros do Rust atuam em cima da syntax tree do Rust. Muito mais legal e ainda permite um tipo de "template metaprogramming".
- Ele não tem o tipo int! Todos os tipo precisam ser explicitamente declarados. Ao invés de int você pode usar u32 ou i16.
- E falando nisso, ele não absolutamente nenhum tipo de cast automático, nem para variáveis inteiras. Você precisa explicitamente fazer um cast para copiar um valor u8 para uma variável u32. Isso vem da filosofia dele de ser o mais explícito possível.
- A stdlib dele é pequena, mas tudo bem porque ele tem um pip-like no pacote default. É só dar um include que ele baixa e instala a lib externa sozinho.
- Em geral, é mais difícil programar em Rust que em Go, C++ ou Python. Mas tem um motivo, é que você é obrigado a escrever um programa sem bugs sempre, senão não compila. Um monte de coisas nas outras linguagens só são fáceis porque você pode ignorar side-effects ou tratamento de erros.
- Inclusive, Rust não tem exceptions. Todo o tratamento de erros é feito com o Option<> e Result<> do Haskell (que colocaram recentemente no java também). Acho isso muito, muito melhor que retornar tuplas como no Go.
- Ele não tem goroutines, mas tem um sistema de threads usando canais para concorrência. Ainda não testei, mas o doc diz que ele pega deadlocks em tempo de compilação. Veremos.
- Ele também não tem garbage collector, mas nem precisa porque o sistema de RAII, lifetime e ownership explicito toma conta da memória sem precisar de gc.
Recomendo dar uma olhada, achei promissor. Já está na versão 1.x então a linguagem está mais ou menos estável. Eu lembro que programei bastante no Go 0.x e os meus programas dessa época nem compilam mais, em Rust stable isso não deve acontecer.


quarta-feira, 7 de setembro de 2016

Custa nada avisar a galera: a brincadeira da vez é postar uma foto da primeira mensagem que você recebeu no gmail, pra mostrar como você é fodão e usava internet no tempo das cavernas e tal. NÃO FAÇAM ISSO.

Talvez você não saiba, mas essa é uma das perguntas de segurança da sua conta. Se por algum motivo você ficar com a conta travada (por exemplo, mudou de celular, aí não consegue receber o otp, e o email alternativo era um do ig que nem existe mais), então o único jeito de destravar a conta é ligando no suporte, e eles vão te fazer perguntas para confirmar. Por exemplo, qual era seu email alternativo e qual a data aproximada em que você criou a conta.

Se você postar a foto do seu gmail, você está dando metade da informação de graça pro hacker. Não faça isso.

(De quebra, não custa nada ir na página de segurança e imprimir uns otps para usar quando você estiver sem celular. Pode acontecer de você ter wifi mas não ter 3g, por exemplo numa viagem, e você não quer ficar travado para fora da conta por isso).


domingo, 7 de agosto de 2016

No desfile dos atletas a Ila Fox estava falando que deve ser emocionante ser um dos atletas que vai representar o seu país, aí disse "ah, eu sei mais ou menos qual é a sensação!".
Como assim?, ela perguntou. Veja, eu nunca fui na olimpíada de esporte, mas já fui na olimpíada de matemática! Foi na Olimpíada Brasileira em 1993, onde ganhei medalha de prata.
A parte do mais ou menos é que eu nunca representei o país de fato. Quem ganhava medalha na olimpíada brasileira era indicado para ir na Olimpíada Internacional, e de fato eles me chamaram.
Mas tinha um detalhe: a comissão organizadora não tinha dinheiro para pagar a minha passagem até Hong Kong, onde seria o evento! Como eu também não tinha dinheiro, acabei cedendo minha vaga para o próximo na fila.
Hoje em dia seria mais fácil, só ir num crowdfunding qualquer e fazer uma vaquinha. De fato, sempre que eu vejo algum aluno pedindo grana para ir em olimpíada eu faço questão de contribuir.
De curiosidade, eu resgatei do backup a prova original da época. Eu fechei essa prova, fiz todas as questões, mas peguei a medalha de prata no desempate. (Quem ganhou o ouro naquele ano foi o Douglas Cancherini).


quinta-feira, 4 de agosto de 2016

Não sei se já mencionei, mas minha mãe costumava bater em mim para sair de casa. Olha só, eu tinha um microcomputador e uma biblioteca grande, sair de casa pra quê?
Claro que isso foi antes do Pokemon Go. Agora eu já saí de casa dois dias seguidos! A Ila Fox até achou que eu deveria escrever um diário, então aí vai:
DIA 1
Eu estava no Uber voltando pra casa quando o jogo saiu. Decidi que ia jantar fora e capturar pokemons no caminho, então peguei meu charmander starter e fui.
No restaurante mexicano já peguei um Poliwag. Os garçons juntaram todos em volta pra ver. Um deles até mencionou "tô ligado esse aí, vira Poliwhirl" (tava manjando mais que eu!)
Depois da janta fui até a igreja onde tinha um marcador, eu não sabia o que fazer com o marcador. Tinha um tiozinho na frente da igreja também. Nós trocamos uma idéia e descobrimos, tinha que girar o marcador, libera pokebola. Boa!
Tinha um marcador rosinha no mapa e resolvi ver o que era. No caminho, passei por uns cinco jogadores (e isso foi tipo uma hora depois do jogo ter lançado). Felizmente o bairro aqui é seguro para andar, o aluguel é caro mas pelo menos dá para caçar pokemon no sossego.
O marcador rosa eu descobri que era spawn de pokemon, alguém usou um item ou something. Tinha um Pinsir na frente de um restaurante coreano que eu nem sabia que existia (nota mental, voltar lá e ver se posso experimentar tô-mandu-ku).
Segui em outra direção, vi um Caterpie mas não conseguia clicar nele no jogo. Não ia de jeito nenhum. Achei que tinha tanta gente jogando que ou o server baleiou, ou a ERB da tim não deu conta de segurar tanto celular ligado.
Tinha um grupinho na esquina e resolvi perguntar se para eles funcionava. Um dos guris me explicou que às vezes acontece isso, tem que sair e entrar de novo no jogo. Testei e funcionou! Perguntei se os guris já se conheciam, nope, todos eles tinham se conhecido ali na esquina. Avisei que tinha um Pinsir três quarteirões pra baixo e eles foram lá contentes.
Terminei a ronda e voltei pra casa. Entrando no elevador eu vi um gurizinho saindo com celular na mão. Batata! Perguntei se ele tinha pego Pikachu, e ele disse que sim! Eu estava disposto a sair de novo se fosse pra pegar Pikachu, então perguntei onde que ele pegou. "Foi em Times Square", ele disse. - "Times Square, New York?" - "Isso!" - "Dammit, muito longe!"
Achei que tinha acabado pelo dia, mas dei sorte, tinha um Staryu no banheiro! Esse foi o último do dia.
DIA 2
Por motivos de força maior eu fui almoçar às 16h30 apenas. Já que ia sair, aproveitei para caçar. No caminho já vi um guri caçando pokemon de skate. Mano, eu tenho medo de deixar o celular cair enquanto estou andando, imagina andando de skate. Mas o guri tava de boa.
Na esquina, outro guri. "Pegou pikachu?", eu perguntei, e ele "já peguei, foi meu primeiro!". Como assim primeiro? "Quando você começa o jogo, se você fugir dos três iniciais aparece um Pikachu", ele respondeu, olhando com aquela cara de "adultos são burros mesmo".
Depois de mais meia dúzia de Pokemons, cheguei no nivel 5, agora posso ir em estádio! Fui em um aqui perto, na hora de escolher o time eu fiquei com dó e peguei o time vermelho. Nesse bairro ninguém vai escolher o time vermelho.
Continuei até uma praça onde tem dois pokestops juntos. Tinha uma galera ali, tipo mais de vinte guris. Todo mundo caçando pokemon quando eu olho pro lado e vejo um filhote de gato. Gato cinza, bonitão, sedoso, não resisti e capturei ele. Perguntei se era de algum dos vinte guris, ninguém reconheceu, então fui pra casa.
Chegando em casa, diagnóstico. Gata filhote, porém gordinha, mansa, sem medo de humanos, provavelmente fugiu de alguém. Nós a batizamos temporariamente de Vesicula. Side mission: achar o dono!
Ila e eu voltamos para a praça dos pokestops. Notamos que agora, além dos caçadores de pokemons, estava cheio de casais adolescentes. Deduzimos que falaram para os pais que iam caçar pokemon, espertos eles.
Batemos de porta em porta até que nos indicaram uma casa no fim de uma vila. Lá dentro tinha a dona Lindalva falando que a gata sumiu. Nós achamos, peraí que vamos trazer!
Voltamos para casa, colocamos a Vesicula em uma caixa de transporte, e a levamos até a dona Lindalva. Nesse meio tempo os filhos tinham chegado da escola. O menorzinho falou "olha a gata voltou!". Depois meteu uma bifa na gata e disse "não foge mais!". A Vesicula olhou pra mim com raiva e eu pensei "Desculpa Vesicula, eu não sabia".
Antes de ir para casa, passei na praça dos pokestops com a caixa de transporte vazia e anunciei pra galera "trouxe uma caixa para transportar os pokemons capturados!". Todo mundo riu. つづく


sexta-feira, 29 de julho de 2016

No fim de semana nós fomos jantar com o Lucas Radaelli, que tinha acabado de voltar de um torneio de xadrez (ele gosta de xadrez porque é um jogo onde um cego pode competir de igual para igual com alguém que enxerga).
Só que aí ele me pediu pra explicar quais são as jogadas típicas do Go, e eu pensei, raios, como eu explico isso? O jeito foi descrever com os coordenadas, eu fechei os olhos e comecei assim:
"Uma jogada típica é tentar fazer dois olhos. Vou falar as coordenadas, primeiro x, depois y (que burro eu). Um olho é uma configuração onde os brancos estão em 0-1, 1-1, 1-0, e os pretos estão em 0-2, 1-2, 2-1, 2-0. Aí o preto joga em 0-0 e come, porque cerca as brancas por dentro. Mas se os brancos estiverem em 0-1, 1-1, 2-1, 3-1, 1-0, 3-0, então mesmo que o preto esteja cercando por fora, não tem como comer, porque teria que jogar em 0-0 e 2-0 ao mesmo tempo, e ele só joga uma por vez"
No fim ele entendeu, mas não sei se na hora alguém sacou por que eu estava me achando burro. É que eu mencionei que ia falar primeiro o x e depois o y, mas isso era irrelevante! Se você imaginar o tabuleiro transposto, dá na mesma. Eu só percebi isso depois que já tinha falado haha.


quinta-feira, 28 de julho de 2016

Eu já passei dos 40 anos, então já deu tempo de acumular um bom repertório de histórias bizarras que aconteceram comigo. Já levei mordida de leão na África, já profanei tumba de 2400 anos na Turquia, e daí em diante.
Mas tem uma história que ninguém bota fé que aconteceu de verdade, que é a história do furacão que levou o circo embora.
Teve uma época que eu morei na Praia Grande (litoral de sp). Eu era pequeno e não tenho muitas lembranças da época. Mas uma das poucas lembranças que eu ainda tenho, é de que teve um fim de semana onde passou um furacão pela cidade, tão forte que levou embora o circo que estava montado na praia.
Eu até estava achando que era memória falsa, mas aí eu liguei pra minha mãe e ela confirmou a história. E mais, não só o furacão levou o circo, como levou as janelas do nosso apartamento junto. Começou a entrar loucamente água do mar pela janela, inundou tudo, e nós tivemos que ficar um tempo na casa da vizinha.
Aí clicou! Disso eu lembro sim, e eu lembro porque a vizinha colecionava Tio Patinhas, enquanto o furacão comia solto eu estava lendo os gibis dela. E vou além, lembro que um dos gibis que tinha saído naquela época era um especial do Peninha com a primeira aparição do Biquinho.
Então agora eu tenho um timeframe: isso foi por volta de julho de 1982. Agora que eu tenho uma data, dá pra ir na biblioteca procurar os jornais da época, algum deles deve ter a notícia de quando o furacão levou o circo 


quarta-feira, 20 de julho de 2016

Tava aqui estudando grego e aprendi uma frase muito útil: MOLON LABE.
Consta que o Leonidas estava de prontidão na passagem das Thermopilas, quando o Xerxes chegou e anunciou "Renda-se, e me dê suas armas". Aí o Leonidas respondeu MOLON LABE, que do grego arcaico significa "vem pegar".
Muito útil para ser usada em uma variedade de contextos!


domingo, 17 de julho de 2016

Falando em tradução, mês passado fizemos um encontro do povo do LSI/USP, e eu aproveitei a oportunidade para pegar um autógrafo do Arnaldo Oka no meu Hikaru no Go #1 (depois da USP, o Oka virou o mestre tradutor dos mangás da JBC).

Em retrospecto, trabalhar no LSI foi muito importante num aspecto pouco usual. Eu estudei eletrônica num dos melhores colégios técnicos do país, depois estudei engenharia num dos melhores cursos do país. O efeito colateral disso é que com tanta overdose de exatas, eu tinha tudo para ser um desses babacas que acha gente de humanas só serve para fazer miçanga.

Felizmente, trabalhar em um laboratório interdisciplinar curou isso. Curou tão bem, que hoje em dia eu sou casado com a Ila Fox, que é formada em artes plásticas. Fora do trabalho, eu passo mais tempo com gente de humanas do que com gente de exatas!



Povo me perguntou se a cor dos escudos no Aleste 2 do MSX faz alguma diferença. Eu não sabia, então fui procurar o manual, e olha só! Não apenas faz, como os escudos tem até nome! Aqui o original e minha tradução:
「シールド・イエロー」   防御のみ。250の耐久力があります。
「サポート・レッド」    耐久力200。ボスキャラの攻撃を受けると誘導弾となってボスキャラにダメージを与えます。
「アシスト・ブルー」    耐久力150。通常弾を貫通弾にします。
「グラヴィ・ティ・ブラック」耐久力120。アレスタ2の攻撃力が50%UPします。
"shield yellow" Defense only, has 250 durability.
"support red" Durability 200, becomes a guided missile that damages boss ships when hit by the boss ship.
"assist blue" Durability 150, normal bullets become piercing bullets
"gravity black" Durability 120, increase offensive ability of Aleste 2 by 50%.
Thx Tornado pela ajuda na tradução.


Povo tava falando de filme de terror, eu comentei que não tenho medo. Eu não acredito em fantasma, em aparição, em nada disso, vou ter medo de quê?
Só senti medo assistindo à Bruxa de Blair.
Tem uma cena apavorante onde eles acordam de manhã, e descobrem que um dos caras jogou fora o mapa, porque se eles estavam perdidos era porque aquilo era inútil.
Imagina só, perceber subitamente que você está cercado de idiotas e que sua vida pode depender deles. Isso sim me dá medo. Fantasma? pft.

Dia desses eu fui melhorar meu tempo no SUMFOUR do SPOJ e descobri que meu script de submissão automática não funciona mais. Eles fizeram um redesign e mudaram o protocolo de autenticação.
Aí ontem me deu um siricutico e fiz a engenharia reversa do site, agora tenho um script novo que funciona direitinho. Você digita:
python submit.py SUMFOUR.cc
Com isso ele se vira para autenticar e submeter. O melhor do script é que se você faz um include usando "lib.h" ao invés de <lib.h>, ele abre o script inline para você. (O spoj só aceita um arquivo por vez, então você faz direitinho local e o script concatena tudo antes de mandar).
Dica importante: se você é pythonzeiro e ainda usa urllib2, larga dessa vida e usa requests que é muito melhor! Esse script seria insanamente mais complicado se fosse feito com urllib2.
Continuando o resgate dos backups, achei o EP2-94 da Poli em um backup de papel (tive que digitar o programinha para salvar no github).
Não tem como negar que o ensino na Poli era forte. Os alunos estavam no terceiro mês de aula, muitos nunca tinham usado um computador antes, e o exercício era fazer um sistema completo para achar as forças de uma treliça.
Se eu peço a mesma coisa numa entrevista para desenvolvedor senior, o cara surta e nunca mais dá notícia haha.
Consegui resgatar não apenas a minha solução mas também o enunciado original, completo com as minhas anotações de margem:


domingo, 10 de julho de 2016

Resgatei mais um programinha dos backups: esse calcula qual é maneira de calcular sqrt(7) usando régua e compasso minimizando o número de traçados. Quer dizer, calcularia, se funcionasse!
A história dele é que certa vez o Joao Kogler me desafiou a calcular sqrt(7) com compasso. É fácil, eu disse, você começa com um triângulo retângulo de catetos iguais a 1, aí vai traçando perpendiculares pelos vértices. Depois de algumas iterações, sqrt(7) aparece como a última hipotenusa da espiral.
Mas esse método é ruim, ele me disse! Para traçar uma perpendicular você precisa usar o compasso duas vezes por iteração, tem um jeito que você usa uma vez só. Começa com duas paralelas espaçadas por uma unidade, aí traça o compasso para cima e para baixo alternadamente. Isso também chega em sqrt(7) no final de uma maneira mais simples!
Imediatamente o que me veio na cabeça foi "tá, mas isso é ótimo?". Na teoria é fácil checar isso, é só construir um forward chaining com as regras de construção do Euclides e deixar rodando, eventualmente ele bate na construção mínima de sqrt(7).
Mas na prática não deu certo! Eu subestimei a complexidade do problema. Para o forward chaining funcionar, você precisa checar a cada número se ele está presente na lista de números já encontrados. E comparar dois números construtíveis sem usar os reais é complicado!
Por exemplo, quem é maior, sqrt(7)+sqrt(2) ou sqrt(3)+sqrt(5)? Você precisa de vários passos para descobrir:
sqrt(7) + sqrt(3) ? sqrt(3) + sqrt(5)
7 + 2*sqrt(21) + 3 ? 3 + 2*sqrt(15) + 5
2 + 2*sqrt(21) ? sqrt(15)
4 + 8*sqrt(21) + 4*21 ? 15
8*sqrt(21) ? 15 - 4 - 2*21
Pronto, o lado de lá é negativo então sqrt(7)+sqrt(2) é maior que sqrt(3)+sqrt(5). Meu programa tinha que fazer isso para cada par de números gerados, então ele estourava exponencialmente antes de chegar no sqrt(7) !
Hoje em dia acho que eu usaria o valor real da expressão como um hash para deixar mais rápido (e mesmo assim daria problema rapidinho com overflow do double, mas provavelmente chega no sqrt(7) antes do overflow).

sábado, 9 de julho de 2016

O algoritmo predileto do Knuth
Meu repositórios oldies tem muitas das coisas que já programei, mas não tem tudo. Uma boa parte está perdida por aí em backups e hard prints. Semana passada eu recuperei um pacotinho que tinha uma lib legal que fiz em 2011, e a história dela começa com o Knuth.
A única vez que vi o Knuth ao vivo foi em 2011. Na ocasião, perguntaram qual o algoritmo predileto dele, e ele disse que era o BDD (binary decision diagram), porque ele tinha acabado de publicar um livro sobre isso e o algoritmo que você mais gosta, em geral, tende a ser que o você acabou de aprender. Bom, se era o preferido do Knuth tinha que ser divertido, eu não podia deixar de implementar né?
O BDD é uma estrutura de dados que serve para guardar uma fórmula booleana em memória, de maneira otimizada. Lembra um pouco o mapa de Karnaugh, mas escala muito melhor, Karnaugh você não faz com mais 3 variáveis, BDD você chega em centenas fácil.
Intuitivamente você espera que guardar toda a fórmula em memória ocupe espaço exponencial (2^número de variáveis). E é isso mesmo! PORÉM, esse é o valor esperado para fórmulas aleatórias. As fórmulas da vida real costumam ter estrutura, e essa estrutura aparece magicamente quando você monta uma BDD. Na prática elas são bem melhores que o exponencial.
A BDD tem várias utilidades, mas eu suspeito que o Knuth gosta delas porque são ótimas para resolver puzzles! No livro Selected Papers on Fun And Games, o Knuth usa uma BDD para resolver o Slitherlink. Na minha implementação, eu usei para resolver o Torto Reverso. A figura mostra o BDD montado para uma instância pequena de Torto Reverso.
(Essa era resposta que eu esperava no ricbit jam #3, que até hoje ninguém resolveu. Eu declaro então o concurso terminado por falta de participantes).
Abaixo o link da lib e a wiki correspondente para quem quiser saber mais:
https://github.com/ricbit/Oldies/tree/master/2011-05-bdd https://en.wikipedia.org/wiki/Binary_decision_diagram


Acabei de assistir à primeira aula de Análise de Algoritmos! E por primeira aula eu quero dizer a primeirona mesmo!
O Knuth inventou o termo "análise de algoritmos" em 1969 quando virou professor em Stanford e deu sua aula inaugural. Na época ninguém pensou que seria algo histórico, então ninguém filmou. Aí, para remediar esse erro histórico, esse ano o Knuth fez um remake da aula: juntou o que tinha de anotações da época e recriou a palestra tal como ela tinha sido feita originalmente. Para ficar mais fiel, até colocou uma peruca ridícula haha.
A aula em si é animal, ele pega um algoritmo bobo (calcular o máximo de uma sequência), e faz a análise completa. Povo hoje em dia segue a cartilha do Cormen e fala "ah isso aí é O(n)". Mas o Knuth não quer saber só o pior caso, ele quer saber a média e o desvio padrão. Aí ele passa por stirling numbers, funções geradoras e chega no resultado final (a média é o harmônico menos um, ou seja, praticamente logarítmico).
A parte bacana é que ele diz que a matemática que ensinam tradicionalmente não serve para analisar algoritmos, então ele vai criar um curso novo de "concrete mathematics" só para isso; e abre vagas para orientados que estejam dispostos a ir na lixeira do prédio de computação pegar todas as saídas dos compiladores, para fazer um mutirão e descobrir se conseguiam usar as técnicas novas de análise para melhorar programas da vida real. ("ir na lixeira pegar programas" parece estranho, mas é que na época os programas eram em fita perfurada que iam para a lixeira).
Achei animal, vale a pena assistir!

quinta-feira, 7 de julho de 2016

O que você fez com o seu primeiro salário?

Eu não fiz nada. Nem saquei o cheque. Quando chegou o segundo salário, aí sim eu juntei os dois e comprei um kit multimídia (que vinha com uma soundblaster 16 e um drive de cd). Lembro que com o troco eu comprei meu primeiro cd, um do Chopin que tinha a Polonaise.

Nessa época a minha frustração era ter saído do msx, que tinha cpu fraca mas som polifônico, e migrado pro pc, que tinha cpu rápida mas som via speaker que só fazia blips e blops.

Naturalmente, três dias depois de comprar a placa de som eu já tinha escrito um conversor para tocar o comando PLAY do msx no PC:

https://github.com/ricbit/Oldies/tree/master/1995-11-sbplayer

Uns meses depois saiu o primeiro emulador de msx que era open source, o fmsx. Ele não tocava a música dos jogos ainda, mas dava pra hackear e escrever no disco o conteúdo dos registros do psg. Com o arquivão de dump, eu escrevi um player para ele. Esse foi meu primeiro emulador, fez 20 anos mês passado! A interface foi claramente inspirada no modplayer original.

https://github.com/ricbit/Oldies/tree/master/1996-06-psgplayer

A parte bacana desse emulador é que ele rodava com o x86 em modo real, culpa do turbo c velhão que eu usava. Mas os arquivos com dump de música passavam fácil de 1Mb, e em modo real o máximo que você endereçava era 640kb, mesmo usando far pointer.

A solução foi ir lá no lendário x2ftp.oulu.fi, que era O POINT para game development na era, e pegar uns docs explicando como funcionava o XMS. Com os docs em mãos eu fiz overload no operator[] do c++ para permitir emulação de memória linear, ficou bacaninha para a época:

https://github.com/ricbit/Oldies/blob/master/1996-06-boss/linmem.h

No x2ftp eu aprendi um monte de coisas, ele não está mais online mas tem um mirror histórico:



http://ftp.lanet.lv/ftp/mirror/x2ftp/msdos/programming/


sexta-feira, 1 de julho de 2016

Chegaram meus livros autografados!
The Martian com autógrafo do Andy Weir
A Storm of Swords com autógrafo do George RR Martin
Cryptonomicon com autógrafo do Neil Stephenson
Realms com autógrafo do Tony Diterlizzi e do Neil Gaiman
Dessa vez foi super rápido, pedi semana passada e já chegou. O truque é que eu pedi para escreverem BOOKS/LIVROS na caixa, então passou reto pela receita.


quarta-feira, 29 de junho de 2016

Terminei de ler Efeito Entropia. Achei bem legal, o Ricbit de 40 agradece ao Ricbit de 15 pela sugestão de livro!
Esse livro é uma daquelas obras onde eu simpatizo demais com o vilão. Normalmente vilões querem dominar o mundo, ou realizar algum plano de vingança, coisas assim. O vilão de Efeito Entropia é um cientista que fez uma teoria bacana e queria publicar, mas nenhum periódico aceitava, então ele teve que apelar e matar algumas pessoas para garantir a publicação. Super entendo.
Outro vilão que eu simpatizo é o Dr. Octopus no Homem-Aranha 2 (filme que ainda está no meu top 3 de filmes de heróis). O Dr. Octopus só virou vilão porque queria terminar um experimento e cortaram o funding dele; aí precisou roubar bancos para comprar a matéria-prima. Admiro muito, isso é que é dedicação à ciência!