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]

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

Project Euler 13

Obter os 10 primeiros dígitos da soma de 100 números de 50 dígitos conforme:

$array = "37107287533902102798797998220837590246510135740250463769376774900097126481248969700780504170182605387432498619952474105947423330951305812372661730962991942213363574161572522430563301811072406154908250230675882075393461711719803104210475137780632466768926167069662363382013637841838368417873436172675728112879812849979408065481931592621691275889832738442742289174325203219235894228767964876702721893184745144573600130643909116721685684458871160315327670386486105843025439939619828917593665686757934951621764571418565606295021572231965867550793241933316490635246274190492910143244581382266334794475817892575867718337217661963751590579239728245598838407582035653253593990084026335689488301894586282278288018119938482628201427819413994056758715117009439035398664372827112653829987240784473053190104293586865155060062958648615320752733719591914205172558297169388870771546649911559348760353292171497005693854370070576826684624621495650076471787294438377604532826541087568284431911906346940378552177792951453612327252500029607107508256381565671088525835072145876576172410976447339110607218265236877223636045174237069058518606604482076212098132878607339694128114266041808683061932846081119106155694051268969251934325451728388641918047049293215058642563049483624672216484350762017279180399446930047329563406911573244438690812579451408905770622942919710792820955037687525678773091862540744969844508330393682126183363848253301546861961243487676812975343759465158038628759287849020152168555482871720121925776695478182833757993103614740356856449095527097864797581167263201004368978425535399209318374414978068609844840309812907779179908821879532736447567559084803087086987551392711854517078544161852424320693150332599594068957565367821070749269665376763262354472106979395067965269474259770973916669376304263398708541052684708299085211399427365734116182760315001271653786073615010808570091499395125570281987460043753582903531743471732693212357815498262974255273730794953759765105305946966067683156574377167401875275889028025717332296191766687138199318110487701902712526768027607800301367868099252546340106163286652636270218540497705585629946580636237993140746255962240744869082311749777923654662572469233228109171419143028819710328859780666976089293863828502533340334413065578016127815921815005561868836468420090470230530811728164304876237919698424872550366387845831148769693215490281042402013833512446218144177347063783299490636259666498587618221225225512486764533677201869716985443124195724099139590089523100588229554825530026352078153229679624948164195386821877476085327132285723110424803456124867697064507995236377742425354112916842768655389262050249103265729672370191327572567528565324825826546309220705859652229798860272258331913126375147341994889534765745501184957014548792889848568277260777137214037988797153829820378303147352772158034814451349137322665138134829543829199918180278916522431027392251122869539409579530664052326325380441000596549391598795936352974615218550237130764225512118369380358038858490341698116222072977186158236678424689157993532961922624679571944012690438771072750481023908955235974572318970677254791506150550495392297953090112996751986188088225875314529584099251203829009407770775672113067397083047244838165338735023408456470580773088295917476714036319800818712901187549131054712658197623331044818386269515456334926366572897563400500428462801835170705278318394258821455212272512503275512160354698120058176216521282765275169129689778932238195734329339946437501907836945765883352399886755061649651847751807381688378610915273579297013376217784275219262340194239963916804498399317331273132924185707147349566916674687634660915035914677504995186714302352196288948901024233251169136196266227326746080059154747183079839286853520694694454072476841822524674417161514036427982273348055556214818971426179103425986472045168939894221798260880768528778364618279934631376775430780936333301898264209010848802521674670883215120185883543223812876952786713296124747824645386369930090493103636197638780396218407357239979422340623539380833965132740801111666627891981488087797941876876144230030984490851411606618262936828367647447792391803351109890697907148578694408955299065364044742557608365997664579509666024396409905389607120198219976047599490197230297649139826800329731560371200413779037855660850892521673093931987275027546890690370753941304265231501194809377245048795150954100921645863754710598436791786391670211874924319957006419179697775990283006991536871371193661495281130587638027841075444973307840789923115535562561142322423255033685442488917353448899115014406480203690680639606723221932041495354150312888033953605329934036800697771065056663195481234880673210146739058568557934581403627822703280826165707739483275922328459417065250945123252306082291880205877731971983945018088807242966198081119777158542502016545090413245809786882778948721859617721078384350691861554356628840622574736922845095162084960398013400172393067166682355524525280460972253503534226472524250874054075591789781264330331690"
$a50 = @()
For ([int]$i=0; $i -lt 100; $i++) { $a50+="" }
$i = 0
[Int64]$sum = 0
For ([int]$j=0; $j -lt 100; $j++) {
    $a50[$j] = $array[$i..($i+49)]
    $tmp = ""
    For ([int]$t=0;$t -lt 10; $t++) { $tmp += $a50[$j][$t]}
    $sum+=[convert]::ToInt64($tmp, 10)
    $i+=50
}
## Obtém somente os 10 dígitos com arredondamento
$TFD = $sum.ToString()
$t = ([int32]($TFD[8]+$TFD[9]+$TFD[10])+5)
$ts = $t.ToString()
$t2 = $TFD.Substring(0,8)
$TFD = $t2+($ts.Substring(0,2))
Write-Host "Os 10 primeiros dígitos da soma dos 100 números de 50 dígitos são: " $TFD

