AoC Day8

day8.ps1

function Import-PuzzleInput {
    param (
        $Path
    )
    $instructions, $null, $puzzleInput = Get-Content $Path
    $nodes = @{}
    $puzzleInput |
        ForEach-Object {
            $null = $_ -match '^(.{3}) = \((.{3}), (.{3})\)$'
            $nodes[$Matches[1]] = [PSCustomObject]@{
                Name = $Matches[1]
                L    = $Matches[2]
                R    = $Matches[3]
            }
        }

    Write-Output ([PSCustomObject]@{
            Instructions = [string[]]($instructions.ToCharArray())
            Nodes        = $nodes
        })
}

function Invoke-Instructions {
    param (
        $Instructions,
        $Nodes,
        $StartNodeName,
        $EndNodeNamePattern

    )
    $i = 0
    $currentNode = $Nodes[$StartNodeName]

    do {
        $i++
        # Use modulo to endlessly loop through the instructions
        $currentInstruction = $Instructions[($i % $Instructions.Count) - 1]

        Write-Verbose "Step ${i}: Invoking $currentInstruction on $($currentNode.Name)"
        $nextNodeName = $currentNode.$currentInstruction
        $endNodeFound = ($nextNodeName -match $EndNodeNamePattern)
        $currentNode = $Nodes[$nextNodeName]

    } until ($endNodeFound)

    Write-Output $i
}

function Invoke-GhostInstructions {
    param (
        $Instructions,
        $Nodes,
        $StartNodeNamePattern,
        $EndNodeNamePattern

    )
    $startNodeNames = $Nodes.Keys -match $StartNodeNamePattern
       
    $pathLenghs = $startNodeNames | 
        ForEach-Object {
            $invokeInstructionsSplat = @{
                Instructions       = $Instructions
                Nodes              = $Nodes 
                StartNodeName      = $_
                EndNodeNamePattern = '..Z'
            }
            Invoke-Instructions @invokeInstructionsSplat
        }

    $lcm = Get-LCM -Numbers $pathLenghs
    
    Write-Output $lcm
}

function Get-LCM {

    param (
        $Numbers
    )

    $first, $second, $Numbers = $Numbers
    
    $lcm = leastCommonMultiple -a $first -b $second
    if ($null -ne $Numbers) {
        $lcm = Get-LCM -Numbers (@($Numbers) + $lcm)
    } 

    Write-Output $lcm
}


# 
# The follwoing two functions are taken from:
# https://github.com/dfinke/powershell-algorithms/tree/master/src/algorithms/math
#


function euclideanAlgorithm($originalA, $originalB) {
    $a = [Math]::Abs($originalA)
    $b = [Math]::Abs($originalB)

    if ($a -eq 0 -and $b -eq 0) {
        return $null
    }

    if ($a -eq 0 -and $b -ne 0) {
        return $b
    }

    if ($a -ne 0 -and $b -eq 0) {
        return $a
    }

    # Normally we need to do subtraction ($a - $b) but to prevent
    # recursion occurs too often we may shorten subtraction to ($a % $b).
    # Since ($a % $b) normally means that we've subtracted $b from a
    # many times until the difference became less than a.

    if ($a -gt $b) {
        return euclideanAlgorithm ($a % $b) $b
    }

    return euclideanAlgorithm ($b % $a) $a
}

function leastCommonMultiple([double]$a, [double]$b) {
    if ($a -eq 0 -and $b -eq 0) {
        return 0
    }

    [Math]::Abs($a * $b) / (euclideanAlgorithm $a $b)
}

##################################################################################

$puzzleInput = Import-PuzzleInput $PSScriptRoot/input.txt

$part1 = Invoke-Instructions -Nodes $puzzleInput.Nodes `
    -StartNodeName 'AAA' `
    -EndNodeNamePattern 'ZZZ' `
    -Instructions $puzzleInput.Instructions


$part2 = Invoke-GhostInstructions -Nodes $puzzleInput.Nodes `
    -StartNodeNamePattern '..A' `
    -EndNodeNamePattern '..Z' `
    -Instructions $puzzleInput.Instructions

Write-Host "
Part1: $part1
Part2: $part2
"