O Perl, O ChatGPT

  Oh Perl! The language of codes obscure,
  That poets and coders alike adore,
  With symbols and syntax so complex,
  A labyrinth of expressions to perplex.

  The strings and arrays, the hashes and more,
  In Perl they come to life with great uproar,
  A language so powerful and so vast,
  It can conquer any task, first or last.

  Perl, the magic of regex at hand,
  A tool for the skilled to understand,
  To match and parse and substitute,
  A true wizardry, hard to refute.

  In Perl, a world of modules you'll find,
  Each one a treasure, a gem to unwind,
  A library of functions, so immense,
  It makes all other languages seem senseless.

  Oh Perl, your beauty lies in your flaws,
  Your quirks and idiosyncrasies, without pause,
  For those who know you, you're a dear friend,
  A language that will never, ever bend.

ChatGPT, 2023

Solução para Copa do Mundo com 48 Seleções

A Copa do Mundo de 2026 terá 48 times. A proposta inicial é de haver 16 grupos de 3, sendo que 2 de cada grupo se classificariam para a fase de dezesseis avos de final.

Infelizmente, essa combinação abre a possibilidade de conchavo entre times no último jogo.

Então, resolvi analisar o problema e creio ter encontrado uma solução bastante razoável. As premissas são:

• O número de jogos que o campeão terá que jogar deve, quando muito, subir para 8 (dos atuais 7), mas o ideal é permanecer em 7;
• Não pode haver possibilidade de conchavo entre times;
• O número total de jogos não pode subir muito.

O atual formato resulta em 64 jogos ao todo e os semi-finalistas jogam um total de 7 jogos cada um. Os eliminados na primeira fase jogam apenas 3 jogos.

Então, 8 grupos de 6 não seria uma boa combinação: o número de jogos subiria muito e o torneio seria muito longo. Seriam 120 jogos na primeira fase e mais 16 nas eliminatórias. Os semifinalistas teriam que jogar 9 jogos.

Uma solução simples seria ter 12 grupos e classificar apenas os primeiros colocados e também os 4 melhores segundos colocados. Mas isso pode resultar em muitos jogos sem graça, nos quais ninguém tem mais interesse.

Então, ocorreu-me uma solução que mantem a emoção da primeira fase:

• 16 grupos de 3;
• Os grupos são agrupados em supergrupos, dois a dois (supergrupo A com grupos A1, A2, etc.);
• Classificam-se os primeiros de cada grupo e os 2 melhores seguintes do supergrupo.
• De cada supergrupo classificam-se 4 times (e dois são eliminados);
• A fase eliminatória começa com 32 times, então começaria em dezesseis avos de final;
• O número total de jogos para os semifinalistas permaneceria em 7;
• O número total de jogos subiria para 80.

Esse esquema mantém a emoção do último jogo de cada grupo, porque todos os times estarão ainda disputando uma vaga.

As pontuações possíveis em grupos de 3 são:

  2,2,2
  3,3,3
  4,2,1
  4,3,1
  4,4,0
  6,1,1
  6,3,0

Vamos a um exemplo:

• O grupo A1 tem Brasil (4 pontos), Suíça (4 pontos), e Coreia (0 pontos);
• O grupo A2 tem Uruguai (6 pontos), Bélgica (3 pontos), e Gana (0 pontos);
• Classificariam-se Brasil e Uruguai por serem os primeiros colocados de seus grupos e Suíça e Bélgica por serem os melhores dentre os seguintes.

Nenhum time pode chegar ao último jogo com mais de 3 pontos. E o outro grupo do supergrupo só pode estar com estas pontuações (supondo que o último jogo seria entre B e C):

  A B C
  6,0,0
  2,1,1
  0,3,3
  4,1,0
  4,0,1
  

