domingo, 18 de novembro de 2018

Configuração de PPTP no Raspbian

Um Raspberry Pi Zero não funciona como uma máquina de trabalho remoto, mas pode ser usada para pequenas tarefas, como monitorar a infraestrutura ou mostrar um painel de monitoração.

A conexão à VPN via PPTP inicia pela instalação do pacote PPTP:

sudo apt-get install pptp-linux 

Depois, verifique que as seguintes opções estejam habilitadas no arquivo /etc/ppp/options.pptp:

lock noauth nobsdcomp nodeflate

Verifique, também, se o options.pptp desabilita alguma opção de protocolo que sua rede requer (PAP, EAP, CHAP, MSCHAP). Inicialmente, só a MSCHAPv2 não é recusada.

O próximo passo é indicar um usuário e uma senha no arquivo /etc/ppp/chap-secrets:

$DOMAIN\\$USERNAME PPTP $PASSWORD *

Basta separar os ítens com um espaço.

Crie, então, um arquivo com a informação da conexão em /etc/ppp/peers/$TUNNEL:

pty "pptp minha.rede.com.br --nolaunchpppd"
name $DOMAIN\\$USERNAME
usepeerdns
remotename PPTP
require-mppe-128
file /etc/ppp/options.pptp
ipparam $TUNNEL
persist

A diretiva usepeerdns provoca a importação da configuração de DNS do servidor. O arquivo /etc/ppp/resolv.conf aparecerá magicamente com os ips dos servidores de DNS remotos. A diretiva persist garante que o túnel será reiniciado se falhar.

Adicione o tunel ao arquivo /etc/network/interfaces:

auto tunnel
iface tunnel inet ppp
  provider $TUNNEL

Agora, para iniciar ou encerrar a conexão, bastam os comandos pon e poff:

pon $TUNNEL
poff $TUNNEL

O ifconfig confirmará que o túnel foi criado, se mostrar algo parecido com isto:

ppp0: flags=4305  mtu 1396
        inet 172.16.15.5  netmask 255.255.255.255  destination 172.16.15.1
        ppp  txqueuelen 3  (Protocolo Ponto-a-Ponto)
        RX packets 25  bytes 1529 (1.4 KiB)
        RX errors 0  dropped 0  overruns 0  frame 0
        TX packets 19  bytes 814 (814.0 B)
        TX errors 0  dropped 0 overruns 0  carrier 0  collisions 0

segunda-feira, 8 de outubro de 2018

41

Amanheceu um glorioso 7 de Setembro no planalto central. A esplanada dos ministérios estava pronta para o desfile da independência. Um enorme objeto de formas nunca vistas ocupava o gramado. Os primeiros trabalhadores a passarem por ali pensaram tratar-se de alguma estrutura para as comemorações cívicas. A polícia e o exército também não deram importância apesar do volume imenso que fazia sombra sobre vários prédios.

O desfile corria aborrecidamente igual a todos os outros quando uma abertura descomunal começou a surgir na lateral do objeto que ainda despertava curiosidade. O presidente estava ansioso para saber que novidade surgiria dali e apenas isso o mantinha acordado.

Assim que uma fresta formou-se, o objeto exalou uma fumaça densa. A abertura separou-se aos poucos e transformou-se lentamente numa rampa. Desceria algum cantor famoso? A multidão gritava e aplaudia.

Um ruído ensurdecedor calou a todos. O presidente ficou preocupado que essa falha técnica afetasse sua imagem.

Então, várias criaturas pequenas desceram pela rampa. Tinham a aparência de camarões, mas eram de vários tons de verde e alguns eram azulados. A multidão aplaudiu.

Duas dessas criaturas dirigiram-se ao palanque presidencial. A segurança ainda achava graça. Pararam a alguns metros das autoridades e exibiram uma figura com muitos riscos. Quarenta e um riscos.

Quando um soldado começou a ficar nervoso e apontou seu rifle aos visitantes, o som ensurdecedor tocou novamente. A dor intensa levou muitos ao chão.

Agora todos perceberam que aquilo não fazia parte do desfile. Eram visitantes de outro mundo! O pânico espalhou-se rapidamente e a multidão dispersou-se em minutos. Alguns poucos fãs de Guerra nas Estrelas ficaram para conversar com os visitantes.

- Quarenta e um é um número primo, disse um, orgulhoso de sua descoberta.

