Jangada de pasto

Numa bela manhã, um vivente levantou-se ao inusitado som do mar. Sim, porque ele havia ido dormir com a certeza inabalável de que, assim como o havia sido por toda sua vida, acordaria com o silêncio do campo. Achou que seria brincadeira do piá e pôs-se de pé já de mau humor. Esquentou água, preparou a cuia e foi olhar o sol nascer sobre o Alegrete.

Os butiás saltaram um a um dos bolsos do gaudério! Ao abrir a porta, avistou a praia de Mostardas e o Rio Grande a afastar-se. Desta vez, o piá fora longe demais!

Algumas semanas depois, mesmo sob os protestos do prefeito e das ligações constantes ao Palácio do Piratini e ao Palácio da Alvorada, o Alegrete continuava à deriva. Embretado entre a França e a Inglaterra, todos acharam que nunca mais veriam o céu celeste sobre o campo.

Mas, como o leitor já deve ter percebido, essa história não está limitada pela realidade física. Nos dias que se seguiram, o Alegrete  despertou-se nos lugares menos esperados.

Os pobres paisanos tiveram que suportar frio, calor, secura e umidade. Ou seja, um dia normal no Rio Grande do Sul.

O código dessa brincadeira é simples, como se pode ver abaixo. Entretanto, as coordenadas ocupam muito espaço. Então, se alguém quiser replicar o experimento com seu próprio município, basta pedi-las!

<!DOCTYPE html>
<html>
<head>
<meta name="viewport" content="initial-scale=1.0, user-scalable=no" />
<style type="text/css">
  html { height: 100% }
  body { height: 100%; margin: 0px; padding: 0px }
  div { float: left }
</style>
<script type="text/javascript"
    src="http://maps.google.com/maps/api/js?sensor=true">
</script>
<script type="text/javascript">
  var coordenadas=[...];

  function getCoords() {
    var coords=new Array();
    var bounds = new google.maps.LatLngBounds();
    for(var i=0; i<coordenadas.length; i+=2) {
      var c=new google.maps.LatLng(-coordenadas[i+1],-coordenadas[i]);
      coords.push(c);
      bounds.extend(c);
    }
    coords.bounds=bounds;
    coords.center=bounds.getCenter();
    return coords;
  }
  
  var lat=-29.7640;
  var lng=-55.8861;
      
  function init() {
    var map = new google.maps.Map(document.getElementById("map"),  { 
      zoom: 6, 
      center: new google.maps.LatLng(lat, lng),
      mapTypeId: google.maps.MapTypeId.ROADMAP
    });
    
    var alegrete = new google.maps.Polygon({paths: getCoords(), 
      strokeColor: '#000000', strokeWeight: 1, strokeOpacity: 1, 
      fillColor: '#00AA00', fillOpacity: 0.4,  clickable: false });
    alegrete.setMap(map);
    
    google.maps.event.addListener(map, 'center_changed', function() {
      var point=map.getCenter();
      alegrete.setMap(null);
      var path=alegrete.getPath();
      path.forEach(function(p,i) {
        path.setAt(i, new google.maps.LatLng(p.lat()-(lat-point.lat()), 
                                             p.lng()-(lng-point.lng())));
      });
      lat=point.lat();
      lng=point.lng();
      alegrete.setPath(path);
      alegrete.setMap(map);
    });
  }

</script>
</head>
<body onload="init()">
  <div id="map" style="width:400px; height:400px"></div>
</body>
</html>

A navegação é a original do Google Maps. A cada mudança de centro do mapa (indicada pelo evento center_changed), o código corrige as coordenadas do Alegrete. Pode-se notar claramente que a forma distorce-se nas aproximações aos polos; é defeito da projeção.

Segundas intenções

Um amigo, passeando por Portugal, achou-se perdido e resolveu pedir ajuda a um paisano. Com a obtusidade típica dos brasileiros, disse "Eu queria ir a Braga". Luso-descendentes, como eu, logo compreendem o erro do pobre tupiniquim e não têm muita dificuldade para imaginar a resposta: "Pois vá".

