2016-04-10

A brand new SCV

Porque já estou com saudades do Natal, um post mais ou menos natalício.

Creio que todos nós aqui nos recordamos de retumbante sucesso musical de Natal de 2007 (ou então de outro ano qualquer... sei lá) que parodia o tradicional cântigo em inglês "Twelve Days Of Christmas", mas com unidaded de Starcraft. Aqui há dias pus-me a pensar (nada de bom pode decorrer daqui):

"Mas afinal quantas unidades é que a Blizzard me deu ao todo?"

Se os meus estimados colegas e amigos sabem que eu sou suficientemente maluco para me pôr a fazer somas, também sabem que sou demasiado preguiçoso para fazer assim tantas. Então pesquisei um bocadinho e encontrei uma solução muito engraçada.

(Portanto, se não era imediatamente evidente, está aqui um post ligeiramente intelectual. Nada de muito. Se querem posts verdadeiramente inteligentes, falem com o Peres ou o Pedro - eles são melhores nisso que eu. Mas hoje venho fazer um post só um bocadinho inteligente.)

O número de itens recebidos cumulativamente ao fim de determinado dia pode representar-se de forma triangular. Desta forma, em cada linha representam-se, em tantos números quantos o número da linha, a soma dos objectos de determinada classe. Exemplificando:

1º Dia:

                                1                brand new SCV.

2º Dia:

                                2                brand new SCV (um do primeiro dia e outro do segundo)
                              1  1              (1 + 1 = 2*) terran Wraiths.

3º Dia:

                                3                brand new SCV
                              2  2              terran Wraiths
                            1  1  1            Marines.

Assim sendo, torna-se mais simples somar as instâncias de cada classe. Semelhantemente, torna-se fácil extrapolar o aspecto do número triangular que representa o 12º dia, com um 12 no vértice superior, dois 11s logo abaixo e assim sucessivamente até aos doze 1s na fila do fundo.

Mas podemos ainda evitar uma data de somas. Experimentemos "rodar" o número triangular do quarto dia em 60º (ou π/3 rad) em ambas as direcções, obtendo, de cada vez, um triângulo diferente e, depois, somar cada elemento com os elementos correspondentes dos outros dois triângulos (ou, se preferirem, "sobrepor" os três triângulos e somar cada número com os números com o qual coincide):

        1                      4                     1                    6
      2  1        +        3  3       +        1  2        =       6  6
    3  2  1              2  2  2              1  2  3             6  6  6
  4  3  2  1          1  1  1  1          1  2  3  4          6  6  6  6

Já viram que giro? O número triangular resultante tem o mesmo número em todas as posições! Isso simplifica-nos a vida. Resta-nos determinar a maneira mais fácil de calcular o número que prevalece na representação triangular do 12º dia (e não se esqueçam de dividir por 3 no final!).

Atentemos, portanto aos vértices. Uma vez que todas as posições terão o mesmo valor, basta-nos calcular o valor dos vértices **, o que é bastante simples: os vértices de baixo têsm sempre valor 1 e o vértice de cima tem sempre valor igual ao número de linhas (ou, no caso, dias). Logo, ao fim do 12º dia, o triângulo tem 14 em cada posição. Trata-se agora de determinar o número de posições do triângulo, sabendo que este tem 12 linhas e que cada linha tem tantas posições quanto o seu ordinal.

Todos os meus estimados colegas engenheiros e amigos têm obrigação de saber que é (n + 1) * n / 2, em que n é o número de linhas (/dias).

Portanto se conclui que a Blizzard me deu (12 + 1 + 1) * (12 + 1) * 12 / 2 / 3 = 364 unidades.

Vocês fazem ideia da quantidade de pylons que eu tive de construir?

Pax vobiscum atque vale and a bra-a-aynd new S. C. Vee!

* - Caso seja advogado, peça à sua secretária para lhe assegurar que esta conta está bem feita,
** - Atenção! Isto é má matemática, mesmo para os advogados! Idealmente, demonstrar-se-ia que a soma dos valores das posições equivalentes é constante independentemente da natureza topológica de cada posição, mas isso já é território moderadamente inteligente e hoje é Domingo.

(originalmente publicado a 10 de Abril de 2016)

EDIT: Ora hoje que já é Quinta-feira (14 de Abril), já se pode demonstrar que cada elemento do triângulo que soma os três anteriores tem o valor que tem.

Comece-se por definir uma notação: T(i, j) é a função que, a cada par ordenado (i, j) tal que i denota o número da linha e j a posição a contar da esquerda de cada elemento, faz corresponder o valor do elemento de um triângulo na posição (i, j), com j a variar entre [1; i] e i a variar entre [1; n], em que n denota o número de linhas do triângulo.

Para o primeiro triângulo, T1(i, j) = i - (j - 1), ou, para simplificar, i - j + 1. Quando não, vejamos:

T(1, 1) = 1 - 1 + 1 = 1;
T(2,1) = 2 - 1 + 1 = 2;
T(2 ,2 ) = 2 - 2 + 1 = 1;
T(3 ,1 ) = 3 - 1 + 1 = 3;
T(3 ,2 ) = 3 - 2 + 1 = 2;
T(3 , 3) = 3 - 3 + 1 = 1;
T(4 ,1 ) = 4 - 1 + 1 = 4;
T(4 , 2) = 4 - 2 + 1 = 3;
T(4 , 3) = 4 - 3 + 1 = 2;
T(4 , 4) = 4 - 4 + 1 = 1;

O segundo triângulo é mais simples, e, evidentemente, T2(i, j) = n + 1 - i. Isto deve ser evidente, uma vez que, conforme podeis constatar, cada elemento do segundo triângulo tem um valor tanto mais baixo quanto mais próximo da linha do fundo, independentemente da sua posição ao longo da linha (logo, a fórmula de T2 é independente de j).

O terceiro triângulo é igualmente simples, e T3(i, j) = j. Mais uma vez, isto é evidente, dado que cada elemento tem um valor tão mais elevado quanto a sua distância à ponta esquerda da linha a que pertence, logo, a fírmula de T3 é independente de i.

Finalmente, para o triângulo final,
T(i, j) = T1(i, j) + T2(i, j) + T3(i, j) <=>
<=> T(i, j) = i - j + 1 + n + 1 - i + j <=>
<=> T(i, j) = n + 2, o que não só é, conforme esperado, uma constante para cada triângulo, mas também equivalente à soma dos 3 vértices e, no caso do triângulo que representa a 4º dia, 6,

Q. E. D..