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.

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 

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!

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:

「シールド・イエロー」　　　防御のみ。２５０の耐久力があります。
「サポート・レッド」　　　　耐久力２００。ボスキャラの攻撃を受けると誘導弾となってボスキャラにダメージを与えます。
「アシスト・ブルー」　　　　耐久力１５０。通常弾を貫通弾にします。
「グラヴィ・ティ・ブラック」耐久力１２０。アレスタ２の攻撃力が５０％ＵＰします。

"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.

https://github.com/ricbit/Oldies/tree/master/2016-07-spojsubmit

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:

https://github.com/ricbit/Oldies/tree/master/1994-05-polimac115

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).

https://github.com/ricbit/Oldies/tree/master/2011-01-geom

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!

https://vimeo.com/161783929/dba6a42ad3

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/

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.