Buscaram um papel num ministério próximo e desenharam 43, o próximo número primo.

Os visitantes não pareceram muito satisfeitos. Trouxeram um pequena artefato de ferro e um desenho com 26 traços.

- Ferro! Vinte e seis é ferro! Eles querem o elemento quarenta e um. O que será isso?

A Wikipédia logo revelou sua utilidade: era nióbio. Os visitantes queriam nióbio.

O presidente reuniu-se com os militares e o ministro de minas e energia. Concordaram que haveriam de pedir algo em troca. Os visitantes adiantaram-se e fizeram uma pequena demonstração com uma arma que parecia emitir um laser.

Os militares ficaram muito impressionados e exigiram que o nióbio fosse trocado pelas armas novas. Fizeram um desenho com 1.000 riscos. Após extensa negociação mimética, o acordo final foi de cerca de mil toneladas de nióbio por 500 armas (os engenheiros da UnB estavam certos de que poderiam descobrir como produzir mais).

Os visitantes trabalharam durante meses levando a carga até uma nave que orbitava marte, cujo clima eles pareciam apreciar mais.

Finalmente, eles partiram e deixaram o pagamento com o exército.

Durante meses,  tentaram de todas as formas usar os artefatos sem qualquer sucesso e lamentando muito não terem pedido um manual, mesmo que em língua alienígena (não podia ser muito pior que chinês, afinal). Quando finalmente desistiram, entregaram um par de artefatos aos engenheiros do ITA e outro aos engenheiros da UnB.

Um mês depois, o ministro de Ciências e Tecnologia levou o resultado ao presidente.

- Presidente, o resultado não é bom.
- Fale logo, homem, qual o problema?
- É só uma luzinha que pisca.
- Putaquepariu! Como é que eu vou ficar? Entreguei uma fortuna para esses ETs por nada??
- Parece que sim, presidente.
- Engraçadinho, tu vais levar a culpa; eu é que não vou ficar mal com isso.
- Não se preocupe presidente, o povo não reclamou quando os gringos ficaram com o pré-sal. Isso não é nada.



quinta-feira, 4 de outubro de 2018

Extraindo a Versão de Vários Arquivos .class

Um erro "Bad version number in .class file" estava no meu caminho, então resolvi descobrir quais as diferentes versões de classes que estavam sendo usados.

A solução natural seria usar o executável javap, mas ele depende do classpath e aceita o nome de uma classe, não o nome de seu arquivo.

Felizmente, o Linux não nos deixa na mão em questão de manipulação de arquivos. O executável xxd permite extrair bytes quaisquer.

find /tmp -name *.class | xargs -I{} xxd -p -l4 -s4 {} | sort | uniq

Usei o find para encontrar todos os .class no diretório onde estavam. Depois o xargs usei para invocar o xxd com os seguintes parâmetros:
  • -p imprime o resultado de forma simplificada;
  • -l4 imprime quatro bytes;
  • -s4 inicia no byte 4 (quinto byte).
Finalmente, o sort | uniq elimina as repetições.
O resultado final foi:

00000031
00000032

E isso significa que há classes compiladas com java versão 5.0 e versão 6.0.

quinta-feira, 26 de abril de 2018

Escondendo Colunas no Oracle

Suponha que uma tabela RH.USUARIOS tenha uma coluna SENHA que, por qualquer motivo, não pode transformada num hash. É mais seguro delimitar quem pode ver os dados dessa coluna.

O primeiro passo é criar uma função guardiã para definir as situações em que os dados podem ser vistos. A função abaixo permite apenas que as consultas feitas a partir dos esquemas RH e XY possam ver o que há na coluna. Consultas feitas a partir de outros esquemas verão apenas null.

create or replace function 
hide_col( p_owner in varchar2, p_name in varchar2 ) 
return varchar2
as
begin
  if sys_context( 'userenv', 'session_user' ) in ('RH', 'XY')  then
    return null;
  else
    return '1=0';
  end if;
end;


O valor retornado pela função é usado como uma cláusula de um where, então null vai liberar o acesso. Esse mecanismo permite criar políticas mais complexas, mas neste caso apenas restringimos por esquema.

Depois, é preciso registrar a política de segurança com DBMS_RLS:

