--- Day 4: Reindeer Tunnels ---
You are still scrubbing the smell of disinfectant and farm animals off your hands when Patch kicks your door open. She looks less panicked than yesterday, but significantly more annoyed.
"Good news," she says, tossing you a protein bar. "The barriers held. The virus is contained. Bad news: while we were playing doctor with the livestock, the engineering department went rogue."
She doesn't even wait for you to put your boots on before dragging you out to the elevators. She hits the button for Sub-Level 4: High-Velocity Logistics.
"We built a new system of 'Reindeer Tunnels' to connect the delivery hubs," Patch explains as the elevator plummets. "It was supposed to be a breakthrough in speed. Unfortunately, Vixen got involved."
The elevator doors open onto a cavernous, echoing tunnel entrance. Standing by a massive whiteboard is Vixen, the Chief Reindeer Engineer. She is currently yelling at a topographical map.
"It is a simple question of thermodynamics!" Vixen shouts at a terrified-looking intern. "Energy in, energy out!" She spots you and Patch and points a laser pointer directly at your chest. "You. You understand graphs, right? Please tell me you understand graphs."
"We have a situation," Patch interrupts, stepping between you and the laser.
"We have a disaster," Vixen corrects. She taps the whiteboard. "These tunnels are clever. Too clever. We integrated natural slopes to provide gravitational speed boosts. Great for speed, terrible for biology."
She pulls up a schematic of the tunnel network.
"Here is the problem," Vixen sighs, her ears drooping slightly. "Reindeer aren't machines; they run on carrots. Moving through these tunnels requires energy. Gravity helps on the slopes, sure, but we still have to manage the metabolic cost. We need to feed them carrots to maintain strength."
"If we take the wrong path," Patch translates, "we run out of food before we hit the exit."
"Exactly," Vixen says. "I need to find the most efficient path from the tunnel entrance to the exit. I need to minimize the total carrot cost. If we use too many carrots, the depot runs dry, the reindeer stall, and Christmas is cancelled."
Can you analyze the tunnel maps and calculate the lowest cost journey for Vixen?
Given a list of maps of the tunnel system, find for each map a path that minimises the total number of carrots required to travel from the start of the tunnel sector, S, to the exit, E.
The maps will be given as 2D ASCII character grids. An example can be seen below. Within the grid, the reindeer caravan can move up, down, left, or right to an adjacent, non-tunnel-wall cell. The characters in the grid each represent the geography of that particular tunnel region:
(space), S, E): The ground is flat.
^, v, <, >): These floors are tilted. The cost to leave depends on your direction relative to the arrow:
>): -0.5 carrots. (The slide provides momentum, enough to reduce the carrots needed for the next tile).>): 3 carrots. (Climbing is exhausting).>): 1 carrot. (Standard effort).C): A delicious snack!
The input file contains a list of double newline separated mazes. For each maze, give your answer as a tuple (c,l):
c: Minimised total carrot cost (If whole, omit the decimal - e.g. 2 instead of 2.0)l: Path length for this carrot cost (Number of moves taken from S to E. This does NOT include the starting position S in the count, but does include the ending position E. See the examples below for more info.)Join your answers for each maze with a , (e.g. (c1,l1),(c2,l2),...). Do not include spaces in your answer.
Example input:
#####
#S E#
##C##
#####
Output: (-1, 4)
The cost is as follows:
+1 (S -> )+1 ( -> C)-4 (C -> )+1 ( -> E)Example input:
###############
#S > > < #
#^###v#^### ###
# <v< # CC #
### ##### #####
# C >> < E#
###############
Output: (5.5, 26)
The cost is as follows:
+1 +1 +1 +1 (S -> -> -> -> >)+1 -0.5 +1 -0.5 -0.5 +1 +1 (> -> v -> -> < -> v -> -> -> C)-4 +1 -0.5 -0.5 +1 (C -> -> > -> > -> -> <)+1 -4 -4 (< -> -> C -> C) - moving up to collect the carrots+1 +1 +1 +3 +1 +1 +1 ((C) -> (C) -> -> < -> -> -> -> E) - retracing our steps to get back to the exit without collecting the carrot bundles a second time.###############
#S---> #
#^###v# ### ###
# v</# CC #
###|#####|#####
# \C->>-<---E#
###############