Project Euler - 19

No problema 19 do Project Euler, vamos assim dizer, há uma "pegadinha", principalmente para quem, como eu, deseja solucionar por força bruta.

O problema é assim proposto:

Observamos que no problema é dito que 1/jan/1900 caiu em uma segunda-feira, entretanto o problema pede para calcular o número de domingos que caíram no primeiro dia do mês, entre 1901 e 2000. Logo, o ano 1900 deve ser desconsiderado. Como 1900 não foi um ano bissexto, no ano seguinte o dia 1 de janeiro cairá no dia da semana subseqüente, ou seja, se em 1900 foi em uma segunda-feira, em 1901 será em uma terça-feira.

Esta informação é importante para a inicialização das variáveis...

Inicialmente, vamos precisar de uma função que indique se determinado ano é bissexto ou não.

Foi implementado assim:

Function is_bissexto([int]$a) {
    [int]$f = 0

    If (($a % 4) -eq 0) { 
        $f = 1 
        If (($a % 100) -eq 0) { $f = 0 }
    }
    Else { $f = 0 }
    If (($a % 400) -eq 0) { $f = 1 }
    Return $f
}

A função is_bissexto recebe um ano como argumento e retorna 1 se o ano é bissexto, ou zero se não é.

Assim, bastará somar 28 ao mês de fevereiro do ano correspondente, ou seja, se o ano for bissexto a função retorna 1 e o mês de fevereiro terá 29 dias, caso contrário, permanece com 28.

Vamos utilizar arrays para armazenar o número de dias de cada mês $mes e para representar qual o dia do mês é determinado dia da semana $dia.

$mes = @(31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)
$dia = @(0, 0, 0, 0, 0, 0, 0)

No caso, $mes[1] é que armazenará os dias do mês de fevereiro, que irá variar conforme o ano em questão for bissexto. O array $dia é inicializado com zero, mas no código receberá os dias do mês que estiver sendo calculado.

A implementação terá 3 laços For (um para o ano, outro para o mês e outro para os dias do mês, preenchendo os dias da semana no array $dia). Sendo que $dia[0] irá representar o domingo e cada vez que $dia[0] = 1, iremos incrementar uma variável que acumulará o somatório de domingos que caem no primeiro dia do mês.

O código completo ficou assim:

Function is_bissexto([int]$a) {
    [int]$f = 0

    If (($a % 4) -eq 0) { 
        $f = 1 
        If (($a % 100) -eq 0) { $f = 0 }
    }
    Else { $f = 0 }
    If (($a % 400) -eq 0) { $f = 1 }
    Return $f
}

$mes = @(31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)
$dia = @(0, 0, 0, 0, 0, 0, 0)
[int]$sun_sum = 0
[int]$ds = 2

For ([int]$ano=1901;$ano -le 2000;$ano++) {
    If (is_bissexto($ano) -eq 1) { $mes[1] = 29 }
    Else { $mes[1] = 28 }

    For ([int]$m=0; $m -lt 12; $m++) {
        For ([int]$d=1; $d -le $mes[$m]; $d++) {
            $dia[$ds] = $d
            If (($ds -eq 0) -and ($dia[$ds] -eq 1)) { 
                $sun_sum++ 
                Write-Host "Encontrou Domingo em: " $d "/"($m+1)"/"$ano
            }
            If ($ds -ge 6) { $ds = 0 }
            else { $ds++ }
        }
    }
}
write-Host "----------------------------------------------"
Write-Host "Há $sun_sum Domingos no primeiro dia do mês entre [1901-2000]"

.
.
.
Encontrou Domingo em:  1 / 3 / 1992
Encontrou Domingo em:  1 / 11 / 1992
Encontrou Domingo em:  1 / 8 / 1993
Encontrou Domingo em:  1 / 5 / 1994
Encontrou Domingo em:  1 / 1 / 1995
Encontrou Domingo em:  1 / 10 / 1995
Encontrou Domingo em:  1 / 9 / 1996
Encontrou Domingo em:  1 / 12 / 1996
Encontrou Domingo em:  1 / 6 / 1997
Encontrou Domingo em:  1 / 2 / 1998
Encontrou Domingo em:  1 / 3 / 1998
Encontrou Domingo em:  1 / 11 / 1998
Encontrou Domingo em:  1 / 8 / 1999
Encontrou Domingo em:  1 / 10 / 2000
----------------------------------------------
Há 171 Domingos no primeiro dia do mês entre [1901-2000]