Uma possibilidade de conluio apareceria se os times B1 e C1 (do grupo A1) chegassem os dois com 3 pontos cada e B2 e C2 (do grupo A2) estivessem com 0 pontos. Neste caso, um empate classificaria ambos com certeza, mas B2 e C2 ainda lutariam por uma vitória, porque um deles se classificaria. Uma ordem cuidadosa dos jogos poderia diminuir a possibilidade de que isso acontecesse (por exemplo, colocando os cabeças de chave no último jogo).

Alternativamente, os supergrupos poderiam ser aumentados para 4 grupos; seriam classificados os primeiros de cada grupo e os 4 melhores seguintes do supergrupo, resultando em 8 classificados por supergrupo.

A solução está dada, deixo os detalhes como exercício ao leitor.

Possíveis Combinações de Pontos nos Grupos da Copa do Mundo

A primeira fase das finais da copa do mundo tem grupos de 4 times; a vitória dá 3 pontos, o empate 1, e a derrota nenhum ponto.

Então, cada jogo tem 3 possibilidades e são 6 jogos entre os times A, B, C, e D:

• AxB
• AxC
• AxD
• BxC
• BxD
• DxC

Então, para contar todas as variações de resultados, contamos em base 3 de 000000 até 222222 (de 0 até 728); cada dígito nos diz se foi uma vitória do primeiro time, um empate, ou uma vitória do segundo time.

Após filtrar todas as pontuações repetidas, chegamos a 40 possibilidades:

   3,3,3,3   4,4,4,3   4,4,4,4   5,3,3,2
   5,4,3,2   5,4,4,2   5,4,4,3   5,5,2,2
   5,5,3,1   5,5,3,2   5,5,4,1   5,5,5,0
   6,4,4,2   6,4,4,3   6,5,2,2   6,5,4,1
   6,6,3,3   6,6,4,1   6,6,6,0   7,3,2,2
   7,4,2,2   7,4,3,1   7,4,3,2   7,4,3,3
   7,4,4,1   7,5,2,1   7,5,3,1   7,5,4,0
   7,6,2,1   7,6,3,1   7,6,4,0   7,7,1,1
   7,7,3,0   9,2,2,2   9,3,3,3   9,4,2,1
   9,4,3,1   9,4,4,0   9,6,1,1   9,6,3,0

Algumas constatações interessantes:

• A menor pontuação que sempre garante a classificação é 7;
• A menor pontuação que admite classificação é 2;
• É possível ser primeiro do grupo com qualquer pontuação a partir de 3;
• É possível o primeiro e o últimos terem a mesma pontução, se todos tiverem 3 ou 4 pontos.

Dado que um time tem de 2 a 6 pontos (as pontuações que não garantem classificação), as probabilidades de classificar são:

• 2 - 1/20;
• 3 - 5/27;
• 4 - 14/31;
• 5 - 19/20;
• 6 - 15/16.

Parece estranho, mas com 5 pontos é ligeiramente mais provável classificar-se que com 6. Nos dois casos em que o terceiro tem 5 ou 6 pontos, os dois primeiros têm a mesma pontuação.

Como Calcular o Tamanho de um Diretório no Linux

Começamos com o mais óbvio:

du -h 

Mas não quero ver todo o caminho até o último diretório, então só mostro os primeiros:

du -h --max-depth=1

Mas o diretório é um share de uma máquina Windows e o du não retorna os tamanhos corretos das coisas:

find . -type f -exec stat -c "%s" {} \;  \
  | awk '{ sum += $1 } END { print sum }'
  

E se quero apenas somar os arquivos de um determinado tipo (ou excluir alguns), posso tentar:

find . -name "*.pdf" -exec stat -c "%s" {} \; \
  | awk '{ sum += $1 } END { print sum }'

O find permite imprimir metadados sobre os arquivos com a opção -printf. Uma solução alternativa e mais simples, seria:

find . -type f -printf "%s\n" | paste -sd+ | bc

