Project - Euler 4

O enunciado do problema de nº 4 pede que se encontre o maior palíndromo da multiplicação de 2 números de 3 dígitos.

O enfoque aqui será o de implementar a solução tendo por base o método de busca de palíndromos que utilizamos no post Invertendo String e Palíndromos. Também, utilizaremos o fato de que estamos a procura do maior palíndromo, logo faz mais sentido começarmos a busca pelos números mais altos, dividindo a busca em intervalos [999-900], [899-700], etc. Assim sendo, quando encontrarmos um palíndromo, certamente será o maior, pois estamos multiplicando números maiores do que os intervalos que se seguirão. A busca então pode ser interrompida, acelerando a resposta.

Function ehPalindromo($pal) {
    $reversePal = -join([System.Linq.Enumerable]::Reverse($pal))
    if ($pal -eq $reversePal) {
        Return $true
    }
    else {
        Return $false
    }
}

Function VerPalNoIntervalo([Int32]$int1, [Int32]$int2) {
    [Int32]$max = 0
    For ($i=$int1; $i -gt $int2; $i--) {
        For ($j=$int1; $j -gt $int2; $j--) {
            If (ehPalindromo ([String]($i*$j))) {
                If (($i * $j) -gt $max) {
                    $max = $i * $j
                    Write-Host "Palíndromo entre $i * $j = $max"
                    Return $max
                }
            }
        } ## for $j
    } ## for $i
    Return 0
}

Clear-Host
[Int32]$i=999
For ([Int32]$j=899; $j -gt 100; $j-=100) {
    $i = $j + 100
    If (VerPalNoIntervalo $i $j) {
        Write-Host "O maior palíndromo encontrado de 3 dígitos foi: $max"
        Break
    }
}

Na implementação, a função ehPalindromo retorna $true se o número em questão é palíndromo. A função VerPalNoIntervalo recebe um intervalo, por exemplo [999-900], e verifica se há um palíndromo nesse intervalo - a verificação é feita chamando a função ehPalindromo.
No corpo principal, foi construído um loop que chama a função VerPalNoIntervalo passando os intervalos de busca. Conforme dito, como a busca está sendo feita a partir dos números maiores, em bloco, ao ser encontrado um palíndromo é seguro deduzir que é o maior.

Palíndromo entre 993 * 913 = 906609
O maior palíndromo encontrado de 3 dígitos foi: 906609

Recursividade

Se tivermos um algoritmo para resolver um problema solucionando uma instância menor do mesmo problema, podemos usar funções recursivas. Reduz-se o problema até uma parte em que a recursividade cessa.

Quando se implementa recursividade, o exemplo clássico que nos vem à mente é o do cálculo do fatorial de um número. Se bem observarmos, o fatorial de um número é calculado multiplicando-o pelos números que o antecedem. Assim, fatorial de 6! = 6x5x4x3x2x1. E, por definição, o fatorial de 0! = 1.

Desse modo, é possível implementar facilmente uma função recursiva que calcule o fatorial de um número. Por exemplo:

Function fatorial([Int32]$num) {
    if ($num -eq 0) { return 1 }
    return $num * (fatorial($num-1))
}