Um equivalente ao CUT do Linux

Estive aprendendo um pouco de programação em Bash/Linux, em Bash Scripting Tutorial - 3. User Input.

Há um exemplo demonstrando o uso do comando cut junto com o pipe, partindo-se do seguinte arquivo summary.sh:

Em destaque, a linha 8, que permite receber um arquivo como entrada e redirecionar via pipe ao cut e, na sequência, ao comando sort.

No caso, o arquivo é denominado salesdata.txt, cujo conteúdo é exibido abaixo, juntamente com a chamada cat salesdata.txt | .\summary.

Como observado, os parâmetros passados ao cut faz com que sejam extraídos a 2ª e a 3ª parte de cada linha, sendo o delimitador o caractere de espaço ' '. Ainda, ao final, os dados são ordenados através do sort.

Assim sendo, o desafio aqui é encontrar um método equivalente de extrair esses dados do arquivo salesdata.txt com o powershell.

Alcança-se o objetivo com o seguinte código em powershell:

PS D:\Linux> Get-Content .\salesdata.txt | %{"$($_.split(' ')[1..2])"} | Sort-Object
apples 20
oranges 5
peaches 7
watermelons 12

Calculando Hash de Arquivos

Com o Powershell Get-FileHash é possível verificar diversos hashes de arquivos, tais como SHA1, SHA256, SHA384, SHA512, MD5.

Seja, como exemplo, verificar o hash de um arquivo baixado da internet, no caso Hex Edit. Na página de download, é exibido os valores de MD5 e SHA1 do arquivo.

E, com o Powershell, podemos conferir o hash MD5 do arquivo baixado:

Bem como, o valor do hash SHA1 do arquivo .zip:

Comparando com os valores do site do Hex Edit, podemos constatar que o arquivo baixado está íntegro.

Calculando Pi

O número Pi (π) há muito tempo encanta não apenas matemáticos, e há uma procura constante por métodos otimizados para obtê-lo com maior precisão. Em 1995, David Harold Bailey, em colaboração com Peter Borwein e Simon Plouffe, descobriu uma fórmula de cálculo de π, uma soma infinita (frequentemente chamada fórmula BBP):

Aqui um exemplo de implementação em Powershell. A fórmula converge rapidamente, com poucas iterações.

$PI = 0
For ([long]$k=0;$k -lt 12;$k++) {
   $PI += 1/[Math]::Pow(16,$k) * ( 4/(8*$k+1) - (2/(8*$k+4)) - 1/(8*$k+5) - 1/(8*$k+6) )
   Write-Host "Para k=$k, PI é ~" $PI 
}

Para k=0, PI é ~ 3,13333333333333
Para k=1, PI é ~ 3,14142246642247
Para k=2, PI é ~ 3,14158739034658
Para k=3, PI é ~ 3,14159245756744
Para k=4, PI é ~ 3,14159264546034
Para k=5, PI é ~ 3,14159265322809
Para k=6, PI é ~ 3,14159265357288
Para k=7, PI é ~ 3,14159265358897
Para k=8, PI é ~ 3,14159265358975
Para k=9, PI é ~ 3,14159265358979
Para k=10, PI é ~ 3,14159265358979
Para k=11, PI é ~ 3,14159265358979

Um equivalente wc do Linux

No Unix/Linux, há o comando wc com o qual é possível obter o número de linhas, número de palavras e o número de bytes de um arquivo.

Uma maneira de obter-se um comando equivalente através do Powershell, poderia ser:

Para mais, leia.

Project Euler 18

No problema 18 do Project Euler, a proposta é encontrar o caminho com a maior soma partindo-se do topo de um triângulo de números. Só são permitidos caminhos que passem pelos números adjacentes da camada (ou linha) seguinte do triângulo. Assim, a proposta é essa, de todos os caminhos possíveis encontrar aquele cuja soma seja a maior.

