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

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

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. つづく

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.

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!

Dia desses a página 33 Dias Sem Machismo postou uma mensagem perguntando qual foi a última autora que você leu. Fácil, eu pensei, foi a... hum... então... dammit. Não lembro. Eu leio tão poucas autoras que não consegui lembrar. Shame on me.

Fiz ao contrário então, qual a primeira autora que você leu? Isso eu lembro bem, foi a Vonda McIntyre! No comecinho da década de 90 a Editora Aleph publicava romances de Star Trek, o primeiro que eu li foi "Efeito Entropia". Provavelmente eu comecei a ler sci-fi com ele, certamente eu li Efeito Entropia antes de ler Fundação, Duna ou Senhor dos Anéis.

Na minha cabeça a história era animal, a Enterprise está circulando uma singularidade, onde o espaço-tempo se comporta de uma forma muito estranha, e o Spock tinha que resolver um mistério através do tempo. Fiquei com tanta saudade que acabei comprando de novo num sebo, comecei a reler agora.

A parte curiosa do romance é que foi nele que a Vonda inventou o nome do sr. Sulu! Três temporadas da série, e o Sr. Sulu só era chamado de sr. Sulu, que nem é um nome japonês (em japonês não tem a letra L). No primeiro capítulo ela conserta o erro: fala que ele se chama Hikaru Sulu. O nome depois entrou pro canon e ficou oficial.

Quem ficar curioso, o livro custa 10 merrecas nos sebos online.

Relendo Clash of Kings. Tem uma parte em que o Stannis acabou de tomar Storm's End e está marchando em direção a King's Landing; aí a notícia chega na Sansa e ela fica super ansiosa, tão ansiosa que sente até dores na barriga de tanta apreensão.

Mas nessa segunda leitura fica claro que as dores de barriga são na verdade cólica menstrual, ela só não sabia disso ainda! Nos capítulos seguintes elatem a menarca, confirmando a teoria.

Aliás, em certo trecho as partes externas da cidade estão todas pegando fogo, e o Hound comenta que se bobear até o Grande Septo de Baelor vai pegar fogo. A Sansa diz "bom mesmo, foi lá que meu pai morreu, por mim que pegue fogo em tudo". Na minha cabeça a Sansa é a única que não é warg; mas ó, rolou uma catiça aí hein?

Ontem eu ganhei acesso a um computador quântico real da IBM! Eles tem agora um website onde você pode submeter remotamente jobs para esse computador quântico, e mandam os outputs por email. Esse website é de acesso restrito, mas eu falei que era blogueiro de ciência e podia divulgar os resultados para os brasileiros em português (colou hehe).

Pois bem, o computador tem 5 qubits e é quântico para valer. Você não programa com linguagens de programação, ao invés disso, a interface é tipo um pspice, mas com portas lógicas quânticas ao invés de portas binárias. (Mas eu já aviso que se você tiver medo de álgebra linear com números complexos, não vai passar do básico).

O computador em si é bem rústico: além de ter que lidar com superposição e entrelaçamento, você ainda tem que pensar que saída é probabilística e tem ruído. Na prática, para ver resultados consistentes você precisa rodar o mesmo algoritmo 1024 vezes e ver na média o resultado.

Dos algoritmos que eu rodei, o mais fácil de entender é o algoritmo de Grover. Ele é o equivalente à busca linear (dado um vetor não ordenado, achar o índice do elemento procurado). Ele é O(n) em um comptador clássico, mas no quântico é O(sqrt(n)). O funcionamento é curioso, você começa com os qubits entrelaçados em todas as soluções possíveis, e rotaciona o espaço de modo que a solução desejada fica um pouco mais provável que o aleatório puro. Se você rodar esse bloco sqrt(n) vezes, dá para provar que a solução correta fica muito mais provável que todas as outras, aí você aplica o threshold e corta. Na wiki tem os detalhes:

https://en.wikipedia.org/wiki/Grover%27s_algorithm

No fim de semana eu quero tentar o algoritmo de Shor de fatoração quântica (ele é muito parecido com o Pollard Rho, mas a detecção de ciclo é feita com entrelaçamento).

O Euclides era foda pra caralho mesmo. Eu estava aqui de boa tomando banho quando me caiu a ficha de que os cinco postulados deles na verdade são propriedades do espaço. Olha só, na forma original eles são assim:

1. Por dois pontos passa um reta.
2. Uma reta sempre pode ser estendida indefinidamente.
3. Dado um ponto e um raio, você pode construir um círculo.
4. Todos os ângulos retos são congruentes.
5. Dado uma reta e um ponto fora dela, você pode construir uma paralela.

O Heath fala que o quarto postulado é esquisito, tinha outras afirmações equivalentes que ele poderia ter usado. Mas ele precisava do quarto nessa formulação exata, senão não tinha como descrever o quinto de forma não-ambígua.

Aí eu fiquei pensando se existem outras maneiras, e achei uma equivalente só com proposições sobre o espaço:

1. O espaço é contínuo.
2. O espaço é infinito.
3. O espaço é métrico.
4. O espaço é invariante a rotações.
5. O espaço tem curvatura zero.

