|
|
using System; using static System.Console; using System.Collections.Generic; using System.IO; using System.Linq; using System.Text.RegularExpressions; using Xunit;
namespace AdventOfCode {
struct Contains { public Contains(string outer, string inner, int count) { Outer = outer; Inner = inner; Count = count; } public string Outer; public string Inner; public int Count;
public override string ToString() { return $"{Outer} contains {Count} {Inner}"; } }
public class Day07 {
static void AddRules(string rule, List<Contains> contains) { string[] tokens = rule.Split(" bags contain "); string color = tokens[0]; string[] otherBags = tokens[1].Split(", "); foreach (var s in otherBags) { Match m = Regex.Match(s, @"^(\d+) (\w+ \w+) bag"); if (!m.Success) { continue; } int count = int.Parse(m.Groups[1].Value); Contains c = new Contains(color, m.Groups[2].Value, count); contains.Add(c); } }
static List<Contains> ParseRules(string[] rules) { var contains = new List<Contains>(); rules.ToList().ForEach(rule => AddRules(rule, contains)); return contains; }
static int WhatCanContain(List<Contains> contains, string target) { var result = new HashSet<string>(); int setSize = 0; result.Add(target);
// transitive closure: keep adding things, until a round of doing so doesn't add anything new
while (true) { foreach (Contains c in contains) { if (result.Contains(c.Inner)) { result.Add(c.Outer); } } if (result.Count() == setSize) { // nothing new to add, we're done
return result.Count() - 1; // our target doesn't actually contain itself
} setSize = result.Count(); } }
static int CountBags(List<Contains> rules, string target) { int total = 1; foreach (Contains rule in rules) { if (rule.Outer == target) { total += rule.Count * CountBags(rules, rule.Inner); } } return total; }
static int Part1() { List<Contains> contains = ParseRules(File.ReadAllLines(Util.RootDir + "day07.txt")); return WhatCanContain(contains, "shiny gold"); }
static int Part2() { List<Contains> contains = ParseRules(File.ReadAllLines(Util.RootDir + "day07.txt")); return CountBags(contains, "shiny gold") - 1; }
[Fact] public static void Test() { string[] example = @"light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags. bright white bags contain 1 shiny gold bag. muted yellow bags contain 2 shiny gold bags, 9 faded blue bags. shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags. dark olive bags contain 3 faded blue bags, 4 dotted black bags. vibrant plum bags contain 5 faded blue bags, 6 dotted black bags. faded blue bags contain no other bags. dotted black bags contain no other bags.".Split('\n');
Assert.Equal(4, WhatCanContain(ParseRules(example), "shiny gold")); Assert.Equal(213, Part1());
string[] example2 = @"shiny gold bags contain 2 dark red bags.
dark red bags contain 2 dark orange bags. dark orange bags contain 2 dark yellow bags. dark yellow bags contain 2 dark green bags. dark green bags contain 2 dark blue bags. dark blue bags contain 2 dark violet bags. dark violet bags contain no other bags.".Split('\n');
Assert.Equal(127, CountBags(ParseRules(example2), "shiny gold"));
Assert.Equal(38426, Part2()); } } }
|