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