Na implementação, escolheu-se a abordagem bottom-up, aplicando a seguinte ideia.
Observe esse triângulo de exemplo, formado pelas primeiras 4 linhas do triângulo proposto.

Soma-se os adjacentes da camada inferior (bottom) com o número da camada de cima (up) e, dessa forma, os valores dos números da camada de cima são substituídos pelo maior valor dessas somas. Por exemplo, da camada inferior (bottom) temos os números 18 e 35, adjacentes do número 17 da camada de cima (up). A maior soma é dos números 35+17, assim o valor 52 é o que será armazenado. Ao final, a camada de cima (up) será atualizada e ficará com os seguintes valores.

Repetindo-se esse algoritmo, a segunda linha ficaria como abaixo, sendo o resultado final, ao ser efetuada a soma com a primeira linha, o valor 304.

Aplicando-se ao triângulo inteiro proposto, a implementação ficou assim:

$tri = @((75),(95,64),(17,47,82),(18,35,87,10),(20,04,82,47,65),(19,01,23,75,03,34),(88,02,77,73,07,63,67),(99,65,04,28,06,16,70,92),(41,41,26,56,83,40,80,70,33),(41,48,72,33,47,32,37,16,94,29),(53,71,44,65,25,43,91,52,97,51,14),(70,11,33,28,77,73,17,78,39,68,17,57),(91,71,52,38,17,14,91,43,58,50,27,29,48),(63,66,04,68,89,53,67,30,73,16,69,87,40,31),(04,62,98,27,23,09,70,98,73,93,38,53,60,04,23))
$bottom = @()
$up = @()
$max = 0

For ($li=(($tri.Length)-1); $li -gt 0; $li--) {
    $bottom = $tri[$li]
    $up = $tri[($li-1)]
    For ($i=1; $i -lt (($tri[$li].Length)-1); $i++) {
        If (($bottom[$i]+$up[$i]) -gt ($bottom[$i+1]+$up[$i])) {
            $up[$i] = ($bottom[$i]+$up[$i])
        }
        Else {
            $up[$i] = ($bottom[$i+1]+$up[$i])
        }
    }
}

If (($bottom[0]+$up[0]) -gt ($bottom[1]+$up[0])) {
     $max = ($bottom[0]+$up[0])
}
Else {
     $max = ($bottom[1]+$up[0])
}

Write-Host "Project Euler 18. Valor Máximo:"$max

Project Euler 18. Valor Máximo: 1074

Project Euler 17

O problema 17 do Project Euler propõe como desafio somar o número de letras dos números de 1 a 1000 escritos por extenso. Vamos adaptar o problema para o português do Brasil, mantendo-se a mesma proposta.

[int]$sum = 0

