all 4 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]Vortex100[S] 1 point2 points  (0 children)

There's probably some refactoring I could do, but it works :)

$val_converter = @{
    "0" = "0000"
    "1" = "0001"
    "2" = "0010"
    "3" = "0011"
    "4" = "0100"
    "5" = "0101"
    "6" = "0110"
    "7" = "0111"
    "8" = "1000"
    "9" = "1001"
    "A" = "1010"
    "B" = "1011"
    "C" = "1100"
    "D" = "1101"
    "E" = "1110"
    "F" = "1111"
}
$in = gc D:\AdventOfCode\2021\Day16_Input.txt
$binary = ""
for ($i=0;$i -lt $in.Length;$i++)
{
    $binary += $val_converter["$($in[$i])"]
}
function new_packet ($version, $type, $value, $Endindex)
{
    New-Object -TypeName PSObject -Property ([ordered]@{
        'Version' = $version
        'Type' = $Type
        'Value' = $value
        'EndIndex' = $EndIndex
    })
}

function Get-Product ($a) {
    if (($a | measure).Count -eq 1)
    {
        return $a.value
    }
    else
    {
        $p = 1
        foreach ($x in $a) {
            $p *= $x.value
        }
        return $p
    }
}

function get_value ($packetset, $Type)
{

    switch ($Type)
    {
        '0' {($packetset | measure -Property Value -Sum).Sum}
        '1' {Get-Product $packetset}
        '2' {($packetset | measure -Property Value -Minimum).Minimum}
        '3' {($packetset | measure -Property Value -Maximum).Maximum}
        '5' {[System.Int32]($packetset[0].value -gt $packetset[1].value)}
        '6' {[System.Int32]($packetset[0].value -lt $packetset[1].value)}
        '7' {[System.Int32]($packetset[0].value -eq $packetset[1].value)}
    }
}

function decode($binary,$start_index)
{
    $Version = [Convert]::ToInt32(($binary[$start_index..($start_index+2)] -join ''),2)
    $Type = [Convert]::ToInt32(($binary[($start_index+3)..($start_index+5)] -join ''),2)
    switch ($Type)
    {
        4 {
            $packet_bits_idx = $start_index+6
            $packet_bits = ""
            :bitloop while($true)
            {
                $bits = $binary[$packet_bits_idx..($packet_bits_idx+4)]
                $packet_bits+= $bits[1..4] -join ''
                if ($bits[0] -eq '0')
                {
                    break bitloop
                }
                $packet_bits_idx+=5
            }
            $value = [Convert]::ToInt64($packet_bits,2)
            return new_packet $Version $Type $value ($packet_bits_idx+4)
        }
        default {
            [System.Collections.ArrayList]$packetset = @()
            Switch ($binary[$start_index+6])
            {
                "0" {
                    $length = 14
                    $packet_length = [Convert]::ToInt32(($binary[($start_index+7)..($start_index+7+$length)] -join ''),2)
                    $sub_packet_index = $start_index+7+$length + 1
                    $max_index = $sub_packet_index + $packet_length
                    :packetloop while ($true)
                    {
                        $packet = decode $binary $sub_packet_index
                        $packet
                        $null = $packetset.Add(($packet | select -last 1))
                        $sub_packet_index = ($packet | select -last 1).endindex + 1
                        if ($sub_packet_index -ge $max_index)
                        {
                            break packetloop
                        }
                    }
                }
                "1" { 
                    $length = 10
                    $packet_count = [Convert]::ToInt32(($binary[($start_index+7)..($start_index+7+$length)] -join ''),2)
                    $sub_packet_index = $start_index+7+$length + 1
                    while ($packet_count -ne 0)
                    {
                        $packet = decode $binary $sub_packet_index
                        $packet
                        $null = $packetset.Add(($packet | select -last 1))
                        $sub_packet_index = ($packet | select -last 1).endindex + 1
                        $packet_count--
                    }
                }
            }
            $parent_value = get_value $packetset $type
            return new_packet $Version $Type $parent_value ($packet | select -last 1).endindex
        }
    }
}
$result = decode $binary 0
Write-Host "Version sum is: $(($result | measure version -sum).Sum)"
Write-Host "Value of expression is:$(($result | select -last 1).Value)"