Essa forma direta de dialogar dos portugueses gera uma infinitude de piadas no Brasil, muitas das quais são baseadas em fatos. Creio que seja uma injustiça e que engraçados sejamos nós, os brasileiros. Nossa forma indireta de perguntar e responder gera muitas confusões. Já que as pessoas perguntam por segunda intenção, os interrogados passam a interpretar os questionamentos e daí só podem surgir dificuldades.

Há pouco tempo, pedi a um pintor que pintasse uma parede em azul até 123cm e em azul celeste dali até o teto. A ordem não podia ser mais clara. No entanto, ele deu-se ao trabalho de interpretar a minha ordem, já que sabia que eu queria colocar uma faixa ornamentada com bichinhos para meu filho. Ele colocou a faixa com a base em 123cm, quando a metade dela deveria estar nessa altura. Se o pintor fosse português, tenho certeza que minha ordem, mais que clara, não seria (mal) interpretada.

Noutro incidente recente, atendi uma ligação para uma colega. A pessoa que chamou disse "Fulano, a Beltrana...". Fiquei suspenso por uns segundos esperando um verbo. A Beltrana morreu? A Beltrana esqueceu de vir para a reunião? A Beltrana está? A Beltrana pediu para avisar que vai chegar tarde? A Beltrana pediu alguma coisa? Enquanto o analisador sintático esperava pelo complemento, o subsistema de previsão de intenções lançou um aviso: essa criatura provavelmente quer falar com a Beltrana. Encaminhei a ligação e torci pelo melhor.

Imagino o horror se os programadores brasileiros levassem essa filosofia para seu código. Por exemplo, um método para indicar se há fundos necessários para efetuar uma retirada poderia ser escrito da seguinte forma:

public Status podeRetirar(double valor) throws FundosInsuficientesException {
  if(saldo-valor<0) {
    throw new FundosInsuficientesException();
  }
  return getStatus();
}

Ou seja, o método, se houver fundos, retorna o status da conta (encerrada ou bloqueada, por exemplo), mas se não houver fundos, lança uma exceção para indicá-lo. Não dá para complicar mais uma coisa tão simples.

Outro defeito grave da comunicação tupiniquim é a falta de cortesia básica. É comum caminhar pela rua e ser surpreendido com um "Que horas são?" ou "Onde fica a rua da Ladeira?". Faltam "Bom dia", "Por favor" e "Com licença", cujos propósitos, antes de mais nada, são os de permitir ao cidadão mudar de contexto e preparar-se para iniciar um diálogo.

Se o TCP/IP tivesse sido projetado por um brasileiro, não haveria o handshake (SYN, SYN-ACK, ACK), mas surgiria a necessidade de uma mensagem HEIN, para quando o servidor não estiver preparado para iniciar uma conexão.

Os mal-entendidos cotidianos devem custar um bocado ao Brasil, então é de se espantar que os personagens principais das piadas ainda sejam o Manoel e o Joaquim.

Coundown Sort II

O Countdown Sort foi otimizado! Infelizmente, a melhoria custou um if adicional. Mesmo assim, como o algoritmo agora está quatro vezes mais rápido, acho que valeu a pena.

O algoritmo original percorria todo o array subtraindo 1 de cada elemento e anexando os que chegavam a 0 a um array ordenado. Evidentemente, não é preciso percorrer os elementos que já chegaram a 0, então resolvi tirá-los da jogada.

  public static short[] countdownSort(short in[]) {
    short[] order=new short[in.length];
    int index=0;
    short delta=0;
    int last=in.length-1;
    do {
      for(int i=last; i>=0; i--) {
        if(in[i]-delta==0) {
          order[index]=in[i];
          index++;
          if(i<last) {
            in[i]=in[last];
          }
          last--;
        }
      }
      delta++;
    } while(last>=0);
    return order;
  }

Agora, sempre que encontrar um 0, o algoritmo o troca pelo último elemento do array original e diminui em uma posição a abrangência da busca. Se justamente o último elemento é que chegou a 0, então basta subtrair 1 do índice que aponta para o fim do array (representado no código pela variável last).