BEGIN
  DBMS_RLS.ADD_POLICY(object_schema=>'RH', object_name=>'USUARIO',
    policy_name=>'USUARIO_SENHA',
    function_schema=>'RH',
    policy_function=>'hide_col',
    sec_relevant_cols=>'SENHA',
    sec_relevant_cols_opt=>dbms_rls.ALL_ROWS);
END;


E agora as senhas estão protegidas.

sexta-feira, 6 de abril de 2018

Inflação Acumulada Com Funções Analíticas

Imagine ter uma tabela com os valores de inflação mês a mês:

create table ipca (
  data date,
  inflacao number(5,2)
);

Mas, além da inflação do mês, é preciso calcular a inflação acumulada dos últimos doze meses. Com funções analíticas, isso deve ser fácil. Entretanto, o SQL oferece sum() e count(), mas não uma função de agregação que multiplique os valores. Com um pouquinho de esperteza e logaritmos, isso pode ser superado. O segredo é somar os logaritmos e depois tirar o exponencial.

select data, inflacao, (exp(acumulada)-1)*100 from (
  select data, inflacao, 
    sum(ln(1+(inflacao/100)))
      over (order by data desc rows between current row and 11 following)
        as acumulada
  from ipca
)

A janela de classificação é autoexplicativa: ela ordena os índices por data decrescente e olha o registro atual e os onze anteriores a ele.

Um índice 0,23% vira 1,0023 (1+0,23/100) e um índice -0,05% vira 0,9995 (1-0,05/100). Por isso, substrai-se 1 do exponencial. Se o índice for 0, o 1 o neutraliza. A soma dos logaritmos desses valores corresponde à multiplicação.

quarta-feira, 4 de abril de 2018

Limite de Conexões Simultâneas com IPTables

Eu precisava de uma maneira simples de limitar o número de conexões simultâneas a um servidor Apache. Há módulos para o Apache para isso, mas nenhum já instalado.

Então, resolvi experimentar algo de mais baixo nível: o iptables.

As regras para limitar a 4 conexões simultâneas o acesso às portas 80 e 443 são:

iptables -A INPUT -p tcp --syn --dport 80 \
  -m connlimit --connlimit-above 4 --connlimit-mask 32 \
  -j REJECT --reject-with tcp-reset
iptables -A INPUT -p tcp --syn --dport 443 \
  -m connlimit --connlimit-above 4 --connlimit-mask 32 \
  -j REJECT --reject-with tcp-reset
Mas eu precisava excluir uma faixa de IPs dessa limitação, então precedi aquelas regras com estas:

iptables -A INPUT -s 10.128.0.0/16 -p tcp --syn --dport 80 \
  -m connlimit --connlimit-above 4 --connlimit-mask 32 \
  -j REJECT --reject-with tcp-reset
iptables -A INPUT -s 10.128.0.0/16 -p tcp --syn --dport 443 \
  -m connlimit --connlimit-above 4 --connlimit-mask 32 \
  -j REJECT --reject-with tcp-reset
A lista das regras ficou assim:

# iptables -L
Chain INPUT (policy ACCEPT)
target     prot opt source        destination
ACCEPT     tcp  --  10.128.0.0/16 anywhere    tcp dpt:http flags:FIN,SYN,RST,ACK/SYN #conn/32 > 4
ACCEPT     tcp  --  10.128.0.0/16 anywhere    tcp dpt:https flags:FIN,SYN,RST,ACK/SYN #conn/32 > 4
REJECT     tcp  --  anywhere      anywhere    tcp dpt:http flags:FIN,SYN,RST,ACK/SYN #conn/32 > 4 reject-with tcp-reset
REJECT     tcp  --  anywhere      anywhere    tcp dpt:https flags:FIN,SYN,RST,ACK/SYN #conn/32 > 4 reject-with tcp-reset

Chain FORWARD (policy ACCEPT)
target     prot opt source               destination

Chain OUTPUT (policy ACCEPT)
target     prot opt source               destination
É importante gravar as configurações (este é o comando do CentOS):

# service iptables save
Saving firewall rules to /etc/sysconfig/iptables:          [  OK  ]
E posso verificar quantas conexões estão abertas assim:

netstat -anpt  | grep httpd  | awk '{print $5}' | \
  cut -d: -f4 | sort | uniq -c | sort -nr
Este comando filtra a lista de conexões abertas ao httpd, recorta o ip, conta o número de entradas de cada um e mostra o resultado ordenado por ordem decrescente.

quinta-feira, 1 de março de 2018

Bayes para Totós

