219 lines
8.5 KiB
C#
219 lines
8.5 KiB
C#
using Spectre.Console;
|
|
|
|
namespace AdventOfCode.Days;
|
|
|
|
public class Valve
|
|
{
|
|
public string Name { get; }
|
|
public int Rate { get; }
|
|
public IList<Valve> AccessibleValves { get; }
|
|
|
|
public Valve(string name, int rate)
|
|
{
|
|
Name = name;
|
|
Rate = rate;
|
|
AccessibleValves = new List<Valve>();
|
|
}
|
|
}
|
|
|
|
public record ValvePath(int CurrentMinute, int PressurePerMinute, int ReleasedPressure, Valve CurrentValve, HashSet<Valve> OpenedValves);
|
|
|
|
public class Day16 : Day
|
|
{
|
|
public override int Number => 16;
|
|
public override string Name => "Proboscidea Volcanium";
|
|
public override void RunPart1(bool display = true)
|
|
{
|
|
var startValve = ParseValves();
|
|
|
|
// Test all possibles paths
|
|
int maxPressure = 0;
|
|
var paths = new Queue<ValvePath>();
|
|
paths.Enqueue(new ValvePath(1, 0, 0, startValve, new HashSet<Valve>()));
|
|
|
|
// Remember best pressure at each valve
|
|
var valvePotential = new Dictionary<Valve, (int currentMinute, int potential)>();
|
|
|
|
while (paths.Count > 0)
|
|
{
|
|
var state = paths.Dequeue();
|
|
|
|
// Check if this state is worse than last one at this same valve
|
|
int potential = state.ReleasedPressure + (30 - state.CurrentMinute + 1) * state.PressurePerMinute;
|
|
if (valvePotential.TryGetValue(state.CurrentValve, out var lastState))
|
|
{
|
|
if (state.CurrentMinute >= lastState.currentMinute)
|
|
{
|
|
if (potential <= lastState.potential)
|
|
{
|
|
continue;
|
|
}
|
|
}
|
|
}
|
|
|
|
valvePotential[state.CurrentValve] = (state.CurrentMinute, potential);
|
|
|
|
// Release pressure at start of minute
|
|
var newPressure = state.ReleasedPressure + state.PressurePerMinute;
|
|
|
|
// Compute new max
|
|
if (newPressure > maxPressure)
|
|
{
|
|
maxPressure = newPressure;
|
|
}
|
|
|
|
// Stop at minute 30
|
|
if (state.CurrentMinute == 30)
|
|
{
|
|
continue;
|
|
}
|
|
|
|
// Check if the valve can be opened
|
|
if (!state.OpenedValves.Contains(state.CurrentValve))
|
|
{
|
|
// New state with current valve opened
|
|
var openedValves = new HashSet<Valve>(state.OpenedValves);
|
|
openedValves.Add(state.CurrentValve);
|
|
|
|
paths.Enqueue(new ValvePath(state.CurrentMinute + 1, state.PressurePerMinute + state.CurrentValve.Rate, newPressure, state.CurrentValve, openedValves));
|
|
}
|
|
|
|
// Move to all accessible valves
|
|
foreach (var accessibleValve in state.CurrentValve.AccessibleValves)
|
|
{
|
|
paths.Enqueue(new ValvePath(state.CurrentMinute + 1, state.PressurePerMinute, newPressure, accessibleValve, state.OpenedValves));
|
|
}
|
|
}
|
|
|
|
if (display)
|
|
{
|
|
AnsiConsole.MarkupLine($"[green]Max pressure released: [yellow]{maxPressure}[/][/]");
|
|
}
|
|
}
|
|
|
|
public override void RunPart2(bool display = true)
|
|
{
|
|
throw new NotImplementedException();
|
|
}
|
|
|
|
private static Valve ParseValves()
|
|
{
|
|
var valves = new Dictionary<string, Valve>();
|
|
|
|
// Create valves first
|
|
foreach (var line in Input.ReadAllLines())
|
|
{
|
|
var span = line.AsSpan();
|
|
|
|
var nameStart = span.IndexOf(' ') + 1;
|
|
var name = span[nameStart..(nameStart + 2)].ToString();
|
|
|
|
var rateStart = span.IndexOf('=') + 1;
|
|
var rateEnd = span.IndexOf(';');
|
|
|
|
var rate = int.Parse(span[rateStart..rateEnd]);
|
|
|
|
valves.Add(name, new Valve(name, rate));
|
|
}
|
|
|
|
// Add links
|
|
// Create valves first
|
|
foreach (var line in Input.ReadAllLines())
|
|
{
|
|
var span = line.AsSpan();
|
|
|
|
var nameStart = span.IndexOf(' ') + 1;
|
|
var name = span[nameStart..(nameStart + 2)].ToString();
|
|
|
|
var valve = valves[name];
|
|
|
|
var valvesStart = span.IndexOf(',') != -1 ? span.IndexOf(',') - 2 : span.Length - 2;
|
|
var valvesToAdd = span[valvesStart..].ToString().Split(", ").Select(v => valves[v]);
|
|
|
|
foreach (var valveToAdd in valvesToAdd)
|
|
{
|
|
valve.AccessibleValves.Add(valveToAdd);
|
|
}
|
|
}
|
|
|
|
return valves["AA"];
|
|
}
|
|
|
|
#region Input
|
|
|
|
public const string ExampleInput =
|
|
"""
|
|
Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
|
|
Valve BB has flow rate=13; tunnels lead to valves CC, AA
|
|
Valve CC has flow rate=2; tunnels lead to valves DD, BB
|
|
Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE
|
|
Valve EE has flow rate=3; tunnels lead to valves FF, DD
|
|
Valve FF has flow rate=0; tunnels lead to valves EE, GG
|
|
Valve GG has flow rate=0; tunnels lead to valves FF, HH
|
|
Valve HH has flow rate=22; tunnel leads to valve GG
|
|
Valve II has flow rate=0; tunnels lead to valves AA, JJ
|
|
Valve JJ has flow rate=21; tunnel leads to valve II
|
|
""";
|
|
|
|
public const string Input =
|
|
"""
|
|
Valve JI has flow rate=21; tunnels lead to valves WI, XG
|
|
Valve DM has flow rate=3; tunnels lead to valves JX, NG, AW, BY, PF
|
|
Valve AZ has flow rate=0; tunnels lead to valves FJ, VC
|
|
Valve YQ has flow rate=0; tunnels lead to valves TE, OP
|
|
Valve WI has flow rate=0; tunnels lead to valves JI, VC
|
|
Valve NE has flow rate=0; tunnels lead to valves ZK, AA
|
|
Valve FM has flow rate=0; tunnels lead to valves LC, DU
|
|
Valve QI has flow rate=0; tunnels lead to valves TE, JW
|
|
Valve OY has flow rate=0; tunnels lead to valves XS, VF
|
|
Valve XS has flow rate=18; tunnels lead to valves RR, OY, SV, NQ
|
|
Valve NU has flow rate=0; tunnels lead to valves IZ, BD
|
|
Valve JX has flow rate=0; tunnels lead to valves DM, ZK
|
|
Valve WT has flow rate=23; tunnels lead to valves OV, QJ
|
|
Valve KM has flow rate=0; tunnels lead to valves TE, OL
|
|
Valve NG has flow rate=0; tunnels lead to valves II, DM
|
|
Valve FJ has flow rate=0; tunnels lead to valves AZ, II
|
|
Valve QR has flow rate=0; tunnels lead to valves ZK, KI
|
|
Valve KI has flow rate=9; tunnels lead to valves ZZ, DI, TL, AJ, QR
|
|
Valve ON has flow rate=0; tunnels lead to valves LC, QT
|
|
Valve AW has flow rate=0; tunnels lead to valves DM, AA
|
|
Valve HI has flow rate=0; tunnels lead to valves TE, VC
|
|
Valve XG has flow rate=0; tunnels lead to valves II, JI
|
|
Valve II has flow rate=19; tunnels lead to valves LF, NG, OL, FJ, XG
|
|
Valve VC has flow rate=24; tunnels lead to valves WI, HI, AZ
|
|
Valve VJ has flow rate=0; tunnels lead to valves UG, AA
|
|
Valve IZ has flow rate=0; tunnels lead to valves VF, NU
|
|
Valve EJ has flow rate=0; tunnels lead to valves ZK, LC
|
|
Valve DU has flow rate=12; tunnels lead to valves TC, UG, FM
|
|
Valve ZK has flow rate=10; tunnels lead to valves JX, EJ, JW, QR, NE
|
|
Valve XF has flow rate=25; tunnels lead to valves OP, VT
|
|
Valve LC has flow rate=4; tunnels lead to valves FM, EJ, ON, AJ, PF
|
|
Valve SV has flow rate=0; tunnels lead to valves XS, IY
|
|
Valve LF has flow rate=0; tunnels lead to valves II, OV
|
|
Valve DI has flow rate=0; tunnels lead to valves KI, BY
|
|
Valve OP has flow rate=0; tunnels lead to valves YQ, XF
|
|
Valve NQ has flow rate=0; tunnels lead to valves TC, XS
|
|
Valve QJ has flow rate=0; tunnels lead to valves VT, WT
|
|
Valve IY has flow rate=22; tunnel leads to valve SV
|
|
Valve AJ has flow rate=0; tunnels lead to valves LC, KI
|
|
Valve TE has flow rate=11; tunnels lead to valves QI, HI, KM, YQ
|
|
Valve ZZ has flow rate=0; tunnels lead to valves KI, AA
|
|
Valve VT has flow rate=0; tunnels lead to valves XF, QJ
|
|
Valve OL has flow rate=0; tunnels lead to valves KM, II
|
|
Valve TC has flow rate=0; tunnels lead to valves NQ, DU
|
|
Valve TL has flow rate=0; tunnels lead to valves VF, KI
|
|
Valve QT has flow rate=0; tunnels lead to valves AA, ON
|
|
Valve BY has flow rate=0; tunnels lead to valves DM, DI
|
|
Valve OV has flow rate=0; tunnels lead to valves LF, WT
|
|
Valve VN has flow rate=0; tunnels lead to valves RR, BD
|
|
Valve VF has flow rate=13; tunnels lead to valves OY, IZ, TL
|
|
Valve BD has flow rate=17; tunnels lead to valves NU, VN
|
|
Valve UG has flow rate=0; tunnels lead to valves VJ, DU
|
|
Valve PF has flow rate=0; tunnels lead to valves LC, DM
|
|
Valve RR has flow rate=0; tunnels lead to valves XS, VN
|
|
Valve AA has flow rate=0; tunnels lead to valves QT, ZZ, AW, VJ, NE
|
|
Valve JW has flow rate=0; tunnels lead to valves ZK, QI
|
|
""";
|
|
|
|
#endregion
|
|
} |