Function decompPTBR([int]$num) {
    $unidade = @("dez","um","dois","três","quatro","cinco","seis","sete","oito","nove")
    $dez_nove = @("onze","doze","treze","quatorze","quinze","dezesseis","dezessete","dezoito","dezenove")
    $dezena = @("vinte","trinta","quarenta","cinquenta","sessenta","setenta","oitenta","noventa","cem")
    $centena = @("cento","duzentos","trezentos","quatrocentos","quinhentos","seiscentos","setecentos","oitocentos","novecentos","mil")

    If ($num -le 10) {
        Write-Host $num":" $unidade[$num % 10]
        Return $unidade[$num % 10].Length
    }
    If (($num -gt 10) -and ($num -lt 20)) {
        Write-Host $num":" $dez_nove[($num % 10)-1]
        Return $dez_nove[($num % 10)-1].Length
    }
    If (($num -ge 20) -and ($num -le 100)) {
        $u = $num % 10
        $d = [Math]::Truncate($num / 10) - 2
        If ($u -eq 0) { 
            Write-Host $num":" $dezena[$d] 
            Return $dezena[$d].Length
        }
        Else { 
            Write-Host $num":" $dezena[$d] "e" $unidade[$u]
            Return ($dezena[$d].Length + 1 + $unidade[$u].Length)
        } 
    }
    If (($num -gt 100) -and ($num -le 1000)) {
        $u = $num % 10
        $d = [Math]::Truncate(($num / 10) % 10) ## - 2
        $c = [Math]::Truncate($num / 100) ## - 1

        If (($d*10+$u) -eq 0) { 
            Write-Host $num":" $centena[($c-1)] 
            Return $centena[($c-1)].Length
        }
        Else {
            If (($d*10+$u) -le 10) {
                Write-Host $num":" $centena[($c-1)] "e" $unidade[$u]
                Return ($centena[($c-1)].Length + 1 + $unidade[$u].Length)
            }
            If ( (($d*10+$u) -gt 10) -and (($d*10+$u) -lt 20) ) {
                Write-Host $num":" $centena[($c-1)] "e" $dez_nove[($u-1)]
                Return ($centena[($c-1)].Length + 1 + $dez_nove[($u-1)].Length)
            }
            If ((($d*10+$u) -ge 20) -and ($u -eq 0)) {
                Write-Host $num":" $centena[($c-1)] "e" $dezena[($d-2)]
                Return ($centena[($c-1)].Length + 1 + $dezena[($d-2)].Length)
            }
            If ((($d*10+$u) -ge 20) -and ($u -gt 0)) {
                Write-Host $num":" $centena[($c-1)] "e" $dezena[($d-2)] "e" $unidade[$u]
                Return ($centena[($c-1)].Length + 1 + $dezena[($d-2)].Length + 1 + $unidade[$u].Length)
            }
        }
    }
}

For ([int]$num=1; $num -le 1000; $num++) {
    $sum += decompPTBR($num)
}

Write-Host "=========================================="
Write-Host "Número de letras dos números de 1 a 1000:" $sum
Write-Host "=========================================="

Estamos imprimindo os números por extenso:

1: um
2: dois
3: três
4: quatro
5: cinco
6: seis
7: sete
8: oito
9: nove
10: dez
11: onze
12: doze
13: treze
14: quatorze
15: quinze
16: dezesseis
17: dezessete
18: dezoito
19: dezenove
20: vinte
21: vinte e um
22: vinte e dois
23: vinte e três
24: vinte e quatro

989: novecentos e oitenta e nove
990: novecentos e noventa
991: novecentos e noventa e um
992: novecentos e noventa e dois
993: novecentos e noventa e três
994: novecentos e noventa e quatro
995: novecentos e noventa e cinco
996: novecentos e noventa e seis
997: novecentos e noventa e sete
998: novecentos e noventa e oito
999: novecentos e noventa e nove
1000: mil
==========================================
Número de letras dos números de 1 a 1000: 19672
==========================================

Project Euler 16

O desafio no problema 16 de está relacionado a estouro de buffer, já que 2 elevado à potência 1000 gera um número muito grande.

Uma alternativa seria calcular as multiplicações tal e qual fazemos manualmente, armazenando os dígitos do resultado em um array. Assim, iremos efetuar 1000 multiplicações de cada resultado intermediário por 2. Ao final, teremos o número correspondente ao resultado de 2^1000 armazenado em um array, dígito a dígito, porém ele estará invertido.

Para o propósito do problema, não faz diferença ele estar invertido, já que estamos interessado na soma dos dígitos.

## Número de dígitos de 2^1000 pode ser calculado com
## Ndig = 1 + Log10(2^1000)
$tamanho_array = [Math]::Truncate(1 + 1000 * [Math]::Log10(2))
## Cria-se um array para armazenar os dígitos
$digito = New-Object int[] $tamanho_array

[int]$ordem = 0
$digito[0] = 1

## O número que será armazenado no array $digito
## será o resultado das multiplicações por 2 (1000 vezes)
## Cada digito é calculado separadamente, na forma
## como se faz a multiplicação manualmente
For ($i=0; $i -lt 1000; $i++) {
    [int]$pracima = 0
    For ($j = 0; $j -le $ordem; $j++) {
        $produto = 2 * $digito[$j] + $pracima
        $digito[$j] = $produto % 10
        If (($produto / 10) -lt 1) { $pracima = 0 }
        Else { $pracima = 1}
        If (($j -eq $ordem) -and ($pracima -gt 0)) {
            $ordem++
        }
    }
}