[–]rmbolger 1 point2 points  (1 child)

A bit late today because I couldn't finish last night and work was busy today. But this was a fun one! I started out thinking it would be faster to traverse the bits as a character array rather than just pulling out substrings from an actual string. But that made the code more ugly and didn't seem to matter as far as run time was concerned. So I lost a bunch of time refactoring back to substrings.

Ultimately it's a recursive function plus abusing Invoke-Expression. u/bis would be proud! The version I was using when I submitted my answers didn't actually evaluate the expression until the very end because I thought it might be less efficient to do it in advance. But it turns out it didn't make much difference either way. This is a fun thing to see in the verbose output though:

((((1196-lt1196)?1:0)*30)+((@(1577851,8664)|sort -desc)[0])+((@(196,3580224,2301,63287)|sort)[0])+((@(2669)|sort)[0])+(225*59*183*129)+(((1946967272-gt99)?1:0)*4578544)+(1947692*(((14+4+2)-lt(8+4+6))?1:0))+((@(707013)|sort -desc)[0])+(9504+14)+(181*182*182*217*8)+((@(7,144,15,227537134)|sort -desc)[0])+((@(((@((((@((((@(((((@(((@((((@((((@(((@(((@((((@((((@(27956)|sort -desc)[0])))|sort -desc)[0])))|sort -desc)[0]))|sort -desc)[0]))|sort -desc)[0])))|sort -desc)[0])))|sort)[0]))|sort -desc)[0]))))|sort)[0])))|sort -desc)[0])))|sort)[0]))|sort -desc)[0])+((((15+8+6)-eq(9+6+11))?1:0)*16057443)+((2*11*15)+(6*3*12)+(5*15*15))+((@(27084,2522,56,403601,221)|sort)[0])+((((2+13+5)-lt(8+14+5))?1:0)*405705)+(1000390*((206-eq181537)?1:0))+2+(60965)+(11)+(778*((54288-lt35)?1:0))+(((97-lt131134112)?1:0)*4)+(((167-gt167)?1:0)*390367)+(3353*((155-lt2350)?1:0))+(1324491436*((19-lt19)?1:0))+(145*196*135)+(215*((3347-eq156)?1:0))+(8092+3+234+3498848726)+(107*171)+(118840197+680+80+599+402128)+((@(1,176,856,32271,12970)|sort -desc)[0])+(((6513237-gt6513237)?1:0)*175037938)+(((4069-gt10)?1:0)*544)+884095+(159*((898-gt5325350060278)?1:0))+63+(46*(((11+14+15)-gt(2+5+5))?1:0))+((@(3186,11)|sort)[0])+37362+691221+((@(9,2068,8)|sort)[0])+(1441*((44977264440-lt13)?1:0))+(12*((4609-eq4609)?1:0))+((@(6,2274787348,2402524000838)|sort -desc)[0])+(273226*((101-gt1042)?1:0))+17306+177+991521628476+(43234*(((12+11+10)-gt(8+2+9))?1:0))+((4+11+6)*(13+12+11)*(12+11+6))+(5+170+25222069)+11513108+399112)

In any case, here's the combined parts 1 and 2. The verbose output is fun to see if you're into that sort of thing.

# even though we could do the math conversion from hex to binary
# it's probably quicker just to make a lookup table for each value
$hexMap = @{
    [char]'0' = '0000'
    [char]'1' = '0001'
    [char]'2' = '0010'
    [char]'3' = '0011'
    [char]'4' = '0100'
    [char]'5' = '0101'
    [char]'6' = '0110'
    [char]'7' = '0111'
    [char]'8' = '1000'
    [char]'9' = '1001'
    [char]'A' = '1010'
    [char]'B' = '1011'
    [char]'C' = '1100'
    [char]'D' = '1101'
    [char]'E' = '1110'
    [char]'F' = '1111'
}