Isso significa que o array original será destruído, mas, como o método retorna uma versão ordenada dos números, o problema não é grave.

Paira ainda no ar a dúvida sobre se algo realmente útil pode advir deste algoritmo.

Chocolate e Jurupiga

O chocolate é a bebida sagrada do Novo Mundo, enquanto a Jurupiga é o vinho vira-latas da Europa. São opostos que combinam muito bem. O álcool traz o otimismo para a criação e o amargo do chocolate ajuda na concetração. A combinação é divina. Com a ajuda deles, escrevi um pouco de Javascript para juntar dois mapas antípodas do Google Maps numa só tela. Quando se muda a posição ou a ampliação do mapa da esquerda, o da direita ajusta-se automaticamente para que seu centro seja o antípoda do centro do outro.

Infelizmente, o antípoda do Rio Grande do Sul está no meio do mar entre o Japão e a China. Por outro lado, esta deve ser a única região da Ásia tão despovoada quanto o Pampa.

<!DOCTYPE html>
<html>
<head>
<meta name="viewport" content="initial-scale=1.0, user-scalable=no" />
<style type="text/css">
  html { height: 100% }
  body { height: 100%; margin: 0px; padding: 0px }
  div { float: left }
</style>
<script type="text/javascript"
    src="http://maps.google.com/maps/api/js?sensor=true">
</script>
<script type="text/javascript">
  function init() {
    var lat=-29.683889;
    var lng=-53.806944;

    var here = new google.maps.Map(document.getElementById("here"),  { 
      zoom: 8, 
      center: new google.maps.LatLng(lat, lng),
      mapTypeId: google.maps.MapTypeId.ROADMAP
    });

    var there = new google.maps.Map(document.getElementById("there"), { 
      zoom: 8, 
      center: new google.maps.LatLng(-lat, 180-Math.abs(lng)),
      mapTypeId: google.maps.MapTypeId.ROADMAP
    });
    
    google.maps.event.addListener(here, 'zoom_changed', function() {
      there.setZoom(here.getZoom());
    });
    
    google.maps.event.addListener(here, 'center_changed', function() {
      var point=here.getCenter();
      var sign=point.lng()<0?1:-1;
      there.setCenter(new google.maps.LatLng(-point.lat(), 
        sign*(180-(Math.abs(point.lng())))));
    });
  }

</script>
</head>
<body onload="init()">
  <div id="here" style="width:400px; height:400px"></div>
  <div id="there" style="width:400px; height:400px"></div>
</body>
</html>

O código foi testado no Chrome, no Firefox e no IE. Em todos funciona, mas é no Chrome que ele roda mais rápido.

Countdown Sort

Resolvi tentar melhorar o Sleep Sort contando alguma coisa diferente e mais rápida que o tempo. A minha primeira idéia foi contar números e usar os próprios elementos desordenados como medida. Então, cheguei ao Countdown Sort.

A idéia é muito simples: subtraio 1 de cada elemento e a ordenação ocorre naturalmente ao passo que os números forem alcançando o zero. O desempenho é terrível, mas o algoritmo é meu e está pago. Além disso, ele não faz nem comparações nem trocas de elementos e isso já é interessante por si só.

Eis o código em Java:

  public static short[] countdownSort(short in[]) {
    short[] order=new short[in.length];
    int index=0;
    short delta=0;
    do {
      for(int i=in.length-1; i>=0; i--) {
        if(in[i]-delta==0) {
          order[index]=in[i];
          index++;
        }
      }
      delta++;
    } while(index<in.length);
    return order;
  }

Um possibilidade interessante é a de implementá-lo em código de máquina, já que todas as CPUs têm instruções para subtrair 1 e comparar com 0. Parece-me que o código seria bem pequeno.

Um pequeno teste mostra que o algoritmo funciona mesmo com elementos repetidos:

  public static void main(String... args) {
    short[] ordered=countdownSort(new short[] {
       2, 40, 33, 1, 100, 4, 2, 0, 0, 1024
    });
    for(short v: ordered) {
      System.out.printf("%d,", v);
    }
  }

%java CountdownSort
0,0,1,2,2,4,33,40,100,1024,