Esses cinco postulados alternativos que eu bolei são equivalentes aos postulados do Euclides, você pode usar esses para provar os dele e vice-versa.

Para mim mostra que o Euclides manjava muito, ele não tinha essas noções modernas sobre o espaço mas achou uma maneira grega de dizer a mesma coisa!

Mindfuck do dia: ninguém sabe qual é a área do conjunto de Mandelbrot. Ninguém conseguiu calcular analiticamente, mas os melhores bounds colocam a área entre 1.66 e 1.71. Agora, se você usar um método numérico, a área é 1.506591884 com precisão no último dígito. Cadê esse 0.16 que falta? Ninguém sabe, mas a melhor teoria até agora é que...

(dramatic chipmunk)

... o contorno contribui para a área! A dimensão hausdorff do contorno do conjunto é 2, então ele é área-like, pode ser isso que os métodos numéricos não estão capturando.

(sim, eu fiquei estudando fractais enquanto não dava meia-noite)

Parece inacreditável, mas existe uma meta-máquina universal de Turing, capaz de computar *qualquer* função f:N->N, *incluindo as não-computáveis*, desde que você ache um universo paralelo apropriado!

http://jdh.hamkins.org/every-function-can-be-computable/

A demonstração em si não é difícil, mas eu vou dar uma simplificada aqui para ficar mais fácil de entender. Quem quiser ver a versão original, é só pegar no link acima que tem os detalhes (thx Joao Kogler pelo link):

Passo 1: Vamos relembrar o "teorema do reirom": existe um emulador capaz de emular qualquer sistema. Formalmente: as máquinas de Turing são enumeráveis, ou seja, para cada máquina você atribuir um número inteiro único. Com isso, você consegue construir uma máquina universal que tem como input o número da máquina que você quer emular, e o input original do problema que você quer resolver. Assim, você emula qualquer função computável.

Passo 2: Vamos relembrar que nenhum sistema formal é completo. Pelo teorema de Gödel, sempre existem proposições de um sistema que não admitem demonstração. E mais, mesmo que você pegue uma proposição e adicione com axioma ao sistema, ele continua sendo incompleto. Você pode adicionar infinitas proposições, sempre vai faltar uma.

Passo 3: Vamos relembrar que um sistema formal admite proposições que são independentes do sistema. Ou seja, tanto faz se você adiciona p ou não-p ao sistema, ele continua consistente. Exemplos conhecidos são o teorema das paralelas em relação aos outros axiomas do Euclides, ou a hipótese do continuum em relação à teoria dos conjuntos (ZFC).

Passo 4 (a pegadinha): Se você tem um sistema formal S onde tanto faz adicionar a proposição p ou a não-p, isso significa que, depois de adicionar a proposição, os sistemas S+p e S+não-p tem *um bit a mais de informação*. Para checar o valor desse bit, é só verificar qual proposição foi adicionada, se foi p o bit é 1, se foi não-p o bit é 0.

Passo 5 (a parte técnica): Se você conseguir construir uma sequência ordenável de proposições p_i, onde todas são independentes entre si, então você consegue adicionar ao sistema S uma string infinita de bits. Essa é a parte complicada da demonstração original, onde ele mostra como construir essa sequência. Mas o fato é que é possível, em qualquer caso.

Passo 6: Se você adicionou uma string infinita de bits ao sistema, então você codificou uma função binária f:N->{0,1} dentro do sistema. Agora é só escrever um algoritmo que, dado n, calcula f(n) através da enumeração das propriedades que você construiu dentro do sistema. Esse é um algoritmo universal que calcula qualquer função binária, até as não-computáveis!, dado que você codificou a função na unha, valor a valor. Assim como o input da máquina universal era o problema + o código da máquina que tem que ser emulado, nessa aqui o input é o problema + o sistema formal acrescido dos p_i que você codificou.

Passo 7: Obviamente, se você tem uma função f:N->{0,1}, então você também tem uma função f:N->N, é só usar um código de comprimento variável, tipo UTF-8.

Pronto, agora você tem um meta-algoritmo que calcula qualquer função. É só levar o algoritmo para um universo onde as regras são S+p_i que ele computa sozinho a função para você! Achar um universo paralelo fica como exercício para o leitor.

Agora as implicações do teorema:

1. Utilidade prática: nula

2. Você consegue codificar f:N->N, mas não consegue codificar f:R->R (Como você adiciona um bit por vez, o máximo que você consegue colocar é aleph-zero. Para suportar os reais precisaria colocar c).

3. Uma das funções não-computáveis que você pode computar é a parada de Turing. Então tem um universo aí onde você pode determinar exatamente quais das nossas máquinas de Turing param, e quais não param! Mas nesse universo, eles não conseguem calcular a parada das máquinas deles, só das nossas.

4. Se você estiver criando um universo do zero, é um jeito bacana de esconder um easter egg dentro da matemática que rege seu universo. Fica a dica aí pra quem for onipotente.

Você acha que o Euclides é grego ou que a Cleopatra é egípcia? Precisa escolher um, os dois ao mesmo tempo não dá.

