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 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

Project Euler 14

Esse problema do Project Euler é sobre a Conjectura de Collatz.

Clear-Host
[int]$maxNumTerm = 0
[int]$numComMaisTerm = 0
$cache = -1000000..0

For ([int]$num=1; $num -lt 1000000; $num++) {
    [long]$curNum = $num
    [int]$curNumTerm = 1
    #Write-Host "Numero atual: " $curNum
    While (($curNum -gt 1) -and ($cache[$curNum] -lt 0)) {
        If ($curNum % 2 -eq 0) {
        ## even
            $curNum = $curNum / 2
        }
        Else {
            ## odd
            $curNum = 3 * $curNum + 1
        }
        If ($cache[$curNum] -gt 0) {
            $curNumTerm+=$cache[$curNum]
            Break
        }
        Else {
            $curNumTerm++
        }
        ##Write-Host $curNum
    }
    $cache[$num] = $curNumTerm
    If ($curNumTerm -gt $maxNumTerm) {
        $maxNumTerm = $curNumTerm
        $numComMaisTerm = $num
        Write-Host "O número que tem mais termos é $numComMaisTerm com $maxNumTerm"
    }
}

A verdade é que não consegui performance satisfatória com esse código. Chega-se ao resultado, mas leva um bom tempo.

O número que tem mais termos é 2223 com 183
O número que tem mais termos é 2463 com 209
O número que tem mais termos é 2919 com 217
O número que tem mais termos é 3711 com 238
O número que tem mais termos é 6171 com 262
O número que tem mais termos é 10971 com 268
O número que tem mais termos é 13255 com 276
O número que tem mais termos é 17647 com 279
O número que tem mais termos é 23529 com 282
O número que tem mais termos é 26623 com 308
O número que tem mais termos é 34239 com 311
O número que tem mais termos é 35655 com 324
O número que tem mais termos é 52527 com 340
O número que tem mais termos é 77031 com 351
O número que tem mais termos é 106239 com 354
O número que tem mais termos é 142587 com 375
O número que tem mais termos é 156159 com 383
O número que tem mais termos é 216367 com 386
O número que tem mais termos é 230631 com 443
O número que tem mais termos é 410011 com 449
O número que tem mais termos é 511935 com 470
O número que tem mais termos é 626331 com 509
O número que tem mais termos é 837799 com 525

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