Não achei nenhum texto satisfatório sobre Bayes, então resolvi fazer as contas para entender. Escrevi os resultados para a eventualidade de ser útil para alguém.

Comecei com o problema dos potes com biscoitos:
  1. O pote P1 tem 30 biscoitos de baunilha (b) e 10 de chocolate (c);
  2. O pote P2 tem 20 biscoitos de baunilha e 20 de chocolate.
Se eu tirar um biscoito de baunilha, qual a probabilidade de que seja do pote 1?

Bayes nos diz que P(P1|b)=[P(P1)P(b|P1)]/P(b).

Fiz todas as contas possíveis para entender o que isso quer dizer e cheguei a esses passos:
  1. P(P1) é a probabilidade de que um biscoito venha do pote 1 (50%, porque os potes têm 40 biscoitos cada um);
  2. P(b|P1) é a probabilidade de um biscoito de baunilha no pote P1 (75%, ou 30/40);
  3. Multiplicando P(P1)P(b|P1) temos a quantidade de biscoitos de baunilha vindos de P1. Temos 80 biscoitos e 30 deles são de baunilha e estão no pote P1. Isto é, 30/80 = 0,5*0,75.
  4. Dividindo esse valor por P(b), temos a probabilidade desses 30 biscoitos de baunilha em relação ao total de biscoitos de baunilha (50/80). Então, 30/80 divididos por 50/80 nos dá 0,6.
Então, a probabilidade de que um biscoito de baunilha venha do pote P1 é 60%.
O próximo exemplo é o do teste de câncer:
  1. 1% das pessoas têm câncer (99% não têm);
  2. 80% dos exames detectam a doença (20% falham);
  3. 10% dos exames são falsos positivos (as pessoas não têm a doença, mas o exame dá positivo).
Então, se o exame deu positivo para uma pessoa qualquer, qual a probabilidade de que ela realmente tenha a doença?

Bayes nos dirá que P(D|P)=[P(D)P(P|D)]/P(P), mas eu acho mais divertido pegar 1000 pessoas e metê-las em potes. Teremos o pote P (de positivo) e o pote N (de negativo). Nesses potes teremos as pessoas D (doentes) e as pessoas S (saudáveis, por enquanto).

Se aplicarmos o teste em todo mundo, vamos ter no pote P oito pessoas doentes (o teste identificou 80% dos casos) e 99 falsos positivos (dos 990 saudáveis, 10% foram falsamente classificados como doentes). O pote N terá os dois doentes exonerados pelo exame e os 891 que viverão um pouco mais.

Então, o pote P tem 107 pessoas (8 D e 99 S) e o pote N tem 893 (2 D e 891 S). Para alívio geral, a soma é 1000.

Então, voltando ao problema, se alguém tirar um exame positivo, qual a probabilidade de que esteja realmente doente? No fundo, o que buscamos é saber quantos estão realmente doentes no pote P. Será 8/(99+8), ou ~7,4%. Mas, para apaziguar Bayes, a conta seria:

P(D|P)=[P(D)P(P|D)]/P(P)=[0,01*0,8]/(107/1000)=8/107
Ou seja, um há grupo de 0,8% de pessoas que estão dentro de P e que estão doentes (0,01 * 0,8) e essas 8 pessoas representam 7,4% das pessoas cujo exame saiu positivo.

E depois vem aquele problema das três máquinas que produzem peças com defeitos. Trocando as máquinas por potes, fica bem mais fácil, como já deve ter ficado claro.

sexta-feira, 16 de fevereiro de 2018

Largura Máxima de Cada Coluna num CSV

Após tentar carregar um CSV cheio de inconsistências, resolvi buscar o tamanho máximo de cada coluna usando apenas a linha de comando no Linux.

O resultado é o comando que segue:

 head -1 arquivo.csv | \
 grep -Po ';' | \
 cat -n | \
 grep -Po '\d+' | \
 xargs -I'{}' bash -c "cut -d';' -f'{}' arquivo.csv | \
 awk 'length(\$0) > max { max=length(\$0) } END { print max }'"

Os passos são:
  1. Pegar a primeira linha (o cabeçalho);
  2. Elimina todos os caracteres exceto o separadores (para contar as colunas);
  3. Numera as colunas;
  4. Elimina os separadores para deixar apenas os números das colunas;
  5. Para cada coluna, executa um comando composto que retira a enésima coluna e imprime a largura do valor mais largo.