Ambos viveram em Alexandria, que pelos critérios de hoje é claramente Egito. Se você levar em conta exclusivamente os critérios de geolocalização, os dois são claramente egípcios.

Mas Alexandria foi fundada por um grego e sempre teve cultura grega. Euclides viveu na época do rei Ptolomeu I, a Cleopatra era filha do Ptolomeu XII, são 200 anos de diferença mas ainda é o mesmo império fundado pelo Alexandre (que era discípulo de Aristóteles, grego de raiz). Se você levar em conta os critérios culturais, os dois eram claramente gregos.

Acho que a treta só existe porque a Cleopatra era populista e queria muito ser a rainha do povo, inclusive ela foi a única da dinastia inteira que aprendeu a falar egípcio (todos os outros Ptolomeus só falavam grego). Ela se vendia como egípcia, mas era só propaganda para ganhar confiança da massa. Na minha cabeça, tanto o Euclides como a Cleopatra são gregos.

Comprei um kit grego: régua, compasso, lapiseira, prancheta e papel de gramatura alta.

Essa é a parte legal de ser adulto, você pensa "puxa estou com vontade de comprar um compasso", aí vai ali na esquina, compra, e pode passar o resto da noite feliz agregando conhecimento.

Pausa para o estudo de grego arcaico. O substantivo "cinco" é πεμπασ, e o verbo "contar" é πεμπαζειυ. Daí você deduz que no tempo do Homero, "contar" era "cincar", e portanto é uma boa evidência de que eles usavam base 5 ao invés de base 10!

(O Heath concorda com o raciocínio então deve ser isso mesmo).

Desenho da noite da Ila Fox: porque todos gostamos de emus! Na real só não gosta de emus quem ainda não conhece, o bracinho dele é igual ao do T-Rex, então se você gosta de dinossauros provavelmente vai gostar de emus também.

(E eu estou falando como especialista em emus, já até escrevi alguns)

O Sedol ganhou uma partida! Não vai ser 5-0 !

Essa eu não assisti ao vivo, mas pelo replay ficou claro para mim que o maior problema do Alphago é que ele não tem a capacidade de levantar e sair da sala de vez em quando.

A partida começou bizarramente igual ao segundo match. O Sedol já tinha dito em entrevista que o opening dele na segunda partida estava bom, e ele tinha estragado na frente. Então ele simplesmente repetiu as jogadas, e o Alphago também. As primeiras 10 jogadas foram repetidas, até que na 11 o Sedol saiu da script.

Quem está acompanhando as partidas sabe que o Alphago tem essa mania de fazer aparecer território "magicamente". O que ele faz é atacar os grupos dos inimigos por fora, e enquanto o oponente defende, as peças de ataque do Alphago acabam formando um paredão que define o território.

Ontem aconteceu isso de novo, o Sedol fez um grupo na borda esqueda, o Alphago fez um paredão. Depois o Sedol fez outro grupo na borda direita, o Alphago fez paredão. Se continuasse assim, o Alpha teria o centro inteiro para ele, que foi mais ou menos o que aconteceu nas outras partidas.

Mas dessa vez o Sedol cortou o paredão no B56. O Alphago tentou bloquear, mas não percebeu uma jogada matadora do Sedol no B78. Quando o Alphago se deu conta de que o B78 era um tesuji sinistro, a partida já estava perdida. Eles se meteram num semeai na borda, e incrivelmente o Sedol ganhou o semeai (o que é bizarro porque supostamente computadores são muito bons de semeai). O resultado é que o Sedol *comeu um grupo inteiro do Alphago*, 8 pedras, e três jogadas depois o Alphago desistiu.

E o que aconteceu? Na minha opinião, o problema do Alphago é que ele não pensou o suficiente. Quando ele fez a jogada lendária na segunda partida, o Sedol levantou da cadeira, ficou 10min longe, e quando voltou ainda ficou mais 15min pensando antes de continuar. Agora foi o oposto, o Sedol fez uma jogada louca, mas o Alphago não se tocou disso. Pensou só 1 min na resposta, que é o padrão dele, ao invés de perceber que era uma jogada crítica e que valia a pena investigar mais.

O que eu acho que aconteceu foi o seguinte: essa pedra que o Sedol jogou no B78 é localmente ruim. Ela só funciona num contexto muito especial, e você precisa fazer uma sequencia especifica de dez jogadas para ver a utilidade dela.

Mas o Alphago é monte carlo né. Ele não analisa TODAS as possibilidades, só faz um sampling do espaço de busca e tira a média das jogadas. Na média, aquela pedra era ruim. Provavelmente o monte carlo não simulou aquela sequencia especial de dez jogadas que é a única que funciona (a chance de aparecer é 1/360^10 after all). Como a sequencia não apareceu, ele não percebeu, e o Sedol ganhou.

Tem solução? Claro, é só simular mais! Eventualmente a sequencia iria aparecer. O Alphago ainda tinha muito tempo sobrando. Se ficasse 25min simulando, como o Sedol fez na partida dois, ele teria achado a sequencia e protegido. Mas ele não tem um algoritmo para decidir quando precisa pensar mais e quando precisa pensar menos, joga sempre 1min por pedra, e isso foi o que o levou à derrota.