Os 10 primeiros dígitos da soma dos 100 números de 50 dígitos são:  5537376230

Project Euler - 6

Duas soluções para o problema 6 do Project Euler.

Function SomaQuadrados([Int32]$Num) {
    [Int32]$soma=0
    For ([int32]$i=1;$i -le $Num;$i++) {
        $soma += $i * $i
    }
    Return $soma
}

Function QuadradoSomas([Int32]$Num) {
    [Int32]$soma=0
    For ([int32]$i=1;$i -le $Num;$i++) {
        $soma += $i
    }
    Return ($soma * $soma)
}

[Int32]$s = SomaQuadrados 100
[Int32]$q = QuadradoSomas 100

Clear-Host
Write-Host -ForeGroundColor Yellow "SOLUÇÃO 1: Força Bruta"
Write-Host "A diferença entre o quadrado da soma dos 100 primeiros números [$q]"
Write-Host "e a soma dos quadrados dos números de 1 a 100 [$s] é: $q-$s ="($q-$s)
Write-Host "---------------------------------------------------------------------"
Write-Host -ForeGroundColor Yellow "SOLUÇÃO 2: Enfoque Matemático"
Write-Host "A soma dos números de 1 a N pode ser calculada com:"
Write-Host "Sn = n * (n + 1) / 2"
Write-Host "Se n = 100"
[Int32]$S100 = 100 * (100 + 1) / 2
Write-Host "S100 = 100 * (100 + 1) / 2 = " $S100
Write-Host "Logo, o quadrado da soma é: " ($S100 * $S100)
Write-Host "A soma dos quadrados de 1 a N pode ser calculada com:"
Write-Host "SQn = n * (n + 1) * (2n + 1) / 6"
Write-Host "Para n = 100"
$SQ100 = 100 * (100 + 1) * (2 * 100 + 1) / 6
Write-Host "SQ100 = 100 * (100 + 1) * (2 * 100 + 1) / 6 = " $SQ100
Write-Host "A diferença entre o quadrado da soma dos 100 primeiros números"
Write-Host "e a soma dos quadrados dos números de 1 a 100 é: "($S100*$S100-$SQ100)

SOLUÇÃO 1: Força Bruta
A diferença entre o quadrado da soma dos 100 primeiros números [25502500]
e a soma dos quadrados dos números de 1 a 100 [338350] é: 25502500-338350 = 25164150
---------------------------------------------------------------------
SOLUÇÃO 2: Enfoque Matemático
A soma dos números de 1 a N pode ser calculada com:
Sn = n * (n + 1) / 2
Se n = 100
S100 = 100 * (100 + 1) / 2 =  5050
Logo, o quadrado da soma é:  25502500
A soma dos quadrados de 1 a N pode ser calculada com:
SQn = n * (n + 1) * (2n + 1) / 6
Para n = 100
SQ100 = 100 * (100 + 1) * (2 * 100 + 1) / 6 =  338350
A diferença entre o quadrado da soma dos 100 primeiros números
e a soma dos quadrados dos números de 1 a 100 é:  25164150

Project Euler 2

Implementaremos 2 soluções para o problema de nº 2 do Project Euler:

Estamos implementando uma solução através do uso de recursividade (RecursiveFibonacciEvenSum) e outra utilizando um loop (FibonacciEvenSum).

Function RecursiveFibonacciEvenSum([Long]$pre, [Long]$cur, [Long]$evenSum) {
    If ($cur -gt 4000000) { Return $evenSum}
    If ($cur %2 -eq 0) { $evenSum = $evenSum + $cur }
    [Long]$tmp = $pre + $cur
    $pre = $cur
    $cur = $tmp
    RecursiveFibonacciEvenSum $pre $cur $evenSum
}
 
Function FibonacciEvenSum([Long]$pre, [Long]$cur) {
    [Long]$tmp = 0
    [Long]$evenSum = 0
 
    While($tmp -lt 4000000) {
        $tmp = $pre + $cur
        If ($tmp % 2 -eq 0) { $evenSum = $evenSum + $tmp }
        $pre = $cur
        $cur = $tmp
    }
    Return $evenSum
}
 
Clear-Host
$time = New-Object System.Diagnostics.Stopwatch
$time.Start()
RecursiveFibonacciEvenSum 1 1 0
$time.Stop()
$ts = $time.Elapsed
Write-Host "Tempo calculado com Recursividade:"
Write-Host $ts.Seconds "segundos e" $ts.Milliseconds "milisegundos"
 
$time2 = New-Object System.Diagnostics.Stopwatch
$time2.Start()
FibonacciEvenSum 1 1
$time2.Stop()
$ts2 = $time2.Elapsed
Write-Host "Tempo calculado com Loop:"
Write-Host $ts2.Seconds "segundos e" $ts2.Milliseconds "milisegundos"

Calculamos a soma dos números pares na Série de Fibonacci, obtendo 4613732 como resultado. Com relação ao tempo gasto, observamos que a implementação através de loop teve melhor desempenho do que a solução que utiliza recursividade.

4613732
Tempo calculado com Recursividade:
0 segundos e 157 milisegundos

4613732
Tempo calculado com Loop:
0 segundos e 28 milisegundos