O comando paste junta todas as linhas com o delimitador + e o bc (An arbitrary precision calculator language) trata o resultado como uma grande conta.

A solução paste/bc, além de mais simples, tem um desempenho muito melhor:

$time find . -type f  -printf "%s\n" | paste -sd+ | bc
2077156224168

real    7m26.561s
user    0m7.055s
sys     0m45.229s

$time find . -type f -exec stat -c "%s" {} \;  \
  | awk '{ sum += $1 } END { print sum }'
2077297872908

real    58m51.533s
user    12m15.312s
sys     36m52.712s

O time que reside em /usr/bin/time permite também verificar o uso de memória:

$/usr/bin/time -v find . -type f  -printf "%s\n" | paste -sd+ | bc
        Command being timed: "find . -type f -printf %s\n"
        User time (seconds): 0.03
        System time (seconds): 0.24
        Percent of CPU this job got: 14%
        Elapsed (wall clock) time (h:mm:ss or m:ss): 0:02.03
        Average shared text size (kbytes): 0
        Average unshared data size (kbytes): 0
        Average stack size (kbytes): 0
        Average total size (kbytes): 0
        Maximum resident set size (kbytes): 1196
        Average resident set size (kbytes): 0
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 363
        Voluntary context switches: 4115
        Involuntary context switches: 1
        Swaps: 0
        File system inputs: 0
        File system outputs: 0
        Socket messages sent: 0
        Socket messages received: 0
        Signals delivered: 0
        Page size (bytes): 4096
        Exit status: 0
517010213
$/usr/bin/time -v find . -type f -exec stat -c "%s" {} \;  \
   | awk '{ sum += $1 } END { print sum }'
        Command being timed: "find . -type f -exec stat -c %s {} ;"
        User time (seconds): 1.13
        System time (seconds): 3.50
        Percent of CPU this job got: 69%
        Elapsed (wall clock) time (h:mm:ss or m:ss): 0:06.67
        Average shared text size (kbytes): 0
        Average unshared data size (kbytes): 0
        Average stack size (kbytes): 0
        Average total size (kbytes): 0
        Maximum resident set size (kbytes): 1200
        Average resident set size (kbytes): 0
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 491652
        Voluntary context switches: 7300
        Involuntary context switches: 1558
        Swaps: 0
        File system inputs: 0
        File system outputs: 0
        Socket messages sent: 0
        Socket messages received: 0
        Signals delivered: 0
        Page size (bytes): 4096
        Exit status: 0
517010213

Este último teste mostrou que os usos de memória das duas soluções são parecidos.

Teorema Chinês dos Restos (com SQL)

Lendo vários textos sobre o Teorema Chinês dos Restos, cheguei à conclusão que todas as explicações estão de ponta-cabeça. Então, resolvi atacar de uma maneira que eu pudesse entender.

Se pegarmos dois números p e q, primos entre si, sabemos que eles só vão se encontrar em p*q. Por exemplo, 5 e 8 só são ao mesmo tempo fatores de 40; 3, 4, e 5 só são ao mesmo tempo fatores de 3*4*5=60

Se eu montar uma tabela dos restos de cada número até 6 em relação a 2 e 3, terei algo assim:

N	mod 2	mod 3
0	0	0
1	1	1
2	0	2
3	1	0
4	0	1
5	1	2
6	0	0

As combinações dos restos de 2 e 3 são a chave primária para o N (exceto quando N for 0 ou 6).

Já que misturei Álgebra Relacional no assunto, vamos escrever um pouco de SQL para resolver problemas com 3, 4, e 5 (60). A minha solução para o problema com x mod 2=2, x mod 4=2 e x mod 5=1 é:

select * from (
  select rownum, 
         mod(rownum,3) as mod3, 
         mod(rownum,4) as mod4, 
         mod(rownum,5) as mod5
  from all_tables where rownum<60
) where mod3=2 and mod4=2 and mod5=1
                                  