## Ao final o número armazenado no array $digito
## está invertido, mas para o propósito de
## somar os dígitos não importa
[int]$soma_digitos = 0

For ($i=0; $i -lt $digito.Length; $i++) {
    $soma_digitos += $digito[$i]
}

Write-Host "A soma dos dígitos de 2^1000 é:" $soma_digitos

A soma dos dígitos de 2^1000 é: 1366

Desabilitar SMBv1

SMBv1 é um protocolo antigo, com muitas falhas, exploradas continuamente por malwares (p.ex.: ramsonware, wannacry, ...). Por conseguinte, vamos aqui mostrar um possível caminho para desabilitá-lo no MS Windows Server 2016 através do Powershell.

Inicialmente, verificamos se o protocolo está habilitado.

O valor True comprova que sim, está habilitado.

Vamos desabilitá-lo com Set-SmbServerConfiguration.

A seguir, vamos descobrir qual o nome da Feature que contém o protocolo SMBv1. Para tanto, vamos utilizar o comando Get-WindowsFeature:

Com o comando, obtemos o nome FS-SMB1 e assim podemos utilizar Remove-WindowsFeature:

O servidor em questão deve ser reiniciado. Na sequência, repete-se o comando Get-WindowsFeature e comprova-se a desinstalação do protocolo SMBv1.

Project Euler 15

Em Project Euler, o problema 15 propõe encontrar o número de caminhos possíveis em uma grade 20x20. Como exemplo, uma figura representando as rotas em uma grade 2x2 é exibida:

Observando a grade 2x2, para chegarmos ao destino (2,2), temos em cada ponto a possibilidade de ir para a direita (D) ou para baixo (B), ou seja, há 2 possíveis caminhos, que são percorridos para a direita um X número de vezes e, para baixo, um Y número de vezes. Todas as rotas terão X+Y passos.
O problema pode ser resolvido de diversas maneiras, mas acredito que todas relacionadas com Binomial Coefficient. Dentro desse contexto, escolhemos a implementação através do Triângulo de Pascal, onde cada número é obtido da soma dos números anteriores que estão à esquerda e acima. Observa-se uma analogia ao problema, pois montando uma grade preenchida com os números do Triângulo de Pascal, a coordenada final sempre indicará o número de caminhos possíveis, como ilustra a figura abaixo.

Cada número alocado em uma coordenada da grade é igual a soma dos números das coordenadas imediatamente à esquerda e acima. Assim, o 6 é a soma 3+3. O 20, a soma 10+10. O 70, a soma 35+35. O 6 representa o número de caminhos possíveis em uma grade 2x2, pois está na coordenada (2,2). O 20 representa o número de caminhos possíveis em uma grade 3x3, pois está na coordenada (3,3). O 70 representa o número de caminhos possíveis em uma grade 4x4, pois está na coordenada (4,4).

Dessa forma, bastaria criar um programa que criasse a grade 20x20 correspondente, preenchendo o valor de cada coordenada. O valor da coordenada (20,20) será a resposta do problema.

$tam = 20
$tam_matriz = $tam + 1 
## Matriz deve ser somada de 1 para o triangulo de Pascal
$path = New-Object 'object[,]' $tam_matriz,$tam_matriz

For ([int]$x=0; $x -lt $tam_matriz; $x++) {
    For ([int]$y=0; $y -lt $tam_matriz; $y++) {
        If ($x -eq 0) { $path[0,$y] = 1 }
        If ($y -eq 0) { $path[$x,0] = 1 }
        If (($x -gt 0) -and ($y -gt 0)) {
            $path[$x,$y] = $path[($x-1),$y] + $path[$x,($y-1)]
        }
    }
}
Clear-Host
Write-Host "O número de caminhos possíveis, obtido pelo triângulo de Pascal"
Write-Host "para uma matriz 20x20, foi:" $path[($tam),($tam)

O número de caminhos possíveis, obtido pelo triângulo de Pascal
para uma matriz 20x20, foi: 137846528820