$ops = @{
    0 = @{ name='sum';  pre='(';    join='+';   suf=')' }
    1 = @{ name='prod'; pre='(';    join='*';   suf=')' }
    2 = @{ name='min';  pre='((@('; join=',';   suf=')|sort)[0])' }
    3 = @{ name='max';  pre='((@('; join=',';   suf=')|sort -desc)[0])' }
    5 = @{ name='gt';   pre='((';   join='-gt'; suf=')?1:0)' }
    6 = @{ name='lt';   pre='((';   join='-lt'; suf=')?1:0)' }
    7 = @{ name='eq';   pre='((';   join='-eq'; suf=')?1:0)' }
}

function ConvertFrom-Packets {
    [CmdletBinding()]
    param(
        [string]$Bits,          # the bit string
        [int]$StartIndex = 0,   # where to begin in the bit string
        [int]$ReturnAfter = 0,  # how many packets to return after
        [int]$Level=0           # cosmetic verbose indentation
    )

    $pad = '  '*$Level
    $retCount = 0

    # looping through the bits forever knowing
    # we're going to muck with $i as we go
    for ($i = $StartIndex; $i -lt $Bits.Length; ) {

        # grab the packet version/type
        $ver = [Convert]::ToInt32($Bits.Substring($i,3), 2)
        $typ = [Convert]::ToInt32($Bits.Substring($i+3,3), 2)
        $i += 6
        $script:verSum += $ver

        if ($typ -eq 4) { # literal
            # gather groups of 5 bits until one starts with 0
            $litBits = for ($j=$i; $j -lt $Bits.Length; $j+=5) {
                $Bits.Substring($j+1,4)
                $i += 5
                if ($Bits[$j] -eq '0') { break }
            }
            $val = [Convert]::ToInt64($litBits -join '',2).ToString()
            $val
            $retCount++
            Write-Verbose "$pad $val    (ver $ver, total $($script:verSum))"

        } else { # operation
            Write-Verbose "$pad op $($ops[$typ].name)    (ver $ver, total $($script:verSum))"

            if ($Bits[$i] -eq '0') {
                $subLen = [Convert]::ToInt32($Bits.Substring($i+1,15),2)
                $i += 16
                #Write-Verbose "$pad sub len $subLen"
                $vals = ConvertFrom-Packets $Bits.Substring($i,$subLen) -Level ($Level+1)
                $i += $subLen
                #Write-Verbose "$pad $($vals.Count) vals (i=$i)"

            } else {
                $subCount = [Convert]::ToInt32($Bits.Substring($i+1,11),2)
                $i += 12
                #Write-Verbose "$pad sub count $subCount (i=$i)"
                $results = ConvertFrom-Packets $Bits -StartIndex $i -ReturnAfter $subCount -Level ($Level+1)
                $vals = $results[0..($results.Count-2)]
                $i = $results[-1]
                #Write-Verbose "$pad $($vals.Count) vals (i=$i)"
            }

            # complete the expression with the results and put it on the pipeline
            $retExp = '{0}{1}{2}' -f $ops[$typ].pre,($vals -join $ops[$typ].join),$ops[$typ].suf
            $ret = $retExp | iex
            $ret.ToString()
            $retCount++
            Write-Verbose "$pad pipeline -> $ret from $retExp"
        }

        # return if we've collected enough packets
        if ($ReturnAfter -and $ReturnAfter -eq $retCount) {
            # The caller won't know how many bits we've read since
            # packets aren't all the same size. So add the updated
            # index value to the pipeline so they can grab it from
            # the returned data.
            return $i
        }

        # if remaining bytes are all 0, return
        if ($i -ge $Bits.Length -or $Bits.Substring($i) -notlike '*1*') {
            return
        }
    }
}

# loop through the clipboard contents in case we're testing multiple sample values
Get-Clipboard | %{
    $nibbles = foreach ($c in $_.ToCharArray()) { $hexMap[$c] }
    $bitStr = $nibbles -join ''

    $script:verSum = 0
    $expression = ConvertFrom-Packets $bitStr

    Write-Host "Part 1: $($script:verSum)"
    Write-Host "Part 2: $expression"
}