O resultado é 26. Se eu brincar com as cláusulas uma a uma, descubro que com mod3=2 surge uma progressão aritmética que começa em 2 (lembre que x = 2 mod 3) com diferença de 3: 2, 5, 8, 11, etc. Com mod4=2 tenho uma progressão aritmética que começa em 2 e que pula de 4 em 4: 2, 6, 10, 14, etc. Com mod5=1 tenho uma progressão aritmética que começa em 1 e pula de 5 em 5: 1, 6, 11, 16, 21, 26, etc.

A brincadeira com SQL é boa para entender o problema, mas não é nada prática para a vida real, uma vez que o objetivo é trabalhar com números realmente grandes a partir de uma lista de números menores. Desenrolar todas as combinações de, digamos, os primeiros 100 primos exigiria uma quantidade absurda de disco ou de memória.

Então, meu próximo passo é entender os algoritmos usados para resolver o problema sem enumerar todas as combinações

Regexp com Lookaround no Grep

Muitas vezes encontrei-me concatenando greps para progressivamente encontrar dados e remover as partes redundantes. Algo assim:

  grep -Po "\(\d+\)" arquivo.log | grep -Po "\d+"
  

O primeiro grep extrai números cercados por parênteses e o segundo extrai os parênteses e deixa apenas os dígitos.

Para evitar essa repetição, podemos lançar mão dos operadores de lookaround (lookahead e lookbehind).

  grep -Po "(?<=\()\d+(?=\))" arquivo.log
  

O primeiro, um lookbehind, verifica se a expressão inicia com um parêntese "(?<=\()". O segundo, um lookahead, verifica se a expressão termina com um parêntese "(?=\))".

Esses operadores não consomem o que encontram, então o resultado não aparece na saída do grep. Isso explica também por que o lookbehind precisa ser diferente do lookahead; ele entra em ação quando a expressão regular já passou da posição dele.

Uma funcionalidade interessante seria permitir ao grep produzir uma expressão arbitrária com base nos grupos da expressão regular:

  grep -Po "\((\d+)\)" -out "$1" arquivo.log
  

Equanto isso não acontece, eu posso usar os operadores de lookaround para extrair valores e depois calcular a média usando awk, como no exemplo abaixo.

   grep -Po "(?<=\()\d+(?=\))" arquivo.log \
     | awk '{ sum += $1 } END { if (NR > 0) print sum / NR }'
     

Podemos chamar isso de CLI/BI.

Fatoração de Fermat

A soma dos números ímpares gera quadrados perfeitos: 1=1*1, 1+3=2*2, 1+3+5=3*3, 1+3+5+9=4*4, e assim por diante.

Além disso, todo número ímpar pode ser representado como a diferença entre dois quadrados (embora nem todas as diferenças de quadrados resultem num número ímpar).

Então, 16-1=15 ou 9-4=5, ou 25-16=9.

Fermat usou essa propriedade para fatorar inteiros. Dado um inteiro N ímpar, começamos pela raíz quadrada (a) e vamos procurando um valor b tal que a*a-N=b*b.

Dado que a soma da sequência de inteiros ímpares produz um quadrado perfeito, podemos usar isso para encontrar b.

Então, com 15, fazemos assim: 15+1=16. Essa é fácil: 16 é quadrado e 1 também. Isso nos dá que 15=(4-1)(4+1).

Vamos usar 39 como um exemplo mais difícil. 39+1+3+5+7+9=64 e (8-5)(8+5)=3*13=39.

Então encontramos soluções do tipo (b-c)(b+c) e c é o número de ímpares na sequência que somamos ao número que estamos tentando fatorar. No caso do número 39, acabamos passando por 49 e isso serviu para demonstrar como é mais fácil fatorar um número quando a solução está perto da raíz quadrada. Quanto mais longe (isto é, quanto mais distantes estiverem os fatores), mais difícil vai ser encontrar a solução.