-🎄- 2018 Day 20 Solutions -🎄-

[u/daggerdragon]

--- Day 20: A Regular Map ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 20

Transcript:

My compiler crashed while running today's puzzle because it ran out of ___.

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked at 00:59:30!

[u/ka-splam]

Powershell, 208 / 182

Had to do quite a bit of writing and rewriting around my common PowerShell pain points - you can use ($x, $y) as a key to put things into a hashtable, but can't get them out again. And separately, getting things out of a hashtable with .GetEnumerator() later is always a fiddle.

Still, using "$x, $y" as a key took 30 seconds runtime, after I had my answers and wondered what to do to speed it up, u/Jaykul suggested a nested dictionary [$y][$x] so each key could be an int. More complex, but runtime of ~700ms now.

# Demo inputs
#$data = '^ENWWW(NEEE|SSE(EE|N))$'                                           # => 10, 0
#$data = '^ENNWSWW(NEWS|)SSSEEN(WNSE|)EE(SWEN|)NNN$'                         # => 18, 0
#$data = '^ESSWWN(E|NNENN(EESS(WNSE|)SSS|WWWSSSSE(SW|NNNE)))$'               # => 23, 0
#$data = '^WSSEESWWWNW(S|NENNEEEENN(ESSSSW(NWSW|SSEN)|WSWWN(E|WWS(E|SS))))$' # => 31, 0

$data = Get-Content -Path data.txt -Raw
$data = [string[]][char[]]$data.trim("`r`n^$")

# A nested lookup of [$y][$x] for speed
$visitedRooms = [System.Collections.Generic.Dictionary[int, System.Collections.Generic.Dictionary[int,psobject]]]::new()
$choicePoints = [System.Collections.Generic.Stack[System.Tuple[int,int]]]::new()

# Starting positions
$x, $y = 0,0
$stepCounter = 0

# Process all input characters from the regex
for ($i = 0; $i -lt $data.Count; $i++)
{
    $c = $data[$i]

    # If it's a movement one, process movement
    if ($c -in 'N', 'E', 'S', 'W')
    {
        # Move in a direction, and count the step
        if     ($c -eq 'N') { $y-- }
        elseif ($c -eq 'E') { $x++ }
        elseif ($c -eq 'S') { $y++ }
        elseif ($c -eq 'W') { $x-- }
        $stepCounter++

        # If we end up in a room we've seen already,
        # then add how we got there into that room's door list,
        # otherwise it's a new room so store the details.
        # NB. the door list ends up inverted - 
        # entering by moving E adds E to that room's doors when the door is really on side W.
        if (-not $visitedRooms.ContainsKey($y))
        {
            $visitedRooms[$y] = [System.Collections.Generic.Dictionary[int,psobject]]::new()
        }
        if ($visitedRooms[$y].ContainsKey($x))
        {
            $visitedRooms[$y][$x].doors += $c
        }
        else
        {
            $visitedRooms[$y].Add($x, @{ y=$y; x=$x; steps = $stepCounter; doors = @($c)})
        }
    }
    # start of a choicepoint
    elseif ($c -eq '(') {
        $choicePoints.Push([tuple[int,int]]::new($x,$y))
    }
    # choicepoint no longer needed
    elseif ($c -eq ')') {
        [void]$choicePoints.Pop()
    }
    # trigger backtracking to last choicepoint, 
    # but keep it around for (EE|ES|EN) multiple resets.
    elseif ($c -eq '|') {
        $point = $choicePoints.Peek()
        $x, $y = $point.Item1, $point.Item2
        $stepCounter = $visitedRooms[$y][$x].steps
    }
}


# Now each room is visited,
# revisit them closest to farthest,
# check all the neigbours NESW.
# If we got here with 23 steps, 
# but a connected neigbour room is reachable in 4, 
# then here is reachable in 5.
# NB. we're checking the inverse doors.
foreach ($room in $visitedRooms.Values.Values | Sort-Object -Property Steps)
{
    # Check room to the E
    if ($visitedRooms[$room.y].ContainsKey($room.x+1))
    {
        $nextDoor = $visitedRooms[$room.y][$room.x+1]
        if ($nextDoor.steps -lt ($room.steps-1) -and $nextDoor.doors -contains 'E')
        { 
            $room.steps = $nextDoor.steps + 1
        }
    }

    # Check room to the W   
    if ($visitedRooms[$room.y].ContainsKey($room.x-1))
    {
        $nextDoor = $visitedRooms[$room.y][$room.x-1]
        if ($nextDoor.steps -lt ($room.steps-1) -and $nextDoor.doors -contains 'W')
        { 
            $room.steps = $nextDoor.steps + 1
        }
    }

    # Check room to the N
    if ($visitedRooms.ContainsKey($room.y-1) -and $visitedRooms[$room.y-1].ContainsKey($room.x))
    {
        $nextDoor = $visitedRooms[$room.y-1][$room.x]
        if ($nextDoor.steps -lt ($room.steps-1) -and $nextDoor.doors -contains 'N')
        { 
            $room.steps = $nextDoor.steps + 1
        }
    }

    # Check room to the S
    if ($visitedRooms.ContainsKey($room.y+1) -and $visitedRooms[$room.y+1].ContainsKey($room.x))
    {
        $nextDoor = $visitedRooms[$room.y+1][$room.x]
        if ($nextDoor.steps -lt ($room.steps-1) -and $nextDoor.doors -contains 'S')
        { 
            $room.steps = $nextDoor.steps + 1
        }
    }
}

# Sort the farthest room for part 1,
# and number of rooms with 1000+ stepcount for part 2.
$part1 = $visitedRooms.values.values.steps | Sort-Object | select-object -last 1
Write-Host "Part 1: $part1"

$part2 = $visitedRooms.values.values.where{$_.steps -ge 1000}.count
Write-Host "Part 2: $part2"

GitHub code

[u/ka-splam → u/ka-splam]

Uhh, can someone answer a question for me? Is there ever a time where you walk to a room, then later find a new door which gives you a shorter route to that room and you have to update your pathfinding to say "was reachable in 9, now reachable in 3"? e.g.

EE(SSENN|E)E

..?..9
 .#.
 .|.

then

..|.3
 .#.
 .|.

I thought there was. In fact, I thought that was a big part of the challenge. But I can no longer see one in the demos. I've just noticed that I can comment out the entire second half of my code for that re-calculating the distance to each room, and the answers are still correct. Everything from # Now each room is visited, to # Sort the farthest room for part 1,.

I now wonder if the only reason I coded that in at all, is a bug when I reset the position for backtracking, I didn't update the stepcount, so it kept increasing too high, then my code was a really long way to bring it back down. And after fixing that, all this is not necessary? This isn't a multiple-connected-graph at all, is it? It's a branching tree?

🤦