91 lines
3.0 KiB
C#
91 lines
3.0 KiB
C#
using System;
|
|
using System.Collections.Generic;
|
|
using System.Collections.Immutable;
|
|
using System.IO;
|
|
using System.Linq;
|
|
using System.Text.RegularExpressions;
|
|
using System.Threading;
|
|
|
|
namespace AoC {
|
|
|
|
internal class Day7 {
|
|
|
|
private record BagCount(string color, int count);
|
|
|
|
private Regex rx = new Regex(@"^(?<count>\d+) (?<color>\w+ \w+)");
|
|
|
|
private string ShinyGold = "shiny gold";
|
|
|
|
|
|
internal void Solve() {
|
|
var readLines = File.ReadAllText("day7/inputTest").Split("\n", StringSplitOptions.RemoveEmptyEntries);
|
|
|
|
var rules = new Dictionary<string, List<BagCount>>();
|
|
foreach (var line in readLines) {
|
|
var strings = line.Split(" bags contain ");
|
|
var bagRule = strings[0];
|
|
|
|
if (strings[1].Equals("no other bags.")) {
|
|
rules.Add(bagRule, new List<BagCount>());
|
|
continue;
|
|
}
|
|
|
|
var bagCounts = new List<BagCount>();
|
|
var bagsContained = strings[1].Split(", ");
|
|
foreach (var bagOption in bagsContained) {
|
|
var groups = rx.Match(bagOption).Groups;
|
|
bagCounts.Add(new BagCount(groups["color"].Value, Int32.Parse(groups["count"].Value)));
|
|
}
|
|
|
|
rules.Add(bagRule, bagCounts);
|
|
}
|
|
|
|
Console.WriteLine(rules);
|
|
|
|
Dictionary<string, List<string>> containedIn = new Dictionary<string, List<string>>();
|
|
foreach (var rule in rules) {
|
|
foreach (var bagCount in rule.Value) {
|
|
if (!containedIn.ContainsKey(bagCount.color)) {
|
|
containedIn.Add(bagCount.color, new List<string>());
|
|
}
|
|
containedIn[bagCount.color].Add(rule.Key);
|
|
}
|
|
}
|
|
|
|
ISet<string> res = new HashSet<string>();
|
|
Queue<String> q = new Queue<string>();
|
|
q.Enqueue(ShinyGold);
|
|
|
|
while (q.TryDequeue(out string bag)) {
|
|
if (!containedIn.ContainsKey(bag)) {
|
|
continue;
|
|
}
|
|
var contained = containedIn[bag];
|
|
contained.ForEach(c => q.Enqueue(c));
|
|
contained.ForEach(c => res.Add(c));
|
|
}
|
|
|
|
Console.WriteLine(res.Count);
|
|
|
|
// second part
|
|
long CountBagsRecursive(string color) {
|
|
var bagCounts = rules[color];
|
|
if (bagCounts.Count == 0) {
|
|
return 1;
|
|
}
|
|
|
|
long res = 1;
|
|
foreach (var bagCount in bagCounts) {
|
|
res += bagCount.count * CountBagsRecursive(bagCount.color);
|
|
}
|
|
|
|
return res;
|
|
}
|
|
|
|
Console.WriteLine(CountBagsRecursive(ShinyGold) - 1);
|
|
// wrong
|
|
// 1141
|
|
// 1251
|
|
}
|
|
}
|
|
} |