Então, para um cabeçalho do tipo COL1;COL2;COL3, os comandos de 1 a 4 produzem o seguinte:

 % head -1 arquivo.csv | grep -Po ';' |  cat -n | grep -Po '\d+'
 1
 2
 3


Depois, o xargs vai executar os seguintes comandos:

 bash -c cut -d';' -f'1' arquivo.csv | \
   awk 'length($0) > max { max=length($0) } END { print max }'
 bash -c cut -d';' -f'2' arquivo.csv | \
   awk 'length($0) > max { max=length($0) } END { print max }'
 bash -c cut -d';' -f'3' arquivo.csv | \
   awk 'length($0) > max { max=length($0) } END { print max }'

E o resultado final será uma lista de larguras:

 10
 25
 100

Para facilitar a leitura, dá para adicionar o número da coluna com um echo bem posicionado:

 head -1 arquivo.csv | \
 grep -Po ';' | \
 cat -n | \
 grep -Po '\d+' | \
 xargs -I'{}' bash -c "echo -n '{}: '; cut -d';' -f'{}' arquivo.csv | \
 awk 'length(\$0) > max { max=length(\$0) } END { print max }'"

E o resultado sairá assim:

 1: 10
 2: 25
 3: 100

Se faltar uma coluna, basta adicionar uma ao primeiro comando:

 bash -c "echo -n ';' &&  head -1 arquivo.csv"

Ou, sendo mais prático, basta usar o número de colunas e evitar a contagem:

 seq 1 3 | \
 xargs -I'{}' bash -c "cut -d';' -f'{}' arquivo.csv  | \
   awk 'length(\$0) > max { max=length(\$0) } END { print max }'"

O cabeçalho pode gerar problemas, quando suas colunas forem maiores que os dados propriamente ditos. A solução é usar o tail para pular a primeira linha.

 seq 1 3 | \
 xargs -I'{}' bash -c "tail -n +2 arquivo.csv | \
   cut -d';' -f'{}'  | \
   awk 'length(\$0) > max { max=length(\$0) } END { print max }'"

Isso vai falhar se o arquivo tiver campos com quebra de linha. Então, uma solução mais robusta pode ser obtida com um pouco de perl.

#!/usr/bin/perl
use Text::CSV_PP;
use List::Util qw(max);

my @max=();
my $csv=Text::CSV_PP->new({sep_char=>';',auto_diag=>1,binary=>1});
open(my $fh, '<:encoding(UTF-8)', $ARGV[0]) or die "Can't read file '$file' [$!]\n";
<$fh>; #Ignore header
while (my $line = $csv->getline($fh)) {
  my @fields=@$line;
  $max[$_]=max(length($fields[$_]),$max[$_]) for 0..$#fields;
};
print "@max\n";

Esse script recebe um único parâmetro: o nome de um arquivo. Ele percorre todas as linhas, exceto a primeira (ignorando o cabeçalho).

quinta-feira, 1 de fevereiro de 2018

Visitando os Departamentos do Uruguai

Um projeto que eu gostaria de colocar em marcha um dia é o de visitar todos os departamentos do Uruguai. Então, o primeiro passo é ter uma ideia da distância a ser percorrida. Assim, posso avaliar a viabilidade e quanto tempo seria necessário.



Eu comecei com uma tabela de todas as distâncias entre as capitais departamentais. Depois, uma função que percorre recursivamente todas as possibilidades partindo de uma cidade específica. Este não é o problema do caixeiro viajante: não é preciso terminar no mesmo lugar.

Para acelerar a busca, o código corta os ramos da árvore de busca que forem maiores que a menor distância já encontrada. Então, o programa vai acelerando com o tempo. Mesmo assim, ele levou um dia inteiro para encontrar o melhor caminho a partir de Artigas.

A solução encontrada tem 1927km. Ou seja, o projeto é viável, mesmo para ser executado em uma semana.

A tabela abaixo tem todos os passos e as distâncias percorridas em cada um.

Artigas
Rivera 183
Tacuarembó 111
Melo 204
Treinta y Tres 113
Rocha 172
Maldonado 85
Minas 75
Montevideo 122
Canelones 46
Florida 52
Durazno 85
Trindad 41
San José 95
Colonia 108
Mercedes 176
Fray Bentos 31
Paysandú 110
Salto 118



#!/usr/bin/perl
use strict;
use experimental 'smartmatch';