Agora, tenho que achar uma maneira de acelerar a contagem.

Sleep Sort

Alguns algoritmos têm pouco valor prático, mas grande valor didático. Há poucas horas foi criado mais um destes (vale ouro presenciar o nascimento de um novo algoritmo de ordenação!): o Sleep Sort. Ele é tão novo, que não tem página na Wikipédia ainda.

O algoritmo é simples: para cada número x, deixam-se passar x unidades de tempo para adicioná-lo à lista ordenada. Quanto maior o valor de x, mais tempo ele precisará esperar e, portanto, mais para o fim da lista ficará posicionado.

Minha solução em Javascript é esta:

function sleepSort(n,callback) {
  var out=new Array();
  for(i in n) {
    var x=n[i];
    var pusher=function(x) {
      return function() { 
        out.push(x); 
        if(out.length==n.length) {
          callback(out);
        }
      };
    }(x);
    setTimeout(pusher, x*100);
  }
}

Como o método setTimeout() usa milissegundos como unidade, multiplico o valor de cada elemento por 100, para ter certeza que haverá tempo suficiente entre eles para não haver confusão.

Quando o último elemento for adicionado, a nova lista estará tão grande quanto a original e a função de callback será chamada. Dada a natureza do algoritmo, não é possível retornar imediatamente o resultado a partir de sleepSort().

O lado didático desse exercício é que ele ajuda a esclarecer como funcionam as closures do Javascript. Eu uso uma função que cria outra função, porque as closures têm referências às variáveis do contexto que as circunda. Logo, sem a função anônima intermediária, todas as chamadas usariam o último valor atribuído a x. Como a função intermediária recebe o x como parâmetro e os parâmetros são passados por cópia, o x da função mais aninhada é cópia e não referência do x original. Logo antes da chamada a setTimeout() está a chamada à função intermediária.

Segue um teste simples:

sleepSort([19,48,61,3,10,20,45,33],
  function(result) { 
    alert(result.join(",")); 
  }
);

Só falta nessa função uma maneira de tirar aquele if intrometido.

P.S. No dia 17/06/2011 surgiu uma entrada na Wikipédia sobre o Sleep Sort.

Transformando colunas em linhas

Um problema que de tempos em tempos surge é o de transformar colunas em linhas no SQL. Os bancos que têm facilidades de XML, como o DB2 e o Oracle, oferecem a possibilidade de resolver isso através do SQL/XML, que é uma extensão padronizada do SQL.

A consulta abaixo mostra como é simples usar essa extensão:

SELECT *
FROM XMLTABLE ('ROWSET/ROW/*' PASSING
     DBMS_XMLGEN.GETXMLTYPE('select 17,25,39 from dual') 
     COLUMNS val VARCHAR2(8) PATH '.'
) X


 17 
 25 
 39 
 

A rotina DBMS_XMLGEN.GETXMLTYPE recebe uma consulta e retorna um XML com a seguinte forma:

<ROWSET>
 <ROW>
  <_x0031_7>17</_x0031_7>
  <_x0032_5>25</_x0032_5>
  <_x0033_9>39</_x0033_9>
 </ROW>
</ROWSET>

Com XMLTABLE, realiza-se o caminho inverso. A expressão 'ROWSET/ROW/*' nos indica que queremos todos os nodos filhos de nodos do tipo ROW. Depois da chamada a DBMS_XMLGEN.GETXMLTYPE há uma descrição dos tipos para os quais as colunas devem ser convertidas.

O primeiro select retornava linhas de apenas uma coluna. Para extrair o nome de cada coluna, é preciso fazer o seguinte:

SELECT x.column_value.getrootelement(), x.column_value.extract('//./text()')
FROM XMLTABLE ('ROWSET/ROW/*' PASSING
     DBMS_XMLGEN.GETXMLTYPE('select 17 as A,25 as B,39 as C from dual')
) X


 A 
 17 
 B 
 25 
 C 
 39 
 

Essa consulta funciona no Oracle 10g. O DB2 e o Oracle 11g tem suporte melhor para o XPath e, portanto, permitem maiores estrepolias.