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

Esta é uma implementação para o problema 8 do Project Euler: Encontrar em um número de 1000 dígitos, o maior número da multiplicação de 13 dígitos adjacentes.

Clear-Host

[String]$milDig = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"
[Long]$Multi13 = 0
[Long]$curMulti = 0
$dig = (0,0,0,0,0,0,0,0,0,0,0,0,0)
$digSalvo = (0,0,0,0,0,0,0,0,0,0,0,0,0)

For ([Int32]$i=0; $i -lt 988; $i++) {
    For ($d=0;$d -lt 13;$d++) {
        $dig[$d] = [convert]::ToInt32($mildig[$i+$d],10)
    }    
    $curMulti = $dig[0]*$dig[1]*$dig[2]*$dig[3]*$dig[4]*$dig[5]*`
        $dig[6]*$dig[7]*$dig[8]*$dig[9]*$dig[10]*$dig[11]*$dig[12]

    If ($curMulti -gt $Multi13) { 
        $Multi13 = $curMulti
        For ([Int32]$d=0;$d -lt 13;$d++) {
            $digSalvo[$d] = $dig[$d]
        }
    }
}

Write-Host "Dígitos adjacentes com maior produto são:"
Write-Host $digSalvo[0] "x" $digSalvo[1] "x" $digSalvo[2] "x" $digSalvo[3] "x"`
           $digSalvo[4] "x" $digSalvo[5] "x" $digSalvo[6] "x" $digSalvo[7] "x"`
           $digSalvo[8] "x" $digSalvo[9] "x" $digSalvo[10] "x" $digSalvo[11] "x"`
           $digSalvo[12] "=" $Multi13

Os 13 dígitos adjacentes com maior produto são:
5 x 5 x 7 x 6 x 6 x 8 x 9 x 6 x 6 x 4 x 8 x 9 x 5 = 23514624000