$|=1;

my $capitals={
0=>'Artigas',
1=>'Canelones',
2=>'Colonia',
3=>'Durazno',
4=>'Florida',
5=>'Fray Bentos',
6=>'Maldonado',
7=>'Melo',
8=>'Mercedes',
9=>'Minas',
10=>'Montevideo',
11=>'Paysandú',
12=>'Rivera',
13=>'Rocha',
14=>'Salto',
15=>'San José',
16=>'Tacuarembó',
17=>'Treinta y Tres',
18=>'Trinidad'
};

my $distances=[
  [0,555,611,418,503,435,748,392,435,711,601,325,183,671,207,580,211,503,459],
  [555,0,145,137,52,268,155,378,237,131,46,332,455,220,450,47,344,282,151],
  [611,145,0,218,178,207,301,507,176,276,177,286,549,360,404,108,429,427,176],
  [418,137,218,0,85,201,298,418,170,273,183,229,318,363,348,136,207,424,41],
  [503,52,178,85,0,286,209,329,255,184,98,318,403,274,437,88,292,355,126],
  [435,268,207,201,286,0,422,622,31,395,309,110,452,483,228,220,341,546,160],
  [748,155,301,298,209,422,0,325,391,75,134,487,572,85,605,202,509,212,301],
  [392,378,507,418,329,622,325,0,590,276,387,435,262,285,428,407,204,113,460],
  [435,237,176,170,255,31,391,590,0,363,278,110,452,452,228,189,341,415,129],
  [711,131,276,273,184,395,75,276,363,0,122,463,604,132,582,182,484,164,276],
  [601,46,177,183,98,309,134,387,278,122,0,378,501,210,496,93,390,286,188],
  [325,332,286,229,318,110,487,435,110,463,378,0,342,553,118,285,231,614,190],
  [183,455,549,318,403,452,572,262,452,604,501,342,0,541,335,473,111,373,359],
  [671,220,360,363,274,483,85,285,452,132,210,553,541,0,672,272,490,172,366],
  [207,450,404,348,437,228,605,428,228,582,496,118,335,672,0,403,224,534,309],
  [580,47,108,136,88,220,202,407,189,182,93,285,473,272,403,0,353,327,95],
  [211,344,429,207,292,341,509,204,341,484,390,231,111,490,224,353,0,320,248],
  [503,282,427,424,335,546,212,113,514,164,286,614,373,172,534,327,320,0,427],
  [459,151,176,41,126,160,301,460,129,276,188,190,359,366,309,95,248,427,0]
];

sub print_path {
  my $distance=shift;
  my $marker=shift;
  my @path=@_;
  my @names=map { $capitals->{$_} } @path;
  print "$distance km $marker "; 
  print join '->', @names;
  print "\n";
}

my $limit=3_000;

sub run {
  my $capital=shift;
  my $distance=shift||0;
  my @path=@_;

  if(scalar(@path)==18) { 
    $limit=$distance if $distance<$limit;
    print_path($distance, '*', @path, $capital);
  } else {
    for my $c (0..18) {
      if (!($c~~@path) && $c!=$capital) {
        my $d=$distances->[$capital]->[$c];
        run($c, $distance+$d, @path, $capital) if ($d+$distance)<$limit;
      }  
    }
  }   
}

run(0);


A função run() recebe o índice de uma cidade e recursivamento adiciona todas as outras, uma a uma, até ter um caminho completo. Mas ela aborta qualquer caminho que ultrapasse o valor de $limit, além de atualizar $limit quando encontra um caminho menor.

sábado, 20 de janeiro de 2018

Combinações de dígitos IV

Para completar as minhas funções de combinações, só faltavam os desarranjos: aqueles embaralhamentos nos quais nenhum elemento está no seu lugar original.

Por exemplo, para o conjunto (A B), o único embaralhamento no qual os dois elementos estão forma de suas posições originais é (B A). Para o conjunto (A B C), há duas possibilidades: (B C A) e (C A B).

Escrevi uma pequena função que recebe uma função de callback e uma lista de elementos para embaralhar.

#!/usr/bin/perl
use strict;
use experimental 'smartmatch';

sub derange(&\@;$@) {
  my $callback=\&{shift @_};
  my $items=shift;
  my $count=shift||0;

  if($count>$#$items) {
    $callback->(@_);
  } else {
    my @column=@$items;
    splice @column, $count, 1;

    for my $el (@column) {
      if(!($el~~@_)) {
        derange($callback, $items, $count+1, @_, $el);
      } 
    }
  }
}