Clear-Host
do {
    try {
        $numOk = $true
        [Int32]$num = Read-host `
        "Digite um número entre 0-100 para calcular o fatorial e pressione [ENTER]"
    }
    catch {$numOK = $false}
}
until (($num -ge 0 -and $num -le 100) -and $numOK)

Write-Host -NoNewline "O fatorial de $num é: "
fatorial($num)

Um exemplo de execução para o cálculo do fatorial de 7!

Digite um número entre 0-100 para calcular o fatorial e pressione [ENTER]: 7
O fatorial de 7 é: 5040

No post Invertendo Strings e Palíndromos, demonstramos uma maneira de implementar uma função que verifica se uma string é um palíndromo, ou seja, sua forma inversa tem escrita idêntica. É possível implementar uma função recursiva que verifica se uma string é palíndromo, mas fica apenas como exercício de programação, dado que a implementação no post anterior é bem mais simples.

Seguindo a ideia para funções recursivas de dividir um problema em instâncias menores, observamos que palavras são palíndromos quando a letra inicial e final são as mesmas. Assim, podemos usar esse algoritmo de testar se são iguais as letras inicial e final, removê-las e repetir a mesma lógica, até que não restem letras ou reste uma letra central. Se isso acontecer, a palavra é um palíndromo. Cada iteração seria uma chamada à função recursiva. O código poderia ser escrito assim:

Function trimFirstLast($pal) {
    $pal = $pal.TrimStart($pal[0])
    $pal = $pal.TrimEnd($pal[$pal.Length-1])
    return $pal
}

Function ehPalindromo([String]$pal) {
    if ($pal.Length -lt 2) { return $true }
    if ($pal[0] -ne $pal[$pal.Length-1]) { return $false }
    return ehPalindromo(trimFirstLast($pal))
}

$palavras = @("RELER","REVIVER","RADAR","ARARA","AMORA","SALAS",`
"ANILINA","MUSSUM","CASACA","MOTOR","OSSO","RIR","MIRIM","ROTOR")

Clear-Host

ForEach ($pal in $palavras) {
    Write-Host -NoNewLine "$pal é palíndromo? "
    ehPalindromo $pal
}

Com o seguinte resultado de execução:

RELER é palíndromo? True
REVIVER é palíndromo? True
RADAR é palíndromo? True
ARARA é palíndromo? True
AMORA é palíndromo? False
SALAS é palíndromo? True
ANILINA é palíndromo? True
MUSSUM é palíndromo? True
CASACA é palíndromo? False
MOTOR é palíndromo? False
OSSO é palíndromo? True
RIR é palíndromo? True
MIRIM é palíndromo? True
ROTOR é palíndromo? True

Referência: KHANACADEMY - Recursividade

Invertendo String e Palíndromos

Não há em System.String um método para inverter uma string, mas nem por isso é difícil consegui-lo.

Vamos enumerar 5 maneiras de inverter strings:

1. $string | %{-join $_[$_.Length..0]}
2. -join([System.Linq.Enumerable]::Reverse($string))
3. -join($string).ForEach({[Regex]::Matches($_ , ‘.’ , ‘RightToLeft’)})
4. $string[-1..-($pal.Length)] -join ""
5. -join (($pal.Length-1)..0 | ForEach-Object { $pal[$_]})

$pal = "Powershell"
$reverseV1 = $pal | %{-join $_[$_.Length..0]}
Write-Host -ForeGroundColor Yellow $pal":" -NoNewline
Write-Host -ForeGroundcolor Cyan $reverseV1

$pal = "Inverte"
$reverseV2 = -join([System.Linq.Enumerable]::Reverse($pal))
Write-Host -ForeGroundColor Yellow $pal":" -NoNewline
Write-Host -ForeGroundcolor Cyan $reverseV2

$pal = "Strings"
$reverseV3 = -join($pal).ForEach({[Regex]::Matches($_ , ‘.’ , ‘RightToLeft’)})
Write-Host -ForeGroundColor Yellow $pal":" -NoNewline
Write-Host -ForeGroundcolor Cyan $reverseV3

$pal = "Muito"
$reverseV4 = $pal[-1..-($pal.Length)] -join ""
Write-Host -ForeGroundColor Yellow $pal":" -NoNewline
Write-Host -ForeGroundcolor Cyan $reverseV4

$pal = "Facilmente"
$reverseV5 = -join (($pal.Length-1)..0 | ForEach-Object { $pal[$_]})
Write-Host -ForeGroundColor Yellow $pal":" -NoNewline
Write-Host -ForeGroundcolor Cyan $reverseV5

Palíndromos são palavras ou frases que podem ser lidas da esquerda para a direita ou da direita para a esquerda, como por exemplo RODADOR.

Vamos utilizar o Powershell para escrever uma função que receba uma palavra como parâmetro e nos diga se ela é um palíndromo. Para tanto, a lógica que vamos utilizar é a de inverter a string e compará-la com ela mesma.

Function ehPalindromo($pal) {
    $reversePal = -join([System.Linq.Enumerable]::Reverse($pal))
    if ($pal -eq $reversePal) {
        Write-Host -ForegroundColor Green $pal "é palíndromo"
    }
    else {
        Write-Host -ForegroundColor Red $pal "não é palíndromo"
    }
}

$palavras = @("RELER","REVIVER","RADAR","ARARA","AMORA","SALAS",`
"ANILINA","MUSSUM","CASACA","OSSO","RIR","MIRIM")

Write-Host "----------------------------------"
Write-Host "   P A L Í N D R O M O S"
Write-Host "----------------------------------"

ForEach ($pal in $palavras) { ehPalindromo($pal) }