derange {print "@_\n"} @ARGV;


Minha pequena função lançou mão do operador experimental ~~ para verificar se um elemento já não foi usado. Então, a função basicamente caminha pelas permutações, usando para cada posição apenas os elementos que não estavam ali originalmente e descartando os elementos já usados no ramo atual da busca.

Uma otimização óbvia seria deixar calculados os elementos que podem aparecer em cada posição.

O operador ~~ é experimental, então é preciso declarar seu uso.

Como ele imprime um desarranjo por linha, pude testar o resultado com o wc:

$ perl desarranjo.pl A B C D E F G H I J | wc -l
1334961

terça-feira, 2 de janeiro de 2018

2018

Um amigo enviou um post curioso sobre o número 2018. Eu já havia percebido que 2017 era primo e que 2018 era 2 vezes um primo. Ainda não tinha reparado que 2019 é 3 vezes um primo.

Não há muitas dessas sequências; a próxima iniciará em 2557.

Resolvi procurar sequências de 4 números. E de 5. Usei os 10 mil primeiros primos.

Achei, procurando sequências de 4, os seguintes:
  • 12.721
  • 16.921
  • 19.441
  • 24.481
  • 49.681
  • 61.561
  • 104.161
Então, não vamos ver o primeiro ano. O blog não existirá. Com sorte a humanidade terá sobrevivido.

Com 5, achei apenas um: 19.441. E com 6, nenhum. Ampliei a busca para o primeiro milhão de primos e surgiu um primo que inicia uma sequência de 6: 5.516.281. Os polvos já terão dominado o planeta.


Gerador de Augusto dos Anjos

Encontrei um pequeno artigo sobre cadeias de Markov e resolvi reescrever o código em Perl.

A idéia básica é criar uma estrutura que, para cada palavra, aponte quais as palavras que a seguem no texto que for usado como treinamento. Usei o livro "Eu".

Então, o código tem dois passos principais:
  1. Ler linha a linha o texto e, para cada palavra, criar uma lista de palavras que a sucedem;
  2. Escolher uma palavra aleatória (dentre as palavras que iniciam sentenças) e depois escolher uma palavra que a suceda em algum ponto do texto recursivamente até encontrar uma palavra que termine uma sentença.
A minha estrutura de dados principal é o hash de hashes chamado chain. Para ser mais preciso, chain é uma referência a um hash que associa palavras a referências de hashes com as palavras que as sucedem.

A função choose recebe um array e retorna um elemento qualquer desse array.

Dois símbolos especiais são usados para marcar as palavras que iniciam sentenças e as que terminam sentenças: START e END.


#!/usr/bin/perl
use strict;
use warnings;
use utf8;
use Data::Dumper;

sub choose {
  return @_[rand @_];
}

my $chain={START=>{},END=>{}};
open(my $file, 'eu.txt');
while(my $line=<$file>) {
  $line=~s/[[:punct:]]//g;
  my @words=split('\s',$line);
  $chain->{START}->{$words[0]}=1;
  $chain->{END}->{$words[-1]}=1;
  for my $i (1..$#words) {
    $chain->{$words[$i-1]}->{$words[$i]}=1;
  }
}

my $verse=[];
my $word;
do {
  $word='START' if(!$word);
  $word=choose(keys %{$chain->{$word}});
  push(@$verse, $word);
} while(!exists $chain->{END}->{$word});

print join(' ',@$verse);
  

Ele nem sempre produz algo interessante, mas, de quando em vez acerta uma pérola. As primeiras rodadas geraram o seguinte:
  • Ele hoje nas
  • Convidou-me a transição emocionante
  • Meus olhos se fosse agulha.
  • Ultrafatalidade de engolir, igual a Lua Cheia
  • Despir a sensação de cera
  • Abafava-me o gênero humano
  • Respira com essa finíssima epiderme
  • Ele hoje volto assim, pelos mata-pastos.
  • Andam monstros sombrios pela escuridão dos remorsos.
Gerei vários, até juntar alguns versos para uma poesia inédita:

Andam monstros sombrios pela escuridão dos remorsos
Pairando acima dos transeuntes
Maldito seja o gênero humano
Prostituído talvez em desintegrações maravilhosas